• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

[System] BigInt

Bribe

Bribe

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,464
The Jass Optimizer breaks ExecuteFunc and UnitAlive, but the solution is to NOT use those natives. I'm sure that you will be adding a description later on, like usual, but stuff like this belongs in a scrapyard language like Perl:

JASS: 
                if (e[n[y]]) then
                    set n[y] = n[0]
                    set n[0] = y
                    set y = p[y]
                    set p[td] = y
                    set n[y] = td
                else
                    set y = p[y]
                endif
 

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
100% precise.

This can handle up to around 8187 digits (in the base) or so if you only have one active number.

1234567 would be 7 digits if it were in b10
35,31,22 would be 3 digits for base 36

etc

does it make sense to use them for numbers with a maximum of 500-200000?
Click to expand...
Not really ;D.

If doing this for save/load, see my new encryption algorithm that generates a key given a player name and encrypts the data with that key at the cost of 1 bit (1 binary digit, which is almost nothing).

Also keep in mind that you can merge up all of your numbers using this to minimize the size of your save/load code.

http://www.hiveworkshop.com/forums/tutorial-submission-283/advanced-data-encryption-189120/

I'm also creating an Encoder that'll do binary shuffling on a BigInt.
 
Last edited:

Dr Super Good

Dr Super Good

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,192
Surly it would be most efficent to store everything in native types...
If you stored all parts in the lower 16 bits of the 32 bit integer type, you would have direct access to bits via simple division of a choosen part instead of having to run an expensive base conversion. Further more, if bitshifting is available (I forget if WC3 had it), you can directly get the overflow and have it ready for the next itteration.

Standardizing the internal base also would allow the creation of efficent methods to add bigint to bigint or even (god help us) multiply bigint with bigint as well as remove all the code needed to support dynamic base size.

This is no substitute for real BigInts... Real BigInts abuse specially created instructions that all computer processors have to allow them to be computed faster. For example, there is a overflow register available meaning that chunks can be as large as 64bits.

JASS probaly has a shit compiler. Consider trying caching some indicies or common opperations into a local to see if a speed gain is given.
 

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Actually, performing arithmetic on an integer would be much slower than looping through a list.

Also, it doesn't have anything for shifting bits.

All of the stuff can be done in this, and handling big bases would be faster than handling small bases because of the smaller amounts of iteration involved in the larger base operations ;D.

Because this is stored digit by digit, it supports any base to any base conversion as the numbers are grouped properly when re added ^_^. And working with binary digits would be the slowest possible thing to do in JASS. The smaller the base, the slower.
 

Dr Super Good

Dr Super Good

Dr Super Good

Spell Reviewer
Level 63
Joined
Jan 18, 2005
Messages
27,192
Actually, performing arithmetic on an integer would be much slower than looping through a list.
Click to expand...

Is the JASS compiler really that shit that loops (which usually involve integer arithimitic) are slower than integer arithimitic? To me that sounds a bit contradictory. Your processor can perform hundreds of millions of integer arithmitic opperations to memeory a second, billions to cache. Weather it is adding 1 to 1 or adding a million to a million, they take the same time as all 4 bytes for each number have to be loaded in any case.

I am afriad I seem to not be communicating my ideas properly.

Its a pitty you can not bitshift, that would make this system so much more efficent (as bitshift opperations are extreemly cheap compared to division or other calculatory instructions).

My sujestion was to make it use a hard coded base of 65536 as that would be half an integer allowing for up to half 65536 with muliplication (due to sign bits and no access to overflow registers) and fewer parts would mean fewer itteration needed (and as all parts are still the same word size, there is no extra computation cost). Further more, there would be no need to base convert to binary (expensive time wise as you said) since you could gain access to individual bits by division of powers of 2 and then modulation (again if bitshift and binary opperators were available, this would become insanly fast via masking flags).

Sigh, I guess JASS just plain sucks.
 

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
I see, but that'd fail as then you couldn't really retrieve specific digits w/o math operations. If I wanted to loop through digit by digit and I wanted a base 10 number, I couldn't do it, or it'd be much, much slower.

On another note, I am planning to change multiply to only take a single parameter and add a pow method ;D.

method multiply takes integer value, integer exponent returns nothing

to

method multiply takes integer value returns nothing

I will apply this change as soon as I finish up this set of hw. I only have like 1 hour left to finish half an assignment ;o.

edit
Removed pow and changed s2i to convertString.

