14
\$\begingroup\$

This is a really neat short challenge.

Write a function or a procedure that takes two parameters, x and y and returns the result of xy WITHOUT using loops, or built in power functions.

The winner is the most creative solution, and will be chosen based on the highest number of votes after 3 days.

\$\endgroup\$

closed as unclear what you're asking by Sriotchilism O'Zaic, Laikoni, NoOneIsHere, Stephen, Embodiment of Ignorance Mar 11 at 16:08

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ What sort of challenge is this? \$\endgroup\$ – VisioN Mar 5 '14 at 12:01
  • 21
    \$\begingroup\$ How about exp(log(x)*y)? \$\endgroup\$ – squeamish ossifrage Mar 5 '14 at 12:04
  • 2
    \$\begingroup\$ Is an answer for integers only acceptable? Since these are the first replies. \$\endgroup\$ – mmumboss Mar 5 '14 at 12:59
  • 4
    \$\begingroup\$ Looks like the answers so far either use recursion or lists of repeated 'x's. I'm wracking my brains trying to think of another way (particularly something that allows a non-integer y). \$\endgroup\$ – BenM Mar 5 '14 at 16:47
  • 1
    \$\begingroup\$ Unfortunately the prohibition on loops rules out fun mathematical solutions like Taylor expansion. \$\endgroup\$ – shadowtalker Jul 31 '14 at 3:15

57 Answers 57

1
\$\begingroup\$
public static void main(String[] argv) {
    int v=getpow(4,3);
    System.out.println(v);
    }
public static int getpow(int b, int v) {
     if (v == 0) {
        return 1;
    } else {
        return b * getpow(b, v - 1);
    }
}

Java: I/P: 3 and 4 O/P: 64

\$\endgroup\$
1
\$\begingroup\$

Scala - 47

def p(x:Int,y:Int)=(1 to y).fold(1)((a,b)=>a*x)

Not dissimilar to the other functional versions that use a variant of repeat or replicate, with the exception that it takes a lot of characters to repeat something in Scala (Stream.continually(x).take(y)).

This version iterates over the range of 1..y, but completely throws out the captured value at each step, instead multiplying the accumulator by the base value 'x'. I was originally going to use map to transform the range into all instances of the value x, and use the product function to multiply it, but this version is actually a bit shorter.

Usage

scala> def p(x:Int,y:Int)=(1 to y).fold(1)((a,b)=>a*x)
p: (x: Int, y: Int)Int

scala> p(5,3)
res44: Int = 125
\$\endgroup\$
1
\$\begingroup\$

Java 8

public long power(long num, int pow) {
    return LongStream.rangeClosed(1, pow).reduce(1, (i, j) -> i * num);
}

does not work with negative powers.

\$\endgroup\$
1
\$\begingroup\$

It's important to return a precise answer, and to support large numbers -

public static BigInteger power(int x, int y) {
    return (y > 0) ? power(new BigInteger(String.valueOf(x)), y)
            : BigInteger.ONE;
}

public static BigInteger power(BigInteger x, int y) {
    return (y > 0) ? power(x, y - 1).multiply(x) : BigInteger.ONE;
}

public static void main(String[] args) {
    // From here
    // http://en.wikipedia.org/wiki/Power_of_two
    String result = "13,407,807,929,942,597,099,574,024,998,205,846,127,479,365,820,592,"
            + "393,377,723,561,443,721,764,030,073,546,976,801,874,298,166,903,427,690,"
            + "031,858,186,486,050,853,753,882,811,946,569,946,433,649,006,084,096";
    result = result.replace(",", "");
    System.out.println(result.equals(power(2, 512).toString()));
}

Of course, the output is

true
\$\endgroup\$
  • \$\begingroup\$ This isn't a code-trolling challenge. You were supposed to return the value of x^y. \$\endgroup\$ – Hosch250 Mar 6 '14 at 16:50
  • \$\begingroup\$ What do you think 2^512 is? \$\endgroup\$ – Elliott Frisch Mar 6 '14 at 16:51
  • \$\begingroup\$ Oh, you overflowed the size of the BigInteger? \$\endgroup\$ – Hosch250 Mar 6 '14 at 16:53
  • \$\begingroup\$ I was thinking it always returned true. \$\endgroup\$ – Hosch250 Mar 6 '14 at 16:54
1
\$\begingroup\$

Javascript/HTML, cheater's (DIY) way:

function (a, b) { return "" + a + "<sup>" + b + "</sup>"; }

