Skip to content

BigNum

A BigNum with Fractions implementation for big-integer calculations, optimized for DataStore storage and networking.

local BigNum = Resources:LoadLibrary("BigNum")
print(BigNum.new("1025123") ^ BigNum.new("9"))
--> 1250212389547080859766804627957328989496357747253559363

The BigNum library utilizes Lua's doubles to hold place values, called "radix" (similar to digits but in a different base). Each double represents a single "radix" of the BigNum. By default, the BigNum library instantiates BigNums with 32 radix (256 bytes) to do calculations. This is big enough for numbers as large as 7.76e230 (see BigNum:GetRange()). If you need integers higher than that, simply pass in how many doubles it should allocate.

-- Explicitly allocate 128 doubles (1024 bytes) for each BigNum
print(BigNum.new("8", 128) ^ BigNum.new("900", 128))

Otherwise, you can externally set the default number of allocated radix:

BigNum:SetDefaultRadix(64)

The library also ships with a data type called BigNumFractions, which can be used for exact calculations with Fractions.

Library API

BigNum.new

BigNum BigNum.new(string Base10Number [, integer Radix])

Returns a new BigNum with the allocated number of Radix (defaults to 32)

BigNum.fromString64

BigNum BigNum.fromString64(string Base64String)

Meant to instantiate BigNums from strings returned via the toString64 method.

BigNum.newFraction

BigNumFraction BigNum.newFraction(BigNum Numerator, BigNum Denominator)

Instantiates a new Fraction in the form (Numerator / Denominator)

BigNum:GetRange

string BigNum:GetRange(integer Radix)

Returns a string representation of approximately how large of integers can be represented with a given number of Radix

print(BigNum:GetRange(128))
--> +/- 2.90e924

BigNum:SetDefaultRadix

void BigNum:SetDefaultRadix(integer DefaultRadix)

Sets the default number of Radix allocated for each number (default is 32)

BigNum API

These are the methods which operate on BigNums themselves.

BigNum:toString64

string BigNum:toString64()

Returns a string-base64 encoding of the BigNum, which can be reproduced using BigNum.fromString64

BigNum:toConstantForm

void BigNum:toConstantForm(integer NumberOfDoublesPerLine = 16)

Creates a file (or on Roblox, a script in the Lighting) with a constant representation of the BigNum. This is useful for directly instantiating BigNums with Big values which would take a lot of processing at run-time to convert from a base10 string to the internal representation.

Looks like this:

local CONSTANT_NUMBER = BigNum.new{
    0, 0, 154059, 3375645, 903522, 1038360, 13086355, 12524895, 10900259, 11967773, 5580376, 3468437, 579970, 6766011, 8397479, 8219103,
    8206478, 4226184, 11579046, 8128945, 3969135, 407937, 10824426, 1462231, 7523964, 16399268, 11691710, 13651477, 10604193, 2791442, 9280589, 5604105
}

BigNum:stringify

string BigNum:stringify()

Returns a representation of the internal format of how BigNums are stored in their array.

BigNumFraction API

BigNumFraction:Reduce

BigNumFraction BigNumFraction:Reduce()

Reduces the Fraction and returns it.

BigNumFraction:toScientificNotation

string BigNumFraction:toScientificNotation(integer NumDigitsAfterDecimalPoint = 2)

Returns a string representation of the Fraction in scientific notation with the given number of digits after the decimal. If there aren't enough digits to format it will just return the unformatted string.

Demo

Here the library is used to calculate the Birthday problem.

local BigNum = Resources:LoadLibrary("BigNum")
local _1 = BigNum.newFraction("1", "1")
local DaysInYear = BigNum.new("365")

local function BirthdayProblem(NumPeople)
    local Chance = BigNum.newFraction(DaysInYear, DaysInYear)

    for i = 2, NumPeople do
        Chance = Chance * BigNum.newFraction(DaysInYear + (1 - i), DaysInYear)
    end

    return _1 - Chance
end

print(BirthdayProblem(70):toScientificNotation(6))
--> 2.291582e179 / 2.293509e179

Writing Optimal Code with BigNum

Sometimes, you will need to perform a massive calculation which might take up too much time to calculate on Roblox without having the thread scheduler cut you off.

What follows is a list of what this library is optimized for and what this library is slow at.

Optimized for:

  • Any code given to you via the toConstantForm method

  • Encoding/Decoding for DataStores/Replication using toString64 and fromString64

Runs slowly:

  • Printing massive numbers (in Base 10) a lot (Never use GetRange at run-time!)

  • Creating BigNums from a Base10String at run-time (toConstantForm is recommended)

  • Using more Radix than the library can be performant with. In my tests, 32 radix approaches native speeds, with going too far above 128 leading to unstability in intensive calculations

Probably asked Questions

What if I want to know what's after the decimal point?

Use Fractions!

How does this library work?

It uses a modified version of two's-complement numbers (but in base 2^24).

Why are calculations done in base 2^24?

Because the highest integer representable by a double is 2^53. 2^24 is the nicest high number which won't result in the internal calculations reaching higher than 2^53. Multiplying two numbers with the highest radix and the highest previous value can result in: (2^24 - 1)(2^24 - 1) + (2^24 - 1)

Are you insane?

I haven't been formally diagnosed, so who's to say?