edit
fixed add method (was broken)
 
Last edited:

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Added the ever useful method toInt takes nothing returns integer

edit
fixed 2 bugs ^_^, working perfectly now. The 2 bugs had to do with untested methods (sh sh). The new toInt that was just added and the never used convertString, lol ; D.


edit
Optimized it a bit and changed how a lot of the loops operated. Do not worry as I tested every single method this time!! I also tested for leaks.

add,divide,multiply,convertString,toString, forwards/backwards list continuity testing, leak testing, push,pop,enq,deq, toInt. It was all thoroughly tested this time >: O.

However, if somehow I missed a bug, let me know ;D.
 
Last edited:

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Updated to 1.1.3.0

3 new method additions
JASS: 
method mod takes integer k returns integer
method rl takes nothing returns nothing
method rr takes nothing returns nothing

Demo
JASS: 
struct tester extends array
    private static method onInit takes nothing returns nothing
        /*//mod demo
        local BigInt int = BigInt.create(Base["0123456789"])
        call int.add(12923,0)
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "11==" + I2S(int.mod(16)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "5==" + I2S(int.mod(6)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "471==" + I2S(int.mod(566)))
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "98==" + I2S(int.mod(225)))
        */
        
        //rotate demo
        local BigInt int = BigInt.create(Base["0123456789"])
        call int.add(123456789,0)
        //rotate left
        call int.rl()
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "912345678==" + I2S(int.toInt()))
        
        //rotate left
        call int.rl()
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "891234567==" + I2S(int.toInt()))
        
        //rotate right
        call int.rr()
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "912345678==" + I2S(int.toInt()))
        
        //rotate right
        call int.rr()
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "123456789==" + I2S(int.toInt()))
    endmethod
endstruct

So I guess with push, pop, enq, deq, rl, and rr, you have full bit shift operations. With mod, you can now do efficient modulo.


edit
Added
JASS: 
method addBig takes BigInt k returns nothing
method multiplyBig takes BigInt k returns nothing
method copy takes nothing returns BigInt

JASS: 
struct tester extends array
    private static method onInit takes nothing returns nothing
        /*//copy demo
        local BigInt int = BigInt.create(Base["0123456789"])
        local BigInt copy
        
        call int.add(194382,3)
        call int.multiply(204202)
        call int.add(2482,10)
        set copy = int.copy()
        
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, int.toString() + "==\n" + copy.toString())
        */
        
        /*//multiply big demo
        local BigInt int = BigInt.create(Base["0123456789"])
        local BigInt int2 = BigInt.create(Base["0123456789"])
        
        call int.add(3429201,0)
        call int2.add(5942242,0)
        call int2.add(793483,8)
        
        call int.multiplyBig(int2)
        
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "272101290085442208642==\n" + int.toString())
        */
        
        /*//add big demo
        local BigInt int = BigInt.create(Base["0123456789"])
        local BigInt int2 = BigInt.create(Base["0123456789"])
        
        call int.add(3429201,0)
        call int2.add(5942242,0)
        call int2.add(793483,8)
        
        call int.addBig(int2,3)
        
        call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "79348305945671201==\n" + int.toString())
        */
    endmethod
endstruct
 
Last edited:

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Buffed up multiplyBig so that it could handle larger numbers w/o a thread crash. I ran a big code through this in Encoder and it died.