example run: http://jsfiddle.net/r4LfF/1/ (click "run" if it doesn't show up automatically)
maybe it can be done better, but I don't know Javascript!..

\$\endgroup\$
  • \$\begingroup\$ funny solution! \$\endgroup\$ – rafaelcastrocouto Jul 30 '14 at 12:27
  • \$\begingroup\$ "Standard loopholes are not funny anymore" \$\endgroup\$ – Jacob Dec 5 '14 at 5:00
  • \$\begingroup\$ @Jacob unfortunately, I have read this long after the solution was posted. \$\endgroup\$ – Sarge Borsch Dec 5 '14 at 6:49
  • \$\begingroup\$ Don't worry about it :) \$\endgroup\$ – Jacob Dec 5 '14 at 7:06
1
\$\begingroup\$

Simple recursive Python solution, works when y is non-negative integer:

def f(x, y):
    return 1 if y == 0 else x * f(x, y - 1)
\$\endgroup\$
1
\$\begingroup\$

C, 79

This is an optimized version of the standard recursive call. It refactors each successive call by powers of 2. In other words if y is 2^n, it will be called n times.

typedef uint64_t Z;Z p(Z x,Z y){return(!y)?1:(1==y)?x:((y&1)?x:1)*p(x*x,y>>1);}
\$\endgroup\$
1
\$\begingroup\$

ECMAScript 6 (32 bytes):

p=(x,y)=>y>2?p(x,--y)*x:+!y||x*x

Defines a function named p which takes x and y as parameters, and returns x to the power of y, without using any built-in functions, or loops.

\$\endgroup\$
1
\$\begingroup\$

R

A cheap trick for positive integer-valued y:

hacky <- function(x, y) Reduce(`*`, rep(x, y))

And an approximation for real-valued y. As far as I'm aware, apply is not technically implemented as a loop:

mathy <- function(x, y, nterms) {
  sum(sapply(seq_len(nterms), function(i) Reduce(`*`, rep(y * log(x), i)) / factorial(i))) + 1
}

This one computed x^y=exp(y*log(x)) by taking the Taylor expansion of the right hand side. It can also be done recursively if you're leery of apply:

recursive <- function(x, y, nterms) {
  taylor <- function(n) {
    if(n==0) z <- 1
    else z <- Reduce(`*`, rep(y * log(x), n)) / factorial(n) + taylor(n-1)
    z
  }
  taylor(nterms)
}

And the coup-de-grace:

goofy <- function(x, y, nterms) {
  eval(parse(text = paste(
    sprintf("Reduce(`*`, (%s * log(%s))^%i) / factorial(%i)", y, x, 0:nterms, 0:nterms),
    collapse=" + "
  )))
}

I ran some single-run benchmarks for fun. Formatting them for looking pretty here is going to be more of a pain than it's worth, but I was surprised to see that the apply version was actually slower than the recursive version for small numbers of terms, and that their timings converged up to the maximum number of terms (171, the largest integer that factorial will accept). The text-based version was slower still for small numbers of terms, but was actually twice as fast for the large number of terms. They obviously fail dramatically compared to R's built-in versions.

