[System] BigInt

zwie, already have a save/load thing up in the spells section, I just need to update it.


My save/load with snippets map is essentially a collection of snippets that you can choose to use or not ;o. It all runs off of this lib. You can make it as simple or as complex as you want. It allows you to easily craft your own save/load system.
 
Last edited:
Fixed BigInt op limit crashes with divideBig.

edit
still running into thread crash problems... trying to make divideBig run less operations now.

edit
currently, this can only handle 119 character save/load codes. I am still working on the division algorithm in order to bring this up to 120. The current version of this that is up is pretty crappy compared to the version I have right now, but I'm going to continue working on it until I can make it so that division does not crash with 2 iterations >.>.


Also, there is a major fps drop still with an encryption level of 3 on larger save/load codes... and when I say major, I mean major.


You may think that using Pipedream's BigInt lib is smarter because it's so damn fast... but it's only so damn fast because it's so unsafe. It can easily run into the op limit or even overflow.
 
Last edited:
Ok, I have solved the division problem. It had to do with the accuracy of the first guess. I have been working on an algorithm to improve the accuracy.

The 120 digit value was off by 180, meaning that it had to go through 180 intensive iterations in order to get to the correct value, which is where the freezes are coming from in the division algorithm.

Using the new algorithm, I went through 3 very light iterations and came up with a guess that was 1 off. If I used decimals and rounded, it would be at the exact guess. What I'll probably do is replace my crazy guessing thing with these highly light loops to drastically increase the speed of the algorithm. The light iterations do not use BigInts at all but rather use plain integers, meaning that the operations are ridiculously fast. Also, 3 iterations vs 180. I should be able to increase the division algorithm so that it will not even freeze with a 120 digit value ^)^.

Sadly, base conversion still causes freezes in Scrambler : |.


Also, I will be increasing the default base size from 32768 to 46340 ;D. This should improve the speed of all operations by quite a bit.


Here is the algorithm
Code: 
Put largest 2 digits of number being divided together
digit1*base+digit2 = combined digit

divide the combined digit by the largest dividend digit
combined/largestDividend = first guess

loop
multiply the first guess by the 2nd largest dividend digit if there is one
If there isn't, exit
2nd largest digit * first guess = some product

divide that by the base
some product / base = some quotient

divide that quotient by the largest dividend digit
some quotient / largest dividend digit = guess off

exitwhen prev guess off == guess off
set first guess = first guess + (prevGuessOff-guessOff)
set prevGuessOff = guessOff
endloop

And an example
Code: 
multiply first 2 digits together
3*46339+1538 = 140555

do that / first digit
140555/21 = 6693

do that * second digit
179914533

divide by 46339
3882

divide by first digit
3882/21 = 184

subtract from first guess

6693 - 184 = 6509
actual: 6513

repeat
6509 * 26881 = 174968429
174968429 / 46339 = 3775
3775/21 = 179
184 - 179 = 5 (exitwhen this is 0)
new: 179
6693 - 179 = 6514

repeat
6514 * 26881 = 175102834
175102834 / 46339 = 3778
3778/21 = 179
179 - 179 = 0

Note that the 179 I got was actually 179.9 and the actual amount off was 180.
 
46340 is the maximum value I can use without overflow.

2^31 = 2147483648
2^15.5 = rt(2147483648) = 46340 ; )

This will mean that I can combine a maximum of 2 digits in a BigInt safely, which is what I need to combine for multiplication ;D.


Oh yes, I have finally solved the damn BigInt division... it now is epic fast >.<. I tried 5000 iteration max and it did not crash with a 120 digit number.

How did I pull off this amazing feat? I came up with an insane guessing algorithm that will always get to within 2 of the actual quotient =O. If you run into any bugs, like crashing threads, let me know >.>.

So... what I now need to do before I release the new version is to somehow make the base conversion faster. I do have some ideas on how to do this, so I will be working at it ; ).

I am also still checking the division algorithm for bugs ;p.

edit
just set encryption strength to 0 in my test map and loaded up a 120 character code with 0 freeze, so everything is coming from the base conversion right now : |. Of course, the encryption does a lot of base conversions..

JASS: 
set so[0]=5
        set so[1]=2
        set so[2]=3
        set so[3]=11
        set so[4]=2
        set so[5]=7
        set so[6]=3

All of those by default (7) +1 more for going back, meaning 8.

edit
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 ;|
 
Ok, so... some new updates..

So #1, I have figured out a way to increase the speed of the division algorithm. Not too great since it's already fast enough, but w/e.

#2, I have found a way to drastically increase the speed of base conversion. When I say drastic, I'm talking 60x+ faster. I am still working on the algorithm, but I have split it up into a couple of things.

First, I use the multiplication algorithm for converting numbers in smaller bases to numbers in larger bases.

I use a division algorithm for converting numbers in larger bases to numbers in smaller bases.

The current problem that I am solving right now is the division piece when converting between bases like 2 and 3 rather than 3 -> 46340 -> 2. As it is right now, 3 -> 46340 -> 2 is faster than 3 -> 2. I am doing some craziness with the division algorithm to make it faster though. With the multiplication piece updates, converting between bases where it applies has caused 0 fps drops on my machine (I tested 7 or 8 base conversions in 1 instant). I think that this speed update is important as it will make it so that you can actually apply powerful encryption to codes using Scrambler w/o dropping a hammer on the performance of the save/load commands... you may think that they don't need to be fast, but you haven't seen these crazy freezes ;p, lolz. I have gotten many complaints, so I am really trying to get rid of the freeze before I update the save/load with snippets map ; ).


The new BigInt with these updates has not yet been released as I am still working on the division algorithm.