If anyone has any thread crashes, please post to this so I can buff the loops up. Just let me know which trigger crashed (it'll show the id). For example, x1 was the crashing thing I fixed up.
 

Magtheridon96

Magtheridon96

Magtheridon96

Level 36
Joined
Dec 12, 2008
Messages
7,379
http://www.homeschoolmath.net/teaching/square-root-algorithm.php

=D

The method you show in the article is archaic. There is a MUCH more efficient algorithm. (This is the algorithm actually used behind the scenes inside a calculator when you hit the square root button.)

1. Estimate the square root to at least 1 digit.
2. Divide this estimate into the number whose square root you want to find.
3. Find the average of the quotient and the divisor. The result becomes the new estimate.

The beauty of this method is that the accuracy of the estimate grows extremely rapidly. Each cycle will essentially double the number of correct digits. From a 1-digit starting point you can get a 4-digit result in two cycles. If you know a square root already to a few digits, such as sqrt(2)=1.414, a single cycle of divide and average will give you double the digits (eight, in this case).

In addition to giving a way to find square roots by hand, this method can be used if all you have is a cheap 4-function calculator. If students can get square roots manually, they will not find square roots to be so mysterious. Also, this method is a good first example of an itterative solution of a problem.

David Chandler
This other way is called Babylonian method of guess and divide, and it truly is faster. It is also the same as you would get applying Newton's method. See for example finding the square root of 20 using 10 as the initial guess:

Code: 
Guess     Divide               Find average

10        20/10 = 2            average 10 and 2 to give new guess of 6 
6         20/6 = 3.333         average 3.333 and 6 gives 4.6666 
4.666     20/4.666= 4.1414     average 4.666,4.1414= 4.4048 
4.4048    20/4.4048=4.5454     average = 4.4700 
4.4700    20/4.4700=4.4742     average = 4.4721 
4.4721    20/4.4721=4.47217    average = 4.47214

This is already to 4 decimal places
Click to expand...

This guy's post seems useful too :p
 

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
So, while the current BigInt seems pretty big, it's pretty slow >.>. We can all agree that Scrambler will freeze the game for a little bit when saving/loading all but the smallest of save/load codes. Well, to address this issue, I have decided to work on BigInt 2, which will have blazing fast speeds.


See more at this pastebin link, including the algorithms that'll be used ; ).

http://www.hiveworkshop.com/forums/pastebin.php?id=70u8ne


Now, as you see, the BigInts themselves won't be able to have their bases changed. The only time bases are ever changed are during post processing in save/load when things are occurring like encryption =P. Furthermore, the only time a real base object is ever needed is when the dern thing is outputted =P. What this means is that BigInts now just take numeric bases until they need to be outputted : ).


The base BigInts are actually stored in is quite huge... why is it huge? Because a bigger base means less operations (less digits), meaning less need for trigger evaluations. The absolute biggest operation is perhaps only 5200 iterations, meaning that nested trigger evals are no longer needed for anything... yes, even base conversion will only be 1 trigger evaluation.


What this also means is that things like Scrambling will no longer freeze the game : D. Hurray! This also means that I will have to recode the Scrambler to use BigInt 2's Buffer stuff.


So why am I introducing Buffers for base conversion? Base conversion, when not outputting something, always involves arrays and swapping digits around... or pushing digits... or adding digits here and there. It always involves something crazy >.<. As such, an array is a rather smart choice as it allows for blazing fast iteration, random memory access, and blazing fast allocation and deallocation. Once loaded into a buffer, it can never go back into a BigInt, and the output of a buffer is extremely fast.



People have complained for a long time about the speed of BigInt and I am now finally addressing it. Yes, I have time this weekend (only really Saturday, lol) to work on something, and I decided to work on BigInt : P.
 

Magtheridon96

Magtheridon96

Magtheridon96

Level 36
Joined
Dec 12, 2008
Messages
7,379
JASS: 
float SquareRootFloat(float number) {
    long i;
    float x, y;
    const float f = 1.5F;

    x = number * 0.5F;
    y  = number;
    i  = * ( long * ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float * ) &i;
    y  = y * ( f - ( x * y * y ) );
    y  = y * ( f - ( x * y * y ) );
    return number * y;
}

^ I found this squareRoot algorithm on the internet.

In Jass, it would be something like this:

JASS: 
function SquareRootX takes real number returns real
    local real x = number * 0.5
    local real y = number
    local real f = 1.5
    local integer i = R2I(y)

    if i < 1 then
        set i = 1
    endif

    set i = 0x5f3759df - i
    set y = i
    set y = y * ( f - ( x * y * y ) )
    set y = y * ( f - ( x * y * y ) )

    return number * y
endfunction

Now if we optimize this function, we'd get this:

JASS: 
function SquareRootX takes real number returns real
    local real x = number * 0.5
    local real y = number
    local integer i = R2I(y)

    if i < 1 then
        set y = 0x5f3759de
    else
        set y = 0x5f3759df - i
    endif

    set y = y * (1.5 - x * y * y)

    return number * y * (1.5 - x * y * y)
endfunction

I haven't tested this algorithm yet, but I'm going to do that in a minute.
Eventually, I'll use this algorithm to write you a BigIntSquareRoot like I promised ^_^

Maybe after that, I'll see if it's possible to do a BigIntLog :eek:
 

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Why... interesting, but not useful at all, lol.


In BigInt 2, I remove a lot of useless methods ; P. I've never personally used the rotation methods, so yea, those are gone =).


edit
Latest news:

Multiplication Method

Tested on values up to 2147483647^225 on 1 thread without any problems. Can go much higher.
​

Base Conversion

Handles 2147483647^26, which is a 127 digit base 80 value, with a small freeze (a plip). This is bigger than the biggest possible save/load codes.

Uses smart thread splitting in order to absolutely maximize the speed. Keeps track of operation count estimates and next operation cost estimates to smartly figure out when to move to a new thread.

Can split down to 1/2 iterations. Can handle around 25000 iterations per thread. 23000 is used to give enough room for generating the final number.
​

Addition:

Handles pretty much anything on 1 thread.
​



BigInt 2.0 can multiply or add with any integer without overflow problems. It converts the integer into BigInt 2.0's internal base and goes digit by digit to absolutely prevent overflow. This means that doing int.multiply(2^32-1) is possible and there will be no overflow.


120 characters is the maximum a save/load code can be without splitting. With splitting, it can go larger. BigInt 2.0's base conversion was tested up to 704 digits (can go much higher) in base 32 with absolutely no problems. A 704 character code is 6 different save/load codes a player would have to type in.



Some sample code (code used for testing)
JASS: 
struct testers extends array
    private static method init takes nothing returns nothing
        local BigInt2 i = BigInt2.create()
        local Base b80 = Base["0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!@#$%^&*()-_+=~?><"]
        local integer b = 26
        call i.add(2147483647)
        
        loop
            set b = b - 1
            exitwhen b == 0
            call i.multiply(2147483647)
        endloop
        
        call DisplayTimedTextToPlayer(GetLocalPlayer(),0,0,60,i.toString(b80))
        
        call DestroyTimer(GetExpiredTimer())
    endmethod
    
    private static method onInit takes nothing returns nothing
        call TimerStart(CreateTimer(),0,false,function thistype.init)
    endmethod
endstruct

As can be seen, BigInts are now outputted in certain bases. BigInts are stored in a special internal base to maximize speed. The above outputs 2147483647^26 in base 80.


A special look at BigInt 2.0's insanely fast multiplication algorithm. This runs at a slightly slower speed than multiplyBig due to the modulos arithmetic and can ofc handle most anything on a single thread.
JASS: 
        private static method multiply2 takes nothing returns boolean
            local integer this = toBeMultiplied
            local integer d = this
            local integer i = toMultiply
            local integer t
            local integer array db
            local integer dbc = 0
            local integer s = 0
            local integer m = 0
            local integer k
            
            loop
                exitwhen 0 == i
                
                set t = i - i/46340*46340
                set i = i/46340
                
                set m = m + 1
                set s = m - 1
                loop
                    set d = n[d]
                    exitwhen h[d]
                    set s = s + 1
                    set db[s] = db[s] + v[d]*t
                    set k = s - 1
                    loop
                        set k = k + 1
                        exitwhen 46340 > db[k]
                        set db[k+1] = db[k+1] + db[k]/46340
                        set db[k] = db[k] - db[k]/46340*46340
                    endloop
                    if (dbc < k) then
                        set dbc = k
                    endif
                endloop
                
                if (dbc < s) then
                    set dbc = s
                endif
            endloop
            
            if (dbc < m) then
                set dbc = m
            endif
            
            loop
                set d = p[d]
                if (h[d]) then
                    set d = n[0]
                    if (0 == d) then
                        set d = ic + 1
                        set ic = d
                    else
                        set n[0] = d
                    endif
                    set p[d] = this
                    set n[d] = n[this]
                    set p[n[this]] = d
                    set n[this] = d
                endif
                set v[d] = db[dbc]
                set dbc = dbc - 1
                exitwhen 0 == dbc
            endloop
            
            return true
        endmethod

BigInts are internally stored in base 46340, which is the square root of 2^31 rounded down.


I also think that this library is a prime example of when you totally need to squeeze out every ounce of performance you can. BigInt 2.0 is, after all, an update that completely focuses on increasing the speed ; P.


edit
Division can't be done digit by digit, so big division is impossible ; |. Division method is safe up to 2147349261 out of 2147483647.
 
Last edited:

Bribe

Bribe

Bribe

Code Moderator
Level 50
Joined
Sep 26, 2009
Messages
9,464
In the multiplication method you posted, you should only set "db[k]/46340" to a local before repeat-referencing.

I also think you opening one thread per method is important because if you only test one method for thread crashes you're safe, but if you're using multiple methods in one thread that one thread could get overloaded. Though you might already be doing this so w/e.
 

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Yea, already doing what you said for the thread thingie ; P.


Anyways, I finally figured out how to do the division with 0 chance of overflow O-o... Polynomial Long Division here we go : D.


wanna see 2^31-1 divided by 46340?

Code: 
2^31-1    *     46340
1		0
1		1
41707		0

x = 46340

   x + 1 + 41707/x
 x x^2+x+41707
   x^2
     0-x
       0-41707


x+1 r41707

(46340+1)*46340+41707 = 2^31-1
 

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Just decided to post some news on how BigInt 2 is coming along ^)^.


