Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
1  
What sort of challenge is this? –  VisioN Mar 5 at 12:01
    
@VisioN A think-out-of-the-box challenge, I suppose –  Imray Mar 5 at 12:03
15  
How about exp(log(x)*y)? –  squeamish ossifrage Mar 5 at 12:04
1  
Is an answer for integers only acceptable? Since these are the first replies. –  mmumboss Mar 5 at 12:59
2  
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). –  BenM Mar 5 at 16:47
show 6 more comments

45 Answers 45

up vote 18 down vote accepted

APL (7)

{×/⍵/⍺}

Left argument is base, right argument is exponent, e.g.:

     5 {×/⍵/⍺} 6
15625

Explanation:

  • ⍵/⍺ replicates times, e.g. 5 {⍵/⍺} 6 -> 5 5 5 5 5 5
  • ×/ takes the product, e.g. ×/5 5 5 5 5 5 -> 5×5×5×5×5×5 -> 15625
share|improve this answer
    
+1 for explanation :) Damn APL, so hard to read! –  l19 Mar 6 at 0:39
add comment

C#: Floating point exponents

OK, this solution is quite fragile. You can easily break it by throwing ridiculously huge numbers like 6 at it. But it works beautifully for things like DoublePower(1.5, 3.4), and doesn't use recursion!

    static double IntPower(double x, int y)
    {
        return Enumerable.Repeat(x, y).Aggregate((product, next) => product * next);
    }

    static double Factorial(int x)
    {
        return Enumerable.Range(1, x).Aggregate<int, double>(1.0, (factorial, next) => factorial * next);
    }

    static double Exp(double x)
    {
        return Enumerable.Range(1, 100).
            Aggregate<int, double>(1.0, (sum, next) => sum + IntPower(x, next) / Factorial(next));
    }

    static double Log(double x)
    {
        if (x > -1.0 && x < 1.0)
        {
            return Enumerable.Range(1, 100).
                Aggregate<int, double>(0.0, (sum, next) =>
                    sum + ((next % 2 == 0 ? -1.0 : 1.0) / next * IntPower(x - 1.0, next)));
        }
        else
        {
            return Enumerable.Range(1, 100).
                Aggregate<int, double>(0.0, (sum, next) =>
                    sum + 1.0 / next * IntPower((x - 1) / x, next));
        }
    } 

    static double DoublePower(double x, double y)
    {
        return Exp(y * Log(x));
    } 
share|improve this answer
31  
"ridiculously huge numbers like 6" I enjoyed that. –  David Carraher Mar 5 at 21:59
    
Surely use of Enumerable functions is relying on looping that was forbidden in the question or is it ok because the loop is inside framework methods? –  Chris Mar 7 at 9:42
add comment

C++

How about some template meta programming? It bends what little rules there were, but it's worth a shot:

#include <iostream>


template <int pow>
class tmp_pow {
public:
    constexpr tmp_pow(float base) :
        value(base * tmp_pow<pow-1>(base).value)
    {
    }
    const float value;
};

template <>
class tmp_pow<0> {
public:
    constexpr tmp_pow(float base) :
        value(1)
    {
    }
    const float value;
};

int main(void)
{
    tmp_pow<5> power_thirst(2.0f);
    std::cout << power_thirst.value << std::endl;
    return 0;
}
share|improve this answer
1  
+1 just for power_thirst –  izabera Mar 5 at 19:04
1  
but this isn't a function, is a compile-time value, isn't it? :O –  PaperBirdMaster Mar 6 at 8:49
    
Well, a constructor is a function, and template parameters are almost like function arguments... right? =) –  erlc Mar 7 at 13:47
    
@PaperBirdMaster Yeah... that's why I admitted to some rule bending. I thought I was going to submit something besides tail-recursion, but I just submitted compile time tail recursion, haha. Close enough though, right? –  astephens4 Mar 7 at 16:19
    
@astephens4 close enough, I love it :3 –  PaperBirdMaster Mar 7 at 23:46
add comment

Python

def power(x,y):
    return eval(((str(x)+"*")*y)[:-1])

