1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.
  2. Welcome to the new Hive! Be advised that we're still working on the site. There are still many rough edges, so please bear with us.
    Dismiss Notice
  3. The 14th Icon Contest is still in progress (and may be extended). You can still make it in time.
    Dismiss Notice
  4. The 25th Texturing Contest has started! Contestants are to create a skin representing a dark elf person/being or any construct related to it using the vanilla models or the custom ones found on the site.
    Dismiss Notice
  5. The poll for Terraining Contest #18 is finally up! Play through the maps and cast your vote on your favourite.
    Dismiss Notice
  6. Buy it, use it, break it, fix it, trash it, change it, mail - upgrade it. Join (Optionally) Paired Techtree Contest #11 - Techno Magic now!
    Dismiss Notice
  7. Voting squad, line up! Cast your vote on the poll for Modeling Contest #29 - Squads!
    Dismiss Notice
  8. Hero Contest #8 is up and running! This time it's a joint contest between artists and coders. Go here for team matchmaking.
    Dismiss Notice
  9. The poll for the theme of our StarCraft II Terraining Contest is up. Cast your note now!
    Dismiss Notice
  10. The ninth Concept Art Contest has launched. Enter now!
    Dismiss Notice
  11. The member Kam is making HIVE coasters. Take a look. For every coaster you buy, Hive gets $1.
    Dismiss Notice

[System] BigInt

Discussion in 'Graveyard' started by Nestharus, Feb 5, 2011.

  1. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    gone
     
    Last edited: Dec 21, 2013
  2. Bribe

    Bribe

    Code Moderator

    Joined:
    Sep 26, 2009
    Messages:
    7,335
    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:

    Code (vJASS):

                    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
     
     
  3. Robbepop

    Robbepop
    Joined:
    Mar 6, 2008
    Messages:
    827
    hiho,

    how precise are these BigInts?
    does it make sense to use them for numbers with a maximum of 500-200000?

    Robbepop
     
  4. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    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

    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: Feb 9, 2011
  5. Dr Super Good

    Dr Super Good
    Joined:
    Jan 18, 2005
    Messages:
    21,152
    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.
     
  6. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    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.
     
  7. Dr Super Good

    Dr Super Good
    Joined:
    Jan 18, 2005
    Messages:
    21,152
    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.
     
  8. Bribe

    Bribe

    Code Moderator

    Joined:
    Sep 26, 2009
    Messages:
    7,335
    JASS compiles into a beautiful game, providing an overall programming experience vastly superior than a "fast" programming language that does not have such satisfying output. How much more fun is it to run an algorithm through a function that you built rather than running it through something like a cell-phone calculator?
     
  9. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    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: Feb 9, 2011
  10. Bribe

    Bribe

    Code Moderator

    Joined:
    Sep 26, 2009
    Messages:
    7,335
    This has a lot of potential. When you're done mucking around with the API in the Base system this is good to go.
     
  11. Bribe

    Bribe

    Code Moderator

    Joined:
    Sep 26, 2009
    Messages:
    7,335
    Alright, API on Base is secure, so this is in the field.
     
  12. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    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: Feb 10, 2011
  13. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    Updated to 1.1.3.0

    3 new method additions
    Code (vJASS):

    method mod takes integer k returns integer
    method rl takes nothing returns nothing
    method rr takes nothing returns nothing
     


    Demo
    Code (vJASS):

    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
    Code (vJASS):

    method addBig takes BigInt k returns nothing
    method multiplyBig takes BigInt k returns nothing
    method copy takes nothing returns BigInt
     


    Code (vJASS):

    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: Feb 16, 2011
  14. D4RK_G4ND4LF

    D4RK_G4ND4LF
    Joined:
    Feb 4, 2009
    Messages:
    1,200
    awesome!
    I once did something similar in c++ but I had way less functions
    how much slower are your bigints compared to casual ints?
     
  15. Bribe

    Bribe

    Code Moderator

    Joined:
    Sep 26, 2009
    Messages:
    7,335
    About a million billion times slower ;)
     
  16. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    Yea, I'd only use this lib with save/load =).


    edit
    fixed a division bug and optimized division a bit ;P.
     
    Last edited: Feb 17, 2011
  17. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    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.
     
  18. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    Put debug statements in front of all of the debug text messages not in static ifs ;|.

    My bad ^_^
     
  19. Nestharus

    Nestharus
    Joined:
    Jul 10, 2007
    Messages:
    6,101
    Fixed a debug statement.
     
  20. D4RK_G4ND4LF

    D4RK_G4ND4LF
    Joined:
    Feb 4, 2009
    Messages:
    1,200
    I wrote a fraction class in c++ recently so I could have unlimited precision numbers and make my pc do my homework
    maybe you like the idea
    canceling was a problem though (right now its bruteforce)

    by the way you are pretty close to 1337 posts
    make sure you don't miss it :thumbs_up: