From: Tom Burgess <Tom_Burgess AT bc DOT sympatico DOT ca>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: need help handling enormous size arrays
Date: Tue, 04 Feb 1997 23:50:19 -0700
Organization: BCTEL Advanced Communications
Lines: 28
Message-ID: <32F82DAB.7B76@bc.sympatico.ca>
References: <5d916e$c1e AT hecate DOT umd DOT edu>
NNTP-Posting-Host: pntn02m01-21.bctel.ca
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp

Jason Stratos Papadopoulos wrote:
> 
> Hello. I'm writing a homebrew arbitrary precision arithmetic package,
> and was coding up a multiply that uses fast Fourier transforms. Everything
> is nice and fast up to array (of doubles) size 2^14, but from 2^15 on
> the computation time hits a brick wall! Before this point (2^10,11,12,etc)
> a given power of 2 only takes a bit more than twice as long as the one
> before. The program does no memory management, and I need to work with
> array sizes perhaps as large as 2^18 or 2^19.
> 
> Am I not doing somethng vital? My hard drive isn't thrashing so it's
> not a virtual memory problem; For the record, I have 16 megs of ram
> and about 20 or 30 megs of free HD space; I'm using a Win95 DOS box
> for dpmi.
> 
> Please don't flame me for missing the obvious...I'm an amateur at
> high-powered scientific computing.
> 
> Thanks in advance,
> jasonp

Hmm. 2^15 is 32K, times 8 bytes is 262,144 bytes. Typical size of the
level 2 cache on most PCs is 256K or less. Think the FFT is trashing
between slow RAM and cache. I vaguely recall having seen descriptions
of FFTs that are cache-friendly, but would have to dig around. Can
anyone else help?

	regards, tom