mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Software

Reply
 
Thread Tools
Old 2017-05-24, 09:06   #1
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

101001100002 Posts
Default 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!
preda is online now   Reply With Quote
Old 2017-05-24, 09:20   #2
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

Quote:
Originally Posted by preda View Post
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.
fivemack is offline   Reply With Quote
Old 2017-05-24, 10:11   #3
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

24·83 Posts
Default

Quote:
Originally Posted by fivemack View Post
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.
preda is online now   Reply With Quote
Old 2017-05-24, 21:22   #4
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
Rep├║blica de California

23×1,229 Posts
Default

Quote:
Originally Posted by preda View Post
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.
ewmayer is offline   Reply With Quote
Old 2017-05-24, 21:57   #5
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

24×83 Posts
Default

Yes, everything is clear now, thank you!
preda is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
CudaLucas correct config jpalo GPU Computing 8 2017-08-06 15:35
How to manually correct CPU GHz in prime net laich2 PrimeNet 6 2012-01-16 04:51
Are these commands correct? jasong Linux 2 2007-10-18 23:40
correct me. Washuu Math 3 2005-05-25 09:04
ARE THE ODDS CORRECT..Please help lpmurray Lounge 4 2005-02-09 10:38

All times are UTC. The time now is 21:00.

Fri Nov 27 21:00:00 UTC 2020 up 78 days, 18:10, 3 users, load averages: 1.52, 1.32, 1.30

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.