16
\$\begingroup\$

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
\$\endgroup\$
4
  • 6
    \$\begingroup\$ Can -1 and 0 really be used as the special value? They are indistinguishable from a valid answer. \$\endgroup\$
    – Arnauld
    Jul 7, 2022 at 23:38
  • 1
    \$\begingroup\$ It's too bad, but you don't have any other choice if all your language has is 16-bit integers. \$\endgroup\$
    – anatolyg
    Jul 8, 2022 at 0:11
  • 6
    \$\begingroup\$ 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). \$\endgroup\$
    – Dingus
    Jul 8, 2022 at 0:57
  • \$\begingroup\$ It should be the same. Updated the text. \$\endgroup\$
    – anatolyg
    Jul 8, 2022 at 7:54

13 Answers 13

14
\$\begingroup\$

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
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ Jul 8, 2022 at 11:49
  • 2
    \$\begingroup\$ 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 _) \$\endgroup\$
    – AnttiP
    Jul 8, 2022 at 16:21
  • \$\begingroup\$ @AnttiP That would panic if x*x overflows. \$\endgroup\$
    – L. F.
    Jul 8, 2022 at 22:17
  • \$\begingroup\$ @L.F. Not with release flags, it will simply overflow. ATO \$\endgroup\$
    – AnttiP
    Jul 9, 2022 at 7:55
  • \$\begingroup\$ @AnttiP Indeed, forgot about that! \$\endgroup\$
    – L. F.
    Jul 9, 2022 at 16:08
9
\$\begingroup\$

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

Ruby, 30 29 bytes

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

Try it online!

Returns nil for errors.

\$\endgroup\$
1
  • 2
    \$\begingroup\$ 23 bytes if different errors are allowed to throw different exceptions. \$\endgroup\$
    – Dingus
    Jul 8, 2022 at 5:12
6
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 25 bytes if different errors are allowed to print different messages. \$\endgroup\$
    – alephalpha
    Jul 8, 2022 at 7:43
5
\$\begingroup\$

Python 3, 41 bytes

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

Try it online!

TIO link using codes from movatica's answer.

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\$.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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). \$\endgroup\$
    – tsh
    Jul 8, 2022 at 8:30
  • \$\begingroup\$ Nice solution with the shifting test! \$\endgroup\$
    – movatica
    Jul 8, 2022 at 16:55
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

Desmos, 86 78 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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Abusing the ambiguity in return value, great! \$\endgroup\$
    – anatolyg
    Jul 9, 2022 at 18:42
  • 1
    \$\begingroup\$ 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.) \$\endgroup\$ Jul 9, 2022 at 22:34
  • \$\begingroup\$ @PeterCordes x86 can calculate approximate float and integer pow with log2 instructions and bsr. \$\endgroup\$
    – xiver77
    Jul 11, 2022 at 8:39
  • \$\begingroup\$ @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. \$\endgroup\$ Jul 11, 2022 at 8:46
4
\$\begingroup\$

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.

NASM listing: address, machine-code (the answer proper), source

                    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.

\$\endgroup\$
3
\$\begingroup\$

Charcoal, 34 bytes

NθNη¿∨⁼¹↔謋η⁰IΦ⟦Xθ↔η⟧№…±X⁸¦⁵X⁸¦⁵ι

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

NθNη

Input x and y.

¿∨⁼¹↔謋η⁰

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

IΦ⟦Xθ↔η⟧№…±X⁸¦⁵X⁸¦⁵ι

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
0
1
\$\begingroup\$

Husk, 13 11 bytes

S&€hṡ32768^

Try it online! or try some of the test-cases

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
\$\endgroup\$
1
\$\begingroup\$

Pascal, 52 B

The ISO standard 10206 “Extended Pascal” defines the integer power operator pow. NB: Zero to the power of zero causes an error. Provided that the implementation-defined value of the required constant maxInt is greater than or equal to 32768 you can wrap pow into a function like this:

function f(x,y:integer):integer;begin f:=x pow y end

The standard specifies that

It shall be an error if an integer operation or function is not performed according to the mathematical rules for integer arithmetic.

An error is

A violation by a program of the requirements of this International Standard that a processor is permitted to leave undetected.

Thus whether and how an overflow is signaled is at the compiler developer’s discretion.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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