20191014, 14:43  #210 
"Ben"
Feb 2007
3,733 Posts 

20220919, 13:57  #211  
"Ben"
Feb 2007
7225_{8} Posts 
Quote:
Below is an updated table of timings on the benchmark semiprime input files (100,000 semiprime inputs each composed of 2 factors of approximately equal size). Unfortunately I don't have the same hardware anymore, so the table incorporates speedups from the hardware as well. (spbrent didn't change, so the hardware portion of the speed increase could be extracted from that.) The code was compiled with icc Ofast march=skylakeavx512 o uecm microecm.c lm Code:
Bits ECM Lehman Brent 42 0.41 0.38 1.13 44 0.51 0.59 1.50 46 0.64 0.94 1.99 48 0.81 2.75 50 0.99 3.76 52 1.25 5.23 54 1.55 7.29 56 1.95 10.3 58 2.46 14.4 60 3.06 20.3 62 3.90 28.7 64 4.76 

20220921, 18:21  #212 
"Ben"
Feb 2007
3,733 Posts 
Update:
I borrowed some singlelimb vector multiply functions from avxecm to make a vectorized version of microecm that operates up to 52 bits (the precision limit of the multipliers). Here it is compared to the others when processing the 100k input test sets. vec_uecm is structured to process largeish lists of inputs... that turned out to be necessary in order to keep vector occupancy high. Code:
timings in seconds for 100k inputs. Bits vec_uecm uecm Lehman Brent 42 0.24 0.41 0.38 1.13 44 0.29 0.51 0.59 1.50 46 0.35 0.64 0.94 1.99 48 0.44 0.81 2.75 50 0.53 0.99 3.76 52 0.65 1.25 5.23 54 1.55 7.29 56 1.95 10.3 58 2.46 14.4 60 3.06 20.3 62 3.90 28.7 64 4.76 Last fiddled with by bsquared on 20220921 at 18:37 
20220921, 18:59  #213 
"Tilman Neumann"
Jan 2016
Germany
13·41 Posts 
Amazing!

20220921, 21:29  #214 
"Curtis"
Feb 2005
Riverside, CA
2^{3}·3·5·47 Posts 
Might this be useful as some sort of patch for GGNFS? Then again, is anyone conversantenough in the code to try changing the current cofactorsplitting routine for this one?

20220922, 12:46  #215  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
37×163 Posts 
Quote:
The cofactorisation strategy is handled in: https://github.com/gchilders/lasieve...ows/strategy.w Probably not too hard to substitute in an alternate ecm method. It is also worth bearing in mind that the majority of time is spent on larger numbers than this thread covers. I suspect that switching to the CADO siever is probably a better use of time though. Last fiddled with by henryzz on 20220922 at 13:27 

20220922, 15:43  #216  
"Tilman Neumann"
Jan 2016
Germany
13·41 Posts 
Quote:
Maybe Ben's 128 bit ecm (should be somewhere in this thread to find, I'm too lazy) would be more adequate? It looked pretty fast and might profit from recent improvements, too. 

20220928, 02:25  #217  
"Ben"
Feb 2007
3,733 Posts 
Quote:
So I went ahead and experimented with this, and indeed it does help! microecm is almost 10x faster than the assembly mpqs in ggnfs. But, that portion of the job is pretty small compared to the whole. So overall the speed increase is not that big. Still, it is something. edit: more details here Last fiddled with by bsquared on 20220928 at 03:32 

20221026, 14:01  #218 
"Ben"
Feb 2007
3,733 Posts 
I've had some fun lately creating a micropm1 (P1) method. I made a pretty graph of success rate with various B1. At the ridiculous looking B1=33 level I was surprised to see that it succeeds between 65% and 25% of the time on semiprime inputs between 32 and 40 bits (smallest factor between 16 and 20 bits), in an average time of 700 nanoseconds per run.
It actually turns out to be useful, as a pretest prior to running ecm curves. Running P1 at B1=333 for inputs between 5264 bits makes microecm slightly faster. 
20221028, 03:19  #219 
"99(4^34019)99 palind"
Nov 2016
(P^81993)SZ base 36
2·7·263 Posts 
I have collected online integer factorizers:
1. https://www.numberempire.com/numberfactorizer.php 2. https://www.alpertron.com.ar/ECM.HTM 3. http://www.javascripter.net/math/cal...calculator.htm 4. https://betaprojects.com/calculators/prime_factors.html 5. https://www.emathhelp.net/calculator...oncalculator/ 6. http://www.numbertheory.org/php/factor.html 7. https://primefan.tripod.com/Factorer.html 8. http://www.se16.info/js/factor.htm 9. http://math.fau.edu/Richman/mla/factorf.htm all of them can factor all numbers with <= 63 bits, in fact, most of them can factor larger numbers, say numbers with about 128 bits also you can use Wolfram Alpha: https://www.wolframalpha.com/ also you can use the online MAGMA calculator: http://magma.maths.usyd.edu.au/calc/ 
20221028, 13:48  #220 
"Ben"
Feb 2007
3,733 Posts 
Thanks for your list... As it happens, I know a thing or two about factoring larger numbers as well. The point of this thread is factoring many small numbers very quickly.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring Mersenne numbers  paulunderwood  Miscellaneous Math  18  20170827 14:56 
Factoring Big Numbers In c#  ShridharRasal  Factoring  10  20080320 17:17 
Question about factoring code  Peter Nelson  Software  9  20050330 18:28 
Factoring Fermat Numbers  Axel Fox  Software  14  20030704 18:57 
Questions about SSE2 code and Factoring  Joe O  Software  2  20020913 23:39 