• Listen to a special audio message from Bill Roper to the Hive Workshop community (Bill is a former Vice President of Blizzard Entertainment, Producer, Designer, Musician, Voice Actor) 🔗Click here to hear his message!
  • Read Evilhog's interview with Gregory Alper, the original composer of the music for WarCraft: Orcs & Humans 🔗Click here to read the full interview.

[General] Help explain Barrett's+Montgomery's Algorithm Please

Status
Not open for further replies.
I'd like to use it for division, but I can't find any site on it that I can understand. Can anyone explain it to me?

Tx.


Also, Montgomery's is just for modulos right? Actually, Montgomery's algorithm would be useful too because I am going to run into the same problem I'm running into for the division method when I start on the mod method ; |.


So if anyone could help or link me to a good site, that'd be awesome : D.


I need to be able to get the quotient + remainder for the division.
I need to be able to get the remainder for the mod.


If I'm looking at the wrong algorithms, please let me know : ).


Ty all again.


edit
It looks like I want to use Montgomery's for both division and mod?


edit
It looks like Montgomery's is used for multiplication and mod as well as Barrett's =P.


Looking up divide and conquer algorithms. Anyone know some good ones besides peasant etc? Need to be able to divide any number by any other number, power of 2 or not ; P.
 
Last edited:

Dr Super Good

Spell Reviewer
Level 64
Joined
Jan 18, 2005
Messages
27,285
and I don't understand why they do the things they do or how to turn it into code ;\
It looks very simple to me... Too bad the algorthim shown in the paper seems to be for low level use rather than something for JASS to run. The behaviour it uses for efficiency execution relies on specific instruction behaviour which is far beyond what JASS is capable of. You will probably find it very slow because of having to emulate the instruction behaviour using JASS.

The google docs one does seem to supply you with a method that should work. Again, its performance might not be optimum for JASS where reducing code complexity would save more time than the actual algorthim.
 
So DSG, how do you suggest I do the division then? Polynomial Long Division or what? I can def write the polynomial long division algorithm : P.


Another thing was I was wondering if there is any way to go digit by digit. The main problem I have is overflow. If there is a way to divide by the divisor digit by digit in a certain base (I'm using 46340 atm), that'd be awesome : D.
 
Thank you all for your help, but I've finally figured out how to do this on my own.


2428/53 = 45 r43

2/53 = 0.03773584905660377358490566037736

First digit: 0

0.03773584905660377358490566037736*base (10) = 0.37735849056603773584905660377358

4/53 = 0.07547169811320754716981132075472+
0.37735849056603773584905660377358=
0.4528301886792452830188679245283

Second digit 0
0.4528301886792452830188679245283*10 = 4.528301886792452830188679245283

2/53 = 0.03773584905660377358490566037736+4.528301886792452830188679245283=
4.5660377358490566037735849056604

Third digit: 4
(4.5660377358490566037735849056604-4)*10 = 5.660377358490566037735849056604

8/53 = 0.15094339622641509433962264150943+5.660377358490566037735849056604 =
5.8113207547169811320754716981134

Fourth Digit 5
(5.8113207547169811320754716981134-5)*53 = 43


45 r43


Good Game >: O. Now the only problem is that this uses reals meaning that accuracy could be lost meaning that there could be a wrong answer ;\. It's also identical to long division if you look at the fractions.

200/53+40/53+2/53 = 242/53. This is pretty much a roundabout way of gathering enough digits to divide by. The good thing about this though is that it should never overflow : ). For getting the remainder, R2I(r+.9) can be done and it should be safe. I'll check into this more later when I have time to validate its accuracy for numbers like 2^(31*60)/2^31 =).
 
Solved
Dr Super Good was saying something like this, but I couldn't understand a word he was saying : P. He just kept saying estimate ; P. Before I read this site, I had no idea what he meant by estimate and words ;D.


This was the tough one: how to divide a by b and get the (integer) quotient and remainder? I just wanted to implement a naive division that essential 'undoes' the steps of naive multiplication, but for a while I couldn't see how to unpick all those additions. Eventually I realised something: if you divide the first few digits of a by the first few digits of b, you will get an estimate for the first few digits of the quotient that will be high by at most 1. Picking two numbers at random...

a = 64,745,023,423,004,376,034,552
b = 798,963,467,349,673,448

To start calculating a/b, BigInt takes the most significant chunk of each number (64 and 798). Since 64 < 798, it appends the next chunk of a to make 67745. Then its guess for the first few digits of the quotient is 67745 / 798 = 81. There is a chance that this is one too high, so the next step is to check by calculating (81000 * b), which is 64716040855323549288000. Since this is less than a, we know that 81 is correct. Now we subtract (81000 * b) from a to get the remainder and go round again. Keep going until the remainder is less than b and there you have it.

So... let's try it out in action (below algorithm still needs work).
Code:
1		2147483647
1
41707

		231701
5
1

