HP Forum Archive 14

[ Return to Index | Top of Index ]

spare brain required Message #1 Posted by hugh steers on 21 Apr 2004, 3:32 p.m. does anyone know a neat way to calculate a*b mod 2^r on a calculator? where a & b are integers < 2^r. let's say i set c = 2^r and do a*b mod c on a 10 digit machine. is there some way to recover the lost remainder that might shift off the low digits? the other way would be to write some sort of double precision subroutine. this would work but could be horribly slow. any ideas appreciated.

Re: spare brain required Message #2 Posted by Nelson M. Sicuro (Brazil) on 21 Apr 2004, 3:55 p.m., in response to message #1 by hugh steers There is an easy way to do the 2^n mod, in assembler, with some bit-shifting by n bits to the right. The bits that "pops" out on the right (LSBs) you can save to use as the reminder right-shifting them on another register. Please correct me if I'm wrong. Best regards, Nelson

Re: spare brain required Message #3 Posted by Paul Brogger on 21 Apr 2004, 4:46 p.m., in response to message #1 by hugh steers Repeatedly subtract c from a*b until the remainder is less than c. The remainder is then, by definition, a*b mod c. ( . . . or am I missing something?)

Re: spare brain required Message #4 Posted by Sam Hughes on 21 Apr 2004, 5:06 p.m., in response to message #1 by hugh steers I am not sure which calulator you intend to use, so use this Q-BASIC program of mine for inspiration: 10 INPUT "n1: ", n1 20 INPUT "n2: ", n2 30 INPUT "r: ", r 40 LET s = 0 50 LET k = r 60 LET s = (s + (((n1 MOD 2) * n2) MOD (2 ^ k)) * (2 ^ (r - k))) MOD (2 ^ r) 70 LET n1 = INT(n1 / 2) 80 LET k = k - 1 90 IF k > 0 THEN GOTO 60 100 PRINT s How it works: Suppose its inputs were 23, 58, and 6. Thus, you're multiplying 010111 by 111010 (in binary), mod 1000000. Normal binary multiplication 010111 x111010 111010 <- bottom number multiplied by top's ones column 111010 <- ... multiplied by top's twos column 111010 <- ... by fours column 000000 <- by eights column 111010 <- by sixteens column 000000 <- by 32 column xxxxxxxxxxx <- these columns are added to get some sum. Binary multiplication mod 64: 010111 x111010 111010 <- bottom number multiplied by top's ones column (mod 64) 11010 <- ...etc... (mod 32) 1010 <- mod 16 000 <- mod 8 10 <- mod 4 0 <- mod 2 xxxxxx <- the columns are added to get some sum. - In calculating the sum, the program adds the row into a cumulative sum and takes the result mod (2^r) each time.

I assume you need an answer for when 2^r is near the calculator's precision Message #5 Posted by John Ioannidis on 21 Apr 2004, 5:32 p.m., in response to message #1 by hugh steers for an ordinary calculator with 10 decimal digits of precision (a tad more than 33 bits), you don't have a problem if both a and b are < 2^16; the trick is how to do this when a and b are more than five decimal digits and still not lose precision. wlg, assume that r is even, r <= 32, and a, b < 2^r; a and b are at most 32 bits long rewrite a and b as a1 * 2^(r/2) + a0 and b1 * 2^(r/2) + b0, where a1 = int(a / 2^(r/2)) and a0 = a mod 2^(r/2). a0, a1, b0, b1 are at most 16 bits long then a*b becomes a1*b1*2^r = (a1*b0 + a0*b1) * 2^(r/2) + a0*b0. and a*b mod 2^r becomes: (((a1*b0 + a0*b1 ) mod 2^(r/2)) * 2^(r/2) + a0*b0 ) mod 2^r the partial products are at most 32 bits long, and at no point do the partial sums exceed 33 bits, so it all fits in a standard 10-digit calculator. I hope you don't really need that translated into RPN! /ji

Re: I assume you need an answer for when 2^r is near the calculator's precision Message #6 Posted by hugh steers on 22 Apr 2004, 12:26 p.m., in response to message #5 by John Ioannidis thanks very much, all, for your help. john is right. the problem i have is indeed when 2^r is near the calculator's precision, and the calculator is decimal. on a binary computer, i simply do; a*b AND (2^r-1) where a & b are machine integers. when wordsize is 32 (r < 32), the overlow == 0 (mod 2^r) anyway. that's the logic i already have, but i need it to work on a calculator (hp41c in this case). john's way is what i have to do. i dont think there's any special trick to exploit with 2^r. this is the bit i needed: (a1*b0 + a0*b1)*2^r/2 mod 2^r = (((a1*b0 + a0*b1) mod (2^r/2)) * 2^r/2) mod 2^r as pointed out, it doesnt overflow. thanks!

Re: spare brain required Message #7 Posted by Renato (brasil) on 21 Apr 2004, 5:47 p.m., in response to message #1 by hugh steers The remainder can be recovered as c * (frac(a*b / c)). Maybe you could set c = 100000 * 2^r . This would get you with a 5 digits remainder- just remember to divide by 100000. I am not sure if this is useful, maybe with some more information about the usage, I might help a bit more. Renato

[ Return to Index | Top of Index ]

Go back to the main exhibit hall