[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Should not integer exponentiation work when it works?
- From: Kaleb Barrett <ktbarrett.connectflour@...>
- Date: Thu, 9 Jun 2016 15:12:51 -0400
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