mersenneforum.org > Math List of primes
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2005-03-16, 20:44 #12 grandpascorpion     Jan 2005 Transdniestr 7678 Posts Doh, I found much better (and pretty obvious) way to store them: http://www.rsok.com/~jrm/printprimes.html
2005-03-17, 23:29   #13
Unregistered

6,947 Posts

Quote:
 Originally Posted by ewmayer Regarding the storage issue, there's no need to store the primes explicitly - you simply store a table of differences between consecutive primes. ... ...nearly all the prime gaps will be smallish (say less than 512), so a byte suffices to store any gap that is < 512 in gap/2 form. What do we do if a gap is larger? Well, since we know a gap must be > 0, we can reserve a zero-valued byte as a representing 512-plus-whatever-the-bext-byte-times-2-is. We can have as many zeros in a row as needed, i.e. can cover gaps of arbitrary size this way. Since gaps this large are very rare, that only trivially increases our storage.

The one subtlety that arises here is: what to do with a gap of precisely length 512? (Length 2^(n+1) for the general n-bit-field scheme.) Without modification, that would lead to an infinite string of zero bytes. To handle that, we only allow each nonzero byte to represent gaps from length 2 (byte = 00000001 in binary) to 510 (11111110), and use 11111111 to represent a *zero* terminating a string of zero-valued bytes (each of which denotes a length-512 interval), i.e. the byte pair 00000000 11111111 represents a 512-gap, the byte triplet 00000000 00000000 11111111 represents a 1024-gap, and so forth. It's still very simple to implement in code, and has one additional nice property which I neglected to mention in my initial post: in the lower limit of a 1-bit field length (n = 1), the resulting bit table is exactly the same one that results from simply labeling all the odd integers in the interval in question with a 0 (not prime) or 1 (prime).

2005-03-18, 10:17   #14
Unregistered

32×5×167 Posts

Quote:
 Originally Posted by grandpascorpion Since 6 is still the "jumping champion" in this range, I think you could save even more space by using a 4-bit solution. ...I could be wrong here. I haven't crunched any numbers but on the surface, it looks like most of the time you would use half the space.

If your aim is to store primes as compactly as possible, the 4-bit solution wins for this size range. I've looked at the range (2*10^13, 2*10^13+10^6) which yields 32,764 primes, with a maximal gap of 376. About 65% of the gaps are 2-30, which would each require half a byte.

I've assumed a simple scheme where the next half byte codes gaps 32-60, the third half byte 62-90 etc. This scheme needs about 25200 bytes to store the range or about 77% of the full-byte scheme.

2005-03-18, 14:04   #15
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

5×2,179 Posts

Quote:
 Originally Posted by Unregistered I've assumed a simple scheme where the next half byte codes gaps 32-60, the third half byte 62-90 etc. This scheme needs about 25200 bytes to store the range or about 77% of the full-byte scheme.
Is it possible to post some of the code that you used?

Last fiddled with by Uncwilly on 2005-03-18 at 14:04

2005-03-18, 17:42   #16
Unregistered

100010111111002 Posts

Quote:
 Originally Posted by Uncwilly Is it possible to post some of the code that you used?
I didn't use any code: I generated the primes using dsouza123's program, copied them into excel and counted the frequencies.

They were
2 to 30 21202
32 to 60 7604
62 to 90 2635
92 to 120 907
122 to 150 273
152 to 180 95

152+ 48

total: 32764

so 21202 gaps will code in 4 bits, 7604 in 8 and so on

 2005-03-18, 19:55 #17 grandpascorpion     Jan 2005 Transdniestr 1111101112 Posts Unregistered, I think there's an even better way to do this, albeit a tad harder to implement. Start with a set of numbers relatively prime to some product of the first n primes, like 30030 or 510510. That set will always be the primes to that point minus the prime factors plus 1. The sieved set size for 30030 is 3243. So, 1 in sieve gap terms translates roughly on average to 9. Since you dealing with a sieved range, it stands to reason that these sort of gaps would be much smaller. I would imagine a 3 bit would be implementable for gaps 1-7 3 bits - sieve gaps 1-7 8 bits - sieve gaps 8-23 12 bits - sieve gaps 24-128 16 bits - sieve 129-1024 (rarely necessary) I did a check: the minimum gap check for 23 for a sieved set of 30030 is 96. So, all gaps under <=96 could be handled in 8 bits. Similarly, for 3 bits, all gaps under 7 (a real gap of 26) could be handled. Note: These are min. values, the max values for the 30030-sieved gaps of 7 and 23 are 130 and 318 respectively. I'll try to implement this this weekend and see how compact it would be.
 2005-03-19, 00:18 #18 Richard Cameron     Mar 2005 2×5×17 Posts Grandpascorpion I think your approach could reduce the storage requirement quite a bit. But it all depends on the distribution of gaps, not just the average sizes. So I'm interested to see what results you get. Richard Cameron -thought it would be polite to register.
 2005-03-20, 00:50 #19 grandpascorpion     Jan 2005 Transdniestr 1111101112 Posts Hi Richard, I got off on the wrong foot with the sieved range. I was working with the primes themselves not the set of relatively prime numbers. I worked with 30030 sieve (2*3*5*7*11*13). I ran a very similar range (a little bit different due a quick-and-dirty sieve implementation) There were 33424 primes from 19999999999980 to 20000001020999 Max sieve gap is: 72 and max real gap is 376 444 Bit Total: 143212, 353 Bit total: 146644, Avg. is 4 Sieveless Bit Count: 203204 The sieveless count is 4 bits for 2-30, 8 for 32-62, 12 for 64-94 (so this would be take a bit less space than your scheme) As you can see, it takes lroughly 16kb to store the primes within roughly a 1Mb range. Not using a sieve, takes more than 25k. It may be overkill but I'll try the next higher range 510510 (30030*17) and see how much that would improve the storage. BTW, for the 30030, sieve range the 353 scheme (3 bits < 8, 8 bits < 24, 11 bits < 64) does better through about 1.1-1.2*10^12.

 Similar Threads Thread Thread Starter Forum Replies Last Post MattcAnderson MattcAnderson 0 2017-05-27 14:00 Lennart Twin Prime Search 58 2017-05-05 14:15 gd_barnes Sierpinski/Riesel Base 5 2 2008-07-01 04:09 rogue Sierpinski/Riesel Base 5 1 2007-02-23 00:35 hyh1048576 Software 5 2003-08-20 13:38

All times are UTC. The time now is 04:10.

Tue Feb 7 04:10:53 UTC 2023 up 173 days, 1:39, 1 user, load averages: 1.40, 1.17, 1.09

Copyright ©2000 - 2023, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