spare brain required



#8

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.


#9

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

#10

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?)

#11

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.

#12

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


#13

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!

#14

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


Possibly Related Threads...
Thread Author Replies Views Last Post
  HP9810A and HP9862A - ROM required? Thomas Falk 0 791 12-07-2013, 09:49 PM
Last Post: Thomas Falk
  Broken HP-97 to spare? davorin 3 1,021 08-29-2013, 01:08 AM
Last Post: davorin
  OT: My brain is failing me again. Help with numerical / mechanical problem required. Harald 4 1,138 07-01-2013, 10:31 AM
Last Post: Harald
  HP-65 logic board repair - help required Alberto Fenini 1 737 02-17-2013, 06:39 PM
Last Post: John Robinson
  Help with geometry problem required Harald 39 5,281 01-22-2013, 10:21 AM
Last Post: Walter B
  [WP 34S] New GCC - Testing required Marcus von Cube, Germany 3 922 01-07-2013, 01:59 PM
Last Post: Marcus von Cube, Germany
  WP 34S: Some testing required Marcus von Cube, Germany 27 4,587 10-15-2011, 11:15 AM
Last Post: Marcus von Cube, Germany
  the HP-65 required more from the user Don Shepherd 10 1,723 08-05-2011, 01:28 PM
Last Post: Don Shepherd
  Brain dead, need help with program briggleman 7 1,218 11-16-2010, 01:13 PM
Last Post: Michael Meyer
  Spare Part Needs - Spice Series Battery Cover - More aj04062 11 1,779 04-27-2010, 07:31 PM
Last Post: aj04062

Forum Jump: