# Implement pow with overflow checking

Implement a function or program which raises x to the power of y. Inputs are 16-bit signed integers. That is, both are in the range [-32768, 32767]. The output should be in the same range. I chose this range because it should make it possible to do exhaustive testing to ensure all edge-cases are covered.

If the output can't be represented (it's too negative, too positive or not an integer), do one of the following:

• Throw an exception
• Print an error message
• Return a special value (-1, 0 or any other specific value)

Please document what your implementation does in case of error; the behavior should be identical for all error cases — the same exception, message or exceptional value!

By definition, 0 to the power of 0 is 1 (not "error").

I am most interested in non-trivial solutions, but if your language has a suitable pow function, you are allowed to use it!

Test cases:

pow(-32768, -32768) = error
pow(-32768, -1) = error
pow(-32768, 0) = 1
pow(-32768, 1) = -32768
pow(-32768, 2) = error
pow(-32768, 32767) = error
pow(-100, 100) = error
pow(-180, 2) = 32400
pow(-8, 5) = -32768
pow(-3, -2) = error
pow(-3, 9) = -19683
pow(-2, 15) = -32768
pow(-1, -999) = -1
pow(-1, -100) = 1
pow(-1, 100) = 1
pow(-1, 999) = -1
pow(0, -100) = error
pow(0, -1) = error
pow(0, 0) = 1
pow(0, 999) = 0
pow(1, -999) = 1
pow(1, 10000) = 1
pow(1, 9999) = 1
pow(2, 14) = 16384
pow(2, 15) = error
pow(8, 5) = error
pow(4, 7) = 16384
pow(181, 2) = 32761
pow(182, 2) = error
pow(10000, 1) = 10000

• Can -1 and 0 really be used as the special value? They are indistinguishable from a valid answer. Jul 7 at 23:38
• It's too bad, but you don't have any other choice if all your language has is 16-bit integers. Jul 8 at 0:11
• If the code throws an exception to indicate error, does it have to be the same exception in every case? For instance, pow(-32768, -32768) is defined but not an integer whereas pow(0, -1) is undefined (division by zero). Jul 8 at 0:57
• It should be the same. Updated the text. Jul 8 at 7:54

# Rust, 68 bytes

|x:i16,y:i16|x.checked_pow(match x{1|-1=>y&1,_=>y}.try_into().ok()?)

Attempt This Online!

Probably not the best language to golf in, but when I saw the description I immediately thought that checked_pow would be a perfect built-in for this task. The equivalent doesn't exist in every single other language I know of.

Returns Some(x**y) if the result is well-defined and fits in the i16 range, None otherwise.

|x:i16,y:i16|           A closure that takes two i16 values
x.checked_pow(...)      Raise x to the power of ... (but the power must be u32)
The only cases where negative power makes sense are 1 and -1
match x{                so let's match on x and
1|-1=>y&1,              if it is 1 or -1, use y modulo 2 (non-negative)
_=>y}                   and simply use y otherwise
.try_into()             and try converting to u32 (inferred)
.ok()                   and convert the Result<u32,E> to Option<u32>
?                       and return None immediately if the conversion fails

• Re: other languages with overflow-detecting operations: GNU C has __builtin_mul_overflow - gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html. But not pow; yeah that's a rare one. Using signed integer, gcc -fsanitize=undefined will abort the program on signed-overflow UB if you just use plain *=, but that doesn't help either for returning an error to the caller. Jul 8 at 11:49
• Using release flags and by moving a type annotation you can get 59 bytes: |x:i16,y|x.checked_pow(if 0i16>y&&x*x!=1{None?}else{y}as _) Jul 8 at 16:21
• @AnttiP That would panic if x*x overflows. Jul 8 at 22:17
• @L.F. Not with release flags, it will simply overflow. ATO Jul 9 at 7:55
• @AnttiP Indeed, forgot about that! Jul 9 at 16:08

# JavaScript (ES7),  46  41 bytes

Saved 5 bytes thanks to @Neil

Expects (x)(y). Returns false for errors.

x=>y=>(q=x**y/(y>=0|x*x<2))==q<<16>>16&&q


Try it online!

### Commented

x =>            // given x
y =>            // and y
(               //
q =           // compute and save in q:
x ** y /    //   x ** y
(           //   leave it unchanged if:
y >= 0 |  //     y is non-negative
x * x < 2 //     or x² is 0 or 1
)           //   otherwise: divide by 0, leading to +/- Infinity
) ==            // test whether the result is invariant by shifting it ...
q << 16 >> 16   // ... by 16 positions to the left and then to the right
&& q            // if it is: return q (or return false otherwise)

• Does x=>y=>(q=x**y/(y>=0|x*x<2))==(q<<16>>16)&&q work or have I overlooked something?
– Neil
Jul 8 at 0:17
• Yes, I've overlooked that bit shifts have higher precedence.
– Neil
Jul 8 at 0:21
• @Neil I can't think of any case where it would not work. Nice! Jul 8 at 0:21