edit
oh yes... my specific problem with the division piece is that while I can calculate the modulo very quickly, calculating the quotient is another story ;p. I need both ;D. I lose the quotient when I attempt to do my special things ; |. If I apply my crazy thing only 1 time to the number, then I don't lose the quotient, but it stays slow >.<.
 
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 ^)^.

edit
blasted division is now broken...
 
Ok, just released the next version with fixed division... I also radically improved the division algorithm... it can no longer crash o-o. Cool right?

So now division is epic fast too ^^


I just did an encryption strength of 5 and the game did not do a hardcore freeze! Man I'm loving this, hahaa : D.


On an encryption strength of 12 with 7 base sets for each encryption on a 120 character code, it froze a little o-o. Roflz, I love this : D.

edit
removed some debug stuff from the divideBig method that i forgot to delete.. the getSize method and the checks on it >.<.
 
Last edited:
Here's an optimized version of one of the loops inside your division method :P

JASS: 
loop
    exitwhen (toSubtract.prev.digit*base + toSubtract.prev.prev.digit <= remainder.prev.digit*base + remainder.prev.prev.digit)
    set guess1 = guess - ((toSubtract.prev.digit*base + toSubtract.prev.prev.digit) - (remainder.prev.digit*base + remainder.prev.prev.digit))/divisor.prev.digit
    
    static if DEBUG_MSGS then
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"Guess 1: "+I2S(guess1))
    endif
    exitwhen (0 >= guess1 or base <= guess1 or guess1 == guess)
    call toSubtract.multFast(base, divisor, guess1)
    if (guess1 + 5 > guess and guess1 - 5 < guess) then
        set guess = guess1
        exitwhen true
    endif
    set guess = guess1
    
    static if DEBUG_MSGS then
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"To Subtract 1: "+toSubtract.toString())
    endif
    
    if (remainder.size > toSubtract.size) then
        set guess2 = guess + ((remainder.prev.digit*base + remainder.prev.prev.digit) - (toSubtract.prev.digit))/divisor.prev.digit
    else
        if (remainder.prev.digit > toSubtract.prev.digit) then
            set guess2 = guess + ((remainder.prev.digit*base + remainder.prev.prev.digit) - (toSubtract.prev.digit*base + toSubtract.prev.prev.digit))/divisor.prev.digit
        else
            set guess2 = guess + (remainder.prev.prev.digit - toSubtract.prev.prev.digit)/divisor.prev.digit + (divisor.prev.prev.digit + base/2)/base
        endif
    endif
    
    static if DEBUG_MSGS then
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"Guess 2: "+I2S(guess2))
    endif
    
    exitwhen (base <= guess2 or 0 >= guess2 or guess1 == guess2)
    call toSubtract.multFast(base, divisor, guess2)
    if (guess2 + 5 > guess and guess2 - 5 < guess) then
        set guess = guess2
        exitwhen true
    endif
    set guess = guess2
    
    static if DEBUG_MSGS then
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,10,"To Subtract 2: "+toSubtract.toString())
    endif
endloop

All I did was change the:

JASS: 
if condition then
    // code
else
    exitwhen true
endif

structure to this:

JASS: 
exitwhen not condition
// code

Because it acts the same way :P
 
Planning a small update on the toString method in this to lower string leaks to 1 =). Right now, this will leak one string for every digit in the number. This may not seem so bad, but azlier is working with numbers that have like 4090 digits in them :\, so we now need a way to prevent these leaks. The method I am planning will lower the leakage from 4090 for proposed string to 2 total.

Keep in mind that a warcraft 3 string is stored in a 4096 array, meaning that it's limited to 4095 characters (1 index for '\0'). This also means that the max BigInt displayable BigInt size w/o crashing wc3 is 4095, not 8191.
 
Azlier has figured out a way to save and load data from the hard drive. BigInt was designed for standard save/load, meaning that it is safe to use up to 240 digits (no thread crash). Azlier is working with 4000 digit long codes, so given this, I'm going to need to update BigInt to be safe with any size digit codes.

I'll begin the update next week on Thursday as I have absolutely no time to do it right now.

Oh yes, Azlier has successfully done his save/load stuff on the hard drive in multiplayer with no desyncs.
 
Slowly updating this to make it so that all methods are 100% op limit safe for ints up to 4096 characters long... I can't do any longer because wc3 crashes with strings longer than that :\.

Also removed masses of string leaks in the toString method using a new method of building strings that I taught to azlier since him building a 4096 character long string would have killed the game after a couple of uses.

There is only one way to build a string character by character in JASS, and that is to store all of the characters into a string array and concatenate them all in one go using 4096 indexes (0-4095). Have to do it in 2 lines atm cuz jasshelper crashes. Only 2 strings are then made each time instead of 4096 =), which is much*** better.
 
IIRC you can't get rid of string leaks, all you can do is make as less concatenations as possible.
Each time a string is created for the first time, it's stored in the internal string table, and each time you make a concatenation there is a big chance that the resulted string was not already stored in this string table.
s1 + s2 + s3 would create 2 strings (s1s2 and s1s2s3) if s1, s2 , s3 were already created (used somewhere else before in the map script).
Store a string in an array has no effect.

You need a wc3 version before the patch of the dead to confirm this (typecast string <-> integer).
 
You must log in or register to reply here.

Similar threads

Nestharus
[System] Dummy
2
Replies
57
Views
15K
Nestharus
Nestharus
Nestharus
[System] Bonus
2
Replies
92
Views
19K
Magtheridon96
Magtheridon96
Nestharus
[System] Unit Attack
Replies
23
Views
8K
Luorax
Luorax
Nestharus
[System] Spell Struct
Replies
33
Views
6K
Nestharus
Nestharus
Nestharus
[System] Timer Tools
2 3 4
Replies
184
Views
35K
Nestharus
Nestharus
Back
Top