lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


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