library BigInt uses ErrorMessage
private function Print takes string msg returns nothing
call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60000,msg)
endfunction
private module Init
static if thistype.init.exists then
private static method onInit takes nothing returns nothing
call init()
endmethod
endif
endmodule
private struct Number extends array
private static constant integer SIZE = 1638
private static integer array recycler
integer digit
integer lastDigit
integer base
static method allocate takes integer base returns thistype
local thistype this = recycler[0]
debug call ThrowError(this == 0, "Alloc", "allocate", "thistype", 0, "Overflow.")
set recycler[0] = recycler[this]
debug set recycler[this] = -1
set lastDigit = this
set this.base = base
return this
endmethod
method setTo takes Number number returns nothing
local thistype digit = this
local thistype num = number
local integer last = number.lastDigit
loop
set digit.digit = number.digit
set number = number + 1
set digit = digit + 1
exitwhen integer(number) > last
endloop
set last = lastDigit
loop
exitwhen integer(digit) > last
set digit.digit = 0
set digit = digit + 1
endloop
set lastDigit = this + (num.lastDigit - num)
set base = num.base
endmethod
method clear takes nothing returns nothing
local thistype digit = this
loop
set digit.digit = 0
set digit = digit + 1
exitwhen integer(digit) > lastDigit
endloop
set lastDigit = this
endmethod
method clearRange takes Number start returns nothing
local integer end = lastDigit
if (integer(start) == integer(this)) then
set lastDigit = this
else
set lastDigit = start - 1
endif
loop
set start.digit = 0
set start = start + 1
exitwhen integer(start) > end
endloop
endmethod
method deallocate takes nothing returns nothing
debug call ThrowError(recycler[this] != -1, "Alloc", "deallocate", "thistype", this, "Attempted To Deallocate Null Instance.")
call clear()
set recycler[this] = recycler[0]
set recycler[0] = this
endmethod
private static method init takes nothing returns nothing
local integer i = 1
loop
exitwhen i + SIZE > 8191
set recycler[i] = i + SIZE
set i = i + SIZE
endloop
set recycler[0] = 1
endmethod
implement Init
endstruct
private function ToInt takes Number number returns integer
local integer base = number.base
local integer end = number
local integer value = 0
set number = number.lastDigit
loop
set value = value*base + number.digit
set number = number - 1
exitwhen integer(number) < end
endloop
return value
endfunction
private function ToString takes Number number returns string
local integer last = number.lastDigit
local string out = ""
local string comma = ""
//if (number.base != 10) then
set comma = ", "
//endif
loop
if (out == "") then
set out = I2S(number.digit)
else
set out = I2S(number.digit) + comma + out
endif
set number = number + 1
exitwhen integer(number) > last
endloop
return out
endfunction
private struct Normalize extends array
static method forward takes Number number, Number first, Number last returns nothing
local integer base = number.base
loop
set Number(first + 1).digit = Number(first + 1).digit + first.digit/base
set first.digit = first.digit - first.digit/base*base
set first = first + 1
exitwhen integer(first) > integer(last)
endloop
loop
exitwhen first.digit < base
set Number(first + 1).digit = Number(first + 1).digit + first.digit/base
set first.digit = first.digit - first.digit/base*base
set first = first + 1
endloop
loop
exitwhen first.digit != 0 or integer(first) == integer(number)
set first = first - 1
endloop
set number.lastDigit = first
endmethod
static method backward takes Number number, Number first, Number last returns nothing
local integer base = number.base
loop
if (first.digit < 0) then
set Number(first + 1).digit = Number(first + 1).digit - (first.digit/base + 1)
set first.digit = first.digit + (first.digit/base + 1)*base
endif
set first = first + 1
exitwhen integer(first) > integer(last)
endloop
loop
exitwhen first.digit != 0 or integer(first) == integer(number)
set first = first - 1
endloop
set number.lastDigit = first
endmethod
endstruct
private struct Add extends array
static method add takes Number number, integer i returns nothing
local Number current = number
local integer base = number.base
local integer digit
if (i == 0) then
return
endif
loop
exitwhen i == 0
set digit = current.digit + (i - i/base*base)
set i = i/base
set current.digit = digit - digit/base*base
set current = current + 1
set current.digit = current.digit + digit/base
endloop
loop
exitwhen current.digit < base
set digit = current.digit
set current.digit = digit - digit/base*base
set current = current + 1
set current.digit = current.digit + digit/base
endloop
if (current.digit == 0) then
set current = current - 1
endif
if (integer(current) > number.lastDigit) then
set number.lastDigit = current
endif
endmethod
endstruct
private struct Subtract extends array
static method subtract takes Number number, integer i returns nothing
local Number current = number
local integer base = number.base
if (i == 0) then
return
endif
loop
exitwhen i == 0
set current.digit = current.digit - (i - i/base*base)
set i = i/base
if (current.digit < 0) then
set Number(current + 1).digit = Number(current + 1).digit - (current.digit/base + 1)
set current.digit = current.digit + (current.digit/base + 1)*base
endif
set current = current + 1
endloop
loop
exitwhen current.digit != 0 or integer(current) == integer(number)
set current = current - 1
endloop
set number.lastDigit = current
endmethod
endstruct
private struct Multiply extends array
private static method multiplyInner takes Number number, integer i returns nothing
local Number target = Number.allocate(number.base)
local integer first = target
local Number currentTarget
local Number digit
local integer lastDigit = number.lastDigit
local integer base = number.base
local integer m
set target.lastDigit = target + (lastDigit - number)
loop
set m = i - i/base*base
set i = i/base
if (m != 0) then
set currentTarget = first
set digit = number
loop
set currentTarget.digit = currentTarget.digit + digit.digit*m
set Number(currentTarget + 1).digit = Number(currentTarget + 1).digit + currentTarget.digit/base
set currentTarget.digit = currentTarget.digit - currentTarget.digit/base*base
set digit = digit + 1
exitwhen integer(digit) > lastDigit
set currentTarget = currentTarget + 1
endloop
loop
set currentTarget = currentTarget + 1
exitwhen currentTarget.digit < base
set Number(currentTarget + 1).digit = Number(currentTarget + 1).digit + currentTarget.digit/base
set currentTarget.digit = currentTarget.digit - currentTarget.digit/base*base
endloop
if (currentTarget.digit == 0) then
set currentTarget = currentTarget - 1
endif
if (integer(currentTarget) > target.lastDigit) then
set target.lastDigit = currentTarget
endif
endif
exitwhen i == 0
set first = first + 1
if (first > target.lastDigit) then
set target.lastDigit = first
endif
endloop
call number.setTo(target)
call target.deallocate()
endmethod
static method multiply takes Number number, integer i returns nothing
if (number.digit != 0 and i != 1) then
if (i == 0) then
call number.clear()
else
call multiplyInner(number, i)
endif
endif
endmethod
endstruct
private struct Compare extends array
static method compare takes Number number, integer i returns integer
local integer d = 0
local integer base = number.base
loop
exitwhen i == 0
set d = d + (number.digit - (i - i/base*base))*base
set i = i/base
set number = number + 1
endloop
return d
endmethod
static method compareNumber takes Number numberLeft, Number numberRight returns integer
local integer sizeLeft = numberLeft.lastDigit - numberLeft
local integer compare = sizeLeft - (numberRight.lastDigit - numberRight)
if (compare == 0) then
loop
set compare = numberLeft.digit - numberRight.digit
set numberLeft = numberLeft + 1
exitwhen integer(numberLeft) > sizeLeft or compare != 0
set numberRight = numberRight + 1
endloop
endif
return compare
endmethod
endstruct
private struct Divide extends array
private static method calculateDigit takes Number dividend, integer divisorBig, integer base returns integer
if (Number(dividend.lastDigit).digit < divisorBig) then
return (Number(dividend.lastDigit).digit*base + Number(dividend.lastDigit - 1).digit)/divisorBig
endif
return Number(dividend.lastDigit).digit/divisorBig
endmethod
private static method getDivisorBig takes integer divisor, integer base returns integer
loop
exitwhen divisor < base
set divisor = divisor/base
endloop
return divisor
endmethod
private static method compare takes Number numberLeft, Number numberRight returns integer
local integer start = numberRight
local integer compare
set numberLeft = numberLeft.lastDigit
set numberRight = numberRight.lastDigit
loop
set compare = numberLeft.digit - numberRight.digit
set numberRight = numberRight - 1
exitwhen integer(numberRight) < start or compare != 0
set numberLeft = numberLeft - 1
endloop
return compare
endmethod
private static method subtract takes Number top, Number bottom, integer base, Number difference returns nothing
local integer end
local Number start
local integer beginning = difference
/*
* Calculate what region to subtract in the number with more digits
*
* If the top number is the one with more digits, it will subtract 0's
*
* If it is the bottom number, then negate the trailing digits
* The bottom number is pretty much subtracting itself from 0's that should
* be in the top number, but aren't to make the algorithm faster
*/
if (integer(top) == integer(difference)) then
set end = top.lastDigit
set start = end - (bottom.lastDigit - bottom)
set top = start
else
set end = bottom.lastDigit
set start = end - (top.lastDigit - top)
loop
exitwhen integer(difference) == integer(start)
set difference.digit = -difference.digit
set difference = difference + 1
endloop
set bottom = start
endif
/*
* Subtract the first x numbers where x is the number of digits
* in the smaller length number
*
* Difference is always the biggest length number
*/
set difference = start
loop
set difference.digit = top.digit - bottom.digit
set difference = difference + 1
exitwhen integer(difference) > end
set top = top + 1
set bottom = bottom + 1
endloop
/*
* Normalize the number (handle carries)
*/
call Normalize.backward(beginning, beginning, Number(beginning).lastDigit)
endmethod
private static method divideInner takes Number number, integer divisor returns integer
/*
* Locals
*/
local Number dividend //number to be divided
local Number subtractor //number to subtract from dividend
local integer digit //specific digit in quotient, can be negative
local integer array digits //collection of all digits in quotient
local integer digitCount //number of digits in quotient, including remainder
local integer base //base of the number
local integer divisorBig //largest digit in divisor
local integer multiplier //current multiplier for digits
local integer remainder
local integer start
/*
* Initialization
*/
set base = number.base
set dividend = Number.allocate(base)
set subtractor = Number.allocate(base)
set divisorBig = getDivisorBig(divisor, base)
set multiplier = 1
set digitCount = 0
call dividend.setTo(number)
/*
* Loop
*/
loop
/*
* Get next biggest digit in quotient
*/
set digit = calculateDigit(dividend, divisorBig, base)
set digits[digitCount] = digit*multiplier
set digitCount = digitCount + 1
/*
* Get subtractor
*/
call Add.add(subtractor, digit)
call Multiply.multiply(subtractor, divisor)
/*
* Do forward subtraction
* (subtract first x digits, where x is length of subtractor)
*/
if (compare(dividend, subtractor) < 0) then
set multiplier = -1
call subtract(subtractor, dividend, base, dividend)
else
call subtract(dividend, subtractor, base, dividend)
endif
exitwhen Compare.compare(dividend, divisor) < 0
call subtractor.clear()
endloop
/*
* Get remainder
*/
set remainder = ToInt(dividend)*multiplier
/*
* Calculate remainder
*/
if (remainder < 0) then
if (digitCount != 0) then
set digits[digitCount - 1] = digits[digitCount - 1] - 1
endif
set remainder = divisor + remainder
endif
/*
* Calculate quotient
*/
call number.clearRange(number + digitCount)
set start = number
loop
exitwhen digitCount == 0
set digitCount = digitCount - 1
set number.digit = digits[digitCount]
set number = number + 1
endloop
set number = start
call Normalize.backward(number, number, number.lastDigit)
/*
* Clean
*/
call subtractor.deallocate()
call dividend.deallocate()
return remainder
endmethod
static method divide takes Number number, integer i returns integer
if (number.digit != 0 and i != 1 and i != 0) then
if (Compare.compare(number, i) < 0) then
set i = ToInt(number)
call number.clear()
return i
else
return divideInner(number, i)
endif
endif
return 0
endmethod
endstruct
private struct Mod extends array
endstruct
private struct Base extends array
endstruct
struct BigInt extends array
endstruct
private struct Tester extends array
private static method onInit takes nothing returns nothing
local Number number = Number.allocate(10)
local Number number2 = Number.allocate(10)
local integer n = 0
local integer remainder
local integer remainderBig
call Print(ToString(number) + " == " + I2S(n))
call Add.add(number, 34)
set n = n + 34
call Print(ToString(number) + " == " + I2S(n))
call Add.add(number, 92)
set n = n + 92
call Print(ToString(number) + " == " + I2S(n))
call Subtract.subtract(number, 45)
set n = n - 45
call Print(ToString(number) + " == " + I2S(n))
call Multiply.multiply(number, 15)
set n = n*15
call Print(ToString(number) + " == " + I2S(n))
call Multiply.multiply(number, 15)
set n = n*15
call Print(ToString(number) + " == " + I2S(n))
set remainderBig = Divide.divide(number, 31)
set remainder = n - n/31*31
set n = n/31
call Print(ToString(number) + "r" + I2S(remainderBig) + " == " + I2S(n) + "r" + I2S(remainder))
endmethod
endstruct
endlibrary