2147483647/231701 = 9268 r78779


Loop until there is a digit in the second number and the first number is bigger than or equal to the second number. If it overflows (negative), then the quotient is 0 and the remainder is just the first number.


Second number: first digit is 5. It is digit #2.
First number: loop until at digit #2 (just build a BigInt)

41707 -> 1

First Number: loop until at end
1,1

Divide 1,1 by 5. Gather digits until the dividend is bigger than the divisor (normal fast algorithm). The divisor will always be 1 digit, so this will never ever overflow ; ).

1,1/5 = 46341/5 = 9268

Ignore the remainder. That's not needed.


Now we have a good idea of where the quotient is at. Do the BigInt we just got * the divisor, which was 5,1.

5,1 = 231701

231701*9268 = 2147404868

2147483647 > 2147404868

Because it's greater than, we we know that the answer we got is the quotient. If it was less than, we'd subtract 1.

The final step is to subtract.

2147483647-2147404868 = 78779

The answer becomes 9268 r78779.


Hurray! : D

11		2351024597175182565196593
99
77
66
44
33

1		99512459638625
1
3
5

23625429475 r99063641724718

1 is the fourth digit.

Loop until at the 4th digit
11,99,77 = 20953266037

20953266037/1 = 20953266037

2351024597175182565196593 >
2085111040804334505879125
 
Last edited:
Dunno, but the algorithm needs work. As the number grows larger, the inaccuracy grows. I can only divide by a max of 1 digit ; |.

Actually if I go through and divide out 2 digits at a time, check it o-o

answer: 23625429475

2351024597175182565196593/
0000000000099512459638625

23/9 = 2 r5
35/9 = 3 r8
5/5 = 1
1/1 = 1


I'll figure something out, but at least I'm on the right track now ^)^.
 
Level 6
Joined
Jun 16, 2007
Messages
235
I have a feeling we are not talking about the same thing.
Do you have a link where I can read about the algorithm you use for making your codes?
 
Level 6
Joined
Jun 16, 2007
Messages
235
How do you get your big number?
By multiplying all the crazy shit you want to remember right?

So instead of doing M = a1*a2*a3*a4*a5*a6
You do K = a1*a2*a3 and L = a4*a5*a6

And weee K and L are square root of magnitude smaller than M.
So now instead of dividing one big mofo you divide two smaller ones.
 
Level 6
Joined
Jun 16, 2007
Messages
235
I see...

Well in that case you are doing it all wrong.
Instead of using jass word size you should be using the size of your alphanumeric code as base for your numbers.

EDIT: (to clarify)
because than you can calculate overflow/carry with normal integer operations since alphanumeric code size is smaller than jass word size.

EDIT2:
not to mention that in that case you would not have to do any base conversions.
 

Dr Super Good

Spell Reviewer
Level 64
Joined
Jan 18, 2005
Messages
27,285
Instead of using jass word size you should be using the size of your alphanumeric code as base for your numbers.
1. Strings leak.
2. Word Size is the number of bits that each component is made of. On x86 systems it is 32 while on x86-64 is 64. Some instructions might even exist to manipulate it at 128 bits at a time (the larger, the more efficient to some extent).
3. JASS has poor string support (no ability to decode a single character to a number nativly). Result is that it is far slower.
4. String are limited to 255 characters, his system supports atleast lengths of over 1000 components of 2^15 (or was it 2^16).
 
Level 6
Joined
Jun 16, 2007
Messages
235
Well in that case you are doing it all wrong.
Was talking to Nestharus here so Dr Super Good got confused.
Btw Dr you don't need to lecture me in general computing, I have BS in computer engineering.

@Nestharus
Why did you pick such a random base?
Going for biggest base that can do multiplication without overflow in jass?
If that is your goal you should use multiple of your alphacode base because in that case you get both size improvement and trivial base conversion.
 
Ok... here is what I'm going to do.


I'm going to change the base to 32768, which happens to be the square root of 2^30. Next, I am going to say that you can only divide by up to 1073709056. If you go over 1073709056, you will overflow ; ). Actually, in some cases, you can divide by up to 2147450880, but those cases are rare ; P.


With this, the division method will be ridiculously fast and very tiny ; P. The modulo method will also be very fast and very tiny ^)^.
 
81900/4

8/4 = 2
First Digit: 2 + Pushed digit (should be 0 for the first) = 2
Push 0,0,0,0 to the next digits

1/4 = 0.25
Second Digit: 0 + Pushed digit (we pushed 0 here) = 0
Push 2,5,0

9/4 = 2.25
Third Digit: 2 + Pushed digit (we pushed 2 here) = 4
Push 2,5

0/4 = 0
Fourth Digit: 0 + Pushed digit (we pushed 7 (2+5)) = 7
Push 0

0/4 = 0
Fifth Digit: 0 + Pushed digit (We pushed 5 here) = 5

81900/4 = 20475

GG :D
 
Status
Not open for further replies.
Top