BigInt 1 thread count for base conversion: over 191 for the outer threads. Every outer thread also spawns many inner threads, so the count could be easily over 1000.

Big Int 2 Proto A: upgraded to smart threading design to minimize threading. Same exact algorithm as BigInt 1 with minor improvements. Thread count of 35.

Big Int 2 Proto B: Completely changed the algorithm. Kept intelligent threading, but was much simplified as the new algorithm is much more simple. Thread count of 7!



What does this mean? Scrambler is no longer going to cause freezes is what it means >: D.


BigInt 2 is split up into two parts. You can no longer freely change the bases of BigInts. The reason for this is to keep operations down to a minimum. Working with smaller bases increases the operation costs of things like adding, multiplying, and dividing. By keeping that base as large as possible, the operation cost is kept to a minimal. This means that some things like multiplication can run on a single thread without crashing!

The base BigInts are kept in is 32768.


toString now takes a base as the argument so that the BigInt can be displayed however (that's what bases are mainly used for anyways).


A BigInt Buffer (static) is created to handle BigInts in different bases. It does not support general operations and acts more like an array with push/pop/enq/deq. This means things like Scrambler will actually be easier to do. The Buffer also allows base changing and includes load and unload commands (unload to a BigInt and load from a BigInt). The buffer can also be cleared with O(1) complexity.


Overall, there are only 4 methods left to code for BigInt 2, so anticipate the release to be soon ^)^. The code is fully commented so that it is easy to read and the algorithms are explained (for the most part). The base conversion algorithm is just division =).


