Re: Pi program and hard disk usage
- From: user923005 <dcorbit@xxxxxxxxx>
- Date: Fri, 28 Sep 2007 11:44:48 -0700
On Sep 27, 8:40 pm, mike3 <mike4...@xxxxxxxxx> wrote:
On Sep 27, 4:10 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Sep 27, 12:39 pm, mike3 <mike4...@xxxxxxxxx> wrote:
On Sep 27, 12:50 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Sep 27, 12:14 am, mike3 <mike4...@xxxxxxxxx> wrote:
On Sep 24, 12:57 pm, user923005 <dcor...@xxxxxxxxx> wrote:
On Sep 22, 4:45 pm,mike3<mike4...@xxxxxxxxx> wrote:<snip>
I think Mr. Harter's (IIRC) suggestion is going to be pretty near to
optimal. You might improve it a bit with LRU cacheing or something,
but no matter what you do you will be waiting on the disk. I think
that also is plainly obvious.
However there must, must be some way that those really fast
pi programs like PiFast, QuickPi, etc. manage to do huge runs
that are too big to fit in RAM so fast. How do they do it? Any
ideas?
I guess that they figured out a way to do it so everything they
operate on fits in RAM.
If you use disk, you slow down by a factor of 300,000. Since they
don't seem horribly slow, we can assume that they are not using disk
for RAM.
Maybe you have more temporary variables than they do.
However it seems that, at least with PiFast, disk memory
is used. But they must have found a way to economize the
amount of access to the disk.
The problem I'm having with my program is that I cannot
fit a large enough Fast Fourier Transform (FFT) (actually
"Number Theoretic Transform" or NTT) to do the entire
128 megs of base 26 digits multiplication in RAM, all at
once. So I'm using a Karatsuba "divide and conquer"
O(n^1.585) approach to break up the large multiplication
into smaller ones that will fit in RAM. How could one
implement this as efficiently as possible when the numbers
are stored on disk, ie. minimize the amount of disk
access as much as possible?
Kratsuba is actually a good idea for disk based use, because it
operates on blocks of the numbers (you would not have to load the
whole number into memory -- just the pieces you are working on).
Because disk will be so dominant, it might even be better to use
*schoolbook*.
You mean a "big digit" multiplication? That's a thought, but it
needs more FFTs since the growth is larger (O(n^2) instead of
O(n^lg(3)) (here "lg" is base-2 log)). For the Karatsuba method,
you need 3 half-length multiplications. For the grade-school "big
digit" method you need 4. For where only a quarter-length multiply
will fit, Karatsuba needs 9 and big digit need 16.
Any suggestions though on how to do it in such a way as to
minimize the amount of disk operations as much as possible?
To minimize disk access, load only the pieces that actually
participate in a given phase of the multiplication into memory. So
you do not load either original number or any partial product into
memory as a complete number. Just load the hunks that directly
participate in the given phase of multiplication from the first number
and the second and only create partial product storage large enough to
hold the intermediate results.
.
- Follow-Ups:
- Re: Pi program and hard disk usage
- From: mike3
- Re: Pi program and hard disk usage
- References:
- Pi program and hard disk usage
- From: mike3
- Re: Pi program and hard disk usage
- From: user923005
- Re: Pi program and hard disk usage
- From: mike3
- Re: Pi program and hard disk usage
- From: user923005
- Re: Pi program and hard disk usage
- From: mike3
- Re: Pi program and hard disk usage
- From: user923005
- Re: Pi program and hard disk usage
- From: mike3
- Pi program and hard disk usage
- Prev by Date: Re: Free E-BOOKS!!
- Next by Date: Re: program made in delphi
- Previous by thread: Re: Pi program and hard disk usage
- Next by thread: Re: Pi program and hard disk usage
- Index(es):
Relevant Pages
|
