Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

OT: Finding Factor Closest To Square Root

by QM (Vicar)
on Feb 18, 2005 at 22:47 UTC ( #432558=perlquestion: print w/ replies, xml ) Need Help??
QM has asked for the wisdom of the Perl Monks concerning the following question:

Given N, and a list of prime factors of N's prime factorization (a list) from Math::Big::Factor::factors_wheel(), I need to find a (possibly composite) (integer) factor near the square root of N.

Is there a nice dynamic programming routine to get reasonably close?

Update:: clarified what Math::Big::Factor::factors_wheel() returns.

Update: Finding the nearest factor less than or equal to the square root, or even it's prime factorization, is sufficient for my needs, and may speed up the search in some cases. (Though the more general problem of "finding the factor nearest the square root, on either side" might be interesting too.)

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

Comment on OT: Finding Factor Closest To Square Root
Select or Download Code
Re: OT: Finding Factor Closest To Square Root
by dragonchild (Archbishop) on Feb 18, 2005 at 23:05 UTC
    Find the two factors in the middle. Their product should be closest to the square root.

    Being right, does not endow the right to be rude; politeness costs nothing.
    Being unknowing, is not the same as being stupid.
    Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
    Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

      Sorry, I was sloppy before...

      Math::Big::Factor::factors_wheel() doesn't give all factors, but the prime factorization.

      For instance,

      factors_wheel(1000) == (2, 2, 2, 5, 5, 5);

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

        Since you've got them in ascending order, take every other prime factor and multiply. Compare that to the product of the ones you didn't choose. Whichever's closer, there ya go. That's just off the top of my head.

        Let's try another way. Pretty clearly, you want roughly half the factors. You can work from the outside in, or the inside out, or do something like this: If you have N factors, take the (N*2)th root of the number. Find the factor closest to that. Divide your number by the square of the chosen factor, decrement N, and repeat until you get further from the square root instead of closer to it.


        Caution: Contents may have been coded under pressure.

        If you get a list of prime factors in ascending order, then I would take every other member of the list, multiply them together and start with that.

        In your example, that would give you 20, which isn't too far from the correct result of 31.

        Hmm .. Actually, an even better answer would be

        • for a list with an odd number of elements, take all of the odd position numbers and multiply them together;
        • for a list with an even number of elements, take the odd numbered elements from 1 to (n/2)-1, and the even numbered elements from n down to (n/2)+2, and multiply them together with the harmonic mean of the (n-1)/2 and n/2 elements.

        For your example, that would be 2 * sqrt(2*5) * 5, which turns out to be exactly the correct answer, 31.622..

        To try out the odd number, we'll try out 2000, which gives us a list of (2, 2, 2, 2, 5, 5, 5) and a result of 2 * 2 * 5 * 5 or 100. Hmm, a little high.

        Well, that's a fascinating question, and good luck with that.

        Alex / talexb / Toronto

        "Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds

        One way to do it, similar to talexb, would be (tested!)
        use Math::Big::Factors; my $val = 2000; my @x = Math::Big::Factors::factors_wheel( $val ); print "@x\n"; my %factors; $factors{$_}++ for @x; use Data::Dumper; print Dumper \%factors; my $sqrt = 1; while (my ($k,$v) = each %factors) { while ($v > 1) { $sqrt *= $k; $v -= 2; } if ($v) { $sqrt *= sqrt( $k ); } } print "$sqrt => ", sqrt( $val ), $/;
        This is going to be slower that just taking the sqrt of the value. Just to let you know ...

        Being right, does not endow the right to be rude; politeness costs nothing.
        Being unknowing, is not the same as being stupid.
        Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence.
        Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.

Re: OT: Finding Factor Closest To Square Root
by BrowserUk (Pope) on Feb 19, 2005 at 00:02 UTC

    Update: Ignore this, it doesn't work.

    You'll have tp pretend that I have M::B::F::f_w().. CPAN's being boring.

    #! perl -slw use strict; use List::Util qw[ reduce ]; my $root = sqrt 1000; my @pfs = ( 2, 2, 2, 5, 5, 5 ); my $near = reduce{ $a * $b < $root ? $a*$b : $a } reverse @pfs; print +( $root - $near ) < ( $near * $pfs[0] - $root ) ? $near : $near * $pfs[0];

    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
      I rearranged it a bit so you can just plug in your factor list and it will figure out what your number is. Note that in this case, the closest value is 5*7, but it returns 3*19.
      use strict; use warnings; use List::Util qw[ reduce ]; my @pfs = ( 3,5,7,19 ); my $num = reduce { $a * $b } @pfs; my $root = sqrt $num; print "N=$num, R=$root\n"; #the rest is the same as you had it
      Here's a fix:
      use strict; use warnings; use List::Util qw[ reduce ]; my @pfs = ( 3,5,7,19 ); my $num = reduce { $a * $b } @pfs; my $root = sqrt $num; print "N=$num, R=$root\n"; my $near = reduce{ abs($root - $a * $b) < abs($root - $a) ? $a*$b : $a } reverse @pfs; print abs($root - $near) > abs($root - ($num/$near)) ? $num/$near : $near ;

      Caution: Contents may have been coded under pressure.

        One testcase was never going to hack it. I should have thought of your method, but I was too busy trying to figure out why CPAN would install M::B::F.


        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
Re: OT: Finding Factor Closest To Square Root
by chas (Priest) on Feb 19, 2005 at 01:09 UTC
    I'm not sure about "reasonably close", but I think that actually finding the factor closest to the square root is very difficult. Curiously, I think it is likely that even if one knew the factor closest to the square root, writing it as a product of the given prime factors is itself very difficult. (And the given problem seems harder than this latter one.)
    This seems quite similar to the problem: given a finite set of natural numbers and another "target" natural number, find a subset of the given finite set whose sum is the target number? (or determine that this is not possible.) This is known to be NP hard (and so probably takes exponential time although this is a big open question.)
    (Of course the problem may have no good solution - consider a number of the form 2p where p is a large prime.)
    chas
      You have the right of it. More precisely, take the logarithim. Then the problem becomes finding a sum of log prime factors that is closest to log(N)/2. This problem is reducible to the subset sum problem, which is NP-hard.

      Although exact solutions are exponential, heuristics can sometimes generate good answers with minimal effort. One example of a heuristic that might work well is the greedy heuristic. To fill a box of size log(N)/2, put the largest factor into the box. Then put the next largest factor that still fits in the box and insert it. Keep doing this until no more factors fit.

      The above will get you the largest factor <= sqrt(N). To get the smallest factor >= sqrt(N), put all the factors in a box, and take them out again largest to smallest, until no more can be taken out. Finally, comapre the two answers to find the closest.

      Update: fixed a typo.

      -Mark

        To fill a box of size log(N)/2, put the largest factor into the box. Then put the next largest factor that still fits in the box and insert it. Keep doing this until no more factors fit.

        The above will get you the largest factor <= sqrt(N). To get the smallest factor >= sqrt(N), put all the factors in a box, and take them out again largest to smallest, until no more can be taken out. Finally, comapre the two answers to find the closest.

        I don't think that does what you think. For example, 2**3 * 19**3 = 54872, and the square root is 234.277....

        Your method gives 19 as the largest less than the square root, and 2**3 * 19**2 = 2888 as the smallest greater than the square root. Notice that 19*2888 = 54872.

        A better result is 2**3 * 19 = 152 (because 19**2 = 361).

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

Re: OT: Finding Factor Closest To Square Root
by artist (Parson) on Feb 19, 2005 at 03:17 UTC
    Can you tell us, why you need to find that one? May be we can come up with non-exhaustive alternatives.
      Can you tell us, why you need to find that one? May be we can come up with non-exhaustive alternatives.
      OK, but I was so enjoying the direction the discussion was going, and I didn't want the thread to lose the focus on the problem I stated. But here goes...

      At various times I've been bitten by the Fibonacci bug, like many others. I've tried my hand at programming F(n), as well as some other interesting things like a prime tester .

      Poking around on Mathworld, I read the Fibonacci page. One of the formulas is

      F(k*n) = L(k)*F(k*(n-1)) - ((-1)**k)*F(k*(n-2))
      where
      L(k) = F(n-1) + F(n+1)
      and substituting
      F(k*n) = (F(n-1)+F(n+1))*F(k*(n-1)) - ((-1)**k)*F(k*(n-2))
      For computing F(k*n), this is most efficient when k==n, giving
      F(n**2) = (F(n-1)+F(n+1))*F(n*(n-1)) - ((-1)**n)*F(n*(n-2))
      If N is prime, use
      F(2*k+1) = F(k+1)**2 + F(k)**2
      As an exercise in programming and improving my grasp of math and computational complexity, I was going to benchmark several methods of computing F(N). Included in this is the standard recursive solution (which is too slow, but we can estimate it's behavior for large N), the closed form using phi, and various identities.

      The identity for F(k*n) seemed to be the most promising in this area, though computing sqrt(N), and/or factoring N, would seem to negate any benefits. Perhaps a quick check to see if N has any small factors, otherwise use the F(2*k+1) identity for odd N, or one of the F(2*k) formulas for even N. (There's a nice identity for N % 3 == 0 too.)

      Update: fixed missing parens in formulae.

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

        Programming F(n) for benchmarking purposes is interesting. However, the fastest way of all is probably:
        F(n)= integer nearest (1/sqrt 5)[(1+sqrt 5)/2]^n

        This isn't perl, but it would only take a line. (If n is extremely large, the exponentiation might become inaccurate, though...)
        chas
Re: OT: Finding Factor Closest To Square Root
by BrowserUk (Pope) on Feb 19, 2005 at 04:49 UTC

    Not sure if this is correct either, but I checked a few cases and it appears to work. Is there a good method of verification?

    It starts to get slow with big numbers, but it's much quicker than factors_wheel() finding the prime factors, for all the cases I tried.

    There appears to be a bug in the overloading in Math::Big, hence the de-Bignumming map.

    Update: Version 3. Anyone care to break this one for me?

    #! perl -slw use strict; use overload; use Math::Big::Factors qw[ factors_wheel ]; use List::Util qw[ reduce min ]; use Algorithm::Loops qw[ NestedLoops ]; my $NUM = $ARGV[ 0 ] || 996; my $root = sqrt $NUM; my @pfs = reverse map{ "$_" } factors_wheel( $NUM ); print "$NUM primefactors ( @pfs )"; my $n = $pfs[ 0 ]; while( @pfs > 1 ) { # print "@pfs"; my $near = reduce{ ( $a * $b ) <= $root ? $a*$b : $a } @pfs; # print "$near : ", $NUM%$near; $n = $near if ( $NUM % $near ) == 0 and abs( $root - $near ) < abs( $root - $n ); my $discard = shift @pfs; next if $pfs[ 0 ] == $discard; unshift @pfs, $pfs[0] while $root > reduce{ $a * $b } @pfs; } print "$NUM ($root} : $n"; __END__ P:\test>432558 1995 1995 primefactors ( 19 7 5 3 ) 1995 (44.6654228682546} : 35 P:\test>432558 1994 1994 primefactors ( 997 2 ) 1994 (44.6542271235322} : 997 P:\test>432558 1993 1993 primefactors ( 1993 ) 1993 (44.6430285710994} : 1e+099 P:\test>432558 1993 1993 primefactors ( 1993 ) 1993 (44.6430285710994} : 1993 P:\test>432558 1994 1994 primefactors ( 997 2 ) 1994 (44.6542271235322} : 997 P:\test>432558 1995 1995 primefactors ( 19 7 5 3 ) 1995 (44.6654228682546} : 35 P:\test>432558 9999999 9999999 primefactors ( 4649 239 3 3 ) 9999999 (3162.27750205449} : 2151 P:\test>432558 99999999 99999999 primefactors ( 137 101 73 11 3 3 ) 99999999 (9999.99995} : 7373 P:\test>432558 999999999 999999999 primefactors ( 333667 37 3 3 3 3 ) 999999999 (31622.7765858724} : 2997 P:\test>432558 1000 1000 primefactors ( 5 5 5 2 2 2 ) 1000 (31.6227766016838} : 25 P:\test>432558 2000 2000 primefactors ( 5 5 5 2 2 2 2 ) 2000 (44.7213595499958} : 40 P:\test>432558 20000 20000 primefactors ( 5 5 5 5 2 2 2 2 2 ) 20000 (141.42135623731} : 125 P:\test>432558 200000 200000 primefactors ( 5 5 5 5 5 2 2 2 2 2 2 ) 200000 (447.213595499958} : 400

    Don't


    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
      Maybe I don't understand the OP's requirements, but 36 isn't a factor of 996 (996/36 = 27.666...). I'm guessing he wants 12 (3*2*2) for that case. And 32 isn't a factor of 1000, but 25 is. etc. Am I missing something?


      -- All code is 100% tested and functional unless otherwise noted.
        Am I missing something?

        Nope. Nothing at all.

        Your just witnessing me loosing sight of the OP's requirements whilst getting caught up with the mechnics of the code. :(


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

        I updated 432636. Does the new version look any better?

        That's the problem with hueristics--how do you validate them?


        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
Re: OT: Finding Factor Closest To Square Root
by sleepingsquirrel (Hermit) on Feb 19, 2005 at 17:04 UTC
    Doesn't use Math::Big::Factor, isn't particularly dynamic, doesn't have exponential complexity, and could be much faster in C. With all those caveats, here you go...
    #!/usr/bin/perl -w use strict; print sqrt_factor(shift), "\n"; sub sqrt_factor { my $n = shift; my $root = int(sqrt($n)); for (my $i=$root; $i>1; $i--) { if( ($n % $i) == 0 ) { my $factor2 = int($n / $i); return (($root - $i)<($factor2 - $root)) ? $i : $factor2 } } return 1; }


    -- All code is 100% tested and functional unless otherwise noted.
      Yes, but this still takes a long time for large prime N, as it has to count down from sqrt(N) to 1.

      It would go twice as fast if we checked N%2==0. It would go six times as fast if we checked for N%3==0 also. Perhaps using GCD(N,sqrt(N)#) (where N# is the primorial of N) would improve the situation? The problem then becomes one of generating all primes upto sqrt(N), where we could cheat and just have a big list precomputed.

      ...Better yet, would a quick test of N for primality solve the problem of prime N?

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

Re: OT: Finding Factor Closest To Square Root
by lidden (Deacon) on Feb 19, 2005 at 19:41 UTC
    I am almost sure this does what you want. I am also convinced it is rather inefficient.
    my @res = (2, 2, 2, 5, 5, 5); my $goal = 1000; print closest($goal, \@res), "\n"; sub closest{ my $exact = shift; my $array = shift; my $best = 0; for my $n ( get_numbers($array) ){ $best = $n if abs( $exact - $n**2) < abs( $exact - $best**2); } $best; } sub get_numbers{ my $array = shift; my $length = @$array; if ($length == 1){ return ( $array->[0] ); } else{ my @ret_arr; my $n = shift @$array; push @ret_arr, $n; my @tmp = get_numbers($array); push @ret_arr, @tmp; push @ret_arr, $n*$_ for @tmp; prune(@ret_arr); } } sub prune{ my %h; undef $h{$_} for @_; keys %h; }
    Uppdate: Cleaned up it a little,removing some(most) of the inefficiense.
      I am almost sure this does what you want. I am also convinced it is rather inefficient.
      Yes on both counts. But I like the hand-crafted code approach :)

      I rather hoped that someone would reveal a method using the prime factorization, or an efficient method for finding a factor reasonably close to the square root.

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

Re: OT: Finding Factor Closest To Square Root
by BrowserUk (Pope) on Feb 19, 2005 at 20:08 UTC

    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";

    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
      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.
        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.
        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.
      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...)
Re: OT: Finding Factor Closest To Square Root
by Roy Johnson (Monsignor) on Feb 22, 2005 at 14:53 UTC
    Here it is, fast and accurate. The comments should describe the algorithm pretty well.
    use strict; use warnings; use List::Util qw[ reduce ]; my $num; # Used in sub, but could be passed if you wanted sub closest { # Args are target and factor-list my ($target, @factors) = @_; # Take the biggest factor my $top_factor = pop @factors; # Find multiple of that factor closest to (and above) target my $guess = int($target) - $target % $top_factor + $top_factor; # Oscillate around the target, looking at multiples of top_factor # until you get one that divides the product for (my $i=$top_factor; $num % $guess; $i += $top_factor) { $guess += ( $target <=> $guess ) * $i; } # Check the complementary factor my $complement = $num / $guess; abs($target - $complement) < abs($target - $guess) ? $complement : $guess ; } my @pfs = (2,2,2,3,3,3,5,5,5,17,19,19,19,19); # Compute product of factors our ($a, $b); $num = reduce { $a * $b } @pfs; my $root = sqrt $num; print "N=$num, R=$root\n"; print closest($root, 1, @pfs), "\n";

    Caution: Contents may have been coded under pressure.
      That's sweet. I especially like the use of <=> in
      $guess += ( $target <=> $guess ) * $i;
      to choose which direction to move.

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

      Roy Johnson,
      Here it is, fast and accurate.

      Well it is certainly fast, but unfortunately it is not always accurate. Try (3, 5, 16381, 77951) - it should produce 81905 but it produces 77951. I didn't bother debugging as I was gathering statistics.


      Cheers - L~R

        You're right. I had an erroneous understanding: that the closest factor that included top_factor would be paired with the closest factor that didn't. Instead, it's paired with the closest factor on the other side of root that doesn't include top_factor. So you have to check both sides of root. Here's a fixed version:
        use strict; use warnings; use List::Util qw[ reduce ]; my $num; # Used in sub, but could be passed if you wanted sub closest { # Args are target and factor-list my ($target, @factors) = @_; # Take the biggest factor my $top_factor = pop @factors; # Find multiple of that factor closest to (and above) target my $guess = int($target) - $target % $top_factor + $top_factor; # Oscillate around the target, looking at multiples of top_factor # until you get one that divides the product my $i; for ($i = $top_factor; $num % $guess; $i += $top_factor) { $guess += ( $target <=> $guess ) * $i; } # Check the complementary factor my $complement = $num / $guess; # Look for a multiple of $top_factor between the last guess on the # other side of sqrt and $complement my $direction = ($target <=> $guess); my $new_guess = $guess + $direction * $i; while (($complement <=> $new_guess) == $direction and $num % $new_ +guess) { $new_guess += $top_factor * $direction; } if ($new_guess and $num % $new_guess == 0 and (($complement <=> $new_guess) == $direction)) { $guess = $new_guess; $complement = $num/ $guess; } abs($target - $complement) < abs($target - $guess) ? $complement : $guess ; } my @pfs = (3, 5, 16381, 77951); # Compute product of factors our ($a, $b); $num = reduce { $a * $b } @pfs; my $root = sqrt $num; print "N=$num, R=$root\n"; print closest($root, 1, @pfs), "\n";

        Caution: Contents may have been coded under pressure.
Re: OT: Finding Factor Closest To Square Root
by Limbic~Region (Chancellor) on Feb 23, 2005 at 17:07 UTC
    QM,
    I am not sure how I missed this one. I haven't really tried to optimize this at all so it is likely not the fastest (yet). The implementation is as follows:
    • Get a list of prime factors
    • Get a unique list of all combinations of those factors
    • Multiply each combination together
    • Divide the number by the result and subtrace the result
    • Use a low water mark to keep track of the closest
    I had Re^2: Finding all Combinations already and it only needed a minor tweak to return unique combinations - will play to see if I can't improve the speed but it is pretty fast now.

    Cheers - L~R

      Thanks. The other replies seem to be converging to this idea too. I still need to do some benchmarking to determine if this approach saves me time for what I'm using it for.

      Unfortunately, my Benchmark module seems to be broken. Specifically, cmpthese and timethese give really weird results, like some counter is initialized wrong or overflowing. I can time a single pass with new Benchmark, but the timethese loop always warns about not enough iterations, gives practically 0 times, but takes minutes to run. I'll have to dig into it more, and maybe post something here later.

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

        QM,
        If you summarize the routines that produce valid solutions, I will be happy to benchmark. To remove the unfair advantage of determining the prime factorization - this will be done before hand and will be common to all routines

        Cheers - L~R

        QM,
        My latest obsession is with Perl internals, improving my C skills. Inline::C is a great way to do both, so I figured I would translate my previous code (minus the %seen cache). It actually loses when checking just one number, but running it in a loop of a lot of numbers it wins hands down. I am sure someone more knowledgeable could make the C cleaner if not faster.

        Cheers - L~R

        Updated - copy/paste fixed as sleepingsquirrel pointed out below

Re: OT: Finding Factor Closest To Square Root
by Limbic~Region (Chancellor) on Feb 27, 2005 at 21:15 UTC
    QM,
    I have spent far too many cycles on this. Though it may have been your intention, your original question was not:

    Given a number N, find the nearest factor of N less than or equal to the square root of N.

    For that question, tall_man's solution is quite concise, efficient, and elegant. Even though I used Math::Pari instead of Math::Big::Factors to get the prime factorization, I interpreted the question to be more about what came after to be important.

    My first, solution was straight forward and only had a %seen cache optimization, though I knew other optimizations were possible. Next, I came up with a Inline::C implementation of the first solution (minus the cache). It has turned out to be the fastest by far even without the cache.

    Since I was really interested in coming up with a Perl solution that had optimizations, I came up with a second solution. Actually, I came up with about 5 variations on tye's 3 simple rules for generating a powerset in progressive order. The problem in finding the fastest implementation was a strange bug that BrowserUk helped me work around. With that - here is my last attempt (ver_3.pl)

    In case you are interested in knowing how well it works, here are some timings for 50_000 random numbers between 1 and 31_415_926_535: I did try various other solutions in this thread that either ran out of memory (recursive) or just took too long. One note: Roy Johnson's best attempt completes in less than 45 seconds, but unfortunately it has bugs.

    Cheers - L~R

      I can't get Math::Pari to compile on my machine, so I did an inferior benchmarking test (code below) between a pruning combinations method I came up with and your method (which I modified -- I think fairly -- to work on the list of factors instead of generating them). My method ran over three times as fast, but as I say, I didn't benchmark over extensive input values. If it's convenient for you to do so, I'd like to see what results you get when you plug it into your benchmarker.

      Note that I have an optimization that can be commented out. In some cases (including the data used here) it gave me a speedup. In others, a slowdown. It would be interesting to see whether it was, on average, an improvement or not.

      I just added my other method to the test list, and it absolutely blows them out of the water. I had no idea it could be that much faster.

      Closest is 70499 Limbic says: 70499 My other way says: 70499 Rate limbic pruner my_old limbic 8.02/s -- -82% -100% pruner 45.1/s 462% -- -98% my_old 2632/s 32727% 5737% --
      For P=4789309440 (factors (2)x12,3,5,77951), the differences are astronomical:
      P=4789309440, R=69204.8368251815 Closest is 61440 Limbic says: 61440 My other way says: 61440 Rate limbic pruner my_old limbic 0.749/s -- -100% -100% pruner 181/s 24119% -- -97% my_old 5545/s 740213% 2957% --
      and if you try P=2176782336 (which is an exact square with a factor list of ((2)x12, (3)x12))), you will give up waiting for your method.

      Caution: Contents may have been coded under pressure.
        Roy Johnson,
        I am sure once you get all the bugs worked out one of your solutions will be the winner (minus my Inline::C solution). Let me know when you think it is bug free and I will update. As it stands now, it breaks on 13316184461 (45863,290347). It says that 290347 is the answer, but that is larger than the sqrt().

        Cheers - L~R

      I have spent far too many cycles on this...
      Well, goodness!!! I'd accuse you of being obsessive or something, but I think you'd take that as a compliment :).

      I appreciate all of the work you've done, and I see it's been quite a lot. I've been busy myself, off working on my original original problem, though I don't have much interesting to show for it yet.

      I did some preliminary reading on Math::Pari, but was put off by the documentation. I also read that Math::Pari was built on top of GMP, and Math::BigInt can use that too. If Math::Pari gives me all of the factors, I might use that instead.

      Again, thanks for all the work (and it looks like you had fun with it).

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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://432558]
Approved by BrowserUk
Front-paged by kvale
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (6)
As of 2014-07-24 11:41 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (160 votes), past polls