mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-04-03, 09:17   #12
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·3·5·13 Posts
Default

Hi Nesio,

Thilo Harich and me have been working recently on an implementation that is very similar to your SM algorithm.
See this post: https://www.mersenneforum.org/showpo...5&postcount=28
Or this Java class: https://github.com/TilmanNeumann/jav...Hart_Fast.java

Both your and our implementations improve upon the orginial Hart algorithm mostly because of the use of multipliers for k.
You use k*m*n with some flexible choice of m, and we use 4*k*n, stepping only over k-values that are multiples of 315.
Additionally, we adjust a=ceil(sqrt(4kn)) by some congruences (mod 2^s) as it is done in Lehman's algorithm.

From your paper I derived that you propose multipliers m like 24, 120, 480, 5040, where smaller m are better suited for small n, and bigger m better for bigger n.

I implemented your SM algorithm in Java in https://github.com/TilmanNeumann/jav...art_Nesio.java
and tested it for n from 20 to 50 bit with the following multipliers m:
1, 4, 24, 48, 120, 240, 720, 1260, 1440, 5040, 10080, 40320, 80640, 110880, 362880, 725760.

Surprisingly I found that 10080 is the best m in the whole n-range. The reason is that I compute the sqrt(k) values already at the construction time of the algorithm. This is a big speedup because we can replace a sqrt by a double multiplication.
But the double multiplication hardly cares about the size of its arguments; thus the size of m only matters in the k*m*n multiplication now, if at all.

Considerung that your SM algorithm does not use adjustments by congruences it is quite fast. Nonetheless the congruence adjustments mean a further speedup. According to my tests with semiprimes having smaller factor between cbrt(n) and sqrt(n), Hart_Fast seems to be constantly about factor 1.46 faster than Hart_Nesio.
Till is offline   Reply With Quote
Old 2019-04-03, 09:37   #13
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·3·5·13 Posts
Default

Here is a performance comparison with 100k test numbers of the mentioned kind (semiprimes with smaller factor between cbrt(n) and sqrt(n) ) from 30 to 50 bit, including a couple of other algorithms, too.
Attached Files
File Type: txt hart-comparison.txt (48.6 KB, 28 views)
Till is offline   Reply With Quote
Old 2019-04-03, 11:13   #14
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by danaj View Post
The SM method looks to be Hart's OLF (as alluded to in the text) using a multiplier. Translating the "Simple Multiplication algorithm" from pseudocode into C becomes exactly my existing code for HOLF. The recursive SM is where things look interesting for larger values.

For multipliers 5040, 720, and 480 work pretty well as constants but the issue often becomes what fits without overflow.

