### Thread: Help Implementing Newton-Raphson Division

Page 2 of 2 First 12
1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2013
Posts
11
Rep Power
0

#### Silly me.........

I forgot to tell you what machine I did the speed tests on. My desktop here at home is a dual core 2.4 GHz AMD Athlon computer with 2 gigs of DDR2-RAM clocked at 266 MHz.
2. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2009
Posts
191
Rep Power
54
That's pretty cool! Your topic has been educational for me. I've long applied Newton-Raphson to square root computation (which has even better than quadratic convergence!), but it never came to my thinking it could be applied to speed up division.

About the off-by-one errors in the quotient: I haven't done the analysis, but my intuition is that it may only be in one direction. There may be some very simple refinement to the iteration that can cure it completely.

But in any case, we know that the remainder must fall in the interval from 0 to one less than the divisor, so a very few lines of code could be used to test for and correct such quotient errors; the added execution time due to this correction should be small.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
Mar 2013
Posts
11
Rep Power
0

#### Got some more speed tests for ya

Hi there. Its been a while. I was looking through our conversation and saw that you asked for speed tests on various sized inputs of the two algorithms. So, I decided to go ahead and do that for you. I compared the two algorithms by starting off with 2^32 / 3 and incremented the exponent on the power of 2 by 32 each time until it got to 1024, each time performing the division 50 times. After the program finished running these were the results:

Now performing 2^32 / 3 fifty times with old division algorithm...completed in 0.2820 seconds.
Now performing 2^64 / 3 fifty times with old division algorithm...completed in 0.5780 seconds.
Now performing 2^96 / 3 fifty times with old division algorithm...completed in 0.8590 seconds.
Now performing 2^128 / 3 fifty times with old division algorithm...completed in 1.1410 seconds.
Now performing 2^160 / 3 fifty times with old division algorithm...completed in 1.4220 seconds.
Now performing 2^192 / 3 fifty times with old division algorithm...completed in 1.7180 seconds.
Now performing 2^224 / 3 fifty times with old division algorithm...completed in 1.9850 seconds.
Now performing 2^256 / 3 fifty times with old division algorithm...completed in 2.2810 seconds.
Now performing 2^288 / 3 fifty times with old division algorithm...completed in 2.5780 seconds.
Now performing 2^320 / 3 fifty times with old division algorithm...completed in 2.8280 seconds.
Now performing 2^352 / 3 fifty times with old division algorithm...completed in 3.1250 seconds.
Now performing 2^384 / 3 fifty times with old division algorithm...completed in 3.4220 seconds.
Now performing 2^416 / 3 fifty times with old division algorithm...completed in 3.7030 seconds.
Now performing 2^448 / 3 fifty times with old division algorithm...completed in 3.9850 seconds.
Now performing 2^480 / 3 fifty times with old division algorithm...completed in 4.2810 seconds.
Now performing 2^512 / 3 fifty times with old division algorithm...completed in 4.5620 seconds.
Now performing 2^544 / 3 fifty times with old division algorithm...completed in 4.8440 seconds.
Now performing 2^576 / 3 fifty times with old division algorithm...completed in 5.1410 seconds.
Now performing 2^608 / 3 fifty times with old division algorithm...completed in 5.4220 seconds.
Now performing 2^640 / 3 fifty times with old division algorithm...completed in 5.7030 seconds.
Now performing 2^672 / 3 fifty times with old division algorithm...completed in 6.0000 seconds.
Now performing 2^704 / 3 fifty times with old division algorithm...completed in 6.2970 seconds.
Now performing 2^736 / 3 fifty times with old division algorithm...completed in 6.5620 seconds.
Now performing 2^768 / 3 fifty times with old division algorithm...completed in 6.8910 seconds.
Now performing 2^800 / 3 fifty times with old division algorithm...completed in 7.1720 seconds.
Now performing 2^832 / 3 fifty times with old division algorithm...completed in 7.4370 seconds.
Now performing 2^864 / 3 fifty times with old division algorithm...completed in 7.7810 seconds.
Now performing 2^896 / 3 fifty times with old division algorithm...completed in 8.0320 seconds.
Now performing 2^928 / 3 fifty times with old division algorithm...completed in 8.3120 seconds.
Now performing 2^960 / 3 fifty times with old division algorithm...completed in 8.5940 seconds.
Now performing 2^992 / 3 fifty times with old division algorithm...completed in 8.8910 seconds.
Now performing 2^1024 / 3 fifty times with old division algorithm...completed in 9.1870 seconds.

Now performing 2^32 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.1560 seconds.
Now performing 2^64 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.2190 seconds.
Now performing 2^96 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.2030 seconds.
Now performing 2^128 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.2660 seconds.
Now performing 2^160 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.2650 seconds.
Now performing 2^192 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.2660 seconds.
Now performing 2^224 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.2810 seconds.
Now performing 2^256 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4380 seconds.
Now performing 2^288 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4370 seconds.
Now performing 2^320 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4380 seconds.
Now performing 2^352 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4370 seconds.
Now performing 2^384 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4530 seconds.
Now performing 2^416 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4380 seconds.
Now performing 2^448 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4530 seconds.
Now performing 2^480 / 3 fifty times with Newton-Raphson division algorithm...completed in 0.4380 seconds.
Now performing 2^512 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0000 seconds.
Now performing 2^544 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0150 seconds.
Now performing 2^576 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0160 seconds.
Now performing 2^608 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0000 seconds.
Now performing 2^640 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0150 seconds.
Now performing 2^672 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0160 seconds.
Now performing 2^704 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0310 seconds.
Now performing 2^736 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0160 seconds.
Now performing 2^768 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0160 seconds.
Now performing 2^800 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0310 seconds.
Now performing 2^832 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0310 seconds.
Now performing 2^864 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0310 seconds.
Now performing 2^896 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0320 seconds.
Now performing 2^928 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0460 seconds.
Now performing 2^960 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0320 seconds.
Now performing 2^992 / 3 fifty times with Newton-Raphson division algorithm...completed in 1.0470 seconds.
Now performing 2^1024 / 3 fifty times with Newton-Raphson division algorithm...completed in 3.1400 seconds.

So, that's how it turned out. Thought you'd like to see the results on various sized inputs. Hey, you think you could explain how Montgomery modular exponentiation works? And how to incorporate that little trick with dividing the exponent into a sequence of 4-bit groups? Again, thanks for all your help!
Page 2 of 2 First 12