Re: Any progress yet? (was Re: Fast pi program?)

On Aug 30, 7:11 pm, "Alf P. Steinbach" <al...@xxxxxxxx> wrote:
....
http://www.mediafire.com/download.php?5ryt5g4mcyo
....

I clicked on the URL above, and it produced

"The quickkey you provided for file download was invalid. This is
usually caused because the file is no longer stored on Mediafire. This
occurs when the file is removed by the originating user or Mediafire."


Darn, I posted the wrong link!!!

This is what it should be:

http://www.mediafire.com/download.php?9mzltzjyizn

Try that one.

Anyway, the way to optimize programs is (1) measure, (2) if optimization
is then deemed necessary, first think about using better algorithms
(this includes e.g. changing in-place instead of copying and creating
values), and only secondly if at all, micro-optimizations such as trying
to make loops fit in processor cache, thinking about page loading (you
don't want the program to hop all over memory, but more localized and
preferentially address-sequential access), and so on.


Well, I measured it using GNU's profiler for a 1M digit run, and found
out
much of the time was going into the long multiplication area of the
program, where all the Fast Fourier transform/Number theoretic
transform
stuff is. I've tried going over that several times and haven't had
much
luck yet. Is there any way to cut down perhaps on the number or
size of multiplications required? Or perhaps to optimize the
multiplication
routines themselves, including the FFT/NTT code? What would you
suggest, based on what you can see from the source code?

Cheers, & hth.,

- Alf

.