In this post I explain R.S.Lehman's factorization algorithm, provide a proof and runtime analysis, and compare with SQUFOF. 1. The algorithm. Let T>0 be a...
23965
WarrenS
warren_d_smi...
Jan 2, 2012 3:12 am
It turns out William B. Hart in a preprint implemented his own heuristic factoring algorithm which he calls "one line factoring algorithm" because it is very...
23966
paulunderwooduk
Jan 2, 2012 8:39 am
... I had to be a little more patient with Vincent's prime sieve. Using GMP, I have now reached all n<10^12 without finding a counterexample to this...
23967
mikeoakes2
Jan 2, 2012 9:08 am
... After about 10 times more usage, with Pari-GP Version 2.5.0, exactly one failure has occurred, in this section of code:- ...
23968
paulunderwooduk
Jan 2, 2012 11:29 am
... I just noticed that I left out the exponent; It should be: Mod(Mod(1,n)*(l*x-3),l^2-x*l+1)^(n+1)+2*x^2-9==0 For the GMP code I use a variation of the...
23969
Bernardo Boncompagni
redgolpe
Jan 2, 2012 8:17 pm
[crosspost to: primenumbers@yahoogroups.com, primeform@yahoogroups.com] A few days ago, David Broadhurst made some hard-to-find large Fibonacci PRPs public...
23970
Kermit Rose
kermit1941
Jan 3, 2012 12:47 am
... Here is trivial illustration with N = 25. ... I take T = 1, N = 25. ... B = 2 ... k = 0 ... k = 1 m = 4 r = 2 a = 7 --> 7%4 == 3 --> do not use a = 8 -->...
23972
WarrenS
warren_d_smi...
Jan 3, 2012 7:30 pm
Good luck trying to decrypt this code... it is the fastest GCD code I have at present. //Binary bithacked algorithm, 260 nanosec on iMac 2.0 GHz. //Warren D....
23973
Maximilian Hasler
maximilian_h...
Jan 3, 2012 10:23 pm
... I can't imagine that d=b-a; (...) a += d ; b -= d+a would be slower. Anyway, the compiler should know (for these 2-3 instances) what is the fastest code...
23974
WarrenS
warren_d_smi...
Jan 3, 2012 10:37 pm
... --it is slower! On my computer, anyhow....
23975
Jack Brennen
jbrennen
Jan 3, 2012 10:40 pm
Is it faster if you replace this: for(s=0; ((a|b)&1)==0; s++){ a>>= 1; b>>= 1; } while((a&1)==0){ a>>= 1; } with this: if ((a&1)==0) { s = __builtin_ctz(a|b);...
23976
Jack Brennen
jbrennen
Jan 3, 2012 10:54 pm
Make that: s=0; if ((a&1)==0) { s = __builtin_ctz(a|b); b>>=s; a>>= __builtin_ctz(a); }...
23977
Jack Brennen
jbrennen
Jan 3, 2012 11:12 pm
Apologies once again, but I don't want to leave broken code out there... It should be: s=0; if ((a&1)==0) { s = __builtin_ctzll(a|b); b>>=s; a>>=...
23978
WarrenS
warren_d_smi...
Jan 3, 2012 11:16 pm
... --thanks! That hack sped it up from 260 to 258 nanosec. You also need to add an "s=0" to your code fragment otherwise s could be used without having been...
23979
WarrenS
warren_d_smi...
Jan 3, 2012 11:20 pm
Yes, as per Brennan's bug fix, the ctz's should be ctzll's. That also speeds it up to 139 nanosec....
23980
Phil Carmody
thefatphil
Jan 4, 2012 10:12 am
From: WarrenS ... I think Bob S posted his highly tuned code to sci.math, or just possibly the Mersenne Forum, about 5 years ago. It had special cases for...
23981
Phil Carmody
thefatphil
Jan 4, 2012 10:17 am
From: Jack Brennen <jfb@...> ... Which is classic UB. Nacked-by: Phil...
23982
Phil Carmody
thefatphil
Jan 4, 2012 10:29 am
From: WarrenS <warren.wds@...> ... It's a sparse enough inner loop that I can easily imagine the increased dependency makes it slower. What's the latency...
23983
WarrenS
warren_d_smi...
Jan 4, 2012 5:08 pm
http://dl.dropbox.com/u/3507527/LehmanClean.c is my C code for Lehman factorization algorithm. Perhaps you amazing coders all will be able to improve it...
23984
WarrenS
warren_d_smi...
Jan 4, 2012 6:28 pm
I reposted a new code version to same place: http://dl.dropbox.com/u/3507527/LehmanClean.c (But the big comment at start now out of date.) What happened was...
23985
WarrenS
warren_d_smi...
Jan 4, 2012 8:13 pm
Let a and b be 64-bit unsigned integers. Suppose I want to compute a*b which has 128 bits and stick the lower & upper halves into two 64-bit integers F,G. How...
23986
Jack Brennen
jbrennen
Jan 4, 2012 8:54 pm
Something like this should work for x86-64 gcc (all variables are uint64_t): asm("mulq %3" : "=a" (F), "=d" (G) : "0" (a), "g" (b)); That should multiply a*b...
23987
Jack Brennen
jbrennen
Jan 4, 2012 9:26 pm
Slight fix and optimization: asm("mulq %3" : "=a" (F), "=d" (G) : "%0" (a), "rm" (b)); Using "%0" allows the compiler to swap the position of a and b if that's...
23988
Ben Buhrow
nebworhub
Jan 4, 2012 9:45 pm
... No problem with the code changes... As I reported to you earlier, here are the results of my tests with pseudo-primes drawn from a random size distribution...
23989
Chuck Lasher
lasher_chuck
Jan 4, 2012 9:53 pm
Regarding the use of the multiply, I concur with exploiting the hardware wherever possible. There is also a technique which is hardware & compiler portable...
23990
WarrenS
warren_d_smi...
Jan 14, 2012 5:51 pm
Related question: If we have two 64-bit unsigned integers a,b and wish to divide the double-length a*2^64 + b by a single 64-bit unsigned integer c to get...
23991
Warren Smith
warren_d_smi...
Jan 14, 2012 6:40 pm
sorry, I'm not much of a programmer. Last question re multiply, got a nice answer from Brennan saying how to within C program, to call the assembler to do the...
23992
Paul Leyland
paul@...
Jan 14, 2012 7:47 pm
... What kind of hardware would you like to use? It's pretty easy to do it with almost any FPGA but if you want an ASIC it's likely to cost you serious money....
23993
samir.musali
Jan 15, 2012 5:02 pm
If p: 1) is not the 1st element of the set of primes; 2) does not equal 2; 3) equals either minimum 3 or other primes; (2^p+1)/3=p* (p*-->prime can be equal p...
23994
Phil Carmody
thefatphil
Jan 15, 2012 8:56 pm
From: samir.musali ... I'm not sure I completelf follow you, but what you've written looks remarkably similar to the conjecture here: ...
