CODEWITHSUNDEEP
luaexponential
Christoph Float
Christoph Float

Reputation: 311

Unexplained behaviour when calculating large powers in Lua

doing some exercises in Lua, I stumbled onto some (to me) really strange behaviour I just cannot explain. The following code is supposed to calculate the number of distinct terms of the form a^b for 2 <= a, b <= 100. This code provides the correct answer, 9183:

local terms = {}
local cnt = 0
for a = 2, 100 do
  for b = 2, 100 do
    term = math.pow(a, b)
    if not terms[term] then
      terms[term] = string.format("%d exp %d", a, b)
      cnt = cnt + 1
    else
      print(term .. " already in set! (" .. terms[term] .. ")")
    end
  end
end

print(cnt)

However, this code produces a different answer (only the 'print()' in the else branch is commented out):

local terms = {}
local cnt = 0
for a = 2, 100 do
  for b = 2, 100 do
    term = math.pow(a, b)
    if not terms[term] then
      terms[term] = string.format("%d exp %d", a, b)
      cnt = cnt + 1
    else
      --print(term .. " already in set! (" .. terms[term] .. ")")
    end
  end
end

print(cnt)

There. that gets me 9254 as an answer. There are no calculations done in that commented-out line, just output to the screen. Yet, it seems to influence the outcome of the calculation. Have I discovered a macroscopic system that underlies the laws of quantum mechanics? ;)

No, but seriously, I'm missing something here, and I would be thoroughly thankful if someone with more experience and knowledge could point me in the right direction.

Thanks in advance!

Upvotes: 2

Views: 216

Answers (1)

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Lua numbers are generally floating point numbers. On most machines, that means practically double in C99 parlance which are represented by IEEE 754 floating point numbers.

You need to read http://floating-point-gui.de/ (floating point is a headache).

In particular, Lua tables are computing some hash and testing for equality, and equality on floating point is not equality on mathematical real numbers. Hence using floating point numbers as key to tables is risky.

Large numbers like 9898 are not represented exactly in IEEE 754...

Morally, if you use a number as a key to some Lua table, you'll better have that number be some integer accurately representable in IEEE754, so concretely be an integer less than 252

I guess that you have been bitten by some implementation specific artifact. You could debug Lua C code (i.e. step by step into Lua C implementation) to find more. Perhaps some garbage collection, or simply hash table reorganization, happens in the first program, but not in the second one, or different rounding rules...

BTW, on my Linux/Debian/Sid/x86-64 desktop with Debian packaged Lua 5.2.4-1 and with Debian packaged Lua 5.3.1-1, both programs give 9183.

Upvotes: 1

Related Questions