in reply to Re^5: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root
BrowserUk,
The following code demonstrates that this is not actually true:
The following code demonstrates that this is not actually true:
#!/usr/bin/perl use strict; use warnings; use Math::Pari qw/factorint PARImat/; print nearest_sqrt( $ARGV[0] ); sub prime_factors { my $N = shift; my %p_fact = PARImat( factorint( $N ) ) =~ /(\d+)/g; return map { ($_) x $p_fact{$_} } sort { $a <=> $b } keys %p_fact; + } sub nearest_sqrt { my $N = shift; my $sqrt = sqrt( $N ); my @factor = prime_factors( $N ); return 1 if @factor == 1; my $end = $#factor; my @subset; my ($pos, $mode) = (-1, 1); my %seen; my $get_factor = sub { if ( $seen{ "@factor[ @subset ]" }++ ) { if ( $mode == 1 ) { push @subset, $pos + 1 .. $end; ++$mode; } return undef; } my $f = 1; $f *= $_ for @factor[ @subset ]; return $f < $sqrt ? $f : undef; }; my %dispatch = ( 1 => sub { push @subset, ++$pos; ++$mode if $subset[ -1 ] == $end; return 1; }, 2 => sub { splice(@subset, $#subset - 1, 1); return $mode++; }, 3 => sub { return () if $subset[ 0 ] == $end; $pos = $subset[ -2 ] + 1; splice(@subset, $#subset - 1, 2, $pos); return $mode = 1; }, ); my ($winner, $offset); while ( $dispatch{ $mode }->() ) { my $factor = $get_factor->() or next; my $diff = ($N / $factor) - $factor; if ( ! defined $offset || $diff < $offset ) { ($winner, $offset) = ($factor, $diff); } } return $winner; }
- If a subset has been seen before, it is skipped prior to determining the product of the subset
- If a subset is the start of a progression of subsets previously seen, the entire progression is skipped
- If a factor is determined to be larger than the sqrt, determining if it is the closest is skipped
Cheers - L~R
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^7: OT: Finding Factor Closest To Square Root
by tall_man (Parson) on Feb 27, 2005 at 22:07 UTC | |
by Limbic~Region (Chancellor) on Feb 28, 2005 at 19:50 UTC | |
Re^7: OT: Finding Factor Closest To Square Root
by BrowserUk (Patriarch) on Feb 26, 2005 at 08:13 UTC | |
by Limbic~Region (Chancellor) on Feb 26, 2005 at 14:10 UTC | |
by BrowserUk (Patriarch) on Feb 26, 2005 at 15:00 UTC | |
by Limbic~Region (Chancellor) on Feb 27, 2005 at 14:29 UTC | |
by BrowserUk (Patriarch) on Feb 27, 2005 at 16:10 UTC |
In Section
Seekers of Perl Wisdom