FFT Multiplication (HP-48G/GX/G+)

[Gerson W. Barbosa]

(02-10-2014 09:25 PM)Gerson W. Barbosa Wrote:  . My HP-48GX is about 50% slower than the HP-71B when multiplying two 512-digit numbers (173 seconds versus 117 seconds).

Two 256-digit numbers, actually, giving a 512-digit result. Sorry for the mistake.

(02-10-2014 09:25 PM)Gerson W. Barbosa Wrote:  However, I've found a discrepancy in this example:

{ 1234 5678 9012 } { 3456 7890 } FFTMULT -->

{ 426 7639 7023 2002 4680 }

This should be fixed by inserting the following instructions between RE and IP in the code above, at the end of the second line after the IFFT command:

Code:


1
\<< .00005 +
\>> DOSUBS

More tests have to be made, though.

P.S.: .05 is better. No problem with 640-digit results (128 groups of 5 digits, constants replaced with 100,000), at least for the few examples I tried.

P.P.S.: Replacing RE IP with RE 0 RND is even better. Actually that's what should've been done in the first place if somehow I hadn't mistaken IROUND with IP. Since the HP-48 built-in IFFTis more accurate than the implementation using FOUR on the HP-71B it is possible groups of 5 digits rather than 4 can be used for up to 1000-digit results. A few empirical tests, as described in the last page of Valentin's article, should be made before we can be sure, however. Here is the fixed code:

Code:


%%HP: T(3)A(D)F(.);
\<< DUP2 SIZE SWAP
SIZE + ROT ROT DUP2
SIZE SWAP SIZE DUP2
MAX LN 2 LN / DUP
FP NOT NOT SWAP IP
+ 2 SWAP ^ DUP +
ROT OVER - NEG ROT
ROT - NEG ROT ROT 1
SWAP
  START 0 +
  NEXT SWAP ROT 1
ROT
  START 0 +
  NEXT OBJ\-> 1 \->LIST
\->ARRY FFT OBJ\-> 1
GET \->LIST SWAP OBJ\->
1 \->LIST \->ARRY FFT
OBJ\-> 1 GET \->LIST
  \<< *
  \>> DOLIST OBJ\-> 1
\->LIST \->ARRY IFFT
OBJ\-> 1 GET \->LIST 1
ROT SUB RE 0 RND
REVLIST DUP SIZE 1
- 1 SWAP
  FOR i i GETI ROT
ROT GETI SWAP DROP
ROT OVER 10000 MOD
+ OVER 10000 / IP
OVER 10000 / IP +
SWAP 10000 MOD ROT
DROP SWAP ROT ROT i
SWAP PUTI ROT PUTI
DROP
  NEXT REVLIST
\>>