mersenneforum.org Correct way to compute the 64bit residue
 Register FAQ Search Today's Posts Mark Forums Read

 2017-05-24, 09:06 #1 preda     "Mihai Preda" Apr 2015 32×151 Posts Correct way to compute the 64bit residue Hi, I would like to ask for confirmation about the correct way to compute the residue. Let's consider this simplified example: N words. bits-per-word == 10 everywhere. In non-balanced representation ("wnb"), word values are 0 everywhere except: wnb[N-2] == 1023 wnb[N-1] == 1023 In balanced representation ("wb"), this becomes 0 everywhere except: wb[N-2] == -1 wb[N-1] == 0 wb[0] == 1. In this situation, should the 64bit residue be 1 or 0? Thanks!
2017-05-24, 09:20   #2
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

13×491 Posts

Quote:
 Originally Posted by preda Hi, I would like to ask for confirmation about the correct way to compute the residue. Let's consider this simplified example: N words. bits-per-word == 10 everywhere. In non-balanced representation ("wnb"), word values are 0 everywhere except: wnb[N-2] == 1023 wnb[N-1] == 1023 In balanced representation ("wb"), this becomes 0 everywhere except: wb[N-2] == -1 wb[N-1] == 0 wb[0] == 1. In this situation, should the 64bit residue be 1 or 0? Thanks!
I believe the residue should be 0 - it is defined as the actual numeric value of the output from the final LL iteration, modulo 2^64.

2017-05-24, 10:11   #3
preda

"Mihai Preda"
Apr 2015

32·151 Posts

Quote:
 Originally Posted by fivemack I believe the residue should be 0 - it is defined as the actual numeric value of the output from the final LL iteration, modulo 2^64.
Yep I agree.

2017-05-24, 21:22   #4
ewmayer
2ω=0

Sep 2002
República de California

7·11·151 Posts

Quote:
 Originally Posted by preda Hi, I would like to ask for confirmation about the correct way to compute the residue.
Here is the comment from the Res64 function in my code - this precedes a downward loop starting with the high residue word which inits the carry as described and exits said loop as soon as a nonzero residue word is found:

/*
If most-significant digit in the balanced-representation form is < 0, add the modulus to the residue.
For Mersenne (2^p-1) and Fermat (2^p+1) moduli, can combine this with the normalize-to-nonnegative-digit
step (which we do in any event) by simply initializing the carry into the latter to -1 or +1, respectively:
*/

Once the carry has been set thusly, we feed it into an upward loop starting from the low residue word, which does several things at once:

o On-the-fly normalizes each word to nonnegative-digit representation (taking account of the IBDWT's variable wordsize, obviously);
o propagates the resulting carries upward;
o counts #bits accumulated and exits when this is >+ 64.

In your example, loop 1 would set cy = -1, which would cancel the low-word 1 in the first pass of loop 2, yielding 0.

 2017-05-24, 21:57 #5 preda     "Mihai Preda" Apr 2015 32×151 Posts Yes, everything is clear now, thank you!

 Similar Threads Thread Thread Starter Forum Replies Last Post jpalo GPU Computing 8 2017-08-06 15:35 laich2 PrimeNet 6 2012-01-16 04:51 jasong Linux 2 2007-10-18 23:40 Washuu Math 3 2005-05-25 09:04 lpmurray Lounge 4 2005-02-09 10:38

All times are UTC. The time now is 02:41.

Thu May 6 02:41:19 UTC 2021 up 27 days, 21:22, 0 users, load averages: 3.30, 2.98, 2.88