Marc:
I've included below two files that I hope will eventually replace the fft bignum multiplication routines in _num.scm. (The advantage of the new approach is that it is provably correct; I'm waiting to see if there are any disadvantages.)
The main loops in direct-fft-recursive and inverse-fft-recursive are scheduled to take 122 and 96 cycles, respectively, on my G5 using CC='gcc -mcpu=970 -m64' with the official Apple gcc 4.0.1; most of the time is taken in constantly reloading W and a from the stack. (You can find this information by passing -dR to gcc. BTW, why does b21 erase the .c file after compiling something with -dynamic? It's almost as if you're embarrassed by the C code that gsc generates ;-) If the number of registers are increased so that W and a are kept in registers, then these two loops are each scheduled in about 31 cycles, the same as a hand rewrite of the code in C.
Please see whether some type of SSA form for GVM variables used in a basic block improves performance the same way that generating SSA- type code for F64 variables in each basic block helped the floating- point code.
Some trivial timing comparisons with the existing code are given below. I hope that when I'm done the new code will be faster than the old. (For example, the new code is more "cache-oblivious" than the old.)
Brad
[descartes:~/programs/gambc40b17/fftmul] lucier% gsc -:m100000 Gambit Version 4.0 beta 21
(load "fftmul-fast")
"/Users/lucier/programs/gambc40b17/fftmul/fftmul-fast.o2"
(define a (expt 3 10000000)) (define b (expt 3 10000000)) (define c (time (* a a)))
(time (* a a)) 2193 ms real time 2090 ms cpu time (1948 user, 142 system) 1 collection accounting for 22 ms real time (3 user, 19 system) 110229552 bytes allocated no minor faults no major faults
(define d (time (fft-mul a a)))
(time (fft-mul a a)) 2621 ms real time 2431 ms cpu time (2203 user, 228 system) 1 collection accounting for 44 ms real time (4 user, 40 system) 112555696 bytes allocated no minor faults no major faults
(define e (time (* a b)))
(time (* a b)) 3659 ms real time 3002 ms cpu time (2777 user, 225 system) 1 collection accounting for 77 ms real time (3 user, 74 system) 171743360 bytes allocated no minor faults no major faults
(define f (time (fft-mul a b)))
(time (fft-mul a b)) 4007 ms real time 3585 ms cpu time (3219 user, 366 system) 1 collection accounting for 64 ms real time (3 user, 61 system) 183596720 bytes allocated no minor faults no major faults
(= c d)
#t
(= e f)
#t