Table 1 shows SM (e.g. Hart's OLF) beating Lehman in the chosen measure. There is some debate on what is faster in practice, and the recent improved Lehman would be very competitive.
Hi, danaj!
In our paper we directly wrote that SM (Simple Multiplication) is a-la-Hart. There are several references in our article to Hart work and thoughts regarding SM also. At the beginning of this forum thread we referenced to Hard too in the connection of SM.

SM and its improvement in applying its multiplier "m" (5040, 720, etc.) was not the object of our research. As you can see we have researched RM (Recursive Multiplication) algorithm and touched of his relations to SM.

We think that the improvement and tricks of speeding SM, RM and Lehman algorithms in practice (at the programming level) is a particular theme.
nesio is offline   Reply With Quote
Old 2019-04-03, 15:28   #15
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2×11×41 Posts
Default

I also got from the paper that SM was not the end goal, and I wasn't commenting on that. I think RM is certainly interesting and non-obvious.

Mainly since we've had discussions on this forum of Hart's OLF (with multiplier) vs. Lehman vs. SQUFOF vs. Pollard/Brent Rho here, I wanted to note that SM and Hart's OLF are basically the same, though just like Hart's paper it leaves the use and choice of multiplier to the user (he suggests 480).

Thilo and Tilman have been doing lots of great work with both Lehman's and Hart's methods in Java. I wish I had more free time to work on this in C! I look forward to what they come up with when looking at RM.
danaj is offline   Reply With Quote
Old 2019-04-03, 16:09   #16
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2×3×5×13 Posts
Default

Actually RM does not look that promising to me. Compared to SM, its advantage in terms of iterations is only 0.6% at 16-digit inputs, but it will (quite certainly) need more instructions per iteration.

Of course it is fair and interesting to investigate such issues. But the final goal is better performance, no?

We found another way to arrange k-values in a good way in class Lehman_CustomKOrder. For "bigger" n like 50 bits, it is around factor 1.4 faster than Lehman_Fast that was reproduced in C by bsquared with some success. Lehman_CustomKOrder's performance is pretty similar to that of our Hard_Fast implementation. The performance of Hard and Lehman seems to be converging. Maybe there is not much space for improvement left (considering current architectures).

Last fiddled with by Till on 2019-04-03 at 16:18 Reason: fixed bsquared's nick ;-)
Till is offline   Reply With Quote
Old 2019-04-03, 17:35   #17
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by Till View Post
Hi Nesio,

Thilo Harich and me have been working recently on an implementation that is very similar to your SM algorithm.
See this post: https://www.mersenneforum.org/showpo...5&postcount=28
Or this Java class: https://github.com/TilmanNeumann/jav...Hart_Fast.java
Hi,Till!
Thanks for the curious links to your and Thilo work.

Quote:
Both your and our implementations improve upon the orginial Hart algorithm mostly because of the use of multipliers for k.
You use k*m*n with some flexible choice of m, and we use 4*k*n, stepping only over k-values that are multiples of 315.
Additionally, we adjust a=ceil(sqrt(4kn)) by some congruences (mod 2^s) as it is done in Lehman's algorithm.
We want to repeat again in this forum thread. We were not improving Hart algorithm. His method was taken to compare with our method RM. Simple Multiplication (SM = Hart) method and Recursive Multiplication (RM) method are relatives. But SM is heuristic and RM is more determined.
Hart's paper contains k*m*n multiplication. k is sought value, m is tuning parameter. He advises set m=480. We took Hart almost as is.
One small result of our work that RM explains some limits of SM as we think.

Quote:
From your paper I derived that you propose multipliers m like 24, 120, 480, 5040, where smaller m are better suited for small n, and bigger m better for bigger n.
As for strategy of choosing of m value in RM (and in SM too) we wrote you notes to our paper in this discussion above (read about "compromise").

Quote:
I implemented your SM algorithm in Java in https://github.com/TilmanNeumann/jav...art_Nesio.java
SM is Hart's simple multiplication.

Quote:
and tested it for n from 20 to 50 bit with the following multipliers m:
1, 4, 24, 48, 120, 240, 720, 1260, 1440, 5040, 10080, 40320, 80640, 110880, 362880, 725760.
Surprisingly I found that 10080 is the best m in the whole n-range. The reason is that I compute the sqrt(k) values already at the construction time of the algorithm. This is a big speedup because we can replace a sqrt by a double multiplication.
But the double multiplication hardly cares about the size of its arguments; thus the size of m only matters in the k*m*n multiplication now, if at all.
Glad that our paper helped you a little in this case.

Quote:
Considerung that your SM algorithm does not use adjustments by congruences it is quite fast. Nonetheless the congruence adjustments mean a further speedup. According to my tests with semiprimes having smaller factor between cbrt(n) and sqrt(n), Hart_Fast seems to be constantly about factor 1.46 faster than Hart_Nesio.
In our work we preferred to compare clear (naked, basic) algorithms without tricks. Improvement is another task to do.
nesio is offline   Reply With Quote
Old 2019-04-03, 17:52   #18
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

39010 Posts
Default

Quote:
Originally Posted by nesio View Post
Hi,Till!
Thanks for the curious links to your and Thilo work.

What's curious about it?


Quote:
Originally Posted by nesio View Post
Improvement is another task to do.

Sure.
Till is offline   Reply With Quote
Old 2019-04-03, 21:15   #19
nesio
 
Apr 2019

408 Posts
Default

Quote:
Originally Posted by Till View Post
Here is a performance comparison with 100k test numbers of the mentioned kind (semiprimes with smaller factor between cbrt(n) and sqrt(n) ) from 30 to 50 bit, including a couple of other algorithms, too.
Till!
We are not ready to comment on your test results now because it needs to analyze your program realization. But it'll demand the time.
However, we have a question. Why your listing contains errors of factorization? Look the table at the attachment, please. There are values of multiplier "m" in the first column. Our SM and RM code found factors of your numbers that contain errors.
Also, this table returns us to the questions (topics) which we touched on in our paper about some hard-factoring numbers for MMFFNN method, about choosing of parameter "m", about some advantage of RM vs SM and so on.
Attached Thumbnails
Click image for larger version

Name:	Till_test_exeptional_numbers.jpg
Views:	25
Size:	107.1 KB
ID:	20160  
nesio is offline   Reply With Quote
Old 2019-04-03, 21:55   #20
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·3·5·13 Posts
Default

Those errors occur because the sqrt arrays I used are not big enough for the n's in question. In my implementation of your SM algorithm I only stored sqrt(km) for k<=2^21.
Till is offline   Reply With Quote
Old 2019-04-04, 13:11   #21
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by Till View Post
Actually RM does not look that promising to me. Compared to SM, its advantage in terms of iterations is only 0.6% at 16-digit inputs, but it will (quite certainly) need more instructions per iteration.

Of course it is fair and interesting to investigate such issues. But the final goal is better performance, no?

We found another way to arrange k-values in a good way in class Lehman_CustomKOrder. For "bigger" n like 50 bits, it is around factor 1.4 faster than Lehman_Fast that was reproduced in C by bsquared with some success. Lehman_CustomKOrder's performance is pretty similar to that of our Hard_Fast implementation. The performance of Hard and Lehman seems to be converging. Maybe there is not much space for improvement left (considering current architectures).
Till!
If you dream to accelerate SM (a-la-Hart) algorithm please take our advices which are based on our work on MMFFNN method.
1. use constant multiplier 4 in all sqrt equations (4*k*n*m - you understand me)
2. use optimum strategy of choosing a multiplier m (we wrote about):
2.1 the smaller n the smaller m and vice versa
2.2 optimize between the cost of multiplication by m (negative factor) and the presence of more prime divisors of m (positive factor)
3. remember about some hard-factoring numbers n in MMFFNN methods (both SM and RM) because Fermat has cycling addition, Lehman has cycling multiplication and addition, MMFFNN has multiplication only:
3.1 hard-factoring numbers have a special ratio a/b where a*b=n; try to consider such "ratios"
4. use fast multiplication methods by k or speed up multiplication operation by k in 4*k*n*m
5. use the consequences from RM method:
5.1 use SM technique while k < (m*n)^(1/3)
5.2 use RM technique when k > (m*n)^(1/3) (you can emulate recursion without call of recursion)
5.3 use in RM your version of isSieve function (an example for your task here: let k is k=k1*k2*k3 in RM; try to sieve excess iterations of seeking k when for example k=24=1*2*12=1*3*8=2*2*6=2*3*4
6. at last use !_additional_! recommendations for improvements from Lehman's and Hart's papers for SM algorithm (we didn't consider them in our work).
nesio is offline   Reply With Quote
Old 2019-04-04, 13:48   #22
DukeBG
 
Mar 2018

3×43 Posts
Default

Quote:
Originally Posted by Till View Post
What's curious about it?
They just meant "interesting", a mistranslation. "Program realization" was supposed to be "implementation", et cetera. Minor language barrier.
DukeBG is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Diamond multiplication and factorization method datblubat Computer Science & Computational Number Theory 6 2018-12-25 17:29
The natural progression of (even perfect numbers)*3 Dubslow Aliquot Sequences 6 2018-05-15 15:59
Montgomery method in Prime Numbers: ACP SPWorley Math 5 2009-08-18 17:27
Elliptic Curve Method factoring - Fermat numbers philmoore Math 131 2006-12-18 06:27
Prime Numbers: Nothing but Errors in Multiplication??? Pax_Vitae Miscellaneous Math 15 2005-11-14 12:41

All times are UTC. The time now is 07:38.

Sun Jul 5 07:38:07 UTC 2020 up 102 days, 5:11, 1 user, load averages: 1.32, 1.34, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.