Waldek Hebisch wrote:
> kuratkull@[EMAIL PROTECTED]
<spamtrap@[EMAIL PROTECTED]
> wrote:
>> Anyway, I am trying to build the very-fast-prime-counter i assembly
>> and I succeeded when using only the regular instructions, but a 6.5
>> secs for a 100k primes is way too slow, so I looked around and
>> profiled my code...and of course, a major bottleneck was the idivl.
>
> I am not sure what "prime-counter" mean -- I you want just generate
> primes than sieve of Eratosthenes is the standard method (much faster
> than method using division).
Indeed, that is the way to do it for any kind of range processing, until
you get into stuff like 500+ bit prime number searching (for RSA keys),
in which case you should be using statistical procedures, i.e. modular
arithmetic.
> In case you really want to use division, you may consider storing
> recipracals -- you are using the same divisor many times.
Using the same divisor/reciprocal many times simply means using a sieve,
and for a properly compressed base table (personally I prefer storing 30
numbers in each 8-bit entry) you can even do stuff like casting out
multiple trial divisor multiples at the same time, when the divisors are
still pretty small.
Do a search on +prime +"sieve of Eratosthenes"!
I'm guessing you have at least a couple of orders of magnitude in speed
to gain. :-)
Terje
--
- <Terje.Mathisen@[EMAIL PROTECTED]
>
"almost all programming can be viewed as an exercise in caching"
|
