Re^6: OT: Finding Factor Closest To Square Root

Here's a recursive solution to find the closest set of factors to a target (with wrapper script). I think it's solid.

use strict; 
use warnings;
use List::Util qw[ reduce ];

my @pfs = ( 2,3,3,3,7, 997 );
my $num = reduce { $a * $b } @pfs;
my $root = sqrt $num;
print "N=$num, R=$root\n";

sub closest {
  # Args are target and factor-list
  my ($target, $car, @cdr) = @_;
  @cdr or return $car;
  reduce { abs($target - $a) < abs($target - $b) ? $a : $b }
         ($car*closest($target/$car, @cdr), closest($target, @cdr), $c
+ar);
}

print closest($root, @pfs), "\n";
[download]

Caution: Contents may have been coded under pressure.

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

Replies are listed 'Best First'.
Re^7: OT: Finding Factor Closest To Square Root by BrowserUk (Patriarch) on Feb 20, 2005 at 00:35 UTC
It seems to work well as far as I can verify it, with one exception. Like one of my other attempts, if N is prime, it produces N as the nearest factor rather than 1. However, being recursive, it suffers in performance one you really start making it work. Try 8585937356. I get a nearest factor of 4 with my dumb crunch code. I gave up waiting for your's :) Examine what is said, not who speaks. Silence betokens consent. Love the truth but pardon error.	[reply]
Re^8: OT: Finding Factor Closest To Square Root by Roy Johnson (Monsignor) on Feb 20, 2005 at 13:54 UTC
When I plug in 1 and 5 as factors, I get 1. Does your factor list include 1? Caution: Contents may have been coded under pressure.	[reply]
Re^9: OT: Finding Factor Closest To Square Root by BrowserUk (Patriarch) on Feb 20, 2005 at 15:07 UTC
The list produced by M::B::F doesn't include 1.	[reply]