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
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

- Raw text -