Import Upstream version 3a1upstream/3a1

1 files changed, 34 insertions, 10 deletions

diff --git a/fft.scm b/fft.scm
index 9537e9c..2257e30 100644
--- a/fft.scm
+++ b/fft.scm
@@ -1,5 +1,5 @@
 ;;;"fft.scm" Fast Fourier Transform
-;Copyright (C) 1999 Aubrey Jaffer
+;Copyright (C) 1999, 2003 Aubrey Jaffer
 ;
 ;Permission to copy this software, to modify it, to redistribute it,
 ;to distribute modified versions, and to use it for any purpose is
@@ -8,7 +8,7 @@
 ;1.  Any copy made of this software must include this copyright notice
 ;in full.
 ;
-;2.  I have made no warrantee or representation that the operation of
+;2.  I have made no warranty or representation that the operation of
 ;this software will be error-free, and I am under no obligation to
 ;provide any services, by way of maintenance, update, or otherwise.
 ;
@@ -28,14 +28,13 @@
 ;;; differs in the direction of rotation of the complex unit vectors.
 
 (require 'array)
+(require 'logical)
 
-(define (fft:shuffled&scaled ara n scale)
+;;@code{(require 'fft)}
+;;@ftindex fft
+
+(define (fft:shuffle&scale new ara n scale)
   (define lgn (integer-length (+ -1 n)))
-  (define new (apply make-array 0 (array-dimensions ara)))
-  (define bit-reverse (lambda (width in)
-			(if (zero? width) 0
-			    (+ (bit-reverse (+ -1 width) (quotient in 2))
-			       (ash (modulo in 2) (+ -1 width))))))
   (if (not (eqv? n (expt 2 lgn)))
       (slib:error 'fft "array length not power of 2" n))
   (do ((k 0 (+ 1 k)))
@@ -61,10 +60,35 @@
 	    (array-set! ara (+ u t) k)
 	    (array-set! ara (- u t) k+m/2)))))))
 
+;;@args array
+;;@var{array} is an array of @code{(expt 2 n)} numbers.  @code{fft}
+;;returns an array of complex numbers comprising the
+;;@dfn{Discrete Fourier Transform} of @var{array}.
 (define (fft ara)
   (define n (car (array-dimensions ara)))
-  (dft! (fft:shuffled&scaled ara n 1) n 1))
+  (define new (apply create-array ara (array-dimensions ara)))
+  (dft! (fft:shuffle&scale new ara n 1) n 1))
 
+;;@args array
+;;@code{fft-1} returns an array of complex numbers comprising the
+;;inverse Discrete Fourier Transform of @var{array}.
 (define (fft-1 ara)
   (define n (car (array-dimensions ara)))
-  (dft! (fft:shuffled&scaled ara n (/ n)) n -1))
+  (define new (apply create-array ara (array-dimensions ara)))
+  (dft! (fft:shuffle&scale new ara n (/ n)) n -1))
+
+;;@noindent
+;;@code{(fft-1 (fft @var{array}))} will return an array of values close to
+;;@var{array}.
+;;
+;;@example
+;;(fft '#(1 0+i -1 0-i 1 0+i -1 0-i)) @result{}
+;;
+;;#(0.0 0.0 0.0+628.0783185208527e-18i 0.0
+;;  0.0 0.0 8.0-628.0783185208527e-18i 0.0)
+;;
+;;(fft-1 '#(0 0 0 0 0 0 8 0)) @result{}
+;;
+;;#(1.0 -61.23031769111886e-18+1.0i -1.0 61.23031769111886e-18-1.0i
+;;  1.0 -61.23031769111886e-18+1.0i -1.0 61.23031769111886e-18-1.0i)
+;;@end example