BigInt 2 is a major, major speed increase from BigInt 1 and gets rid of a lot of useless methods that I personally never used, like rotate etc =p.


In this case, I think that we can all agree that BigInt 1 was just too slow ;o.



Division in BigInt 2 is safe up to 1,000,000,000. Multiplication and addition were safely tested up to 240 digit numbers without a thread crash. Base conversion is safe up to any sized number. The reason multiplication, addition, and division are only tested up to 240 is because a player can only type in 120 character codes. Yes, you can split the codes up into different strings, thus giving the player like 3 codes for a huge 360 digit save/load code, but the fact is that even a 120 character code is just plain too big : P. It was tested up to 240 for checksums : ).


Anyways, here is a look at the new toString method that shows the base conversion algorithm used
JASS: 
        private static method toString2 takes nothing returns boolean
            //Base toBase       base
            //BigInt toStr      BigInt being converted to string
            //string returnStr  string to return
            local integer size = toBase.size        //base size
            local integer ii = 0                    //op count
            local integer d = toStr                 //divide BigInt
            local integer m = 0                     //remainder
            local integer cc = 0                    //calc next op limit
            
            //op limit loop
            loop
                set cc = 0
            
                //division loop
                loop
                    //division gather numbers to divide
                    if (m < size) then
                        loop
                            set d = p[d]            //go to prev digit
                            exitwhen h[d]
                            
                            set cc = cc + 2
                            
                            //exitwhen remainder (numbers being pulled out of BigInt) is bigger than number doing the dividing
                            set m = m*BASE + v[d]
                            exitwhen m >= size
                            
                            //! runtextmacro BIG_INT_REMOVE("d")
                            //! runtextmacro BIG_INT_DEALLOCATE("d")
                            
                            set cc = cc + 9
                        endloop
                    endif
                    
                    set cc = cc + 2
                    
                    exitwhen h[d]
                    
                    //in this case, remaining digits will always be < base
                    //! runtextmacro BIG_INT_GET_REMAINING_DIGITS("v[d]", "m", "size")
                    //! runtextmacro BIG_INT_GET_CURRENT_DIGIT("m", "m", "size")
                    
                    set cc = cc + 4
                endloop
                
                set returnStr = toBase.char(m) + returnStr
                
                exitwhen h[n[toStr]]

                set m = 0
                
                set cc = cc + 2
                set ii = ii + cc
                
                if (ii > 23000) then
                    return false
                endif
            endloop
            
            return true
        endmethod
        method toString takes Base base returns string
            //if BigInt isn't empty
            if (not h[n[this]]) then
                set this = copy()
                
                set toBase = base
                set toStr = this
                set returnStr = ""
                
                //loop until done converting
                loop
                    exitwhen TriggerEvaluate(strt)
                endloop
                
                return returnStr
            endif
            return base.char(0)
        endmethod
 
