mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-03-16, 20:44   #12
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

7678 Posts
Default

Doh, I found much better (and pretty obvious) way to store them:

http://www.rsok.com/~jrm/printprimes.html
grandpascorpion is offline   Reply With Quote
Old 2005-03-17, 23:29   #13
Unregistered
 

6,947 Posts
Default

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.
Addendum #2:

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).
  Reply With Quote
Old 2005-03-18, 10:17   #14
Unregistered
 

32×5×167 Posts
Default

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.
  Reply With Quote
Old 2005-03-18, 14:04   #15
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

5×2,179 Posts
Default

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
Uncwilly is offline   Reply With Quote
Old 2005-03-18, 17:42   #16
Unregistered
 

100010111111002 Posts
Default

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
  Reply With Quote
Old 2005-03-18, 19:55   #17
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

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.
grandpascorpion is offline   Reply With Quote
Old 2005-03-19, 00:18   #18
Richard Cameron
 
Richard Cameron's Avatar
 
Mar 2005

2×5×17 Posts
Default

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.
Richard Cameron is offline   Reply With Quote
Old 2005-03-20, 00:50   #19
grandpascorpion
 
grandpascorpion's Avatar
 
Jan 2005
Transdniestr

1111101112 Posts
Default

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.
grandpascorpion is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Here is a list of Mersenne Primes MattcAnderson MattcAnderson 0 2017-05-27 14:00
List of megabit primes found Lennart Twin Prime Search 58 2017-05-05 14:15
List of all base 5 primes? gd_barnes Sierpinski/Riesel Base 5 2 2008-07-01 04:09
Mistake in List of Primes rogue Sierpinski/Riesel Base 5 1 2007-02-23 00:35
Does Prime95 has a list of primes inside it??? 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

Powered by vBulletin® Version 3.8.11
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.

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