mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-04-07, 16:35   #34
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

10110 Posts
Default

Sorry.

The sum of all divisors - not only the prime divisors I thought of - can be higher then the number itself. So I misinterpreted your model.

So yes abundant numbers https://en.wikipedia.org/wiki/Abundant_number are good candidates.
But for example 105 and 15 are no such numbers but are good 'k'.

Last fiddled with by ThiloHarich on 2019-04-07 at 17:01
ThiloHarich is offline   Reply With Quote
Old 2019-04-07, 17:03   #35
nesio
 
Apr 2019

25 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
Sorry.

The sum of all divisors - not the prime divisors I thought of - can be higher then the number itself. So I misinterpreted your model.

So yes abundant numbers https://en.wikipedia.org/wiki/Abundant_number are good candidates.
But for example 105 and 15 are no such numbers but are good 'k'.
Sum means here the amount, quantity.

Last fiddled with by nesio on 2019-04-07 at 17:11 Reason: grammar correction
nesio is offline   Reply With Quote
Old 2019-04-07, 18:16   #36
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1101101002 Posts
Default

Quote:
Originally Posted by nesio View Post
Sum means here the amount, quantity.

We have some language problems here. Just to clarify:

12 has divisors 1, 2, 3, 4, 6, 12. Is 6 the result you mean, or is it 28?

Quote:
Originally Posted by ThiloHarich View Post
why should my model be very rough?
The rough model is the one he proposed, not yours:

Quote:
Originally Posted by nesio View Post
You can check this rough (very rough) model of m on your source data of n:
maximum(S/(m^1/3)) and m < n^1/3,
where S - the sum of all divisors of m.
Here are S and m^1/3 have equal weights in maximum function.
What will be?
I interprete this as follows:

The quality of a multiplier m is about S/(m^1/3), where we consider m < n^1/3 only.


S might be
a) the sum of divisors of m, or
b) the number of disivors of m.
My first question in this post aims to clarify which of the two options is the correct one.

nesio, do I get that right so far?

Last fiddled with by Till on 2019-04-07 at 18:19 Reason: make clear that only one option for S is correct
Till is offline   Reply With Quote
Old 2019-04-07, 18:31   #37
nesio
 
Apr 2019

25 Posts
Default

A rough model of m:
Find the maximum of (S/(m^1/3)) when m < n^1/3,
where S - the number of all divisors of m (excluding 1 and m).
Here are S and m^1/3 have equal weights in maximize function.
nesio is offline   Reply With Quote
Old 2019-04-07, 18:43   #38
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

22×109 Posts
Default

Quote:
Originally Posted by nesio View Post
S - the number of all divisors of m (excluding 1 and m).

Ok, now we understand that one.


Quote:
Originally Posted by nesio View Post
A rough model of m:
Find the maximum of (S/(m^1/3)) when m < n^1/3,
where S - the number of all divisors of m (excluding 1 and m).
Here are S and m^1/3 have equal weights in maximize function.

I'ld say this is not a model of m, but a procedure to choose the best m. A model would give a kind of score to any m. (at least)



Quote:
Originally Posted by nesio View Post
What will be?

A simple weighting function giving a "plus" for smooth m, a "minus" for big m.


This is no rocket science. We tested dozens of ways to arrange k's according to such principles, and many other constellations...
Till is offline   Reply With Quote
Old 2019-04-07, 19:04   #39
nesio
 
Apr 2019

25 Posts
Default

Is it working on your data and what are the results?

Last fiddled with by nesio on 2019-04-07 at 19:11 Reason: lang
nesio is offline   Reply With Quote
Old 2019-04-07, 19:39   #40
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

22·109 Posts
Default

Unfortunately, none of our attempts to sort k's by such measures worked well.

I believe that you did not try an efficient implementation yet.
Theory (aka computational complexity, counting iterations being a simplified version of) and reality (measuring speed) are quite different for "small" factoring algorithms.
After all, this is the only reason why Lehman or Hart algorithms have a right to exist. Otherwise NFS would wipe out all other algorithms at any number scale.

If you try to optimize Hart/Lehman for small n, say n<=60 bit, then you will realize that instructions that are very fast on that number scale have a big or even decisive impact on the general performance. Complexity theory is often not strong enough to capture such influences. Storing the sqrts of k or of km is such a point. Without it, you will not be able to get a really fast Hart/Lehman implementation. Using congruences is a theoretical improvement, but also necessary.


You can disprove my assumption that you did not try an efficient implementation yet by posting a fast piece of software ;-)
Till is offline   Reply With Quote
Old 2019-04-07, 21:29   #41
nesio
 
Apr 2019

25 Posts
Default

For example such rough model (procedure) gives these values m from n
n m
555 6
5555 12
55555 36
555555 60
5555555 120
55555555 360
555555555 720
5555555555 1680
55555555555 2520
555555555555 5040
5555555555555 5040
55555555555555 5040
555555555555555 5040
It is light and quite workable way for m in "multiplication method" we hope.

Til!
Our work is a research and a paper about Recursive Multiplication algorithm and its relation to Simple Multiplication algorithm.
Your work is improving Lehman and Harts algorithms.
You asked us about our vision regarding m. We wrote then.
Something does not suit you in our discussion?
Let's not continue to cross the red and wet ;-)
We think you and Thilo should write a paper about your work that may be interesting not only in that forum.

Last fiddled with by nesio on 2019-04-07 at 21:30 Reason: lang
nesio is offline   Reply With Quote
Old 2019-04-08, 06:18   #42
Till
 
Till's Avatar
 
"Tilman Neumann"
Jan 2016
Germany

1B416 Posts
Default

Hi nesio,
sorry if I have been unpatient. I do not understand Russian, so I cannot get all information from your paper. And it took some time to get some interesting information from you.



I will try to implement your particular proposition of sorting m by

Code:
score(m) = S(m) / n^(1/3) with S(m) = sum of divisors(m) without 1 and m
this evening.


Maybe we made an error so far in our evaluations of the smoothness of m's. We will see.


You said that the computation of score(m) above is a very rough model. What would a more elaborate model look like?
Till is offline   Reply With Quote
Old 2019-04-08, 06:39   #43
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

23·32·7·19 Posts
Default

Quote:
Originally Posted by Till View Post
What would a more elaborate model look like?
Just to share, it's been wonderful watching you two work with each other. Inspiring!
chalsall is online now   Reply With Quote
Old 2019-04-08, 09:27   #44
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

6516 Posts
Default

- Choosing the right m depends on the implementation.

Til and me used some adjustments/improvements for odd multipliers m -> in our algorithm the good multipliers are not only even, best multipliers are odd.

the numbers from nesio model : 6,12,36,60,120,360,720,1680,... do not appear in the list of good multipliers for this tuned algorithm in the top

- the number of divisors is the product of the exponents + 1 of its prime factors

If the exponents are all 1 then this is just 2^(number of prime factors of m). Having a factor with an exponent greater then one reduces the number of divisors. -> it looks like a good measure for good multipliers. But our best multiplier 315 = 3^2 * 5 * 7 has an exponent 2.

When finding the best multipliers for numbers starting at 2^54 (and only factoring numbers with factors above n^1/3) I get a complete different list then when factoring numbers starting at 2^55.

Last fiddled with by ThiloHarich on 2019-04-08 at 09:33
ThiloHarich 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 14:20.

Fri May 14 14:20:15 UTC 2021 up 36 days, 9:01, 0 users, load averages: 2.02, 2.05, 2.01

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.