Doesn't work for noninteger powers.

share|improve this answer
    
I like this one. –  Imray Mar 5 at 20:06
1  
Why are you adding a separator without using join? eval('*'.join([str(x)] * y)). –  Bakuriu Mar 6 at 7:45
1  
Was this code-trolling? –  gerrit Mar 6 at 14:51
    
Would like to also note that python has the ** operator, so you could've eval()d that. –  Riking Mar 6 at 21:14
3  
@Riking: that'd be an inbuilt, though. –  Hovercouch Mar 6 at 21:50
add comment

Python

If y is a positive integer

def P(x,y):
    return reduce(lambda a,b:a*b,[x]*y)
share|improve this answer
add comment

JavaScript (ES6), 31

// Testable in Firefox 28
f=(x,y)=>eval('x*'.repeat(y)+1)

Usage:

> f(2, 0)
1
> f(2, 16)
65536

Explanation:

The above function builds an expression which multiply x y times then evaluates it.

share|improve this answer
add comment

Haskell - 25 chars

f _ 0=1
f x y=x*f x (y-1)

Following Marinus' APL version:

f x y = product $ take y $ repeat x

With mniip's comment and whitespace removed, 27 chars:

f x y=product$replicate y x
share|improve this answer
    
use replicate y x instead of take y $ repeat x –  mniip Mar 5 at 18:38
    
Updated, thanks mniip –  intx13 Mar 5 at 18:59
3  
I was convinced that you could save characters by writing your second function pointfree. As it turns out f=(product.).flip replicate is exactly the same number of chars. –  Kaya Mar 6 at 2:17
add comment

C# : 45

Works for integers only:

int P(int x,int y){return y==1?x:x*P(x,y-1);}
share|improve this answer
    
Beat me to it :-) I think you could save a few bytes by writing return --y?x:x*P(x,y); instead –  squeamish ossifrage Mar 5 at 12:13
1  
But this isn't code-golf... –  Oberon Mar 5 at 12:26
1  
@oberon winning criteria was not clear when this was posted. Things have moved on. –  steveverrill Mar 5 at 13:47
    
@steveverrill Sorry. –  Oberon Mar 5 at 13:54
    
Also in C# --y would be an int which is not the same as a bool like in other languages. –  Chris Mar 7 at 9:39
add comment

I'm surprised to see that nobody wrote a solution with the Y Combinator, yet... thus:

Python2

Y = lambda f: (lambda x: x(x))(lambda y: f(lambda v: y(y)(v)))
pow = Y(lambda r: lambda (n,c): 1 if not c else n*r((n, c-1)))

No loops, No vector/list operations and No (explicit) recursion!

>>> pow((2,0))
1
>>> pow((2,3))
8
>>> pow((3,3))
27
share|improve this answer
    
Uh, I've just seen right now KChaloux's Haskell solution that uses fix, upvoting him... –  berdario Mar 6 at 16:35
add comment

Javascript

function f(x,y){return ("1"+Array(y+1)).match(/[\,1]/g).reduce(function(l,c){return l*x;});}

Uses regular expressions to create an array of size y+1 whose first element is 1. Then, reduce the array with multiplication to compute power. When y=0, the result is the first element of the array, which is 1.

Admittedly, my goal was i) not use recursion, ii) make it obscure.

share|improve this answer
add comment

Golfscript, 8 characters (including I/O)

~])*{*}*

Explanation:

TLDR: another "product of repeated array" solution.

The expected input is two numbers, e.g. 2 5. The stack starts with one item, the string "2 5".

Code     - Explanation                                             - stack
                                                                   - "2 5"
~        - pop "2 5" and eval into the integers 2 5                - 2 5        
]        - put all elements on stack into an array                 - [2 5]
)        - uncons from the right                                   - [2] 5
*        - repeat array                                            - [2 2 2 2 2]
{*}      - create a block that multiplies two elements             - [2 2 2 2 2] {*}
*        - fold the array using the block                          - 32
share|improve this answer
    
Golfscript is always the way to go. –  Nit Mar 7 at 0:27
add comment

