Path: utzoo!mnetor!uunet!husc6!linus!alliant!muller
From: muller@Alliant.COM (Jim Muller)
Newsgroups: comp.arch
Subject: Powers of 2, was Re: RISC is a nasty no-no!
Message-ID: <1339@alliant.Alliant.COM>
Date: 3 Mar 88 20:43:06 GMT
References: <17415@think.UUCP>
Reply-To: muller@alliant.UUCP (Jim Muller)
Organization: Alliant Computer Systems, Littleton, MA
Lines: 20

In <17415@think.UUCP> barmar@fafnir.think.com.UUCP (Barry Margolin) writes:

>...What scientific applications naturally map onto
>power-of-two arrays?  I suspect that making arrays a power of two in
>size is a habit mostly of systems programmers, who know to make things
>fit neatly into memory pages in order to reduce paging.

Practically anything involving Fourier Transforms will tend to use
power-of-2-length arrays, since this is required to do FFT's (Fast Fourier
Transforms) - the requirement is built into the algorithm.  Well, okay, it
isn't strictly required, but is generally desirable.  The fields which do
FFT's routinely are anything involving signal or image processing, e.g.
radar, seismic, acoustic, or visual data processing.  (Okay, technically,
it isn't the scientific application itself which maps into a 2**N array,
but the gain in processing speed dictates it, so the effect is the same.)

Also included is practically any subject which deals with wave propagation,
since many problems are easier to solve in wave-number space rather than
in position in x,y,z coordinates.  (Wave-number is the Fourier mapping of
position just as frequency is the Fourier mapping of time.)