Integer Domain

wiki

--**** should be compatible with 5.xx
function intlimit()
  local floor = math.floor

  -- get highest power of 2 which Lua can still handle as integer
  local step = 2
  while true do
    local nextstep = step*2
    if nextstep-(nextstep-1) == 1 and nextstep > 0 then
      step = nextstep
    else
      break
    end
  end

  -- now get the highest number which Lua can still handle as integer
  local limit,step = step,floor(step/2)
  while step > 0 do
    local nextlimit = limit+step
    if nextlimit-(nextlimit-1) == 1 and nextlimit > 0 then
      limit = nextlimit
    end
    step = floor(step/2)
  end
  return limit
end

Example:

  local limit = intlimit()

  print()
  print("IntegerDomain - what is the largest supported integer number?")
  print()

--**** do not rely on Lua to print "limit" properly by itself!
--local printablelimit = string.format("%d", limit)         -- fails under Lua!
  local printablelimit = string.format("%.16e", limit)

  print("supported integer range is: -" ..
        printablelimit .. "...+" .. printablelimit)

As you can see, Lua has no problems to process large integer numbers - as long as you don't try to convert them into strings ;-)

To make sure integer numbers are properly converted into string (without scientific notation), rather than using tostring(x), use format.string("%.0f",x)

--AndreasRozek

Can the correctness be proven? Does it assume IEEE? --DavidManura

Hmmm, let me think about the requirements:

• the range of presentable integers must be dense (i.e., there must be no holes)
• there must be a test, which detects whether a given number is a presentable integer or not

Additionally, there are two other assumptions I made

• 0 must be a presentable integer (I use it as a starting point)
• the range of presentable integers is independent of their sign

Both assumptions may easily be checked explicitly (don't forget to replace "floor" by "ceil" when testing negative numbers!).

If the requirements apply, it is possible to use "successive approximation" in order to get the largest presentable integer.

As I do not mention any concrete results, I do not really assume IEEE apart from my assumptions shown above (sign-magnitude coding guarantees the symmetry) and the test I've chosen:

• floor(x) == x should already be sufficient in order to test if a number is integral
• x-1 ~= x has just been added in order to exclude NaN and Infinity

--AndreasRozek

---- I ran this algo with lua 5.1 and it did not quite worked : it gave 9007199254740994 as the max integer, but print(string.format("%0.f", intlimit()-1) returns 9007199254740992 instead of 9007199254740993. I corrected three things in the code :

• floor(x) == x is useless, since you start from integers and do integer stable operation, even when going further than the max integer (floating numbers larger than what the mantis can represent are always integers)
• x-1 ~= x has been replaced by x-(x-1) == 1 it check whether x-1 is also representable (it also exclude NaN and infinity, but they are unreachable anyway)
• On lua 5.3, the integers are handled differently and lua can count up to 2^63 or 2^31 instead of roughly 2^52. The problem is not imprecision due to approximation but overflow, absence of which can be tested by : x > 0
• added a simple way to print integers

--4xel