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

## 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 0⁰.)

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

## marked as duplicate by Downgoat, mbomb007, Peter Taylor code-golf StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 6 '15 at 18:19

• Is there any time/memory limit? If not, I can just use Cartesian product/power to implement multiplication/exponentiation. – Dennis Aug 6 '15 at 2:38
• How about string/list multiplication? – xnor Aug 6 '15 at 2:44
• 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). – Reto Koradi Aug 6 '15 at 3:08
• @RetoKoradi — Thanks — Edited to clarify that. – Todd Lehman Aug 6 '15 at 3:34
• 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. – Peter Taylor Aug 6 '15 at 18:22

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


# CJam, 21 bytes

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


Only uses stack manipulation, loops and addition.

Try it online.

• Hoo boy! That is fuuuugly code but runs so beautifully! Nice work. – Todd Lehman Aug 6 '15 at 4:48

# 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


# 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:'+"]']


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

(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


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

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

## 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

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