Interestingly, it seems like R (or the package I'm using to benchmark, microbenchmark) does some magic in its innards, and when I set microbenchmark to use more than one trial all of the times drop by several orders of magnitude. The variation follows a similar pattern, but the differences are now in nanoseconds rather than logarithms of miliseconds.

\$\endgroup\$
1
\$\begingroup\$

JavaScript formerly 44 , now 41

f=(x,y)=>y?eval(Array(y).join(x+"*")+x):1

TESTING:
alert(f(5,3))
OUTPUT (alert): 125
alert(f(6,3))
OUTPUT (alert): 216
alert(f(8,0))
OUTPUT (alert): 1

Changes, altered logic to allow reversed execution, thus removing 3 characters...

Only works for positive integers

\$\endgroup\$
  • \$\begingroup\$ f(2,0) returns 2 instead of 1 \$\endgroup\$ – Florent Mar 5 '14 at 23:24
  • 1
    \$\begingroup\$ A more ES6 solution: f=(x,y)=>{a=1;[x for (i of Array(y))].map(z=>a*=z);return a} \$\endgroup\$ – Florent Mar 5 '14 at 23:25
  • \$\begingroup\$ @Florent Corrected for x^0... And your ES6 solution unfortunately is using a for loop :/ \$\endgroup\$ – WallyWest Mar 6 '14 at 0:15
  • \$\begingroup\$ Well, it’s a list comprehension. Is it closer to a loop than map? \$\endgroup\$ – Ry- Mar 6 '14 at 19:55
  • 1
    \$\begingroup\$ I didn’t say you were. What I said was that the for in Florent’s ES6 isn’t a for loop – it’s a list comprehension. I consider that a lot closer to map than a typical for. \$\endgroup\$ – Ry- Mar 6 '14 at 23:48
1
\$\begingroup\$

Python

def pow (x, y):
    class Num:
        n = 1
        def __eq__ (self, v):
            Num.n *= v
            return False
    x in [Num()] * y
    return Num.n

x=2
y=3
print(pow(x, y))

Weirdo.

\$\endgroup\$
1
\$\begingroup\$

TI-BASIC

For TI-83/84 calculators

:Input X,Y
:Lbl 1
:Y-1->Y
:X*X->X
:If 1<Y
:Goto 1
:X

Displays/returns X

\$\endgroup\$
1
\$\begingroup\$

C++

Since most answers use some language quirks to get things done, i thought about trying to spice things up using quirks of data types themselves. Following function uses integer representation of IEEE float to get a logarithm approximation.

Blazingly fast and inaccurate.

float fapxpow(float x, float y) {
    __int32 lx = *(__int32 *)&x;
    lx = (lx - 0x3F7A7DD3)*y + 0x3F7A7DD3;
    float xy = *(float *)&lx;
    return xy;
}
\$\endgroup\$
1
\$\begingroup\$

R

f=function(x,y) prod(c(rep(x,y)))

Not super sure about 'prod', I didn't check how it's implemented. I might just be calling a loop here.

\$\endgroup\$
0
\$\begingroup\$

F#

Since ^ and ** were already taken and infix operators are fun, let's call it ^^

let rec (^^) (x: int) y =
  let fx = float x
  match y with
  | y when y < 0 -> (x ^^ y + 1) / fx
  | 0 -> 1.0
  | y -> (x ^^ y - 1) * fx

x and y are integers and it returns a float, since it handles negative exponents. Call it with x ^^ y

\$\endgroup\$
0
\$\begingroup\$

Delphi XE3

Uses a recursive function that will keep calling itself until multiplied according to the power.

Required input like p^o

var
  p,o:integer;

  function Pwr(n,r,c:integer):integer;
  begin
    if c=o then
      Result:=r
    else
      Result:=Pwr(n,r*p,c+1);
  end;
begin
    readln(p,o);
    Writeln(Pwr(o,p,1));
    readln;
end.

Input: 2 5
Output: 32

\$\endgroup\$
0
\$\begingroup\$

C

int power(int x,int y)
{
if ( y!=1 )
    return (x*power(x,y-1));
}

What is this illegal?

\$\endgroup\$
  • \$\begingroup\$ what if condition not true ?? no return \$\endgroup\$ – Omer Obaid Mar 7 '14 at 12:44
  • \$\begingroup\$ @Omer the question didn't specify that the function should work for all x and y. For instance none of the functions would work for y<=0. I could add a condition to work for y==1. But I don't see any need for it currently. \$\endgroup\$ – Mhmd Mar 8 '14 at 14:04
  • \$\begingroup\$ @user689 My answer handles all valid ECMAScript numbers (whole and floating-point; negative and non-negative). \$\endgroup\$ – Toothbrush Mar 8 '14 at 20:00
0
\$\begingroup\$

PHP

function altpow($x,$y) {
    if ( $y > 0 ) {
        return array_product(array_fill(0,$y,$x));
    } else if ( $y < 0 ) {
        return 1/array_product(array_fill(0,$y*-1,$x));
    }
    return 1;
}

Doesn't work with floating point exponents.

Test:

pow(4.33,-5) // 0.00065699266096183
altpow(4.33,-5) // 0.00065699266096183
\$\endgroup\$
0
\$\begingroup\$

Using C++

#include <iostream>

using namespace std;

float power(float x, float y) {
    if(y  == 0)
    return 1;
    if(y == 1)
    return x;

    return power(x,y-1) *x;

    }

int main()
{
   cout << "Hello World" << endl; 

   cout<<power(2,3);

   return 0;
}
\$\endgroup\$
0
\$\begingroup\$

Clojure

(defn pow [x y]
 (if (= y 0) 1  
  (reduce * x (take (- y 1) (repeat x)))))

(pow 2 2)
=> 4  

It will not work for negative exponent.

\$\endgroup\$
  • \$\begingroup\$ Perhaps you could add an explanation of how it works? \$\endgroup\$ – Toothbrush Mar 8 '14 at 20:05
  • \$\begingroup\$ Also, it doesn't seem to work for 2, 0, 0, 0, or 2, -2. \$\endgroup\$ – Toothbrush Mar 8 '14 at 20:07
  • \$\begingroup\$ This is a little overcomplicated. (defn pow [x y] (if (<= y 0) 1 (reduce * (repeat y x)))) works just fine. @toothbrush It takes list of x repeated y times and returns the product ((reduce * [1 2 3]) == 1 * 2 * 3) \$\endgroup\$ – seequ Jul 30 '14 at 18:52
  • \$\begingroup\$ @Sieg Yes, but x to the power of 0 is always 1. \$\endgroup\$ – Toothbrush Jul 30 '14 at 20:29
  • \$\begingroup\$ @toothbrush That is why the if-clause is there. See, if the first argument is true (that being (<= y 0) which is more traditionally y <= 0), then it returns the second argument (that being 1). Otherwise it returns the third argument, which is the product. \$\endgroup\$ – seequ Jul 30 '14 at 20:36
0
\$\begingroup\$

Java 8 lambda recursion

    static BinaryOperator<Integer> powerof;
public static void main(String[] args) {
    powerof = (x, y) -> {return y == 0 ? 1 : x * powerof.apply(x, y-1);};
    System.out.println(powerof.apply(5, 3));
}

Guess it's kind of late, but I'll post anyway to celebrate the imminent release of java 8 :)

