in reply to Re^4: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root

I moved away from using M::B::F. The "best" I came up with is: 

#! perl -slw
use strict;

my $NUM = $ARGV[ 0 ] || die 'No arg';
$NUM = eval $NUM if $NUM =~ m[\D];

my $root = sqrt( $NUM );
my $near = int $root;
my $step = $NUM % 2 ? 2 : 1;

$near-= $step while $near and  $NUM % $near;
$near = 1 unless $near;

printf "%10.f (%10f) %.f\n", $NUM, $root, $near;

[download]

It's a simple brute force search for a factor < root.

There may be a way to use the prime factors to speed the search, but the time they take to produce, a linear search down from the root is quicker.

Even with a largish prime like 988041964007, which means a linear search all the way to 1, this takes less than a second, where Math::Big::Factors::Factors_wheel() churns for hours trying to factorise it.

Maybe there's a qucker factorising module out there somewhere? Even so, from what I've tried and seen from other peoples attempts, having the prime factors doesn't give you any obvious way to avoid what amounts to a linear search.

Examine what is said, not who speaks.
Silence betokens consent.
Love the truth but pardon error.

Replies are listed 'Best First'.
Re^6: OT: Finding Factor Closest To Square Root
by hv (Prior) on Feb 21, 2005 at 10:15 UTC

    The original question started "given N and N's prime factorization", so it seems inappropriate to take into account the time taken to factorize.

    In this case though, note that 988041964007 = 7 x 11087 x 12731023 - you are losing accuracy by throwing out the BigInts.

    In general if the factorization of N is taking longer than it takes to do sqrt(N) trial divisions then the factorization algorithm is pretty bad, since "trial division up to the square root" is the classical example of a slow algorithm.

    Many of the high precision maths libraries out there do factorization - for example the pari library (Math::Pari) has a factorint() function:

      use Math::Pari qw/ factorint /;
  my $n = Math::Pari->new("988041964007");
  my $f = factorint($n);
  my $count = $#{ $f->[0] };
  print join(" * ", map {
    my($prime, $power) = ($f->[0][$_], $f->[1][$_]);
    $power > 1 ? "$prime ^ $power" : $prime
  } 0 .. $count), "\n";
7 * 11087 * 12731023

    [download]

    Note that this algorithm does not guarantee primality: for large factors you need to verify with an isprime() check.

    Hugo

[reply]
[d/l]
[select]
      so it seems inappropriate to take into account the time taken to factorize

      Inappropriate maybe, but it's bloody boring waiting for it :)

      The other part of the argument against doing the factorising, is I haven't thought of, nor seen, a way to use them, that arrives at the result more quickly.

      As the factor you are looking for can be any combination (small c), of the prime factors of N, I haven't seen any algorithm that doesn't require an exhaustive search of those combinations plus trial division to determine if you've found the answer. The result is that the descending, linear search is easier to code and runs more quickly.

      I have produced the results for all the integers 1-2 million, and 3-4 million, 10-11 million and 100-101 million and then atttempted to find some sort of pattern to the results. There may be one there, but my meagre memory of numerical analysis is not enough to devine it.

      28.x% of of the low ranges are primes. This falls of very slowly as the scale of the range increases, but it's only dropped to 27.76% by the time you get the the 100-101 million range. This is worst case for the linear search. If the factorisation ran more quickly, then it would allow you to skip the search in those cases.

      Whether that would result in an overall speed up, given that you would have to factor all the numbers and (so far) fall back to a linear search for those Ns that are not primes, I think is dubious.

      As the range gets higher, the frequency of the primes gets less, so the benefit of performing the factorisation reduces as the cost of the linear search increases, but also the cost of the factorisation increase and much more rapidly that the cost of the linear search.

      I will install Math::Pari. I think it would be interesting to see if there is any pattern to the prime factors of the factor.

      This has probably already been analysed to death sometime, but if it has, I'm not typing in the right keywords to locate it.

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.
[reply]
        If you install Math::Pari, try the function sigma($N,0). That computes the total number of divisors of $N. It requires factorization to compute, but Math::Pari has very fast factorization algorithms.

        If N = (p1^a1)*(p2^a2)*...(pR^aR) then sigma(N,0) = (a1+1)*(a2+1)*...(aR + 1)

        This number is usually very small, even for huge N.

        If sigma($N,0) is reasonable, you can call divisors($N), which returns a list of all the divisors in order. A simple binary search will find the desired number.

        This should be incredibly faster than brute-force countdown searches for large N.

[reply]

In Section Seekers of Perl Wisdom