in reply to OT: Finding Factor Closest To Square Root

Maybe one of the mathematician's will show me the error of my ways, but I think that the prime factors thing is a red-herring.

The following brute force approach works quite quickly for numbers up to about 12 or 13 digits, usually much more quickly that it takes M::B::F to find the prime factors.

If you're looking to do this with very large numbers (as suggested by your use of Math::Big), then your probably in for a long wait either way. If the number in question is itself prime, then the nearest factor to the square root will be 1. That means you have to add 1 to list that factor_wheel() produces before you start doing your combinatorics, and it's presence just slows the search to what effectively amounts to a linear search anyway. 

#! perl -slw
use strict;

my $NUM = $ARGV[ 0 ] || die 'No arg';

my $root = sqrt( $NUM );
my( $lo, $hi ) = ( int( $root ), int( $root + 1 ) );;

$lo-- while $NUM % $lo;
$hi++ while $NUM % $hi;

my $near = ( $lo, $hi )[ abs( $root - $lo ) > abs( $root - $hi ) ];

print "$NUM ($root) : $near";

[download]
Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.

Replies are listed 'Best First'.
Re^2: OT: Finding Factor Closest To Square Root
by sleepingsquirrel (Chaplain) on Feb 20, 2005 at 01:00 UTC
    Do you really have to do a search for numbers greater than the sqrt(N)? (See Re: OT: Finding Factor Closest To Square Root for my approach). Certainly you don't have to go beyond 2*sqrt(N) on the ++ side. In fact I'm currently thinking the closest factor has to be less than sqrt(N), eliminating any checking for factors greater than sqrt(N). I'd be interested to see if someone could construct a counter-example (a number where the closest factor to sqrt(N) is greater than sqrt(N)).

    -- All code is 100% tested and functional unless otherwise noted.
[reply]
      Do you really have to do a search for numbers greater than the sqrt(N)?

      You right. And now you pointed it out, it seems fairly obvious:

      3600: sqrt=60; 59* 61= 3599

      10000: sqrt=100; 99*101= 9999

      12: sqrt=3.464; 3* 4= 12

      Which, in very non-technical terms because my memory doesn't go back to my formal math days, says to me that:

      with lo = int( sqrt( N ) ) & hi = int( sqrt( n ) )+1; lo * hi is always less than or equal to N.

      If you reduce lo, leaving hi the same, you get further away from N. And if you increase hi, lo will be nearer.

      Does that form an explaination? Hmm. Maybe one of our resident math whiz can phrase that correctly?

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.
[reply]
        Here's an informal proof of our conjecture "The factor of N closest to sqrt(N) is less than sqrt(N)".
        1. Let M be the positive square root of N. (M*M = N, M>0)
        2. The closest factor to M is bewteen 1 and 2*M. (i.e. 1 is closer to M than any number greater than twice M. (M-1 < 2*M-M))
        3. For every pair of numbers whose product is N, one of the pair will be greater than M and the other less than M. (the product of two numbers greater than M is greater than N, and the product of two numbers less than M would be less than N)
        4. Take a pair of numbers whose product is N. Call the smaller (M-X) and the larger (M+Y). (i.e. X>0, Y>0)
        5. So, (M-X) * (M+Y) = N
        6. Multiplying out, M^2 + M*(Y-X) - X*Y = N
        7. But M^2 = N (by definition)
        8. Substituting: N + M*(Y-X) - X*Y = N
        9. Subtracting N: M*(Y-X) - X*Y = 0
        10. Since X and Y are positive (by definition, step 4), the term -X*Y is negative
        11. If -X*Y is negative, the only way for the entire sum to equal 0 is if the term M*(Y-X) is positive
        12. But M is positive (step 1), so (Y-X) must also be positive, which means that Y is greater than X.
        13. Finally, if Y is greater than X, the smaller factor, (M-X) is closer to M than (M+Y), so you can limit your factor search to numbers less than sqrt(N).

        -- All code is 100% tested and functional unless otherwise noted.
[reply]
      Certainly you don't have to go beyond 2*sqrt(N) on the ++ side

      The high side search would always have terminated there or earlier anyway as it stopped as soon as the difference between it and the root was greater than that between lo and root. Lo can't go below 1, so hi would never go above root*2-1. But skipping the hi search is much better.

      Another optimisation possible if N is odd, is to step back by 2 each time.

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.
[reply]
        Another optimisation possible if N is odd, is to step back by 2 each time.
        And if N is even, factor out all the powers of 2, and run the algorithm against the remaining factor. For example, 
        1000 == 2**3 * 5**3

        [download]
        which leaves 
        125 == 5**3

        [download]
        leading to 
        5 * 2**2 == 20

        [download]
        as "close enough".

        -QM
        --
        Quantum Mechanics: The dreams stuff is made of

[reply]
[d/l]
[select]
Re^2: OT: Finding Factor Closest To Square Root
by chas (Priest) on Feb 20, 2005 at 23:08 UTC
    My feeling is that you are correct that the prime factorization is a red-herring for the reasons I mentioned in another post in this thread (solving the problem using that info is probably NP hard.) However, finding any nontrivial factor of a large number may be just as hard. Clearly, if one could do that in a reasonable time, then one could also find the prime factorization in a reasonable time. This would upset many people so much that I believe it is forbidden to publish any such result...even partial ones!! (Such results would defeat many common encryption schemes.)
    chas
    (***This was supposed to be in reply to BrowserUk's 432772 post,but it didn't seem to appear in the right position...likely something I did wrong...)
[reply]

In Section Seekers of Perl Wisdom