Deviant Login Shop  Join deviantART for FREE Take the Tour
×



Details

Submitted on
November 2, 2008
Image Size
211 KB
Resolution
1280×1024
Link
Thumb
Embed

Stats

Views
3,595
Favourites
8 (who?)
Comments
12
Downloads
894

License

Creative Commons License
Some rights reserved. This work is licensed under a
Creative Commons Attribution-Share Alike 3.0 License.
×
Prime Numbers by panzi Prime Numbers by panzi
Only FULL VIEW gives the right image!

My sister wanted to know how dense prime numbers are distributed. She wanted a visual representation so I wrote a little python script using PIL that generates a picture where each pixel represents an integer >= 0. The white pixels are normal numbers, the red ones are prime numbers. The pixel at the top left represents the number 0, the pixel at the bottom right represents the number 1310719.

Get the python script as GitHub Gist (I know it could be written better/faster).

Usage:
python visprim.py

E.g.:
python visprim.py 1280 1024 visprim.png

Update:
I rewrote it in C++ using Magick++ and boost. I also added multithreading support so it runs faster on multiprocessor systems.

Get the C++ source as GitHub Gist.

Usage:
visprim [number-of-threads]

E.g.:
visprim 1280 1024 visprim.png 2


PS: I know the category isn't correct, but which category would be a better fit? deviantART forces me to select a certain sub-category. I can't just select "Digital Art".
Add a Comment:
 
:iconeatmeatagain:
line 24: switch "n / 2" for "sqrt(n)" and the program runs exponentially faster.
Reply
:iconpanzi:
Have you given that a test? My guess would be it runs a lot slower because of the function call overhead. Currently there is no function call whatsoever (isprime should be inlined) during the calculation and everything should run in registers only (except setting the pixle color). Also sqrt is a floatingpoint operation, which is again much slower than an integer operation. One way to speed it up might be some manual loop unrolling. However, prove me wrong with some benchmarks. :)
Reply
:iconeatmeatagain:
For very small graphs the difference isn't substantial. For instance, with the original code, a grid 32x32 will be 1024 pixels large and assuming the code didn't stop on values of n found to not be prime the last loop in isprime() will end up running approximately 262912 fast integer divisions via the modulus operator (n % p) and 1024 fast integer divisions (n / 2). On most modern cpu's these operations should only use a single cycle.
Using a somewhat slower floating point sqrt should add some ten or twenty cycles (some from the function call, some for the float math. Most cpu's should have a sqrt function built in these days), but we save time by calling modulus on a *far* smaller number of values. As you know, 'half' determines how many loops isprime() does -- half of n vs the square of n. The last prime pixel pixel of the 32x32 grid is 1021 and your code runs 510 fast modulus operations to determine that it is prime. Even with a slow sqrt, and assuming it takes a hundred cycles (rather than the twenty I suggested earlier), the fast integer modulus is only run 31 times, saving roughly 480 operations -- perhaps 400 cycles. Assuming the code didn't stop when it found the number wasn't prime, this results in approximately 11442 modulus calculations in total (vs 262912 before), costing 1024 sqrt() operations.
The reduction in loops is *much* more dramatic at higher grid sizes. Again, assuming the code kept running, not stopping when it found a value that wasn't prime, 4096x4096 will result in approximately 16777216 'n / 2' operations, and approximately 35184393060352 'n % p' calculations. with sqrt(), it should be roughly 22923271509 'n % p' calculations.

You asked for some benchmarks:

with 'n / 2'
time ./visprim.ndiv2 4096 4096 4096x4096_n_div_2.gif 2
real 69m12.404s
user 123m58.922s
sys 0m21.646s

with 'sqrt(n)'
time ./visprim.sqrtn 4096 4096 4096x4096_sqrt.gif 2
real 0m10.634s
user 0m11.335s
sys 0m0.254s

Just over an hour with the original code, and just over ten *seconds* with my one simple modification. No loop unrolling, no compiling with different gcc flags, and no rewriting sections of your code with assembler. For reference, my machine is an Intel Core2 Duo E8400 3.0ghz, 8gb of ram, running 64bit Linux.

The resulting files are identical ([link]):
md5sum 4096x4096_n_div_2.gif 4096x4096_sqrt.gif
1dddbc4e224fc442c7e3d16a4400926f 4096x4096_n_div_2.gif
1dddbc4e224fc442c7e3d16a4400926f 4096x4096_sqrt.gif

I'm not on a hunt for slow prime number implementations. I thought your little project here was interesting, and I was curious -- I've written my own prime number generator a couple years back, but I hadn't used threads to do it. I can get your implementation even *faster*, but it no longer produces correct results with more than one thread. Still toying with the code, though.
Reply
:iconpanzi:
Ok, that's enough proof for me. Quite a substantial speed improvement! :)

If I would use/maintain my implementation I would change it (I only used it to generate this image, so I don't need it any more).
Reply
:iconeatmeatagain:
"half of n vs the square of n" -- meant square root of n, my bad. Also, my math was a bit incorrect in that paragraph; 31 * 100 is 3100, not 310. Still, my explanation on the whole is sound. Benchmarks back me up, too. :D
Reply
:iconagorf:
agorf Nov 10, 2009  Hobbyist Photographer
Cool idea. ;)
Reply
:iconagorf:
agorf Nov 10, 2009  Hobbyist Photographer
I just hacked a quick Ruby version (also slow): [link]
Reply
:iconagorf:
agorf Nov 10, 2009  Hobbyist Photographer
-quick
Reply
:iconcymbaloum:
That's very nice. If you (and your sister) are into this, then I suggest you have a look at another way of plotting prime numbers that reveals some interesting features: use the Ulam spiral (check this site: [link])
Reply
Add a Comment: