Script to Handle Very Large Numbers

Share your scripts and packages with other Mudlet users.
Post Reply
Jor'Mox
Posts: 1142
Joined: Wed Apr 03, 2013 2:19 am

Script to Handle Very Large Numbers

Post by Jor'Mox »

Like most programming languages, Lua loses mathematical precision after a certain point, which can be problematic for certain applications, one of which I was reminded of today when looking at something else. SO, I wrote a script to attempt to handle "very large numbers" accurately. Basically, it makes a class for these numbers and attempts to implement all of the mathematical operators (+, -, *, /, %, ^) and comparative operators (<, >, <=, >=, ==, ~=). Right now, there are some fairly significant limitations to this script, namely that it only handles integers, and you can only use non-negative integer powers when using the ^ operator. I'm slowly figuring out a method for effectively including decimals, though to avoid blowing up computers I'll naturally have to limit precision when dividing (since 1/3 produces an infinitely long number, and we just don't have room for that), though I think I'll be able to make the precision something you can select if you care to. Also, I would LIKE to be able to exponents that aren't strictly non-negative integers, but I'm how to implement that at this point (I would LOVE to hear ideas for algorithms to calculate them).

Anyway, here is what I have so far:
Code: [show] | [select all] lua
vln = vln or {}
local meta

local copy = function(num)
    local tbl = {}
    for k,v in pairs(num) do
        tbl[k] = v
    end
    setmetatable(tbl,meta)
    return tbl
end

local fix_zeroes = function(num)
    for k = #num,1,-1 do
        if num[k] == 0 then
            num[k] = nil
        else
            break
        end
    end
    num[1] = num[1] or 0
    return num
end

local check = function(num)
    if type(num) ~= "table" then
        num = vln.new(num)
    else
        return copy(num)
    end
    if num.type ~= "vln"then
        error("vln: can only be added to a number, a number as string, or another vln",3)
    end
    return num
end

meta = {
    __newindex = function() error("vln: manual modification not permitted for this object",2) end,
    __tostring = function(self)
            local str = ""
            for k,v in ipairs(self) do
                str = v .. str
            end
            if self.is_negative then
                str = "-"..str
            end
            return str
        end,
    __unm = function(self)
            self.is_negative = not self.is_negative
            return self
        end,
    __add = function(a,b)
            a = check(a)
            b = check(b)
            if a.is_negative == b.is_negative then
                local result, sum, carry, maxn = {type = "vln"}, 0, 0, math.max(#a,#b)
                for k = 1,maxn do
                    sum = (a[k] or 0) + (b[k] or 0) + carry
                    carry = math.modf(sum/10)
                    table.insert(result,sum%10)
                end
                result.is_negative = a.is_negative
                result = fix_zeroes(result)
                setmetatable(result,meta)
                return result
            else
                if a.is_negative then
                    a.is_negative = false
                    return b - a
                else
                    b.is_negative = false
                    return a - b
                end
            end
        end,
    __sub = function(a,b)
            a = check(a)
            b = check(b)
            if a.is_negative == b.is_negative then
                local result, sum, carry, maxn, switch = {type = "vln"}, 0, 0, math.max(#a,#b), false
                if b > a then
                    local tmp = a
                    a = b
                    b = tmp
                    switch = true
                end
                for k = 1,maxn do
                    sum = (a[k] or 0) - (b[k] or 0) + carry
                    if sum < 0 then
                        carry = -1
                        sum = 10 + sum
                    else
                        carry = 0
                    end
                    table.insert(result,sum)
                end
                result.is_negative = a.is_negative
                if switch then
                    result.is_negative = not result.is_negative
                end
                result = fix_zeroes(result)
                setmetatable(result,meta)
                return result
            else
                b.negative = a.negative
                return a + b
            end
        end,
    __mul = function(a,b)
            a = check(a)
            b = check(b)
            local result = vln.new(0)
            for k1 = 1,#b do
                local sum, carry = {type = "vln",is_negative = false}, 0
                for k2 = 1,#a do
                    local mult = a[k2] * b[k1] + carry
                    table.insert(sum,mult%10)
                    carry = math.modf(mult/10)
                end
                if carry ~= 0 then
                    table.insert(sum,carry)
                end
                for k2 = 1,k1-1 do
                    table.insert(sum,1,0)
                end
                sum = fix_zeroes(sum)
                setmetatable(sum,meta)
                result = result + sum
            end
            result.is_negative = a.is_negative ~= b.is_negative
            return result
        end,
    __div = function(a,b)
            a = check(a)
            b = check(b)
            local result = {type = "vln"}
            local tmp = vln.new(0)
            for k = #a,1,-1 do
                tmp = tmp + a[k]
                if b <= tmp then
                    local mult = 1
                    for k = 1,9 do
                        if b * k > tmp then
                            break
                        end
                        mult = k
                    end
                    table.insert(result,1,mult)
                    tmp = tmp - (b * mult)
                else
                    table.insert(result,1,0)
                end
                tmp = tmp * 10
            end
            if a.is_negative == b.is_negative then
                result.is_negative = false
            else
                result.is_negative = true
            end
            result = fix_zeroes(result)
            setmetatable(result,meta)
            return result
        end,
    __mod = function(a,b)
            a = check(a)
            b = check(b)
            local div = a/b
            return a - div*b
        end,
    __pow = function(a,b)
            a = check(a)
            if type(b) ~= "number" or b < 0 or b ~= math.floor(b) then
                error("vln: power must be a positive integer",2)
            end
            if b == 0 then
                return vln.new(1)
            else
                local result = vln.new(1)
                for k = 1,b do
                    result = result * a
                end
                return result
            end
        end,
    __eq = function(a,b)
            if a.negative ~= b.negative then
                return false
            elseif #a ~= #b then
                return false
            else
                for k = 1,#a do
                    if a[k] ~= b[k] then
                        return false
                    end
                end
                return true
            end
        end,
    __lt = function(a,b)
            a = check(a)
            b = check(b)
            if a.is_negative ~= b.is_negative then
                return a.is_negative
            elseif #a ~= #b then
                return #a < #b
            else
                for k = #a,1,-1 do
                    if a[k] ~= b[k] then
                        return a[k] < b[k]
                    end
                end
                return false
            end
        end,
    __le = function(a,b)
            a = check(a)
            b = check(b)
            return a == b or a < b
        end,
    __index = function(self,key)
            if key == "value" then
                return tostring(self)
            end
        end,
}

vln.new = function (num)
    local n = {type = "vln"}
    num = num or 0
    local is_negative = false
    if type(num) == "number" then
        if num < 0 then
            is_negative = true
            num = math.abs(num)
        end
        num = math.floor(num)
        while num >= 1 do
            table.insert(n,num%10)
            num = math.floor(num / 10)
        end
    elseif type(num) == "string" then
        num = string.trim(num)
        for k = #num,1,-1 do
            local l = string.sub(num,k,k)
            if tonumber(l) then
                table.insert(n,tonumber(l))
            elseif l == "-" and k == 1 then
                is_negative = true
            else
                error("vln.new: string argument must only contain numbers or an inital minus sign",2)
            end
        end
    else
        error("vln.new: argument invalid type, must be string, number, or nil",2)
    end
    n = fix_zeroes(n)
    n.is_negative = is_negative
    setmetatable(n,meta)
    return n
end
Note, in case it isn't obvious, you can give the vln.new function either a number or a string that appropriately represents an integer number to create a vln object, but after that you just use normal math operators, and you can use it with either other vln objects, numbers, or appropriate strings. To see the value of the object, use the tostring function or check the value property of the object (i.e. obj.value).

Jor'Mox
Posts: 1142
Joined: Wed Apr 03, 2013 2:19 am

Re: Script to Handle Very Large Numbers

Post by Jor'Mox »

For my own sanity, I also made a little function that will insert commas where they should be in numbers stored as strings.
Code: [show] | [select all] lua
function add_commas(str)
    local extra = #str%3
    if string.sub(str,1,1) == "-" then
        if extra == 0 then
            extra = 3
        else
            extra = extra + 1
        end
    end
    local result = ""
    if extra > 0 then
        result = string.sub(str,1,extra)
        str = string.sub(str,extra+1)
    end
    for w in string.gmatch(str,"%d%d%d") do
        result = result .. "," .. w
    end
    return result
end

Post Reply