spare brain required « Next Oldest | Next Newest »

 ▼ hugh steers Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 04-21-2004, 03:32 PM 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. ▼ Nelson M. Sicuro (Brazil) Senior Member Posts: 301 Threads: 28 Joined: Jan 2005 04-21-2004, 03:55 PM 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 Paul Brogger Posting Freak Posts: 1,153 Threads: 94 Joined: Mar 2006 04-21-2004, 04:46 PM 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?) Sam Hughes Junior Member Posts: 14 Threads: 0 Joined: Jan 1970 04-21-2004, 05:06 PM 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.``` John Ioannidis Member Posts: 141 Threads: 35 Joined: Jun 2007 04-21-2004, 05:32 PM 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 ▼ hugh steers Senior Member Posts: 536 Threads: 56 Joined: Jul 2005 04-22-2004, 12:26 PM 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! Renato (Brasil) Junior Member Posts: 31 Threads: 0 Joined: Jan 1970 04-21-2004, 05:47 PM 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: 