mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-04-08, 13:53   #45
nesio
 
Apr 2019

2016 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
- Choosing the right m depends on the implementation.
... ... ...
the numbers from nesio model : 6,12,36,60,120,360,720,1680,...
... ... ...
- the number of divisors is the product of the exponents + 1 of its prime factors
Thilo!
36 = (2^2)*(3^2), so "number" = 2*2+1=5, as you wrote.
all divisors of 36 (excluding 1 and 36) are: 2, 3, 4, 6, 9, 12, 18, so "number" = 7, as we wrote.
nesio is offline   Reply With Quote
Old 2019-04-08, 15:22   #46
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2×7×31 Posts
Default

Quote:
Originally Posted by chalsall View Post
Just to share, it's been wonderful watching you two work with each other. Inspiring!

We are working on it.
Till is offline   Reply With Quote
Old 2019-04-08, 16:50   #47
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2×7×31 Posts
Default

@nesio:


while working on the implementation of your propostion I found an obstacle: S depends on n. So we should rather define your measure as

Code:
score(m, n) = S(m) / n^(1/3) with S(m) = number of divisors(m) without 1 and m
and unfortunately it cannot be computed before n (or its approximate size) is known. That's probably the reason why RM computes the m in a recurrent fashion?

Last fiddled with by Till on 2019-04-08 at 16:59 Reason: number, not sum
Till is offline   Reply With Quote
Old 2019-04-08, 17:15   #48
nesio
 
Apr 2019

25 Posts
Default

It seems natural for us. There is n as input. So we need to define suitable m. After that we can start SM or RM algorithm.

Last fiddled with by nesio on 2019-04-08 at 17:26 Reason: lang
nesio is offline   Reply With Quote
Old 2019-04-08, 18:27   #49
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2×7×31 Posts
Default

Ok. So finally we identified a fundamental difference in our approaches:
* Thilo and me usually sort the m's before knowing n.
* You compute the (order of) m after n gets known.
Till is offline   Reply With Quote
Old 2019-04-08, 18:55   #50
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by Till View Post
Ok. So finally we identified a fundamental difference in our approaches:
* Thilo and me usually sort the m's before knowing n.
* You compute the (order of) m after n gets known.
we understood that.
you make preliminary calculations and place them in captured memory to speed up calculations.we understood that.
you make preliminary calculations and place them in captured memory to speed up calculations.
nesio is offline   Reply With Quote
Old 2019-04-09, 10:05   #51
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·7·31 Posts
Default

So for each n that you want to factor, you have to evaluate score(m,n) for several m first in order to find a good m. Evaluating score(m,n) includes computing the sum of divisors of m.


Sorry, but I can not imagine at all how to turn that into a reasonable fast implementation.



I tried another measure: score(m) = S(m) / m^(1/3). There is still a tradeoff between smoothness and size, just that we consider the size of m instead of the size of n. Now the score can be computed before we start to factor some n's. But plugging that into the Hart-Algorithm is still slower than Hart_Nesio (which is a Hart with constant m=10080), which again was slower than Hart_Fast.



I thank you for your patience and informations and wish you good luck.
Till is offline   Reply With Quote
Old 2019-04-09, 10:59   #52
nesio
 
Apr 2019

3210 Posts
Default

Til!

So for each n that you want to factor, you have to evaluate score(m,n) for several m first in order to find a good m. Evaluating score(m,n) includes computing the sum of divisors of m.

Til!
Our model (procedure) of m gives a simple dependency if you change n to a digit size of n.

=============================
If you an Thilo will write and publish a final article about your results of the acceleration of Lehman and Hart, please let us know about it on e-mail.

Wish you and Thilo the best.

Last fiddled with by nesio on 2019-04-09 at 11:13 Reason: lang
nesio is offline   Reply With Quote
Old 2019-04-11, 18:50   #53
nesio
 
Apr 2019

25 Posts
Default

In private forum correspondence we have been asked about examples of speedups for multiplication method of factoring numbers.
Here we attach the results of simple ways of speedups. We took the Table 2 from our article and appended there 2nd and 3rd columns. The 2nd column contains the results of improved performance.
If this is interesting then we can comment on these simple improvements of the multiplication method.
Attached Thumbnails
Click image for larger version

Name:	Table_2 - speedups MMFFNN algorithm.jpg
Views:	70
Size:	49.1 KB
ID:	20197  
nesio is offline   Reply With Quote
Old 2019-04-12, 13:27   #54
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

2·7·31 Posts
Default

This is certainly a good improvement and I am quite sure it will be interesting to more people than Thilo and me how you did it.

I want to apologize that some of the struggle in this thread resulted from me being unable to read or understand your posts correctly. For example, I did not read your post #37 thoroughly enough.

score(m, n) = S(m)/m^(1/3), m<=n^(1/3) can be computed in advance for some exemplaric n, e.g. n=10^1, 10^2, 10^3 etc. as you did in post #41. From that we can choose some "best" m for each n-size. Then when it comes to factor some concrete n of a certain size, just pick the m that was chosen for that size.

Last fiddled with by Till on 2019-04-12 at 13:37 Reason: score computation
Till is offline   Reply With Quote
Old 2019-04-12, 17:53   #55
nesio
 
Apr 2019

25 Posts
Default

To get shown improvement of metric q(r) you should

1. take SM (Simple Multiplication) algorithm (see pseudo-code in our paper which was pointed out in post #1);
2. add there constant multiplier "4" and use 4*m*n*k multiplication everywhere instead of m*n*k;
3. apply simplified rule to multiplier "m": if the decimal size of n <= 3 then m = 120 (5!) else m = 5040 (7!);
4. apply simplified sieve: increment variable "iteration" and take sqrt if radical expression (i.e. the expression under the square root) ends in the following decimal digits: 00, 01, 04, 09, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96, otherwise don't do that;
5. if the value "k" becomes k > m*n then continue the calculations by the RM (Recursive Multiplication) algorithm using there rules №№3,4 there also.

BTW the rule №4 you can apply to Lehman's algorithm too.
nesio 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:57.

Thu May 6 07:57:01 UTC 2021 up 28 days, 2:37, 0 users, load averages: 1.56, 1.77, 1.81

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.