Write a function that takes (x, y) and return x to the power of y WITHOUT Loops [closed]

Question

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.

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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!..

Answer 6

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)

Answer 7

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);}

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

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.

Answer 12

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

Answer 13

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;
}

Answer 14

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.

Answer 15

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

Answer 16

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

Answer 17

C

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

What is this illegal?

Answer 18

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

Answer 19

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;
}

Answer 20

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.

Answer 21

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 :)

Answer 22

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.

Answer 23

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.

Answer 24

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;

Answer 25

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.

Answer 26

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.

Answer 27

F# (.NET Core), 42 bytes

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

Try it online!