# [System] BigInt

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

1. ### Nestharus

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
This resource has moved here.

--

gone

Last edited by a moderator: Jan 17, 2018
2. ### Bribe

Joined:
Sep 26, 2009
Messages:
8,159
Resources:
25
Maps:
3
Spells:
10
Tutorials:
3
JASS:
9
Resources:
25
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

Joined:
Mar 6, 2008
Messages:
892
Resources:
7
Maps:
6
Spells:
1
Resources:
7
hiho,

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

Robbepop

4. ### Nestharus

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
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.

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

Last edited: Feb 9, 2011

### Spell Reviewer

Joined:
Jan 18, 2005
Messages:
25,930
Resources:
3
Maps:
1
Spells:
2
Resources:
3
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

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
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.

### Spell Reviewer

Joined:
Jan 18, 2005
Messages:
25,930
Resources:
3
Maps:
1
Spells:
2
Resources:
3
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

Joined:
Sep 26, 2009
Messages:
8,159
Resources:
25
Maps:
3
Spells:
10
Tutorials:
3
JASS:
9
Resources:
25
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

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
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

Last edited: Feb 9, 2011
10. ### Bribe

Joined:
Sep 26, 2009
Messages:
8,159
Resources:
25
Maps:
3
Spells:
10
Tutorials:
3
JASS:
9
Resources:
25
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

Joined:
Sep 26, 2009
Messages:
8,159
Resources:
25
Maps:
3
Spells:
10
Tutorials:
3
JASS:
9
Resources:
25
Alright, API on Base is secure, so this is in the field.

12. ### Nestharus

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
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

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
Updated to 1.1.3.0

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 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"])
//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
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.multiply(204202)
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.multiplyBig(int2)

call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "272101290085442208642==\n" + int.toString())
*/

local BigInt int = BigInt.create(Base["0123456789"])
local BigInt int2 = BigInt.create(Base["0123456789"])

call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "79348305945671201==\n" + int.toString())
*/

endmethod
endstruct

Last edited: Feb 16, 2011
14. ### D4RK_G4ND4LF

Joined:
Feb 4, 2009
Messages:
1,196
Resources:
20
Models:
3
Spells:
15
Tutorials:
2
Resources:
20
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

Joined:
Sep 26, 2009
Messages:
8,159
Resources:
25
Maps:
3
Spells:
10
Tutorials:
3
JASS:
9
Resources:
25
About a million billion times slower

16. ### Nestharus

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
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

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
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

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
Put debug statements in front of all of the debug text messages not in static ifs ;|.

19. ### Nestharus

Joined:
Jul 10, 2007
Messages:
6,146
Resources:
8
Spells:
3
Tutorials:
4
JASS:
1
Resources:
8
Fixed a debug statement.

20. ### D4RK_G4ND4LF

Joined:
Feb 4, 2009
Messages:
1,196
Resources:
20
Models:
3
Spells:
15
Tutorials:
2
Resources:
20
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