my own Integer-based LL-test not pass 3 Mprimes!?

[ktpn2011]

this is on CPU E8500, Win XP32.
I like code optimization in direct asm.
So now I like to see other code speeds compared to others coding & publish my codes.
I am ready to start optimize other interesting codes..

for now let me share idea of storing prime numbers.
before that, what methods (other then compression) are known?

[kriesel]

Originally Posted by ktpn2011

this is on CPU E8500, Win XP32.
I like code optimization in direct asm.

Implementing a slow algorithm, even well, with assembler is not an optimization, compared to an efficient algorithm. At exponents of current interest, anything less than an fft method of squaring is a slow algorithm.

[science_man_88]

Originally Posted by ktpn2011

for now let me share idea of storing prime numbers.
before that, what methods (other then compression) are known?

is a bitsieve compression ?

[ktpn2011]

Originally Posted by kriesel

Implementing a slow algorithm..

I am about optimizing.. so than FFT or other can be optimized..

science_man_88 , as wrote, it is not about compression.
mostly for number 1byte.

[preda]

Originally Posted by ktpn2011

this is on CPU E8500, Win XP32.
I like code optimization in direct asm.
So now I like to see other code speeds compared to others coding & publish my codes.
I am ready to start optimize other interesting codes..

for now let me share idea of storing prime numbers.
before that, what methods (other then compression) are known?

This paper by Crandall & Fagin is a starting point, highly recommended:

https://www.ams.org/journals/mcom/19...-1185244-1.pdf

[ktpn2011]

thank for link, but maybe you did not understood my question about storing method for prime numbers.
here is attachment. I collect & store prime numbers using mostly 1 byte for each. Is something like this implemented?

[CRGreathouse]

Originally Posted by ktpn2011

thank for link, but maybe you did not understood my question about storing method for prime numbers.
here is attachment. I collect & store prime numbers using mostly 1 byte for each. Is something like this implemented?

I don't think you've given us enough information to work from. There are tons of ways of doing this, so probably the answer is yes, it's been done before, but I'm not at all sure what exactly you are doing.

One method is to store differences (or half-differences, or the like) between primes. Another method is to store bitmaps of primes; a popular technique is to have a byte represent a block of 30 numbers, each one representing the primality of 30n + 1, 30n + 7, ..., 30n + 29.

[ktpn2011]

thanks, so that is differences.

[ewmayer]

Originally Posted by CRGreathouse

I don't think you've given us enough information to work from. There are tons of ways of doing this, so probably the answer is yes, it's been done before, but I'm not at all sure what exactly you are doing.

One method is to store differences (or half-differences, or the like) between primes. Another method is to store bitmaps of primes; a popular technique is to have a byte represent a block of 30 numbers, each one representing the primality of 30n + 1, 30n + 7, ..., 30n + 29.

I find a good balance between storage space and runtime is to store a precomputed table of base-2 Fermat pseudoprimes ('pseudo' here meaning false) not divisible by 3 or 5 up to one's desired bound, then combine a fast base-2 F-PRP test with a 30-based small-p sieve to generate candidates, each one passing those 2 filters gets compared to the next-expected false prime in the 2-PRP table:

1. If (current candidate != next-false-prime), it's prime;
2. If (current candidate == next-false-prime), it's not prime, and we reset next-false-prime to the next entry in the precomputed table.

A table of the above form to cover all primes < 2^32 has fewer than 10000 entries.

[ktpn2011]

why call it storing method? rather, easy finding method.

[retina]

You are storing them, great. But then what? What are your retrieval requirements? Do prioritise fast retrieval over storage space, or the opposite, or some balance? What are your precise criteria?