Bobert13
Prince
- Joined
- Feb 25, 2013
- Messages
- 346
Why did I re-write the plus sign?
Sadly, floating point math on the x86 architecture is inconsistent. You can literally multiply the same two numbers a hundred times and end up with three (or more) different results. This happens because the floating point unit (FPU) of the processor can be set to a different mode (half-precision, single-precision, double-precision, extended precision) during the execution of your script, and the script won't know about it. This inconsistency may be responsible for desynchronized maps spawning in multiplayer for many of the more popular mapscripts (Perfect World, and Communita's for sure at the time of writing this)
How does one implement the library?
Copy and paste it into your script above where it's being used. You'll need to use the provided conversion functions (tobob and tonum) to convert floats into "bobs" (what I've named my fixed precision, consistent number type) and back to floats again if necessary. From there, you use one of the provided math functions (addbob, subbob, mulbob, divbob, powbob, and comparebob) to do math with bobs.
Can you help Improve this Library?
YES! Any performance, accuracy, or (most importantly) consistency improvements are very much appreciated. Beyond that, if anyone is familiar with Newton's approximation of nth root (and more importantly, how to implement it in code), any help in that regard would be much appreciated. I'm currently having to convert back to floating point, use Lua's math.exp and then convert back to bob for calculating roots. Additionally, a F.O.I.L.-based method for division would also be nice (I'm pretty sure I'm capable of this I just haven't gotten it right yet).
Are there any limitations?
YES! bobs are meant to be used on decimal numbers between 0.0 and 1.0. That means I did include the "ones" digit in bobs, but no others (yet. I plan on going up to at least the thousands if not the millions digit). In the other direction, bobs can only go out to 8 digits past the decimal, anything smaller than 0.00000001 is zero. This will probably not be changing as I see no need for precision past the hundred-millionths in anything this Library is meant to be applied towards, and adding more digits makes the table that holds bobs larger meaning all of the functions require more memory and take longer to return.
The library:
Revision 2:
Known Possible Bugs:
Neither of these bugs have been confirmed at this point. All of my tests have shown 100% consistency; however I haven't tested every possible input...
Why are bobs consistent?
bobs are numbers broken down into a table of numbers that (ideally) never exceed the size of what half-precision floating point can represent at "full" half-precision. That means no matter what the FPU happens to be set to, all calculations done on bobs should be 100% consistent. Each table index holds a three digit integer number. These tables are aligned so that the decimal is always one-digit into index [0] (if bob[0] holds the number 438, in floating point it would be the number 4.38; if bob[1] (the next index) holds 438 it would represent 0.00438 and so on...). Negative numbers are handled by the table index ["n"] (if bob["n"] is defined (as anything), then that bob-type number is negative; I did it this way to avoid the overhead of returning the extra table value when dealing with positive numbers). When numbers greater than 9.999... are added to the bob, they will be handled in a similar way to avoid said overhead.
Sadly, floating point math on the x86 architecture is inconsistent. You can literally multiply the same two numbers a hundred times and end up with three (or more) different results. This happens because the floating point unit (FPU) of the processor can be set to a different mode (half-precision, single-precision, double-precision, extended precision) during the execution of your script, and the script won't know about it. This inconsistency may be responsible for desynchronized maps spawning in multiplayer for many of the more popular mapscripts (Perfect World, and Communita's for sure at the time of writing this)
How does one implement the library?
Copy and paste it into your script above where it's being used. You'll need to use the provided conversion functions (tobob and tonum) to convert floats into "bobs" (what I've named my fixed precision, consistent number type) and back to floats again if necessary. From there, you use one of the provided math functions (addbob, subbob, mulbob, divbob, powbob, and comparebob) to do math with bobs.
Can you help Improve this Library?
YES! Any performance, accuracy, or (most importantly) consistency improvements are very much appreciated. Beyond that, if anyone is familiar with Newton's approximation of nth root (and more importantly, how to implement it in code), any help in that regard would be much appreciated. I'm currently having to convert back to floating point, use Lua's math.exp and then convert back to bob for calculating roots. Additionally, a F.O.I.L.-based method for division would also be nice (I'm pretty sure I'm capable of this I just haven't gotten it right yet).
Are there any limitations?
YES! bobs are meant to be used on decimal numbers between 0.0 and 1.0. That means I did include the "ones" digit in bobs, but no others (yet. I plan on going up to at least the thousands if not the millions digit). In the other direction, bobs can only go out to 8 digits past the decimal, anything smaller than 0.00000001 is zero. This will probably not be changing as I see no need for precision past the hundred-millionths in anything this Library is meant to be applied towards, and adding more digits makes the table that holds bobs larger meaning all of the functions require more memory and take longer to return.
The library:
Spoiler :
Revision 2:
Code:
-------------------------------------------------------------------------------------------
-- bob Class finite precision math
--
-- tobob expects a floating point number
--
-- tonum expects a bob
--
-- The four primary arithmetic functions (add, sub, mul, div) expect two bobs as input
--
-- The pow function expects a bob, and a floating point number as input
--
-- compare expects two bobs, and a string (see compare for the strings and the Global variables that save you from typing the quotations)
-------------------------------------------------------------------------------------------
function split(num)
local int, dec = math.modf(num)
if num >= 1.0 then
if dec > 0.999999999 then
print("0.999... returned from math.modf ", int, dec)
dec = 0
int = int + 1
elseif dec < 0.1 and dec > 0.0999999999 then
print("0.0999... returned from math.modf ", int, dec)
dec = 0.1
elseif dec < 0.01 and dec > 0.00999999999 then
print("0.00999... returned from math.modf ", int, dec)
dec = 0.01
elseif dec < 0.001 and dec > 0.000999999999 then
print("0.000999... returned from math.modf ", int, dec)
dec = 0.001
end
end
return int, dec
end
-------------------------------------------------------------------------------------------
function tobob(num)
local bob = {}
local temp
local neg = 1
if num < 0 then
num = -num
bob["n"] = 0
end
bob[0], temp = split(num * 100)
bob[1], temp = split(temp * 1000)
bob[2] = math.floor(temp * 1000 + 0.1) -- adding 0.1 here to prevent issues with FP returning 0.999... in place of 1.0
-- print(bob[0].."."..bob[1]..bob[2])
return bob
end
-------------------------------------------------------------------------------------------
-- Global bobs used for various things
zerobob = tobob(0)
halfbob = tobob(0.5)
onebob = tobob(1)
twobob = tobob(2)
Ebob = tobob(0.00000001)
-------------------------------------------------------------------------------------------
function tonum(bob)
local num = (bob[0] * 0.01) + (bob[1] * 0.00001) + (bob[2] * 0.00000001)
if bob["n"] then
return -num
else
return num
end
end
-------------------------------------------------------------------------------------------
-- global strings for comparebob
NE = "NE" -- ~=
EQ = "EQ" -- ==
GT = "GT" -- >
GE = "GE" -- >=
LT = "LT" -- <
LE = "LE" -- <=
-------------------------------------------------------------------------------------------
function comparebob(bob1, bob2, op)
if op == "NE" then
if (bob1["n"] and (not bob2["n"])) or
((not bob1["n"]) and bob2["n"]) then return true
elseif bob1[0] ~= bob2[0] then return true
elseif bob1[1] ~= bob2[1] then return true
elseif bob1[2] ~= bob2[2] then return true
else return false
end
elseif op == "EQ" then
if (bob1["n"] and (not bob2["n"])) or
((not bob1["n"]) and bob2["n"]) then return false
elseif bob1[0] ~= bob2[0] then return false
elseif bob1[1] ~= bob2[1] then return false
elseif bob1[2] ~= bob2[2] then return false
else return true
end
elseif op == "GT" then
if (not bob1["n"]) and bob2["n"] then return false
elseif bob1["n"] and (not bob2["n"]) then return true
elseif bob1[0] > bob2[0] then return true
elseif bob1[0] == bob2[0] then
if bob1[1] > bob2[1] then return true
elseif bob1[1] == bob2[1] then
if bob1[2] > bob2[2] then return true
end
end
else return false
end
elseif op == "GE" then
if (not bob1["n"]) and bob2["n"] then return false
elseif bob1["n"] and (not bob2["n"]) then return true
elseif bob1[0] > bob2[0] then return true
elseif bob1[0] == bob2[0] then
if bob1[1] > bob2[1] then return true
elseif bob1[1] == bob2[1] then
if bob1[2] > bob2[2] then return true
elseif bob1[2] == bob2[2] then return true
end
end
else return false
end
elseif op == "LT" then
if (not bob1["n"]) and bob2["n"] then return false
elseif bob1["n"] and (not bob2["n"]) then return true
elseif bob1[0] < bob2[0] then return true
elseif bob1[0] == bob2[0] then
if bob1[1] < bob2[1] then return true
elseif bob1[1] == bob2[1] then
if bob1[2] < bob2[2] then return true
end
end
else return false
end
elseif op == "LE" then
if (not bob1["n"]) and bob2["n"] then return false
elseif bob1["n"] and (not bob2["n"]) then return true
elseif bob1[0] < bob2[0] then return true
elseif bob1[0] == bob2[0] then
if bob1[1] < bob2[1] then return true
elseif bob1[1] == bob2[1] then
if bob1[2] < bob2[2] then return true
elseif bob1[2] == bob2[2] then return true
end
end
else return false
end
else
return nil
end
end
-------------------------------------------------------------------------------------------
function addbob(bob1, bob2)
local retbob = {}
local carry
retbob[2] = bob1[2] + bob2[2]
if retbob[2] > 999 then
carry, retbob[2] = math.modf(retbob[2] * 0.001)
retbob[2] = retbob[2] * 1000
else
carry = 0
end
retbob[1] = bob1[1] + bob2[1] + carry
if retbob[1] > 999 then
carry, retbob[1] = math.modf(retbob[1] * 0.001)
retbob[1] = retbob[1] * 1000
else
carry = 0
end
retbob[0] = bob1[0] + bob2[0] + carry
return retbob
end
-------------------------------------------------------------------------------------------
-- Subtracts bob2 from bob1
function subbob(bob1, bob2)
local retbob = {}
local carry
if comparebob(bob1, bob2, LT) then
retbob["n"] = 0
end
-- retbob[0] = 0
-- retbob[1] = 0
-- retbob[2] = 0
retbob[2] = bob1[2] - bob2[2]
if retbob[2] < 0 then
retbob[2] = retbob[2] + 1000
carry = 1
end
retbob[1] = bob1[1] - bob2[1] - carry
carry = 0
if retbob[1] < 0 then
retbob[1] = retbob[1] + 1000
carry = 1
end
retbob[0] = bob1[0] - bob2[0] - carry
if retbob[0] < 0 then
retbob[0] = 100 + retbob[0]
end
return retbob
end
-------------------------------------------------------------------------------------------
function mulbob(bob1, bob2)
local retbob = {}
local lastbob = 0
local lastlastbob = 0
local carry = 0
local add = 0
retbob[0] = (bob1[0] * bob2[0]) * 0.01
retbob[0], carry = math.modf(retbob[0])
if carry > 0.999 then
carry = 0
retbob[0] = retbob[0] + 1
elseif carry < 0.1 and carry > 0.0999 then
carry = 100
elseif carry < 0.01 and carry > 0.00999 then
carry = 10
else
carry = carry * 1000
end
retbob[1] = ((bob1[0] * bob2[1]) + (bob1[1] * bob2[0])) * 0.01 + carry
retbob[1], carry = math.modf(retbob[1])
if carry > 0.999 then
carry = 0
retbob[1] = retbob[1] + 1
elseif carry < 0.1 and carry > 0.0999 then
carry = 100
elseif carry < 0.01 and carry > 0.00999 then
carry = 10
else
carry = carry * 1000
end
retbob[2] = ((bob1[1] * bob2[1]) + (bob1[0] * bob2[2]) + (bob1[2] * bob2[0])) * 0.01 + carry
retbob[2], carry = math.modf(retbob[2])
if carry > 0.999 then
carry = 0
retbob[2] = retbob[2] + 1
elseif carry < 0.1 and carry > 0.0999 then
carry = 100
elseif carry < 0.01 and carry > 0.00999 then
carry = 10
else
carry = carry * 1000
end
lastbob = ((bob1[1] * bob2[2]) + (bob1[2] * bob2[1])) * 0.01 + carry
lastbob, carry = math.modf(lastbob)
if carry > 0.999 then
carry = 0
lastbob = lastbob + 1
elseif carry < 0.1 and carry > 0.0999 then
carry = 100
elseif carry < 0.01 and carry > 0.00999 then
carry = 10
else
carry = carry * 1000
end
lastlastbob = (bob1[2] * bob2[2]) * 0.01 + carry
lastlastbob = math.floor(lastlastbob)
if lastlastbob > 999 then
add = math.floor(lastlastbob * 0.001)
lastbob = lastbob + add
end
if lastbob > 999 then
add = math.floor(lastbob * 0.001)
retbob[2] = retbob[2] + add
end
if retbob[2] > 999 then
add, retbob[2] = math.modf(retbob[2] * 0.001)
retbob[1] = retbob[1] + add
retbob[2] = retbob[2] * 1000
end
if retbob[1] > 999 then
add, retbob[1] = math.modf(retbob[1] * 0.001)
retbob[0] = retbob[0] + add
retbob[1] = retbob[1] * 1000
end
if (bob1["n"] and (not bob2["n"])) or ((not bob1["n"]) and bob2["n"]) then
retbob["n"] = 0
end
return retbob
end
-------------------------------------------------------------------------------------------
function divbob(bob1, bob2)
-- ##### Inverse Multiplication Method #####
local retbob = {}
local temp1 = bob1
local temp2 = bob2
if comparebob(bob1, bob2, EQ) == true then
retbob[0] = 100
retbob[1] = 0
retbob[2] = 0
return retbob
elseif comparebob(bob1, bob2, GT) == true then
temp1 = tobob(1 / tonum(temp2))
else
-- print("poopy")
temp2 = tobob(1 / tonum(temp2))
end
retbob = mulbob(temp1, temp2)
-- ##### Subtraction Method (very slow, bug @ "* 10") #####
-- local temp1 = bob1
-- local temp2 = bob2
-- local retbob = {}
-- local zerobob = {}
-- retbob[0], zerobob[0] = 0, 0
-- retbob[1], zerobob[1] = 0, 0
-- retbob[2], zerobob[2] = 0, 0
-- retbob[3], zerobob["n"] = 1, 1
-- local count1 = 0
-- local count2 = 0
-- local count3 = 0
-- local count4 = 0
-- local count5 = 0
-- local count6 = 0
-- local count7 = 0
-- local count8 = 0
-- local count9 = 0
-- if comparebob(temp1, bob2, "GT") == true then
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count1 = count1 + 1
-- if count1 > 9 then
-- print("OH NOES! WE NEED MORE DIGITS")
-- break
-- end
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count2 = count2 + 1
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count3 = count3 + 1
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count4 = count4 + 1
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count5 = count5 + 1
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count6 = count6 + 1
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count7 = count7 + 1
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count8 = count8 + 1
-- end
-- end
-- if comparebob(temp1, zerobob, "GT") == true then
-- temp1[0] = temp1[0] * 10
-- temp1[1] = temp1[1] * 10
-- temp1[2] = temp1[2] * 10
-- while comparebob(temp1, bob2, "GE") == true do
-- temp1 = subbob(temp1, bob2)
-- count9 = count9 + 1
-- end
-- end
-- retbob[0] = count1 * 100 + count2 * 10 + count3
-- retbob[1] = count4 * 100 + count5 * 10 + count6
-- retbob[2] = count7 * 100 + count8 * 10 + count9
--print(retbob[0], temp1[0],temp1[1],temp1[2])
return retbob
end
-------------------------------------------------------------------------------------------
-- Halley's method applied to finding nth rooth of num (works to a point, with a very close starting guess)
function halleybob(app, num, root)
local appnth = app
for n = 2, 1/root do
appnth = mulbob(appnth, app)
end
print(tonum(app), tonum(appnth), tonum(num))
-- retbob = divbob(mulbob(app, addbob(appnth, addbob(num, num))), addbob(addbob(appnth, appnth), num))
local retbob = divbob(mulbob(app, addbob(appnth, addbob(num, num))), addbob(addbob(appnth, appnth), num))
return retbob
end
-------------------------------------------------------------------------------------------
-- Newton's nth root (Way broken)
function newtonbob(app, num, root)
--local onebob = tobob(1)
print(tonum(app), root, tonum(num))
--subbob(app, mulbob(root, subbob(app, divbob(num, mulbob(app, app)))))
local retbob = subbob(app, mulbob(tobob(root), subbob(app, divbob(num, mulbob(app, app)))))
return retbob
end
-------------------------------------------------------------------------------------------
function rootbob(guess, bob, root, add)
local nthguess = guess
local newguess = guess
--print(tonum(nthguess))
for n = 2, root do
nthguess = mulbob(nthguess, guess)
end
local DOOET = comparebob(nthguess, bob, NE)
while DOOET == true do
-- print(tonum(nthguess).." < "..tonum(bob))
newguess = addbob(newguess, add)
nthguess = newguess
for n = 2, root do
nthguess = mulbob(nthguess, newguess)
end
DOOET = comparebob(nthguess, bob, LE)
if DOOET == true then
guess = newguess
end
end
-- print(tonum(nthguess).." !< "..tonum(bob), "bob: "..bob[0]..","..bob[1]..","..bob[2], "add: "..tonum(add))
-- print("guess: "..tonum(guess))
return guess
end
-------------------------------------------------------------------------------------------
function powbob(bob, pow)
local retpow = tobob(1)
local retsqr = tobob(1)
local sqr = 0
pow, sqr = split(pow)
if sqr ~= 0 then
if sqr > 0.999 then
sqr = 0
pow = pow + 1
else
sqr = Round(1 / sqr)
local guess = zerobob
for n = 0, 8 do
guess = rootbob(guess, bob, sqr, tobob(10^-n))
end
retsqr = guess
--retsqr = tobob(tonum(bob)^sqr) -- this line may not produce consistent results
end
end
if pow ~= 0 then
retpow = bob
for n = 1, pow-1 do
retpow = mulbob(bob, retpow)
end
end
retbob = mulbob(retpow, retsqr)
return retbob
end
-------------------------------------------------------------------------------------------
function Round(n)
if n > 0 then
if n - math.floor(n) >= 0.5 then
return math.ceil(n)
else
return math.floor(n)
end
else
if math.abs(n - math.ceil(n)) >= 0.5 then
return math.floor(n)
else
return math.ceil(n)
end
end
end
-------------------------------------------------------------------------------------------
Known Possible Bugs:
- Anywhere I'm using math.modf could possibly return 0.999... instead of 1 given the right (rare) input number. I haven't verified that the places where I haven't checked for this can possibly do so, but the script should consistently do this for a given input so atleast it should consistently produce the wrong value instead of doing whatever the FPU tells it.
- In divbob and during the calculation of non-integer exponents (roots) in powbob I'm using standard Lua math that may produce inconsistent results.
Neither of these bugs have been confirmed at this point. All of my tests have shown 100% consistency; however I haven't tested every possible input...
Why are bobs consistent?
bobs are numbers broken down into a table of numbers that (ideally) never exceed the size of what half-precision floating point can represent at "full" half-precision. That means no matter what the FPU happens to be set to, all calculations done on bobs should be 100% consistent. Each table index holds a three digit integer number. These tables are aligned so that the decimal is always one-digit into index [0] (if bob[0] holds the number 438, in floating point it would be the number 4.38; if bob[1] (the next index) holds 438 it would represent 0.00438 and so on...). Negative numbers are handled by the table index ["n"] (if bob["n"] is defined (as anything), then that bob-type number is negative; I did it this way to avoid the overhead of returning the extra table value when dealing with positive numbers). When numbers greater than 9.999... are added to the bob, they will be handled in a similar way to avoid said overhead.