int32 multiplication, with truncation on overflow
- From: Duncan Cross <duncan.cross@xxxxxxxxx>
- To: luajit@xxxxxxxxxxxxx
- Date: Thu, 1 May 2014 00:09:47 +0100
Say that I have two Lua number values, a and b, that I know are both
integers within the range of a signed 32-bit int. I want to multiply
these numbers, ensuring the result is also in int32 range -- if it
doesn't fit, the higher bits should just be truncated -- but the
result should otherwise be reliably consistent integer multiplication.
Doing it this way:
--
local bit = require 'bit'
result = bit.band(0xFFFFFFFF, a * b)
--
...seems fine initially, but if a and b get pretty huge (e.g. both
over 100 million) then the result can no longer be represented
precisely as a double/Lua number [1], so the results start to get
skewed.
Using a version of LuaJIT that supports bitops on 64-bit numbers, we
could convert a and b to 64-bit ints, multiply those, then convert the
result back to 32 bits:
--
local bit = require 'bit'
result = tonumber(bit.arshift(bit.lshift((0LL + a) * (0LL + b), 32), 32))
--
On the other hand, if only 32-bit ops are available, we could do
"manual" multiplication using adds and bitops [2]:
--
local bit = require 'bit'
result = 0
while b ~= 0 do
if bit.band(b, 1) == 1 then
result = bit.band(0xFFFFFFFF, result + a)
end
a = bit.lshift(a, 1)
b = bit.rshift(b, 1)
end
--
I'd be interested in any comments on this, if there is anything
obvious I've missed or further recommendations that could be made.
[1] Side note: Of course, If either value is known to be in a much
smaller range than the full range of int32s, then bit.band(0xFFFFFFFF,
a * b) should be OK. I'm not sure exactly what this smaller range is,
but I think +/- 1 million is a reasonable conservative approximation.
[2] http://en.wikipedia.org/wiki/Bitwise_operation#Applications
-Duncan
Other related posts:
