20190408, 13:53  #45  
Apr 2019
20_{16} Posts 
Quote:
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. 

20190408, 15:22  #46 
"Tilman Neumann"
Jan 2016
Germany
2×7×31 Posts 

20190408, 16:50  #47 
"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 Last fiddled with by Till on 20190408 at 16:59 Reason: number, not sum 
20190408, 17:15  #48 
Apr 2019
2^{5} 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 20190408 at 17:26 Reason: lang 
20190408, 18:27  #49 
"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. 
20190408, 18:55  #50  
Apr 2019
2^{5} Posts 
Quote:
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. 

20190409, 10:05  #51 
"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 HartAlgorithm 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. 
20190409, 10:59  #52 
Apr 2019
32_{10} 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 email. Wish you and Thilo the best. Last fiddled with by nesio on 20190409 at 11:13 Reason: lang 
20190411, 18:50  #53 
Apr 2019
2^{5} 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. 
20190412, 13:27  #54 
"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 nsize. 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 20190412 at 13:37 Reason: score computation 
20190412, 17:53  #55 
Apr 2019
2^{5} Posts 
To get shown improvement of metric q(r) you should
1. take SM (Simple Multiplication) algorithm (see pseudocode 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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Diamond multiplication and factorization method  datblubat  Computer Science & Computational Number Theory  6  20181225 17:29 
The natural progression of (even perfect numbers)*3  Dubslow  Aliquot Sequences  6  20180515 15:59 
Montgomery method in Prime Numbers: ACP  SPWorley  Math  5  20090818 17:27 
Elliptic Curve Method factoring  Fermat numbers  philmoore  Math  131  20061218 06:27 
Prime Numbers: Nothing but Errors in Multiplication???  Pax_Vitae  Miscellaneous Math  15  20051114 12:41 