Exponentiation of natural numbers using only primitive integer operations [duplicate]

Question

This question already has answers here:

Implement hyperexponentiation/tetration without the use of '^' [closed] (47 answers)

Closed 10 years ago.

The challenge

Implement the C equivalent of the pow() function (exponentiation) for natural numbers, in a language of your choosing, using only addition, subtraction (which includes negation and comparisons), bit-shifting, boolean operations on signed and/or unsigned integers, and of course looping.

(Note that this is different from hyperexponentiation/tetration, which is repeated exponentiation. This is merely a single application of exponentiation, which can be expressed mathematically as repeated multiplication.)

This is a code-golf challenge, so the shortest answer is king.

Input assumptions

You are computing x raised to the y power. You may assume that x ≥ 1 and y ≥ 1, because 0 is not a natural number. (In other words, you don't have to check for 00.)

Output

Your function should return the correct value for all valid input, except in the event of internal overflow, in which case you may return a garbage value. (In other words, if your language only supports 64-bit integers, then you may return whatever you like for input such as x=10, y=100.)

Bonus

There is a –10 point bonus if your function properly detects internal overflow and either aborts or returns some sort of error condition to the caller.

• Dennis: Is there any time/memory limit? If not, I can just use Cartesian product/power to implement multiplication/exponentiation.
• xnor: How about string/list multiplication?
• Reto Koradi: I think the more general question is: You list operations that can be used, and operations that cannot be used. What about all other operations? It might be clearer if you have only one list. Either operations that are allowed (with everything else excluded), or operations that are excluded (with everything else allowed).
• Todd Lehman: @RetoKoradi — Thanks — Edited to clarify that.
• Peter Taylor: It was a toss-up between voting to close as unclear (because the spec as written prohibits loops, which seems to make it impossible) or as duplicate (because on the assumption that loops are actually intended to be permitted it's just a question of taking the answers to the other question which don't go for the bonus and replacing * with +). The latter seems the more reasonable of the two options, but for future reference when whitelisting operations you should be more careful.

Answer 1

Java, 84

A boring "addition in a double loop" method. One loop is to multiply, the other makes it happen more than once. Works until overflow on int types. The -10 bonus just isn't worth it in Java ;)

int p(int x,int y){int r=1,p,i=0,j;for(;i++<y;r=p)for(p=0,j=0;j++<x;)p+=r;return r;}

Answer 2

CJam, 21 bytes

{1@@,f{;0@@,f{;+}~}~}

Only uses stack manipulation, loops and addition.

Try it online.

• Todd Lehman: Hoo boy! That is fuuuugly code but runs so beautifully! Nice work.

Answer 3

CJam, 22 bytes

Since the other CJam answer uses nested loops, I went with recursion. It's a lot slower.

{:X({:BX(F0\{B+}*}&}:F

Try it online.

Answer 4

Element, 18 bytes

1__'['[2:'+"]#"]#`

This is just a simple double-loop solution. It only uses addition and simple stack operations. (I'm not done golfing yet).

Input is like

5
3

for 5^3 giving 125.

Here's a very similar 18 byte solution:

1_'_'["#[2:'+"]']`

Answer 5

Pyth, 27 bytes

K1Vr0@Q1J0Vr0@Q0=J+JK)=KJ)K

Works by adding numbers together whilst looping. Takes input in the form:

x,y

Try it here.

Answer 6

Haskell, 37 bytes

(foldl1((sum.).replicate).).replicate

Usage example (note: exponent comes first, then base):

Prelude> ((foldl1((sum.).replicate).).replicate) 5 2
32
Prelude> ((foldl1((sum.).replicate).).replicate) 6 3
729

Answer 7

Python 2, (削除) 67 (削除ここまで) 62 bytes

m=lambda x,y:y and x+m(x,y-1);p=lambda x,y:y<1or m(x,p(x,y-1))

This is an obvious solution: define multiplication in terms of addition, then exponentiation in terms of multiplication.

Unfortunately, this rather naive implementation very quickly reaches the maximum recursion depth (Python's default maximum depth is 1000, I think). For instance, you can do p(9, 4) and it immediately outputs 6561. But if you try p(10, 4) it chokes, because it ultimately has to evaluate m(10, 1000) (that is, 10*1000) and it takes 1000 nested additions to do it.

Of course, you can always raise the stack depth limit...

By the way, p(0, 0) returns 1, which is desirable behavior in my view (if interested, please see my answer and comment here: https://math.stackexchange.com/questions/20969/prove-0-1-from-first-principles/1094926#1094926).

Thanks so much to xnor for saving me 5 bytes!

• lirtosiast: Nice job getting an answer in in the same minute the question is closed.
• mathmandan: @ThomasKwa Uh, thanks. This is a little like handing in your test as the professor is walking out the door.
• xnor: It's a bit shorter to do 0**y or _ for _ if y else 1.
• mathmandan: @xnor I don't think I'm allowed to use built-in exponentiation 0**y in this challenge?
• xnor: @mathmandan Ah, right, that's funny. y<1or should work instead and is shorter.

Answer 8

Powershell - 124 bytes

:\>cat pow.ps1
filter m([double]$a,$b){$r=0;while($b--){$r+=$a};return $r}
filter p([double]$c,$d){$s=1;while($d--){$s=m $s $c};return $s}
:\>cat pow.ps1 | wc --chars
124
:\>runpow.bat
:\>powershell -nologo -noexit -c "& {. .\pow.ps1; p 3 4;p 2 10; p 10000 77; p 10000 78}"
81
1024
1.0000000000004E+308
Infinity <------- if result above [double]::MaxValue

PowerShell 51 bytes

(answer prior to edit concats a multipliable string and evaluates it )

$p=[string]$args[0]+"*";powershell($p*$args[1]+"1")

result

PS E:\> .\pow.ps1 10076.45 77
1.79755288402548E+308
PS E:\> .\pow.ps1 2 10
1024
PS E:\> .\pow.ps1 10 100
1E+100
PS E:\> .\pow.ps1 4 20
1099511627776
PS E:\> .\pow.ps1 20 4
160000
PS E:\> .\pow.ps1 10077 77
Infinity

• Todd Lehman: Is this using only primitive integer operations?
• Todd Lehman: (I didn't downvote you, by the way.)
• Beta Decay: @ToddLehman No, this uses multiplication :/