Anybody have any code that gives a representation of the distribution of primes rather than just giving the nth prime.


that might be something worth working on.

Posted on 2003-08-15 19:23:32 by IwasTitan
Iwabee: the point is that until the BBP was discovered, all known methods for calculating pi required all the preceding digits to be computed.

Hagen: if your program can calculate 1 million digits in 15 seconds, you should post it on Stu's Pi Page:

15 seconds will place your program as the 3rd fastest of all the programs that are listed in that website.
Posted on 2003-08-16 00:59:16 by PiGeek
Yes, more exactly it have follow performances

timings on P4 1500Mhz 512Mb, Win2k

decimals : seconds
1000000 : 13.77
2000000 : 33.26
2500000 : 46.40
4000000 : 82.07
5000000 : 121.13
8000000 : 198.16
16000000 : 483.48
32000000 : 1151.34
64000000 : 3288.20

But I'am never aware of the fact to be so fast, because it was only a small mind training for me and never designed to get a world ranking. Now I must take first a look onto Stu's Pi pages again.
If you are interessted the essential Pi algorithm use only about 40 Lines Source and i used it to check the correctness of my Sch?nhage Strassen FFT Multiplication, thats all :)

Thank you for this hint. Hagen
Posted on 2003-08-16 19:05:23 by Hagen
Hagen: If you can get your timing down to 8 seconds for 1 million digits, then your program would be the fastest on Stu's website. I suppose you have checked the outputs of your program and the digits are correct?!
Posted on 2003-08-17 01:35:10 by PiGeek
Yes, the computation are correct, that is a need to use it as Bug-Detection for other algorithms, such as FFT Multiplications. And the goal was hit, then with my Pi algorithms i found two very difficult Bit overflow errors in the FFT.
In fact I have implemented 5 diffierent Pi Algorithms. Chudnovsky with BinarySplitting, iterative Chudnovsky, AGM, Machin (ArcTan) with BinarySplitting and iterative Machin.

But now I think about to get out my reserves in the algorithms, then there exists a lot. As i implemented my algorithms I supposed it can be optimized about 2-2.5 times to be faster. Never i developed my Pi algos. to be fast as possible, only to get a universal and slightly fast librarary (nobody of cryptographers need such a fast library in this range of numbers :)

The BinarySplitting stage runs in 8 seconds and the preprocessing in 5 seconds. Xavier's Algo. need 6 seconds for the BinarySplitting and only 1 seconds for the preprocessing. So I have to optimize the preprocessing stage from 5 secs downto 8/6 = 1.3 seconds. Then I get about 9.3 seconds. I suppose Xavier use another algorithm to do the preprocessing faster. Currently my implementation use none special optimized algorithms, means only plain Chudnovsky such as it is. All other optimization must be made deeper on low level algorithms. As example my FFT Code don't use SSE2. With my other SSE2 assembler code i get 2 times faster algorithms. Because the FFT ist the most time cost process i think it could be with SSE2 >1.5 times speedup. So I suppose to get 9.3 / 1.5 ~< 6 seconds for 1M digits. That's possible. 6 seconds / 1600Mhz * 1500Mhz = 5.6 seconds time estimate from 1.6GHz CPU to my 1.5GHz P4.

But currently I asked me what i realy get with such hard working.

Best Regards, Hagen

PS, Ah, on 100k Digits I'm currently faster as Xavier's Pi code. It runs in 0.57 seconds, Xavier's need 1.1 secs and Steve's need 0.67 seconds. This show very good that I have optimized my libraray for smaller numbers that's most often needed for cryptographical applications.
Posted on 2003-08-17 05:31:37 by Hagen
Hagen: What do you get? The satisfaction that, for the moment, your program is the fastest in the "world."
Posted on 2003-08-17 13:58:06 by PiGeek
Hm, not enough for me.
Suppose it is the fastest one, the next question of a potential user is how he/s can compute 250M digits of Pi, and then I should rewrite all my source to support fast disk swapping. Maybe, but that's to many work for me currently.

Posted on 2003-08-17 14:41:01 by Hagen