1. We have added a Gift Upgrades feature that allows you to gift an account upgrade to another member, just in time for the holiday season. You can see the gift option when going to the Account Upgrades screen, or on any user profile screen.
    Dismiss Notice

Bob's Crappy Lua Math Library

Discussion in 'Civ5 - SDK / LUA' started by Bobert13, Feb 24, 2014.

  1. Bobert13

    Bobert13 Prince

    Joined:
    Feb 25, 2013
    Messages:
    345
    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:
    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.
     
  2. whoward69

    whoward69 DLL Minion

    Joined:
    May 30, 2011
    Messages:
    8,407
    Location:
    Near Portsmouth, UK
    You could save some lines of code, and hence possible areas for bugs, by removing four of the ifs in comparebob() - you only need explicit code for EQ and GT - as

    comparebob(b1, b2, "NE") can be rewritten internally as (comparebob(b1, b2, "EQ") == false)

    comparebob(b1, b2, "GE") can be rewritten internally as (comparebob(b1, b2, "LT") == false)

    comparebob(b1, b2, "LE") can be rewritten internally as (comparebob(b1, b2, "GT") == false)

    comparebob(b1, b2, "LT") can be rewritten internally as ((comparebob(b1, b2, "EQ") or (comparebob(b1, b2, "GT)) == false)

    You've also pasted a huge wall of commented out code in the middle of divbob()
     
  3. bc1

    bc1

    Joined:
    Jan 12, 2004
    Messages:
    1,250
    I find it a bit difficult to understand the approach taken...
    Processors are quite deterministic, and will produce the same results given the same inputs.
    The reason for seemingly different results are that the bit resolution used to represent numbers is not taken into account when truncating or comparing numbers.
    It is these functions that need fixing: number truncation rounds up if within "epsilon" of next higher integer, down otherwise. Numbers are equal if within "epsilon" of each other.
    It is likely that your complex code may actually fall short of solving these issues...
    Cheers
     
  4. Bobert13

    Bobert13 Prince

    Joined:
    Feb 25, 2013
    Messages:
    345
    Thank you for the suggestion, I'll implement and test it for speed. If it's not any slower than my current solution, I'll keep it. The commented out code in divbob() is an alternative method for processing division. I left it in there intentionally as division needs a revision and I figured if anyone out there were to tackle that revision, seeing that slow method may have been helpful to their efforts.

    See here: http://forums.civfanatics.com/attachment.php?attachmentid=359294&d=1377390398 (where I show that the same two inputs going through the same exact math operation (divide) produce different results)

    and the link found here: http://forums.civfanatics.com/showpost.php?p=12734282&postcount=8 (where the issue of FP inconsistency is discussed at length)

    The FPU in the x86 architecture on Windows will allow an interrupting process to change the operation flag controlling precision without notifying the currently running process or reverting it to what the currently running process had it at. Outside of this flaw (that's been around since before Intel rolled the first x86 processor off the assembly line), yes processors are deterministic. My approach sidesteps the issue by ensuring that the state of the FPU is irrelevant and by undermining any previously determined epsilon through telling it that 0.00000001 is 1.
     
  5. whoward69

    whoward69 DLL Minion

    Joined:
    May 30, 2011
    Messages:
    8,407
    Location:
    Near Portsmouth, UK
    It'll be a very close call on speed - in theory will be very, very slightly slower. But the advantage is in maintenance and removing (what are effectively) duplicate, redundant blocks of code.

    Have you though about implementing the library as a Lua pseudo-class? So you could write code such as

    Code:
    -- Create a new bob
    local a = Bob:new(0.002)
    
    -- Add a constant to it, getting a bob back and print that bob
    local b = a:add(0.03)
    print(b:tonum())
    
    -- Create another new bob, and use it in one logical flow
    local c = Bob:new(0.0004)
    print(c:add(a):tonum())
    
    -- Test the subtraction code
    print(a:sub(0.0008):tonum())
    print(a:sub(b):sub(c):tonum())
    
    W

    PS - I'm having flash-backs to Black Adder episodes ... Bob!
     
  6. Bobert13

    Bobert13 Prince

    Joined:
    Feb 25, 2013
    Messages:
    345
    I was actually thinking about having some global defines that are remappable to either bob-class math or standard Lua math. That way I could write interchangeable code; allowing the consistency of bobs in multiplayer and the speed of Lua math when 100% consistency doesn't matter (singleplayer). I like your idea there as it would have it's benefits but I'd also have to wrap the standard math functions into there own psuedo-class to make them interchangeable.
     
  7. whoward69

    whoward69 DLL Minion

    Joined:
    May 30, 2011
    Messages:
    8,407
    Location:
    Near Portsmouth, UK
    You'll have to wrap the standard binary operators anyway, as there's no way to make
    a = b + c
    and
    a = addbob(b, c)
    easily substitutable (unless they've slipped in a math.add() method in the library when I wasn't looking!)

    With SpBob and MpBob classes, you'd just need to use a factory pattern to hand out the appropriate one depending on circumstances
     
  8. Pazyryk

    Pazyryk Deity

    Joined:
    Jun 13, 2008
    Messages:
    3,584
    I don't know why but this caught my interest and sucked up my morning reading about it. (I'm not much of a programmer but I like math.) Two questions:

    1. Wouldn't this affect multiplayer synchronization beyond just map creation?
    2. Are you sure you need to reprogram all math? Is it possible that the inconsistent digits only creep in for some specific math library methods like exp and log?
     
  9. Bobert13

    Bobert13 Prince

    Joined:
    Feb 25, 2013
    Messages:
    345
    The inconsistency in floating point math? Possibly, yes, but it's yet to be shown that it does cause desync.

    The big thing here is that the screenshot I posted shows an error as high as the 8th digit past the decimal. That number is very, very early in the course of generating the elevation map and is getting ready to go through a number of multiplications, divisions, and exponentiations. The inconsistency will get exaggerated greatly as well as the potential for more erroneous, inconsistent, results to creep in during the process. Once elevation map is done, it's literally used to generate everything else Perfect World does (rainfall, rivers, plot types, terrain types, map shift, potentially even player and city-state placement...). An error early on in the elevation map can cause one tile to roll mountains for one player and ocean for the next. This can lead to some really big problems in initial synchronization.

    I believe epsilon, for numbers representable in 1:1 parity in floating point, in the implementation of Lua Civ uses, is around 0.000001. Unless the numbers being used are going through enough operations to achieve an amount of inconsistency greater than that, the inconsistency never becomes a factor.

    No. I started bob numbers as a proof of concept with the conversion formulas and add. I grew it from there. When I get to implementing it, I'll likely start with only replacing multiply, divide and exp/pow (I don't believe log() is being used explicitly anywhere in PW3 and I haven't used it in any work I've done expanding on it). If that proves to be consistent I may not replace add and subtract. I can say for certain that multiply and divide are subject to inconsistency. Right now, the focus is on revising divide and the root calculation portion of pow.
     
  10. bc1

    bc1

    Joined:
    Jan 12, 2004
    Messages:
    1,250
    :lol: you'd better make an immediate worldwide announcement to stop using PCs for math, weather modeling, CAD, protein folding, .... :lol:
     
  11. Pazyryk

    Pazyryk Deity

    Joined:
    Jun 13, 2008
    Messages:
    3,584
    Could you implement this by modifying the metatable for the Lua number type? From the metatable doc for 5.1:
    ...which seems to imply that you can do it with debug.setmetatable.

    This link indicates that debug.setmetatable sets the default metatable for an object type rather than the specific metatable for an object instance. It's not clear whether that is a bug or feature, but it implies that you can change the behavior of "+", "-", etc. for all variables of type number if you want.

    You might be stopped at any point here by sandboxing. I know that some specific object metatables have been modified so that getmetatable(object) gives you nil. Also, it's possible that debug.setmetatable was not added when they added the debug library (which you have to enable in config, but you probably know that already).

    One other thing to watch out for is that the Lua implementation seems to have a whole different set of metatables for each state for some object classes but not others. For example, getmetatable(player) will always give you the same table regardless of state, but getmetatable(city) will give you a different table from each state. (I learned this when I was adding stuff like unit:MyFunction on the Lua side.) I don't know which situation would apply to the default metatable for object types. But, assuming getmetatable(iNumber) gives you the metatable for type number, be sure to check that it is the same metatable if called from different Lua states.


    I actually do something along these lines. But we don't need or expect deterministic behavior. In fact, we inject a lot of random numbers into the process on purpose, and then look for robustness in the face of those random inputs. If the result is dependent on some 8th digit somewhere, then it isn't a weather forecast or protein folding prediction that you want to count on.
     
  12. whoward69

    whoward69 DLL Minion

    Joined:
    May 30, 2011
    Messages:
    8,407
    Location:
    Near Portsmouth, UK
    Could all the worldwide apps for weather modelling, CAD, protein folding ... using the standard C/C++ math library (at least in a way that pays zero attention to multi-threading, mode-switching issues around the 8087) please identify themselves ....

    No one? Nope, thought as much.
     
  13. Pazyryk

    Pazyryk Deity

    Joined:
    Jun 13, 2008
    Messages:
    3,584
    Um... most of the scientists I know who do this sort of thing couldn't even answer your question. Only a subset can even read the code. I can't speak for the grad students that write the code. I'm sure they are at least as competent as the interns that wrote SocailPolicyPopup.lua.


    Edit: Bah!... why do I let myself get drawn in to these discussions? Metatables! Check the metatables! Maybe that will work for you...
     
  14. bc1

    bc1

    Joined:
    Jan 12, 2004
    Messages:
    1,250
    That's just the point: it's not an FPU bug (the more recent apps likely use the more modern efficient FPU modes than the 8087), but rather an lua library bug
     
  15. bc1

    bc1

    Joined:
    Jan 12, 2004
    Messages:
    1,250
    I do hope your random number generation science is a bit more evolved than rely on random bugs :lol:
     
  16. Pazyryk

    Pazyryk Deity

    Joined:
    Jun 13, 2008
    Messages:
    3,584
    Darn, I thought that you could just redefine +, -, /, ^ etc for type number. Then you could just do that before map run and not have to modify the map script at all.

    But it doesn't work. You can make a table, string or userdata think it is a number to be acted on by your own "+ function". But you can't fool a number into using your own "+ function". Strangely, you can get a number to think it is a function:

    Code:
    > n = 69
    > getmetatable(n)
    > debug.setmetatable(n,{})
    true
    > getmetatable(n)
    table: 54BCF0A0
    
    --Can make a number callable like a function:
    > getmetatable(n).__call = function(self, str) print("hello " .. str .. ", I am number " .. self) end
    > n
    69
    > n("whoward")
    hello whoward, I am number 69
    
    --Unfortunately, can't redefine +, -, /, ^ etc for numbers (this can be done for other types)
    > getmetatable(n).__add = function(x, y) return x+y+10 end
    > 1+1
    2
    > n+n
    138

    Edit: I still think the idea of using "magic tables" (with a associated metatable defining +, -, /, etc.) would be easier, at least for the end user. Then you could do:
    Code:
    bob1 + bob2
    bob1 + 1
    1 + bob1
    All three of the above will use "+" as defined in the .__add field of the bob metatable (despite my failure above to get this to work for type number; it definitely works for tables).

    That's a lot nicer than making the mapscript writer use:
    Code:
    addbob(bob1, bob2)
    addbob(bob1, 1)
    addbob(1, bob2)
    You still have to get the mapscript writer to define all number variables as bobs though. That's easy enough for them:
    Code:
    local n = GetBob(69)
    The user doesn't need to know that n is really a table. It behaves like a number in all ways that matter but using functions you provide in its metatable. For example, you could even make:
    Code:
    local x = n + 1
    automatically create x as a bob.
     
  17. Bobert13

    Bobert13 Prince

    Joined:
    Feb 25, 2013
    Messages:
    345
    You're definitely on to something. Shoot me a PM detailing the steps to get "bob + FP" working if you don't mind.

    I've posted Revision 2 of the code in the OP. powbob() has been updated with a very slow method of approximating nth root (BUT, only where n is an integer number). I'm even rounding to force the root to an integer at the moment. It seems that calling powbob() recursively for non-integer roots could become problematic. Plus, squareroot currently takes about 80 times longer to compute than multiply. I've included a semi-working version of Halley's Approximation of nth root, and a completely broken version of Newton's Approximation of nth root.

    I also fixed some issues with subtraction and compare, and ran into a whole new slew of issues from my new wrapper function for math.modf that tests for 0.999... instead of 1.
     
  18. Pazyryk

    Pazyryk Deity

    Joined:
    Jun 13, 2008
    Messages:
    3,584
    Code below. All arithmetic and and comparison operations (+, -, <, etc.) get funneled through bobMeta methods. You would have to modify these methods to get the behavior you want (the way I have it now, bobs will act like FPs).

    It's untested. But here is a phony Fire Tuner session:

    > bob1 = GetBob(69)
    > print (bob1)
    69
    > print(type(bob1))
    table
    > bob2 = bob1 + 7
    > print(bob2)
    76
    > print(type(bob2))
    table
    > bob2[5] = 1
    Error! Don't try to use a bob as a table!

    Spoiler :
    Code:
    -- bob's are magic tables that think they are numbers. The actual
    -- number is held in bob[1], but you should never access this directly.
    
    -- Note: Bobs should work fine when passed as args to any Lua functions,
    -- since they contain their own instructions for handling arithmetic. But
    -- you will need to use ConvertToNumber before passing to C++ or using
    -- as an index (but these aren't things you should do with bobs anyway).
    
    local bobMeta = {}
    
    function GetBob(number)
    	local bob = {number}		--keep value in index [1] of bob
    	setmetatable(bob, bobMeta)
    	return bob
    end
    
    function ConvertToNumber(bobOrNumber)
    	if type(bobOrNumber) == "table" then
    		return bobOrNumber[1]
    	else
    		return bobOrNumber
    	end 
    end
    -------------------------------------------------------
    -- Bob metamethods
    -------------------------------------------------------
    local GetBob = GetBob
    local ConvertToNumber = ConvertToNumber
    
    bobMeta.__tostring = function(x)	--this shoud be invoked by print(bob)
    	return tostring(x[1])
    end
    
    bobMeta.__index = function()
    	error("Don't try to use a bob as a table!")
    end
    
    bobMeta.__newindex = function()
    	error("Don't try to use a bob as a table!")
    end
    
    -- Arithemetic: +, -, *, /, %, ^
    
    bobMeta.__add = function(x, y)
    	return GetBob(ConvertToNumber(x) + ConvertToNumber(y))
    end
    
    bobMeta.__sub = function(x, y)
    	return GetBob(ConvertToNumber(x) - ConvertToNumber(y))
    end
    
    bobMeta.__mul = function(x, y)
    	return GetBob(ConvertToNumber(x) * ConvertToNumber(y))
    end
    
    bobMeta.__div = function(x, y)
    	return GetBob(ConvertToNumber(x) / ConvertToNumber(y))
    end
    
    bobMeta.__mod = function(x, y)
    	return GetBob(ConvertToNumber(x) % ConvertToNumber(y))
    end
    
    bobMeta.__pow = function(x, y)
    	return GetBob(ConvertToNumber(x) ^ ConvertToNumber(y))
    end
    
    bobMeta.__unm = function(x)
    	return GetBob(-x[1])		--must be a bob if it called this function
    end
    
    -- Comparison: ==, <, <= (you don't need inverse of these; lua will convert as needed)
    
    bobMeta.__eq = function(x, y)
    	return GetBob(ConvertToNumber(x) == ConvertToNumber(y))
    end
    
    bobMeta.__lt = function(x, y)
    	return GetBob(ConvertToNumber(x) < ConvertToNumber(y))
    end
    
    bobMeta.__le = function(x, y)
    	return GetBob(ConvertToNumber(x) <= ConvertToNumber(y))
    end
     

Share This Page