Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!amdahl!nsc!taux01!taux02!yuval
From: yuval@taux02.UUCP (Gideon Yuval)
Newsgroups: comp.sources.wanted
Subject: Re: integer FFT ?
Keywords: FFT integer
Message-ID: <36@taux02.UUCP>
Date: 5 Aug 88 18:59:38 GMT
References: <102@skio.UUCP>
Reply-To: yuval@taux02.UUCP (Gideon Yuval)
Organization: National Semiconductor (IC) Ltd, Israel
Lines: 23

In article <102@skio.UUCP> Tom Gross writes:
>I need information about methods to do a Fast Fourier Transform with
>integer arithmetic.  I have heard of a technique called a block integer
>FFT where the range of the integers is kept track of during the FFT so
>that the block can be rescaled to keep within integer ranges.  

If (as you say below) ranges are known in advance, you don't need
block-floating-point (which I presume is what "block integer" refers to).

>ranges can be anticipated in advance.  Speed is essential and error
>checking will be sacrificed.

The obvious way out is to work with FIXED-point numbers (so many bits
integer, so many bits fraction), and then use integer math to fake them out.
This is known as "poor man's floating-point", and a good deal of the
algorithms are exactly those of (H/W or S/W) floating-point systems.

If you can get hold of an Ada compiler, use Ada's fixed-point datatype, and
look at the assembly-code expansion to find out how this faking-out is done.
-- 
Gideon Yuval, yuval@taux01.nsc.com, +972-2-690992 (home) ,-52-522255(work)
 Paper-mail: National Semiconductor, 6 Maskit St., Herzliyah, Israel
                                                TWX: 33691, fax: +972-52-558322
             (alternative E-mail address: decwrl!nsc!taux01!yuval@uunet.uu.net)