\$\endgroup\$
0
\$\begingroup\$

Another Mathematica Solution, 33 characters

D[ExpIntegralEi[(1 + y) Log[x]], x, y]

I believe that this does not violate the rule against using "built in power functions", as while the exponential integral function implies E^t dt, it does not involve x^y.

This solution is unusual among those posted here in that it works for more than just positive integers, and in fact works for any complex numbers for both x and y.

\$\endgroup\$
0
\$\begingroup\$

Python

import math
def recurse_log(x, minimum, cur):
    val = math.log(cur, x)
    if cur == minimum:
        return (val,)
    else:
        return recurse_log(x, minimum, cur-1) + (val,)

def exp(x,y):
    crude_ans = 1<<(int(y*math.log2(x)))
    min_ans = crude_ans//2
    max_ans = crude_ans*2
    possible = list(recurse_log(x, min_ans, max_ans))
    return min_ans + min(range(len(possible)), key=lambda v: abs(possible[v]-y))

Works only with integers. This code finds a crude calculation of the answer using log base two and a bitshift (which serves as a base 2 exponents). This gives an answer accurate to the nearest power of two. Then, it takes the log of every integer in the possible range and sees which is closest.

It's very very slow.

\$\endgroup\$
  • \$\begingroup\$ Interesting idea, but "WITHOUT Loops" vs. for i in range ? \$\endgroup\$ – Digital Trauma Dec 6 '14 at 5:15
  • \$\begingroup\$ @DigitalTrauma I guess list comprehensions count as loops. I changed it to use a recursive function, but that hits Python's recursion limit for large numbers. \$\endgroup\$ – Ian D. Scott Dec 6 '14 at 5:41
0
\$\begingroup\$

Pascal;

FUNCTION pwr(base,power:REAL):REAL;    // calculates base**power for base >0.0 
BEGIN   
  IF base > 0.0 THEN pwr := EXP(power*LN(base)) ELSE HALT(1);
END;
\$\endgroup\$
0
\$\begingroup\$

JavaScript, ES5+

This may be bending the rules a bit, due to the use of forEach, although it's not being used in the typical fashion.

function pwr(x, y){
  var array1 = [], i = 0, result = 1;
  array1.push(function(){i++; result *= x; if(i >= y) throw {};});
  array1.push(function(a){array1.forEach(a)});
  try{
    array1.forEach(array1[1]);
  }
  catch(e){
    return result;
  }
}
console.log(pwr(3,4)); //81

y must be an integer; x does not need to be.

\$\endgroup\$
0
\$\begingroup\$

Jelly - 3 bytes

x×/

Pretty much identical to the APL and J solutions, but as a newer language Jelly is more efficient.

x turns a,b into [a,a,...,a] (length b)

×/ computes reduce(c,d-->c×d, [a,a,...,a]), to get a×a×...×a = a^b.

\$\endgroup\$
0
\$\begingroup\$

F# (.NET Core), 42 bytes

fun(x,y)->Seq.reduce(*)<|Seq.replicate y x

Try it online!

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.