Author Topic: [Library] BigInteger - Too big numbers to handle yourself  (Read 2066 times)

Few requested for it, but no one wanted it that badly to even bother doing it. However, I came to the conclusion that if something is possible through JavaScript, it should be possible to do it trough TorqueScript, to some extent.

Therefore I searched and found a library that would do perfectly to be ported to TorqueScript. After a coupe of days I managed to finally make BigInt, the library that can handle any size of number thrown at it, and will calculate it within reasonable time.

GitHub

Performance tests
All iterates 16,384 times each

Add with strings
500 + 150:       32ms  avg: 0.00195313ms
1500 + 2500:     64ms  avg: 0.00390625ms
100 digits:  28,416ms  avg: 1.73438ms
Add without strings
500 + 150:      896ms  avg: 0.0546875ms
1500 + 2500:  1,088ms  avg: 0.0664063ms
100 digits:   8,256ms  avg: 0.503906ms

Subtract with strings
500 - 150:       32ms  avg: 0.00195313ms
1500 - 2500:     64ms  avg: 0.00390625ms
100 digits:  44,960ms  avg: 2.74414ms
Subtract without strings
500 - 150:    1,024ms  avg: 0.0625ms
1500 - 2500:  1,280ms  avg: 0.078125ms
100 digits:   8,416ms  avg: 0.513672ms

Multiply with strings (last does 2,048)
500 * 150:       32ms  avg: 0.00195313ms
1500 * 2500:    288ms  avg: 0.0175781ms
100 digits:  68,704ms  avg: 33.5469ms
Multiply without strings (last does 2,048)
500 * 150:    1,760ms  avg: 0.107422ms
1500 * 2500:  3,296ms  avg: 0.201172ms
100 digits:  61,280ms  avg: 29.9219ms

Div with strings (last does 2,048)
500 / 150:       64ms  avg: 0.00390625ms
1500 / 2500:     64ms  avg: 0.00390625ms
100 digits:  12,480ms  avg: 6.09375ms
Div without strings (last does 2,048)
500 / 150:   44,416ms  avg: 2.71094ms
1500 / 2500: 34,112ms  avg: 2.08203ms
100 digits: 18,848ms avg: 9.20313ms


Compare it to an another library.

Current issues
Smaller calculation on objects is currently not done. This was a hard nut to crack, as checks needs to be done in such a way that it might hurt the performance. I've added the smaller variants of each operator, just need to stitch everything together.
« Last Edit: January 19, 2018, 04:01:32 PM by mctwist »

This is pretty great, but yeah it needs massive optimizations (which I can help with if you want!)

That benchmark of my library was all the way back in 2013, and since then it's been massively improved (both by me and Klarck). Just for convenience, going by those benchmarks multiplying two ~150 digit numbers takes 7.7ms for my library and 4.7ms for Klarck's
« Last Edit: January 19, 2018, 02:33:15 PM by Ipquarx »

I would love to get some help on this, unless you want to integrate mine into yours.

A quick introduction would make it easier for you to get up to speed:
I'm using objects heavily. Tried to strip it down to not using it, but it actually hurt performance instead of helping it. Not sure why that happened.
The library is currently working with 3 digits for each part, almost 10bits. This is currently only for laziness, but it sure should be easy to make it support up to 5 digits. I would like to make it bit-compatible, like you did, but due to how the library this was derived from was built, I think it would be hard to do such a thing without damaging the performance even further. It's not impossible, just hard. Would love to have this go up to 16bit.

There is a multiplication algorithm I added, but never tested. It's used when a certain criteria is met. Like if both numbers exceeds 1600 positions, which is extremely rare. I have no idea how fast it is, but apparently it is used only when big numbers are introduced. The sad part with that is that it heavily relies on objects.


Other than that, the divMod functionality I guess that you want to use for your own purpose. If you want, then go ahead, take it. It currently uses some objects already, but only to a certain extent.

calling functions in ts incurs pretty heavy penalty, so if you want to up performance dont subdivide functions. also use only local or global vars for fastest performance

Objects also store all variables inside them as strings (even if it's obviously an integer or a float), so avoid storing the actual number information in them and delegate it to global variables.

Once all those things are done, then you should have yourself a much much faster library (I can probably send some pull requests your way for this)

Yeah stuff like .length() is making this slower

calling functions in ts incurs pretty heavy penalty, so if you want to up performance dont subdivide functions.
Yeah stuff like .length() is making this slower

This is true. I didn't divide it up for the sake of not destroying the algorithm too much. Wanted to keep the similarities intact. However, now it is time to merge everything together to normalize the function into bigger solid ones.

also use only local or global vars for fastest performance

I thought this would make a great impact on the performance, but when I removed the use of object and went global all the way, it in fact went slower. Could be due to the concatenation of array strings.

Objects also store all variables inside them as strings (even if it's obviously an integer or a float), so avoid storing the actual number information in them and delegate it to global variables.

I didn't know this, but I know one thing from what I found out while developing this: I could use the numbers fine without any penalty on result or performance. It actually, as mentioned previously, went slower when I tried to optimized it through global variables. However, I did not try any numbers that reaches anything higher than 6 digits in size.

Once all those things are done, then you should have yourself a much much faster library (I can probably send some pull requests your way for this)

I would be happy if you could provide some pushes. As long as the general algorithm is like it is now, unless a better one is found, then this is the fastest library when it were written in JavaScript. Keep in mind that as this is TorqueScript, several more changes needs to be made in order to optimize this further. I am all ears for improvement suggestions, but please keep in mind that test results through the included test suit needs to be provided to make sure that the speed is indeed faster. I'll update it later on to make it easier to see changes from previous runs.



On an another note, I added a quick way for the functional version to determine the size of the number and do a calculation directly on it instead of converting it to an array. The speeds have been updated to mirror this change.


can it calculate pi
i mean theoretically yes but it would be much slower than using a TCPobject to grab digits of pi off an external website

can it calculate pi

Like Ipquarx said, but you need to handle it yourself. This library does not support floats, so you need to simulate floats through an integer.
« Last Edit: January 26, 2018, 03:31:57 AM by mctwist »