I know this thread is really old, but it was interesting. I looked at a few different methods.

Getting the factors or divisors. Choices include:

Edit: updated for <= instead of <. Also updated code 3 and reran timing.

Methods for getting the largest divisor less than or equal to sqrt(n):

Results. Times for 1 million random integers 0 to 2^47-1 (code 0)

Factoring in pure Perl is definitely slower than C (but maybe someone has faster Perl factoring code). Math::Factor::XS tests all integers from 2 to sqrt(n) without pruning. This is definitely slower at this size than generating the divisors from the prime factors. factors_wheel has two problems: it always uses Perl bigints which are slow, but more importantly it makes an implementation mistake and tests to n instead of sqrt(n. These combined make it completely unreasonable in performance for these 47-bit numbers.

So.. (1) unless you have tiny inputs, you need a fast factoring method, today that would be ntheory or Pari. (2) Pari's overhead gets in the way here, but it still yields reasonably fast solutions. (3) the simple divisors call (do everything in C) is fastest, but we can do a good job given just the factors. My method of creating all the divisors from the factor list was slow at first, but improving the code made it much better.

(code 0)

srand(1);  # So everything is using the same numbers
my $s = 0;
for (1..1000000) {
  $s += nearest_sqrt(int(rand(2**47)));
}
print "$s\n";

[download]

(code 1)

use ntheory qw/divisors/;
sub closest {
  my @d = divisors(shift);
  $d[ $#d >> 1 ];
}

[download]

(code 2)

use ntheory qw/fordivisors/;
sub closest {
  my($n,$sqrtn,$min) = ($_[0], int(sqrt($_[0])));
  fordivisors { $min = $_ if $_ <= $sqrtn; } $n;
  $min;
}

[download]

(code 3)

use ntheory qw/factor/;
sub closest {
  my($n) = @_;
  my(@factors, @d, @t);
  # 1. Get list of factors
  @factors = factor($n);
  # 2. Turn this into an unsorted list of divisors
  @d = (1);
  while (my $p = shift @factors) {
    my $e = 1;
    while (@factors && $p == $factors[0]) { $e++; shift(@factors); }
    push @d,  @t = map { $_ * $p } @d;               # multiply throug
+h once
    push @d,  @t = map { $_ * $p } @t   for 2 .. $e; # repeat
  }
  # 3. Sort
  @d = sort {$a<=>$b} @d;
  # 4. Return the largest divisor <= sqrt n.
  $d[ $#d >> 1 ];
}

[download]

(code 4)

use Math::Pari qw/divisors/;
sub closest {
  my $d = divisors(shift);
  $d->[ $#$d >> 1 ];
}

[download]

(code 5)

use Math::Factor::XS qw/factors/;
sub closest {
  my @d = (1, factors($_[0]), $_[0]);
  $d[ $#d >> 1 ];
}

[download]

In reply to Re: OT: Finding Factor Closest To Square Root by danaj
in thread OT: Finding Factor Closest To Square Root by QM

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.