Re: How to Generator Prime Numbers in a short time ?

Cristiano wrote:
If the sieving step is done over the RAM (e.g. allocate a 'big' block of
RAM, initialize all the bits to 1 and then set the sieved bits to 0), that
is not always the fastest way because of the cache memory.
In my implementation (using GMP library), I get the best speed when I sieve
out the prime < 50000 over a range of 90000 numbers (it seems that the code
must fit in the L1 caches of my Barton). So that, when I need to find a
512-bit prime, the sieving and the SPRP test are done even 100, 500 times.

for(i=0;i<9500;i++) {
temp=(Mod(PrimeTable[i]));
if(temp!=0)
{if(temp%2==1)
p=(PrimeTable[i]-temp)/2;
else
p=(2*PrimeTable[i]-temp)/2;
for(int n=0;n<(1000/PrimeTable[i]);n++)
{ S[p+PrimeTable[i]*n]=1;}
}
else
S[0]=1;
}

Do you mean like this ?
I have tried this method , however , it slower than generator random
numbers
and check with PrimeTable and Miller-Rabin tests.
Why ? Is it that my PrimeTable is not large enough?
90000 numbers as you said ?
It perhaps use too many memory space.

.

Relevant Pages

  • wait for signal in process
    ... one is a cache memory and the other is a RAM memory. ... How could I "wait" for the RAM to put the output and then storing it in variable "Result"? ... state (cache.vhd is a FSM). ...
    (comp.lang.vhdl)
  • Re: Next Generation of Language
    ... top corner, above layers of memories, L1, L2 and now L3, the RAM, the ... We could also add layers for the Internet and the ... near the processor is cache memory or normal RAM, ...
    (comp.lang.lisp)