Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Re: OT: Finding Factor Closest To Square Root

by BrowserUk (Patriarch)
on Feb 19, 2005 at 04:49 UTC ( [id://432636]=note: print w/replies, xml ) Need Help??


in reply to OT: Finding Factor Closest To Square Root

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

#! 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 = 0; while( $root <= reduce{ $a * $b } @pfs ) { my $near = reduce{ ( $a * $b ) <= $root ? $a*$b : 0+$a } @pfs; $n = $near if abs( $root - $near ) < abs( $root - $n ); $n = $near * $pfs[ -1 ] if abs( $root - $n ) > ( $near * $pfs[ -1 ] - $root ); 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 996 primefactors ( 83 3 2 2 ) 996 (31.559467676119} : 36 P:\test>432558 1000 1000 primefactors ( 5 5 5 2 2 2 ) 1000 (31.6227766016838} : 32 P:\test>432558 100000000000000 100000000000000 primefactors ( 5 5 5 5 5 5 5 5 5 5 5 5 5 5 2 2 2 2 2 2 + 2 2 2 2 2 2 2 2 ) 100000000000000 (10000000} : 10000000 P:\test>432558 10000000000000 10000000000000 primefactors ( 5 5 5 5 5 5 5 5 5 5 5 5 5 2 2 2 2 2 2 2 +2 2 2 2 2 2 ) 10000000000000 (3162277.66016838} : 3125000 P:\test>432558 1995 1995 primefactors ( 19 7 5 3 ) 1995 (44.6654228682546} : 35
>

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 19, 2005 at 16:03 UTC
    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.
        For the case of 1994, I'd say 2 is closer to 44.65... than 997. For 1993, I'd probably go with 1 over 1e99 or 1993. For 99999999, I think 9999 (101*11*3*3) is closest. (I'm just basing this on the comments after the __END__ tag in your code, 'cause I'm to lazy to install Math::Big::Factor)


        -- All code is 100% tested and functional unless otherwise noted.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://432636]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chilling in the Monastery: (4)
As of 2024-03-29 12:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found