Request from Phil

[axn]

Alright then.. I'll run it on 339728*5^249588-1.


Slightly unrelated question. Can the FFT be done using multiple bases (mixture of 5^8 & 5^9)? If the previous question is completely daft, feel free to say so

[fatphil]

Originally Posted by axn1

Alright then.. I'll run it on 339728*5^249588-1.


Slightly unrelated question. Can the FFT be done using multiple bases (mixture of 5^8 & 5^9)? If the previous question is completely daft, feel free to say so

It's so daft I've got several hundred primes in the top-5000 with exactly that property. (See pies and LG.)

The funny thing is that it's bloody obvious how to do it once you've read a bit of Crandall et al, but no-one else has ever done it before! (Crandall himself indicated he was not familiar with that precise technique.) It's not in the FFT literature either, assuming that Bernstein's summary of the field is complete.

It's a little hairy, I will admit, and it doesn't come for free, as it requires carries to be done in both directions! (honestly!) but I do intend to implement it eventually.

[axn]

phrot.47.exe -b=3 -q"339728*5^249588-1"
Actually testing 339728*1953125^27732-1 (27733/57344 limbs)
339728*5^249588-1 [] is PRP. (e=0.42856 (3.35822e-12@1.010) t=3762.44s)

[rogue]

I have successfully tested hundreds of primes from Wilfrid Keller's Riesel list. This was on PowerPC. Phil and I are trying to work out an issue where using -b=3 returns a PRP and without returns a composite. I'm snowed in today (thanks to the blizzard hitting the Midwest as I write), so I get to play instead of work. Although by play, I mean play in the snow as that's what the kids want to do.

[fatphil]

attached. No changes to exponentiation or modular reduction - only to the selection of FFT size.

It may sometimes be a bit paranoid, but tests show that occasionally it's not paranoid enough. Please shout very loudly if you see any e=0.5 logs.

I'm also interested in any case where the maxerr upper bound predictor mis-estimates, such as the following:

Actually testing 71999928*1594323^1146-1 (1148/2304 limbs)
888888*3^14902-1 [314664,9608,11581,34061] is composite LLR64=B4CFC53446291412. (e=0.06250 (0.0614335~7.25699e-16@0.923) t=10.56s)

I predicted, from b and n, that maxerr would be < 0.0614335, but it came in at 0.06250. OK, no disaster, but it would be interesting to know what proportion of guesses are incorrect. My predictor is very tweakable, it has in-depth knowledge (a.k.a. guesswork) about how the different sized FFTs are performed, and effectively has a different predictor for each FFT type. (See predictMaxerr in the code, those values came from thousands of tests.)

Some good news - Guillermo has noticed that he didn't complete certain parts of YEAFFT for SSE2 machines, as he doesn't need them for GLucas. However, he's said that he will revisit the code, and fill the gaps so that ordinary convolutions can be performed. (Which is what I use.) If he pulls this off, it will mean that there should be a speed boost for P4/Ath64/EMT64 machines some time in the future.

[fatphil]

Originally Posted by fatphil

attached.

Argh! Third time lucky. The previous one had the wrong (0.47) version of the C.

[axn]

phrot.48.exe -b=3 -q"177418*5^154971-1"
Actually testing 22177250*390625^19371-1 (19373/40960 limbs)
177418*5^154971-1 [] is PRP. (e=0.01306 (0.0148053~6.14955e-16@0.927) t=1341.08s)

phrot.47.exe -b=3 -q"177418*5^154971-1"
Actually testing 177418*1953125^17219-1 (17220/36864 limbs)
177418*5^154971-1 [] is PRP. (e=0.34779 (3.45862e-12@1.009) t=1153.67s)

Interesting...

[rogue]

Originally Posted by axn1

phrot.48.exe -b=3 -q"177418*5^154971-1"
Actually testing 22177250*390625^19371-1 (19373/40960 limbs)
177418*5^154971-1 [] is PRP. (e=0.01306 (0.0148053~6.14955e-16@0.927) t=1341.08s)

phrot.47.exe -b=3 -q"177418*5^154971-1"
Actually testing 177418*1953125^17219-1 (17220/36864 limbs)
177418*5^154971-1 [] is PRP. (e=0.34779 (3.45862e-12@1.009) t=1153.67s)

Interesting...

Phil modified his code to be a little more dynamic at choosing the base (390625 vs 1953125) based upon a predicted error. As you can see phrot chose a higher base with fewer limbs. It increases the maxerr, which is still below .50000, but saves reduces the time for the PRP test by about 17%.

[fatphil]

Originally Posted by axn1

Actually testing 22177250*390625^19371-1 (19373/40960 limbs)
...
Actually testing 177418*1953125^17219-1 (17220/36864 limbs)

Interesting...

0.48 predicted that the maxerr might be as large as:

Run till exit from #0  predictMaxerr (tb=1953125, tn=17219) at glprov.c:2041
0x004047ab in main (argc=4, argv=0x6a26e0) at glprov.c:2383
2383                        bankb=tb; bankk=tk; bankn=tn;
Value returned is $2 = 0.44042911805189722

It's not willing to take maxerr that close to 0.5 by default, and so it falls back to a smaller limb size. And unfortunately there is a cost for this extra security.
However, FFT errors are very very spiky things. It's not worth taking too much risk. LLR takes a lot less risk than even me at my least risky.

Phil

[axn]

Originally Posted by fatphil

It's not willing to take maxerr that close to 0.5 by default, and so it falls back to a smaller limb size. And unfortunately there is a cost for this extra security.
However, FFT errors are very very spiky things. It's not worth taking too much risk. LLR takes a lot less risk than even me at my least risky.

That makes sense. By the end of the week, I'll be starting a massive triple check of all the lower k/n pairs (riesel side). Will let you know how it goes.

btw, is there any timeframe for doing the + side? Or are you waiting for more assurance on the - side?

[fatphil]

Originally Posted by axn1

That makes sense. By the end of the week, I'll be starting a massive triple check of all the lower k/n pairs (riesel side). Will let you know how it goes.

btw, is there any timeframe for doing the + side? Or are you waiting for more assurance on the - side?

My highest priority area is getting non-x86 working. Then it's mapping everything that works to +1. I can reeorder those if it's important to you.