mersenneforum.org Multiplication method for factoring natural numbers
 Register FAQ Search Today's Posts Mark Forums Read

2019-04-08, 13:53   #45
nesio

Apr 2019

2016 Posts

Quote:
 Originally Posted by ThiloHarich - 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.

2019-04-08, 15:22   #46
Till

"Tilman Neumann"
Jan 2016
Germany

2×7×31 Posts

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

We are working on it.

 2019-04-08, 16:50 #47 Till     "Tilman Neumann" Jan 2016 Germany 2×7×31 Posts @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
 2019-04-08, 17:15 #48 nesio   Apr 2019 25 Posts 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
 2019-04-08, 18:27 #49 Till     "Tilman Neumann" Jan 2016 Germany 2×7×31 Posts 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.
2019-04-08, 18:55   #50
nesio

Apr 2019

25 Posts

Quote:
 Originally Posted by Till 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.

 2019-04-09, 10:05 #51 Till     "Tilman Neumann" Jan 2016 Germany 2·7·31 Posts 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.
 2019-04-09, 10:59 #52 nesio   Apr 2019 3210 Posts 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
 2019-04-11, 18:50 #53 nesio   Apr 2019 25 Posts 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
 2019-04-12, 13:27 #54 Till     "Tilman Neumann" Jan 2016 Germany 2·7·31 Posts 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
 2019-04-12, 17:53 #55 nesio   Apr 2019 25 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post datblubat Computer Science & Computational Number Theory 6 2018-12-25 17:29 Dubslow Aliquot Sequences 6 2018-05-15 15:59 SPWorley Math 5 2009-08-18 17:27 philmoore Math 131 2006-12-18 06:27 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