On Sat, 18 Apr 2015 20:30:31 +1000, Jasen Betts wrote:

On 2015-04-18, rickman wrote:
On 4/17/2015 10:56 PM, Jasen Betts wrote:
On 2015-04-17, rickman wrote:
On 4/17/2015 7:51 AM, Jasen Betts wrote:

one 16 bit - 7 bit subtract
one 16 bit + 0 bit add with carry.

I'm not following. Are you saying a modulo 65537 operation can be
done
with two adders?

yes.

I appreciate the effort in the drawing, but that isn't needed. Knowing
that you use adders doesn't help me understand how the arithmetic works.
Is there a simple explanation? BTW, what do you do with bit 16 on the
input? Is that a typo? Does it go with the lsbs or the msbs?

It's a typo (or a fence-post error).

this is the arithmetic in c:

// a=a % 65537 in c:

a = a & 0xffff - ( a & ~ 0xffff ) 16;
a = a0 ? a & 0xffff + 1 : a ;


Its an abortive mistake.

It should be mod 2^n i.e. 65536. or 256 or 16 etc

also you don't use a rotation just a left shift. Each left shift by 1 bit
works like a multiply *2 and you don't need to track the carry outs or
MSB's of the shifted number the mod function throws them away anyway.

So to use an adder to multiply by say 5 you have the input number feed
into one input of the adder shifted left by 2 bits - that is 4 x the input
number. Into the other input of the adder you input the original seed - so
4 x the input number plus the input number = 5 x the input number. If the
modulus function is a power of 2 then discarding the right number of MSB's
take care of that - you don't even have to feed them into the adder since
the result will be discarded anyway.

Last if you use the carry in of the least significant adder as a + 1
function then a simple LCG takes one adder only (excluding latches you
might need to avoid race issues)