JavaScript

function f(x,y){return y--?x*f(x,y):1;}
share|improve this answer
add comment

bash & sed

No numbers, no loops, just an embarrasingly dangerous glob abuse. Preferably run in an empty directory to be safe. Shell script:

#!/bin/bash
rm -f xxxxx*
eval touch $(printf xxxxx%$2s | sed "s/ /{1..$1}/g")
ls xxxxx* | wc -l
rm -f xxxxx*
share|improve this answer
    
"Preferably run in an empty directory to be safe." :D –  Almo Mar 6 at 13:53
add comment

C, exponentiation by squaring

int power(int a, int b){
    if (b==0) return 1;
    if (b==1) return a;
    if (b%2==0) return power (a*a,b/2);
    return a*power(a*a,(b-1)/2);
}

golfed version in 46 bytes (thanks ugoren!)

p(a,b){return b<2?b?a:1:p(a*a,b/2)*(b&1?a:1);}

should be faster than all the other recursive answers so far o.O

slightly slower version in 45 bytes

p(a,b){return b<2?b?a:1:p(a*a,b/2)*p(a,b&1);}
share|improve this answer
1  
For odd b, ~-b/2 == b/2. –  ugoren Mar 5 at 17:49
    
@ugoren oh sure, you're right –  izabera Mar 5 at 18:31
    
This is a popular interview question :) "How can you write pow(n, x) better than O(n)?" –  Jordan Scales Mar 6 at 0:28
add comment

Q

9 chars. Generates array with y instances of x and takes the product.

