AptInt is the fastest luau implementation of BigInteger. It uses base 10^7 to store numbers and uses asymptotically faster algorithms designed for working with numbers over 10,000 digits long.
What makes it so fast?
AptInt uses the Karatsuba and Toom-Cook3 algorithms for multiplication, Knuths algorithm D for division, Karatsuba sqrt for finding the square root and more. Alongside these algorithms, it uses many techniques to shave off hundreds of milliseconds of computing time.
It also utilizes the full power of native code generation to get even faster results.
Construction
You can construct an AptInt in four ways:
AptInt.new() -- equal to AptInt.new({0})
AptInt.new("123")
AptInt.new(123)
AptInt.new({123}) -- this is the fastest way
It also has built in metamethods for convenience. It is recommended to use the raw functions every time, as these avoid the metamethod overhead.
Releases
Github (ONLY get it from the releases section, the current commit may have bugs)
Please keep in mind that there will most likely be bugs. They will be fixed once reported.
Here’s my feedback on using the library (just testing):
The results of multiplication starts to accumulate trailing zeros that shouldn’t be there when stress tested with huge integers (around 250 digits or more).
Your Knuth D division looks correct and does come with good performance and correctness, but there is still some edge cases that needs refinement, for example, this crashes out with a “size out of range” error:
-- 13:54:19.189 ReplicatedStorage.AptInt:513: invalid argument #1 to 'create' (size out of range) - Server - AptInt:513
local quotient: AptInt = AptInt.new(tcreate(m + 1, 0)) -- this line
Notes:
Toom-3 is a lot harder to implement correctly than expected and the runtime overhead in a VM would outweigh the benefit unless it’s well past Karatsuba’s practical range. You should be more wary with implementing it and good luck.
You should check for correctness first before pushing performance so you can ensure reliability for your arbitrary-precision library.
Overall your library is actually fast compared to other popular arbitrary-precision libraries (I benchmarked), good luck with making it!
The bugs you have encountered are strange and i havent been able to reproduce them. Could you provide some examples? Are you using the v1.0.1 release or the latest commit?
I think you did update the code before you saw my reply but that’s fine, no worries.
You did fix that division bug I stated earlier (I checked), so that’s good.
I’ve updated the library and I’ve still got this correction error in this script I used below.
local AptInt = require(game.ReplicatedStorage.AptInt)
local a = AptInt.new("44372184372189432789321489432714893217443127432189489321743213213443721843721894327893214894327148932174431274321894893217432132134437218437218943278932148943271489321744312743218948932174321321344372184372189432789321489432714893217443127432189489321743213213443721843721894327893214894327148932174431274321894893217432132134437218437218943278932148943271489321744312743218948932174321321344372184372189432789321489432714893217443127432189489321743213213443721843721894327893214894327148932174431274321894893217432132134437218437218943278932148943271489321744312743218948932174321321344372184372189432789321489432714893217443127432189489321743213213")
local b = AptInt.new("9999999943216743218943219432543254325437643271849632714321432421114321432112097873654365436543554363643599999999432167432189432194325432543254376432718496327143214324211143214321120978736543654365435543636435999999994321674321894321943254325432543764327184963271432143242111432143211209787365436543654355436364359999999943216743218943219432543254325437643271849632714321432421114321432112097873654365436543554363643599999999432167432189432194325432543254376432718496327143214324211143214321120978736543654365435543636435999999994321674321894321943254325432543764327184963271432143242111432143211209787365436543654355436364359999999943216743218943219432543254325437643271849632714321432421114321432112097873654365436543554363643599999999432167432189432194325432543254376432718496327143214324211143214321120978736543654365435543636435999999994321674321894321943254325432543764327184963271432143242111432143211209787365436543654355436364359999999943216743218943219432543254325437643271849632714321432421114321432112097873654365436543554363643599999999432167432189432194325432543254376432718496327143214324211143214321120978736543654365435543636435999999994321674321894321943254325432543764327184963271432143242111432143211209787365436543654355436364359999999943216743218943219432543254325437643271849632714321432421114321432112097873654365436543554363643599999999432167432189432194325432543254376432718496327143214324211143214321120978736543654365435543636435999999994321674321894321943254325432543764327184963271432143242111432143211209787365436543654355436364359999999943216743218943219432543254325437643271849632714321432421114321432112097873654365436543554363643599999999432167432189432194325432543254376432718496327143214324211143214321120978736543654365435543636435")
local m = a * b
print(m)
-- result got 2854337209852400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000045987064679243198093391073707853590159572714911030166371365855286063488246792431980933910737078535901595727149110301663713658552860634882467924319809339107370785359015957271491103016637136585528606348824679243198093391709180923407531029340000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000026453509264695445707519445561890386414518446052276489391458438681749694832546599044189062701042092595901120622004276580015260625115684580121139744097397576208780677742117792475441762246023744933611077688528956802588790878949074787859897248051181712847474705607406844618252311873221666944301520070222636337150392267785821249015545634298177227930026247292648801830730737481531490098633774706696845418873352206866648224319598760236722146696471442078315842844587744809721167774018521683696364244959681105804386914660112788581729190675027035746100367720613715149037335087456782907127595304813239486174568831047141193395495098036631868300345982651335104556968895588740093550765541071560215655
This has been fixed! the issue ended up being here:
if len < SAFE_UNPACK_THRESHOLD then
-- select(n + 1, unpack(limbs)) is wayy faster than {unpack(limbs, n+1, #limbs)}
--> for some reason we gotta set it to a variable first or else it breaks...
local z: {number} = {select(n + 1, unpack(limbs))}
return AptInt.new(z)
end
if you didn’t declare the variable z, it would return a table with only one index.
Implement the Toom-Cook 3 algorithm for multiplication, speeding up multiplication by 200%.
Implement the Karatsuba square root algorithm, speeding up :sqrt() by 300%.
Better initial guess for NewtonHeronSqrt
Greatly speed up :LeftShift()
Add :ModPow() extension
Future plans
Adding in-place arguments to all arithmetic functions
Reducing overhead for most algorithms
GCD, LCM functions
Here is one week of me bashing my head trying to figure out what’s wrong, summarized in these couple of lines :(. I can say that it was worth it though.
There might still be some bugs left, so please report them either in the repository or in here. there’s only so much one person can do
Are you always using the same algorithms? It could make sense to have a hybrid approach of dumber but less intensive algorithms for smaller inputs, like what sort function in C does: it chooses between qsort, insertionsort and heapsort depending on the array size.
You can benchmark it against any other biginteger library made in luau and see the results for yourself. Im confident it’ll win against every single one
local aptint = require(game.ReplicatedStorage.AptInt)
local two = aptint.new("2")
local indices = {}
for i = 1, 20 do
indices[i] = aptint.new(i)
end
local function ends(value, n)
local s = tostring(value)
local len = #s
if len <= n * 2 then
return s, ""
end
local first = string.sub(s, 1, n)
local last = string.sub(s, len - n + 1, len)
return first, last
end
for i = 1, 20 do
print("x =", i)
local start = os.clock()
local exponent = two ^ indices[i] -- 2^i
local value = two ^ exponent -- 2^(2^i)
local elapsed = os.clock() - start
local first20, last20 = ends(value, 20)
print(" 2^(2^x):")
print(" first 20 =", first20)
print(" last 20 =", last20)
print(string.format(" took %.6f seconds", elapsed))
if elapsed > 3 then
print(" computation too large, stopping early")
break
end
task.wait(0.1)
end
Gotta admit it’s actually really fast, but the first 20 digits are wrong.
Do fix your pow, hopefully.
@BlueFish_12345 While the current v1.2.0 release doesn’t have this issue (its just the current github commit that’s broken), i have pinpointed the issue to be from an in-place mutation inside the toom-3 function.
Thanks for reporting the issue as I would’ve not spotted it myself. Release v1.3.0 will have it fixed.
edit: bug ended up being at this line: local vinf: AptInt = x2:MultiplyRaw(y2, true). just remove the true and it gets fixed.
That wasn’t the bug that caused, and yeah I usually take the source code from the github file, I’ve checked your file in the v1.2.0 release and it does work.
But damn it can compute 2^2^20 in 4.11 seconds with my CPU, you definitely take the top 1 spot in performance I gotta admit.
