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

[Gerson W. Barbosa]

HP 50g version:

Code:


%%HP: T(3)A(R)F(.);
\<< DUP2 SIZE OBJ\-> DROP SWAP SIZE OBJ\-> DROP DUP2 MAX UNROT + 4 ROLLD LN 2 LN / DUP FP NOT NOT SWAP IP + 2 SWAP ^ DUP + DUP ROT SWAP 1 \->LIST RDM UNROT 1 \->LIST RDM FFT SWAP FFT HADAMARD IFFT AXL 1 ROT SUB RE 0 RND REVLIST DUP SIZE 1 - 1 SWAP
  FOR i i GETI ROT ROT GETI NIP ROT OVER 10000 MOD + OVER 10000 / IP OVER 10000 / IP + SWAP 10000 MOD ROT DROP SWAP UNROT i SWAP PUTI ROT PUTI DROP
  NEXT REVLIST AXL
\>>

[ 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. ]

[ 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. 1234. 5678. 9012. 3456. ]

<< FFTMULT>> TEVAL -->

[ 152. 4157. 8753. 2388. 2031. 7024. 9644. 8712. 3910. 9892. 536. 5036. 5790. 2759. 1428. 1360. 7669. 5626. 2319. 7684. 9548. 8493. 3211. 4009. 1428. 1360. 4103. 333. 3307. 4227. 4994. 6657. 5186. 7094. 5886. 2981. 7065. 9961. 6777. 9305. 8945. 2828. 7669. 5630. 824. 5695. 8561. 1954. 2703. 8562. 9452. 8278. 4583. 1430. 344. 4602. 6462. 4297. 1236. 926. 8341. 7164. 2127. 7250. 9916. 1715. 5512. 8798. 8036. 8848. 4621. 2474. 6157. 5981. 3729. 6150. 4278. 3114. 2837. 9826. 2399. 247. 1946. 3502. 519. 7380. 1054. 7177. 8640. 4513. 163. 853. 6761. 1645. 9271. 4529. 4881. 8778. 8379. 8205. 3002. 5911. 7488. 1881. 1123. 3044. 6596. 5556. 9244. 177. 5704. 9232. 7364. 7310. 4813. 2908. 5485. 4443. 3921. 6584. 3606. 1576. 3030. 260. 1726. 8709. 2138. 3936. ]

s:41.0499

The version using <<*>> DOLIST instead of HADAMARD for element by element vector multiplication is about 2 seconds faster for numbers this size, despite vector to list to vector conversions. At this point double input sizes imply in triple running times, which is strange. Sure the final part needs more optimization, but I don't see why this behavior occurs.