{prd y#x}

Can explicitly cast to float for larger range given int/long x:

{prd y#9h$x}
share|improve this answer
1  
Matching Golfscript in length is a feat to achieve. –  Nit Mar 7 at 0:29
add comment

Similar logic as many others, in PHP:

<?=array_product(array_fill(0,$argv[2],$argv[1]));

Run it with php file.php 5 3 to get 5^3

share|improve this answer
add comment

I'm not sure how many upvotes I can expect for this, but I found it somewhat peculiar that I actually had to write that very function today. And I'm pretty sure this is the first time any .SE site sees this language (website doesn't seem very helpful atm).

ABS

def Rat pow(Rat x, Int y) =
    if y < 0 then
        1 / pow(x, -y)
    else case y {
        0 => 1;
        _ => x * pow(x, y-1);
    };

Works for negative exponents and rational bases.

I highlighted it in Java syntax, because that's what I'm currently doing when I'm working with this language. Looks alright.

share|improve this answer
    
@RoyTinker Why don't you stop being a buzzkill and produce something yourself? Besides, an explicit loop would be something using while, for etc. Arguably EVERY answer here has some form of loop, some just more well hidden than others. As far as I can tell, all the non-recursive answers use some form of fold/reduce, which is basically just a higher-order loop. Edit: Removing your comment, great. Remove the downvote too then. –  daniero Mar 7 at 1:42
add comment

Haskell - 55

pow x y=fix(\r a i->if i>=y then a else r(a*x)(i+1))1 0

There's already a shorter Haskell entry, but I thought it would be interesting to write one that takes advantage of the fix function, as defined in Data.Function. Used as follows (in the Repl for the sake of ease):

ghci> let pow x y=fix(\r a i->if i>=y then a else r(a*x)(i+1))1 0
ghci> pow 5 3
125
share|improve this answer
add comment

Pascal

The challenge did not specify the type or range of x and y, therefore I figure the following Pascal function follows all the given rules:

{ data type for a single bit: can only be 0 or 1 }
type
  bit = 0..1;

{ calculate the power of two bits, using the convention that 0^0 = 1 }
function bitpower(bit x, bit y): bit;
  begin
    if y = 0
      then bitpower := 1
      else bitpower := x
  end;

No loop, no built-in power or exponentiation function, not even recursion or arithmetics!

share|improve this answer
add comment

Mathematica

f[x_, y_] := Root[x, 1/y]

Probably cheating to use the fact that x^(1/y) = y√x

share|improve this answer
    
Not cheating. Smart. –  Michael Stern Mar 12 at 21:49
add comment

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

share|improve this answer
add comment

Python

from math import sqrt

def pow(x, y):
    if y == 0:
        return 1
    elif y >= 1:
        return x * pow(x, y - 1)
    elif y > 0:
        y *= 2
        if y >= 1:
            return sqrt(x) * sqrt(pow(x, y % 1))
        else:
            return sqrt(pow(x, y % 1))
    else:
        return 1.0 / pow(x, -y)
share|improve this answer
1  
** is built-in operator imo. –  Silviu Burcea Mar 5 at 12:28
    
@SilviuBurcea True, editing. –  Oberon Mar 5 at 12:30
    
@SilviuBurcea operator =/= function –  VisioN Mar 5 at 12:32
    
@VisioN true, but the idea was about built-ins. I don't think the OP knows about all these built-in operators ... –  Silviu Burcea Mar 5 at 12:34
add comment

Ruby

class Symbol
  define_method(:**) {|x| eval x }
end

p(:****[$*[0]].*(:****$*[1]).*('*'))

Sample use:

$ ruby exp.rb 5 3
125
$ ruby exp.rb 0.5 3
0.125

This ultimately is the same as several previous answers: creates a y-length array every element of which is x, then takes the product. It's just gratuitously obfuscated to make it look like it's using the forbidden ** operator.

share|improve this answer
add comment

Javascript

With tail recursion, works if y is a positive integer

function P(x,y,z){z=z||1;return y?P(x,y-1,x*z):z}
share|improve this answer
add comment

Bash

Everyone knows bash can do whizzy map-reduce type stuff ;-)

#!/bin/bash

x=$1
reduce () {
    ((a*=$x))
}
a=1
mapfile -n$2 -c1 -Creduce < <(yes)
echo $a

If thats too trolly for you then there's this:

#!/bin/bash

echo $(( $( yes $1 | head -n$2 | paste -s -d'*' ) ))
share|improve this answer
add comment

C

Yet another recursive exponentiation by squaring answer in C, but they do differ (this uses a shift instead of division, is slightly shorter and recurses one more time than the other):

e(x,y){return y?(y&1?x:1)*e(x*x,y>>1):1;}
share|improve this answer
add comment

Mathematica

This works for integers.

f[x_, y_] := Times@@Table[x, {y}]

Example

f[5,3]

125


How it works

Table makes a list of y x's. Times takes the product of all of them.`


Another way to achieve the same end:

#~Product~{i,1,#2}&

Example

#~Product~{i, 1, #2} & @@ {5, 3}

125

share|improve this answer
add comment

Windows Batch

Like most of the other answers here, it uses recursion.

@echo off
set y=%2
:p
if %y%==1 (
set z=%1
goto :eof
) else (
    set/a"y-=1"
    call :p %1
    set/a"z*=%1"
    goto :eof
)

x^y is stored in the environment variable z.

share|improve this answer
add comment

perl

Here's a tail recursive perl entry. Usage is echo $X,$Y | foo.pl:

($x,$y) = split/,/, <>;
sub a{$_*=$x;--$y?a():$_}
$_=1;
print a

Or for a more functional-type approach, how about:

($x,$y) = split/,/, <>;
$t=1; map { $t *= $x } (1..$y);
print $t
share|improve this answer
    
"a: stuff goto a if something" looks like a loop. –  Glenn Randers-Pehrson Mar 6 at 1:34
    
Yep, the goto version is a loop, but isn't tail recursion also essentially a loop? –  skibrianski Mar 6 at 2:21
add comment

Python

def getRootOfY(x,y):
   return x**y 

def printAnswer():
   print "answer is ",getRootOfY(5,3)
printAnswer()

answer =125

I am not sure if this is against the requirements, but if not here is my attempt.

share|improve this answer
    
Welcome to PPCG! When you do your language header you can leave out the "language=" since by custom everyone puts the language in the header so that's understood. You may indeed have run afoul of the rules here, but we'll let the voters decide. Glad to have a new member at the country club. –  Jonathan Van Matre Mar 6 at 4:12
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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