llrp, a portable version of LLR using FFTW

[IBethune]

Originally Posted by nuggetprime

Bug: segfaults when testing 1525*2^700391-1, before starting LL loop.
Seems to fail for every large-k/large-n combination.

Nugget

Most likely this is caused by compiling LLR for 64 bit system - try adding -m32 to your compiler flags and this should fix it.

Cheers

- Iain

[IBethune]

Originally Posted by stevenj

A couple of suggestions regarding performance:
...
Regards,
Steven G. Johnson

I've been playing with the code along the lines suggested above, and have made the following performance improvements (all for N=12.5K FFT length)

• Modified code to allow compiling for 64-bit targets (~60% speedup)
• Use FFTW r2c instead of r2r interface (~80% speedup)
• Use FFTW_PATIENT instead of FFTW_MEASURE (~2% speedup)

Overall, for test of 5719*2^100002+1 (LLR N=8K, LLRP N=12.5K)
LLRP (original, 32 bit) = 109.958s
LLRP (new, 64 bit) = 37.891s (2.9x speedup)
LLR (native, 32 bit) = 8.645s

For a larger test 40311639203955*2^666666-1 (LLR N=72K, LLRP N=88K)
LLRP (old) = 48.749 ms/bit
LLRP (new) = 11.04 ms/bit (4.4x speedup)
LLR = 0.95 ms/bit

Clearly native LLR is a lot faster still (and is relatively even faster for the larger case. This may be because it requires a generic reduction, I'm not sure...), but though the above might be of use to anyone else who is using LLRP.

I attach a modified gwpnum.c with these changes.

Cheers

- Iain

[Jean Penné]

Many congrats, Iain and Steven, for this nice work!
I will include this new gwpnum.c in the next release of llrp.
Indeed, r2c usage is better than r2r one in the real input case.
Thank you again,and Best regards,
Jean

[msft]

Hi ,IBethune

Originally Posted by IBethune

• Use FFTW r2c instead of r2r interface (~80% speedup)

CUFFT support r2c function.
Thank you,

[Jean Penné]

Hi,

I uploaded now the 32 bit Windows and Linux binaries, and also the complete source of the llrp 3.8.1 version on my Development directory :

http://jpenne.free.fr/Development/

No new feature in this version ; I only updated it according to Steven and Iain's suggestions.

Regards,
Jean

[danholle]

Hmmm...

Just testing my installation.

./sllrp -q"1*2^19937-1"

returns composite. 11213 and 21701 are correctly found to be prime.

Tried this on i5 based Ubuntu machine using llrp 3.8.0 and 3.8.1.

--- Dan