- --- In primenumbers@yahoogroups.com, "WarrenS" <warren.wds@...> wrote:
>

Please tell us what your Lehmer test is.

> I succeeded in programming such a test. It is a combination of a

> base-2 strong pseudoprime test and a certain Lehmer test.

> No multiprecision math libraries needed. I'll try to

> give the details later. It has a lot of similarity to the BPSW test.

> If run on the 31894014 odd strong pseudoprimes

> below 2^64, it correctly identifies them

> all as both composite and spsp(2). The runtime is

> 258 or 259 sec if only the Lehmer test is run (two runs timed)

> 164 sec if only the spsp(2) test is run

> 395 sec if both tests are run (which you need for infallibility)

> from which I deduce that processing the input & other extraneous stuff

> took 27 or 28 seconds, so that the speed was

> 231 sec for Lehmer only (138K tests/sec)

> 137 sec for spsp(2) only (233K tests/sec)

> 368 sec for combined test (87K tests/sec)

> on 2GHz apple imac core duo, while also running other stuff, this was not the sole job.

Not very scientific, if your machine started indexing the disk for example.

> Note my Lehmer test actually ran in "1.69 Selfridges" experimentally, i.e.

1.69 sounds good but can you be more precise?

> 231/137=1.69, which somewhat surprised me and indicates my (unfinished)

> attempt to build a 3-selfridge infallible test for n<2^64 using spsp tests only, was a waste of time, although I currently believe that test will be possible and will be found

You might want t use GPGPU:

> once my computer grinds enough.

>

http://www.gpgpgpu.com/gecco2009/6.pdf

> This also tells us that if my "faster than Eratosthenes" prime generator (explained in an earlier post) were run, it would generate primes at a rate of 87000*c primes output per second, for some constant c with 0<c<1. This is slower than available primesieve software by a factor of 500 to 1000 for primes up to 10^13, so I think my new prime generator, even though asymptotically superior to Eratosthenes, in practice will be a lot slower unless there is special purpose (e.g. pipelined) hardware. With said hardware, who knows, but I suspect my prime generator would be winning versus all rival methods.

Paul

> Probably nobody will have the money to design & build a good hardware implementation, though, in which case that victory would be irrelevant to the real world.

>

>

> --

> Warren D. Smith

> http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

>

> For the fixed g==2 case, this is suboptimal,

--I also thought of the idea of making a special modular exponentiation routine

(B^x mod m) for the special case B=2, but using different ideas than Carmody suggested.

His ideas were based on a special doubling routine. Mine were based on bitshifting.

(He also muttered about both-sign integers and use of floating point, but I avoided those

ideas entirely.)

Turned out my approach is 3% faster than

Carmody's for 32-bit uint 2^x mod m based primetest, both unsurprisingly

were speedups versus the general-base routine.

Also my approach is 6% faster than Carmody's for 64 bits.

On my machine anyhow... one might be able to play with compiler and

loop unrolling and such to make his approach faster, they are close, or might be

better to hybridize both ideas.

Carmody also suggested making a special squaring routine, not just multiply.

This seems to yield a small (perhaps nonexistent?) speedup.

Hence 2^x mod m now runs in only about "0.68 selfridges" while B^x mod m

would be 1 selfridge if B>=3.

As a result, my 32-bit and 64-bit prime tests now both faster than Worley's 32-bit

test on average!

Indeed my 32-bit test currently 35% faster on average (random odd numbers) although

presumably 2X slower in worst case (primes only) than Worley's.