Re: OT: Finding Factor Closest To Square Root

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

#!/usr/bin/perl
use strict;
use warnings;
use Math::Pari qw/factorint PARImat/;

print nearest_sqrt( $ARGV[0] ), "\n";

sub prime_factors {
    my $num = shift;
    my %p_fact = PARImat( factorint( $num ) ) =~ /(\d+)/g;
    return map { ($_) x $p_fact{$_} } keys %p_fact; 
}


sub nearest_sqrt {
    my $num = shift;
    my @list = prime_factors( $num );
    my (%seen, @position, @stop, $end_pos, $done, $winner, $offset);
    my ($by, $next) = (0, 1);
    while ( ! $done ) {
        if ( $next ) {
            $by++;
            last if $by > @list;
            @position = (0 .. $by - 2, $by - 2);
            @stop     = @list - $by .. $#list;
            $end_pos  = $#position;
            $next = 0;
        }
        my $cur = $end_pos;
        {
            if ( ++$position[ $cur ] > $stop[ $cur ] ) {
                $position[ --$cur ]++;
                redo if $position[ $cur ] > $stop[ $cur ];
                my $new_pos = $position[ $cur ];
                @position[ $cur .. $end_pos ] = $new_pos .. $new_pos +
+ $by;
            }
        }
        if ( $position[0] == $stop[0] ) {
            $position[0] == @list ? $done = 1 : $next = 1;
        }
        next if $seen{"@list[ @position ]"}++;

        my $factor = 1; 
        $factor *= $_ for @list[ @position ];        

        my $diff = ($num / $factor) - $factor;
        if ( $diff >= 0 && (! defined $offset || $diff < $offset) ) {
            ($winner, $offset) = ($factor, $diff);
        }
    }
    return $winner ? $winner : 'prime';
}
[download]

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

Comment on Re: OT: Finding Factor Closest To Square Root Download Code

Replies are listed 'Best First'.
Re^2: OT: Finding Factor Closest To Square Root by QM (Parson) on Feb 23, 2005 at 19:14 UTC
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	[reply] [d/l] [select]
Re^3: OT: Finding Factor Closest To Square Root by Limbic~Region (Chancellor) on Feb 24, 2005 at 16:20 UTC
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. Read more... (3 kB) 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	[reply] [d/l]
Re^4: OT: Finding Factor Closest To Square Root by sleepingsquirrel (Chaplain) on Feb 24, 2005 at 17:28 UTC
I took a quick glance at your code, and found this snippet to be a little odd... `end_pos = p; for (p = 0; p <= end_pos; ++p) { }` [download] ...perhaps there was something between the brackes in an earlier version? -- All code is 100% tested and functional unless otherwise noted.	[reply] [d/l]
Re^3: OT: Finding Factor Closest To Square Root by Limbic~Region (Chancellor) on Feb 23, 2005 at 19:33 UTC
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	[reply]
Re^4: OT: Finding Factor Closest To Square Root by QM (Parson) on Feb 25, 2005 at 16:45 UTC
It seems that I'm not going to have the time to summarize this and take advantage of your offer. But thanks for trying. Maybe in a few weeks I can revisit this and follow up. Otherwise, is someone else with a similar interest up to the task? -QM -- Quantum Mechanics: The dreams stuff is made of	[reply]