System BigInt

[Nestharus]

Fixed a debug statement.

 

[Nestharus]

Fixed a bug. In the divide method, when dividing 0 by a number, it returned a bad value (just a random number in a variable). Now it returns 0.

 

[Nestharus]

Updated BigInt's docs and convertString method

 

[Nestharus]

Updated to 1.1.4.8


Removed a few useless local declarations, a few extra sets, and made one strict if statement a bit less strict

Fully commented the code

 

[tooltiperror]

Official tooltiperror review.

BigInt is a system that is not a revolutionary concept for programming. It has been done for many programming languages that do not support big enough integers. However, BigInt is revolutionary in its own right, as it is the first implementation of a BigInt in JASS, ever I believe.

The code is as well documented as possible. Variables of the type BigInt (herein referred to as BigInts) are already very slow compared to normal Warcraft III integers in arithmetic. Nestharus makes up for this with insane programming concepts, and genius algorithms.

The code, while mainly unreadable, was commented upon and now someone advanced with JASS should be able to understand what a method does at least, and how to modify it.

It's also possible to manipulate BigInts. You can treat it as a stack and push in new digits, and you can perform all four of the basic math operations on it.

There are wide uses for BigInt. I used it personally to make random numbers in combination with [LJASS]SetRandomSeed[/LJASS], [LJASS]StringHash[/LJASS], and [LJASS]GetPlayerName[/LJASS]. Nestharus used it himself for his giant save/load system, Encoder.

This is a high quality resource.

Approved.

 

[Nestharus]

Fixed a crash in multiplyBig when number being multiplied is 0.

edit
Fixed logical error in multiplyBig

 

[Nestharus]

Released BigInt 2!!!

Yes, it is finally time...

Division algorithm is much, much faster. When I attempted to do a fast modulo algorithm using Montgomery, it was actually slower than the Division algorithm when working in very large bases like 32768, so I decided to make mod just use division ;o, lol...

The old mod from first BigInt is faster than the current one, but the old one could possibly overflow.


The only things that are op limit safe are those things that crash on their own now. Methods like add and addBig and multiply are no longer op limit safe as they will never crash on their own. What this means is that you have to use them intelligently. If you want to make a method that returns no value op limit safe, simply execute it -> method.execute(args).

Be sure to always work with base 0 -> set i.base = 0. Base 0 is actually base 32768. It is the only non Base object that you may work with. It increases the speed of the system dramatically ; ). If you are working in something like base 10 or base 36, don't come complaining to me about the speed because that's your own problem for working in a stupid base ; P. If you want to output the number in base 10 or 36, change the base after you have done all your operations ;o, lol.


Anyways, enjoy BigInt v2 ;D.


I will start updating my save/load snippets later today as it's 1:30 am atm.

I have thoroughly tested this thing, but if you run into any bugs, let me know.

 

[Bribe]

More like method.evaluate(args) because .execute is like 4-6 times slower

 

[Nestharus]

method.evaluate doesn't work... it's the same as call method.


edit
nvm, it could be that evaluate only works on methods that return booleans.

 

[Nestharus]

Fixed BigInt op limit crashes for divide big.

 

[Nestharus]

Fixed bugs with division algorithm
Made division MUCH faster ^^
Made base conversion quite a lot faster
Base conversion still drops a hammer on fps with lots of encryption huge codes ;|

 

[Nestharus]

The new version is now released..

my magical base conversion algorithm is incredibly fast.. it only needs 1 trigger evaluation as the thread won't crash ^)^. I tested it up to 140 digit very high base numbers, meaning that it is safe to use for any real purposes. Obviously, it will crash on like a 240 digit number, lolz, but a player can only type in 120 characters anyways.

How did I solve the base conversion problem? Rather than converting directly from base to base, I do a very fast conversion to a very large base, then convert to the target large base (not actual base) then do a fast conversion to actual base.

So each conversion works like this
original base -> big base -> big base 2 -> target base

So why the heck are 4 base conversions way the hell faster than 1? The only slow base conversions are those between the 2 big bases, and because the bases are so massive (talking between 1500 and 46340), even these base conversions are fast.

The reason that the base conversions from small -> large -> small are fast is because these conversions convert the base to a higher power. They essentially just group the digits up to make the number smaller. I introduced 2 new methods to do this: pack and unpack. The pack method will pack the number up as much as possible while maintaining safety in the number (no overflow). Unpack will put it back in its normal format.

For example, packing a base 10 number would convert it to base 10000, which is just a matter of combining the digits in groups of 4.

So loop through each group of 4 digits and just combine them... very fast, very easy ; P. Unpacking just goes through each group of digits and takes them apart using modulo. Again, very fast, very easy.

So why does this work? You can group digits up any way you like. Grouping digits up in their own base is the most efficient grouping possible. This is the reason why bases like octal and hexadecimal are so popular, because converting between binary, octal, and hexadecimal, as well as any other power of 2 base, is very fast.

Let's take an example
101110001110

What would that be in hexadecimal?

16 is 2^4, meaning that hexadecimal groups binary up into groups of 4 bits.
1011|1000|1110

So the value would be 1011, 1000, and 1110, which happens to be B8E. You can only do this with bases that are of the same power. For example, 3 could group up into base 9 easily as each base 9 digit is two base 3 digits. Base 10 can go into base 100. Base 60 can go into base 3600, etc, etc. I applied this concept to my base conversion algorithm. Rather than going through tons and tons of division on very massive numbers, I first pack the numbers up into a massive base to minimize the BigInt division as much as possible. Packing is not BigInt division, it is just putting digits together ;o. From there, I do the BigInt division on 2 relatively small numbers, then I unpack the result.

What happens when I convert from something like base 2 to base 4? I can pack base 2 up into base 4 : O. Yes... however, I don't do it ;p. If two bases do share the same packed base, I simply pack the BigInt and then unpack it.

For example, base 2 and base 36 share the same base 32768 for packing. Because of this, converting from base 2 is a simple pack and unpack, no BigInt division necessary ^)^.

 

[Darthfett]

I don't see anything in the documentation about HOW big of an 'int' this will allow. Is it arbitrary precision/size?

What's with the lack of any indentation in the code, and the very small amount of comments? This isn't very friendly for anyone to read, and intentionally unfriendly. I doubt you program without any indentation.

 

[Nestharus]

The code won't fit into the post, lolz... so I had to remove all the spaces D:

If you want to see the code, here it is at THW where it does fit ;p
http://www.hiveworkshop.com/forums/jass-resources-412/system-bigint-188973/


This runs off of arrays, so the max total digits you can have across all BigInts is 8191 =).

The last version did have a bug with division, but I already fixed it + made division way the hell faster o-o.

I decided to do a simple save/load using Scrambler and an encryption strength of 12 . I loaded up a 120 char code and it only did a small freeze >: D. I am just so happy with this lib right now ^)^.

 

[Nestharus]

Fixed bugs with sizing in deto and popto as well as a couple of bugs in the range deallocations.

 

[Nestharus]

Fixed a small typo on line 210

sry about the spacing, but it's thehelper's fault since the code can't fit into the post ; \. If the post max char size is increased, I can put up the regular code. If you want the regular code, check THW since it can fit into one post there =).

 

[Nestharus]

Fixed another bug with BigInt