Correct way to compute the 64bit residue

[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!

[fivemack]

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.

[preda]

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.

[ewmayer]

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.

[preda]

Yes, everything is clear now, thank you!