Integer Domain

lua-users home
wiki

The following code calculates the actual limits for integer numbers which can be exactly represented by Lua (double precision floating point) numbers - besides, it's a nice example for the "successive approximation" technique:

--**** 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:

Additionally, there are two other assumptions I made

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:

--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 :

--4xel


RecentChanges · preferences
edit · history
Last edited April 15, 2016 5:54 pm GMT (diff)