Re: Should not integer exponentiation work when it works?

[Kaleb Barrett <ktbarrett.connectflour@...>]

On 06/09/2016 04:45 AM, Dirk Laurie wrote:
> I know I am reopening an old can of worms.

Alaskan Bull Worms at that.


> Would it not be nice if 37^12 returned 6582952005840035281?
> I'm not asking that an integer exponent always calls  a different
> algorithm, only that when integer^n with integer n>=0 can be
> represented exactly, that exact result will be provided.

I agree, mostly.
Between most arithmetic operations (+, -, *) if Lua detects that both 
operands are integers, it will use integer arithmetic. Otherwise, it 
will use floating point arithmetic. It is a good idea to keep this 
behavior consistent for exponentiation (and division too!!).

However, I think detecting overflow and using floating point arithmetic 
under overflow conditions doesn't fit into Lua's model. Integer 
arithmetic overflows are ignored in the other integer operations.

> One difficulty is that ipow is not easy to write. We are multiplying
> large numbers in the process, e.g
>
> > 69343957*3512479453921
> 3761551257857134389
>
> In base 10, you can see the result is wrong (the last digit should
> be a 7) so there must have been an overflow, but is there a cheap,
> elegant way to detect it?

Detecting overflow is easy; just not in C. Which is probably why there 
is no integer overflow behavior in the other arithmetic operations.

The quickest way you are going to check to see if an exponentiation will 
overflow in Lua is with logarithms or doing the operation with higher 
precision integers. Neither method is particularly fast (compared to 
checking a bit in a register). But given the modification to 
exponentiation, you could just do something like

local INT_BITS = math.log(math.maxinteger, 2)
function pow_s(n, e)
  if  e >= 0 and e <= 63 and
      math.type(n) == "integer" and math.type(e) == "integer" and
      math.log(n, 2)*e > INT_BITS
      then
    n = n * 1.0
  end
  return n^e
end

to catch overflows and do floating point exponentiation instead. Just as 
you would for catching overflow in the other operators. Or you can write 
a C function that takes advantage of GCC's or Clang's builtins.

The justification for not implementing overflow checking in the runtime 
is the obvious additional cost of every operation or the need to use 
non-portable builtins. Those who need the behavior can bear the cost.


This is of course if I'm understanding how integers are supposed to 
function within the language. (Should floats and ints be easily 
intermixed and separate operators given for different behaviors, or 
should the types be distinct with type-generic operators? It seems like 
Lua prescribes to neither philosophy expressly in 5.3).


--
Kaleb