Re: Should not integer exponentiation work when it works?

[Egor Skriptunoff <egor.skriptunoff@...>]

On Thu, Jun 9, 2016 at 11:45 AM, Dirk Laurie <dirk.laurie@gmail.com> wrote:

I know I am reopening an old can of worms.

I like the worms from this can.

 

so there must have been an overflow, but is there a cheap,
elegant way to detect it?

Obvious answer:
if log(37)*12 < log(2^63) then integer_operation else float_operation end

Is log(x) cheap?

The idea to use approximation for log() may be attractive:

log2((1+m)*2^e) ~ m+e  (m and e are extracted from float using bit-fiddling)

Or more exact approximation:
http://www.machinedlearnings.com/2011/06/fast-approximate-logarithm-exponential.html

But, unfortunately, approximated log() is not sensitive enough to feel the difference:
2^63 > 3037000499^2
2^63 < 3037000500^2

More straightforward solution:

Calculation of a^b (both a and b are integers, b is non-negative)

If a is non-negative:

1) Do float calculation, as usual: result = a^b

2) If result is less that 2^53, then convert it to integer and return integer result

3) If result is above 2^63, then return float result
4) Recalculate the result using integer multiplication and return it

If a is negative, then we calculate (-1)^b*(-a)^b,
but instead of returning float on step 3 we raise an error.