Last edited:

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
Actually, right now I'm running into some bugs for larger numbers on BigInt 2 ; |. Not sure what's bugging. It is all 100% written, but I have to find the one bug >.<. I'm not sure if it's the base conversion or multiplyBig, but I'll find out soon enough ^)^. Apparently, there are 0 thread crashes and 0 overflows, so... not sure yea ; D. I'm thinking it's multiply big and I'm going to have to rip the numbers out of it in base 32768 and convert to base 10 to find out >.>.


edit
good news.. I found the bug... division was overflowing >.<... division could actually only handle up to like 64k, not 1 bill >.>. I wasn't thinking of the remainders D :.

-> set m = m*BASE + v[d]

soooo... what to do, I dunno >.>. Actually, yes I do know... but it'll slow down the division a lot o-o... I can store the remainder in a BigInt. What this'll mean is that the number will be able to safely be divided by up to 2^31-1 without any overflowing. I'd really love to be able to divide by BigInts as well, but I don't know a good way :\.


Anyways, considering that I forgot about the mod method and that I have to rewrite division and everything to do with base conversion, the release of this is now delayed >.>... however, the update will make division super awesome ^)^. I'll also do some smart threading for multiplication, addition, and convert string to make it impossible to crash anything : ). However, this will still crash on array overflow, but the chances of that happening in base 32768 is slim to none ;o.

Base 32768 still has to stay due to multiplication overflow protection. Changing it to a higher base would just slow things down in multiplication.
 
Last edited:

Nestharus

Nestharus

Nestharus

Level 31
Joined
Jul 10, 2007
Messages
6,306
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.
 

Zwiebelchen

Zwiebelchen

Zwiebelchen

Hosted Project GR
Level 35
Joined
Sep 17, 2009
Messages
7,236
Nicely done so far.

Will you code a full-fledged Save/Load Snippet when it's done? Will it have some compatible interfaces?

I still use Pipedreams Save/Load System and I love how it is done (in terms of using it, not in terms of the actual coding) in the first place. I don't like noob-friendly systems that allow direct saving of abilities, units, etc. ...
I like to "compress" my data on my own, as tailor-made data compression is always better than generic compression.

all the features I would love to have are
- storing integers with fixed max values
- encryption with player name
- a version checker integer (this one is important ... for every 'code wipe', just count the number up by 1 to disallow old codes to work)
- op limit save (I'm looking at you, Pipedream!)

No fancy additional encryption (As players don't know the maxints, they won't figure it out anyway - if people want to cheat, they will usually just deprotect the map anyway). No dynamic Ints you usually don't need them anyway (big numbers to save are always a sign of bad game design, if you ask me) but make the system slower and over the top complicated and no stupid charsets.
a-z,A-Z,0-9 is all you need. No symbols, no weird layout. Possibly leave out lowercase L and uppercase i and 1 to avoid confusions.
Usually people prefer typing 5 more 'simple' chars instead of having to use weird symbols on their keyboard.
4 chars between each minus. Make the char coloring optional, as people nowadays want to print the string to a preload txt instead of just displaying it.

That's all I can say for now, giving a user's feedback on what I would prefer to have and not to have in a save/load system.
 
You must log in or register to reply here.

Similar threads

Nestharus
[System] LUA_JASS_GLOBALS
Replies
2
Views
1K
doomhammer99
doomhammer99
Nestharus
[System] Dummy
2
Replies
57
Views
12K
Nestharus
Nestharus
Nestharus
[System] Bonus
2
Replies
92
Views
13K
Magtheridon96
Magtheridon96
Nestharus
[System] Unit Attack
Replies
23
Views
7K
Luorax
Luorax
Nestharus
[System] Spell Struct
Replies
33
Views
4K
Nestharus
Nestharus
Top