# Ruby, 30 29 bytes

->x,y{[x**=y][x>>15]rescue p}


Try it online!

Returns nil for errors.

• 23 bytes if different errors are allowed to throw different exceptions. Jul 8 at 5:12

# PARI/GP, 36 bytes

f(x,y)=iferr([z=x^y,z][2+z>>15],t,e)

Attempt This Online!

A port of Dingus's Ruby answer. Returns e for errors.

• 25 bytes if different errors are allowed to print different messages. Jul 8 at 7:43

# Python 3, 41 bytes

lambda x,n:int([x**n][x*x>1and x**n>>15])


Try it online!

This function throw errors when failed. But different errors for different testcases.

Code lambda x,n:[x**n][x**n>>15] failed when $$\\lvert x\rvert=1 \land n<0\$$.

• x**n>>15 will be 0 if x is an integer in 0~32767, or -1 if x**n is an integer in -32768~-1, or raise exception is x**n is non-integer, or other integer values for other cases (which try to access array [x**n] out of range and raise another exception).
– tsh
Jul 8 at 8:30
• Nice solution with the shifting test! Jul 8 at 16:55

# Retina, 114 bytes

^(-?1,)-
$1 /,-/(K T-_.+[02468]$
~-?(.+),(.+)
\d.+¶$$.(2*(1*)_ A\d{6} \d+ *_# A^(-_)?_{32768} (_*)# .1  Try it online! Link includes test cases modified to run in a reasonable amount of time on TIO. Outputs nothing in case of error. Explanation: ^(-?1,)- 1  Negating the exponent of 1 or -1 has no effect. /,-/(K  Other negative exponents are an error, otherwise: T-_.+[02468]  Even exponents always produce a non-negative result. ~-?(.+),(.+) \d.+¶$$.($2*$($1$*)_


Perform the exponentiation by evaluation of repeated multiplication of 1 by the base.

A\d{6}


Values of six or more digits are an error.

\d+
*_#


Convert to unary, with a marker to make it golfier to convert negative numbers back to decimal. (Conveniently it also makes it possible to distinguish between 0 and error.)

A^(-_)?_{32768}


Values of 32768 or -32769 or greater absolute value are an error.

(_*)#
\$.1


Convert to decimal.

# Desmos, 8678 77 bytes

k=32768
g(n)=\{-k<=n<k\}\{\mod(n,1)=0\}
f(a,b)=g(a)g(a^b)g(b)a^b\{b>=0,aa=1\}


Returns undefined for errors. Not sure if this is fully correct, but it at least passes all the test cases.

Try It On Desmos!

Try It On Desmos! - Prettified

# C (gcc), 43 42 bytes

f(a,b){float c=pow(a,b);a=c-(short)c?0:c;}


Try it online!

1 byte shaved off thanks to ceilingcat.

Uses the standard library's pow(), which works on doubles, which themselves might overflow but will then become ±infinity, and then checking if the result is representable as a short.

• Abusing the ambiguity in return value, great! Jul 9 at 18:42
• Huh, this doesn't actually detect the underflow in 32767 ^ -32768 ~= 2^-491518.55 (way below FLT_MIN), but returning c means returning 0. Good approach to handle / sidestep the seemingly-pointless requirement to handle negative exponents for an integer power function, in languages where you have an easy to access FP pow available. (Unlike assembly, for example.) Jul 9 at 22:34
• @PeterCordes x86 can calculate approximate float and integer pow with log2 instructions and bsr. Jul 11 at 8:39
• @xiver77: I considered looking into an x87 FP pow function with frint or fistp at the end, but for an integer problem was more interested in golfing an integer implementation (to take advantage of imul's built-in detection of signed overflow out of that range; see my answer). Pretty sure an x87 pow would be at least as long, and obviously bsr is way too approximate; rounding up or down to a power of 2 is huge error when we need an exact integer result. Jul 11 at 8:46

# x86-16 machine code, 12 bytes

Could save 1 byte by using opcode CE (into) to trap on OF=1, instead of jumping to return from the function.

• 32-bit mode: 13 bytes: need a 66 operand-size prefix for imul si, rest can use the same machine code bytes, which will give 32-bit operand-size. (So in source you'd write it as xor eax,eax/inc eax. And jecxz. loop automatically uses the address-size as the width of CX/ECX/RCX it uses, so the mode-sized width of that register is significant as an arg.)
• 64-bit mode, 14 bytes: like 32-bit plus inc eax is a 2-byte instruction. (Negative exponents will run nearly 2^64 iterations, so rather impractical, unlike 32-bit bit mode where it only takes a couple seconds when the base is -1 so it doesn't overflow.)

Fixme: non-competing, doesn't handle pow(0, -100) = error, instead returns 0. Handles any non-zero base with any exponent, or any base with any non-negative exponent. I don't see why it's interesting to have an integer power function allow negative exponents in the first place; unsigned or guaranteed non-negative would make more sense. But I think this is interesting because 0 ** (unsigned)n with overflow-checked multiply comes so close to handling everything without any special work to deal with negative exponents.

                    checked_pow:      ; x in SI,  n in (ER)CX
00 31C0               xor  ax,ax
02 40                 inc  ax      ; mov [e]ax,1  and clear OF
03 E306               jcxz  .exit
.loop:              ;do{
05 F7EE               imul  si         ; total *= x;
07 7002               jo  .exit        ; break on signed overflow of the low half (i.e. if cwd would change DX)
09 E2FA               loop .loop      ;}while(--n!=0);
.exit:
0B C3                 ret


Function taking args in SI and CX, returning an out-of-band error status in OF (the overflow flag), and a value in AX. The AX value is meaningful if OF=0, otherwise there was overflow. (So just like an instruction like add; the caller can into to trap on overflow if they want, or jo like this function did.)

Widening multiply can't actually lose any bits, so x86's mul and imul instructions set FLAGS according to whether the low half is the same as the full result. i.e. whether the high half is the zero- or sign-extension of the low half respectively. i.e. after imul, if cwd to sign-extend AX into DX:AX would change anything. If the result doesn't fit in the low half, CF=OF=1, otherwise they're cleared to zero.

Corner case handling:

• x^0 (including 0^0) correctly returns 1, detected with jcxz. If not for this, could save 2 bytes

• x^negative correctly overflows for |x| > 1, because loop treats the count as unsigned. Any negative exponent is treated as an unsigned exponent of at least 32768 (in 16-bit mode; much higher in 32 or 64-bit mode if sign-extended into ECX or RCX as required, instead of zero-extended to be large positive).

Any base other than 1, 0, or -1 will result in signed overflow in at most 16 iterations.

• -1^negative correctly returns 1 or -1, according to the exponent being odd or even. Negative even two's complement signed integers have their low bit clear, so represent even unsigned numbers. To put it another way, -1^-n = -1^|n|, and 2's complement absolute value doesn't change the low bit.

• 0^negative: unhandled, we just do 0 ** (unsigned)n, producing zero without overflowing like we should for 1/0.

Semi-related: Implement Binary Exponentiation shows a more efficient algorithm (more bytes, but much faster for large n. Of course overflow happens so fast that it's not a big deal except for degenerate cases like 1 and -1 with huge exponents. Since we don't need performance here, it's of course smaller code to just use the O(n) algorithm.

# (Python 3, 53 bytes)

Fails(!) for the first test case, I do not yet understand what's wrong.

Posted for the sake of the test code boilerplate, and the idea of using set operations.

lambda b,e:int(({b**e}&{*range(-2**15,2**15)}).pop())


Try it online!

• I think the problem is that -32768**(-32768) computes to 0. I was having the same problem. Jul 7 at 22:51
• Seems to be a precision problem with floating points, so the challenge is to take care of it and use precise integer arithmetics. Jul 7 at 23:01
• @movatica (-32768)**-32768 isn't an integer.
– Neil
Jul 8 at 0:20
• @Neil: That's what I ment. Python falls back to floating point, then precision fails to handle it, and the result is 0.0, when it really should be out of the range. Jul 8 at 16:54
• @movatica Not sure what you mean by "out of the range" there.
– Neil
Jul 8 at 22:34

# Charcoal, 34 bytes

ＮθＮη¿∨⁼¹↔θ¬‹η⁰ＩΦ⟦Ｘθ↔η⟧№…±Ｘ⁸¦⁵Ｘ⁸¦⁵ι


Try it online! Link is to verbose version of code. Outputs nothing in case of error. Explanation:

ＮθＮη


Input x and y.

¿∨⁼¹↔θ¬‹η⁰


If the absolute value of x is 1 or y is non-negative, then:

ＩΦ⟦Ｘθ↔η⟧№…±Ｘ⁸¦⁵Ｘ⁸¦⁵ι


Output x to the power of y if it lies in the range [-32768,32768).

# C (gcc), 73 bytes

c;f(a,b){c=b?b>0||!(a+1&~2)&&(b=-b)?a*f(a,b-1):0:1;return(short)c-c?0:c;}


Try it online!

(-1 bytes @ceilingcat)
(-5 bytes @JuanIgnacioDíaz)

Returns 0 for error.

# Husk, 13 11 bytes

S&€hṡ32768^


Outputs 0 as 'special value' for error.

          ^    # pow without overflow/error checking;
ṡ32768     # range from -32768 to 32768
h           # without the last element
# (so: -32768 to 32767);
€            # is the pow a member of this range?
S&             # if yes, output the pow
# if no, output falsy = zero