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

First, thanks for the good work. I go back and reread this sometimes, and somehow manage, mostly, not to get bitten, being satisfied rereading all the excellent ideas. It was loads of fun at the time, and still tickles my fancy even now.

In your code 1, I find this a little odd:

$d[($#d-1)>>1];
[download]

If there are 3 divisors, then $#d == 2, and $#d -1 == 1, and 1>>1 == 0. So instead of the middle divisor, we get 1. If there is 1 divisor, we get -1 (I think), which perhaps doesn't matter, giving the last element by Perl magic.

But overall, I would agree a priori that something well written that returns a list of divisors will be faster than something returning a list of prime factors, which then have to be recombined to get divisors. Unless there is a very large list of divisors, and a very short list of prime factors, but that is an edge case, I think.

Thanks for refreshing one of my favorite threads.

-QM
--
Quantum Mechanics: The dreams stuff is made of

Comment on Re^2: OT: Finding Factor Closest To Square Root Select or Download Code

Replies are listed 'Best First'.
Re^3: OT: Finding Factor Closest To Square Root by danaj (Friar) on Oct 13, 2014 at 07:49 UTC
Re code 1, I was solving for the largest divisor less than the square root so that was on purpose. Rereading the thread, we want instead `<=`. I've edited my answer to reflect this. Thanks for pointing that out. While the results for the random numbers were identical, clearly they didn't include any perfect squares. I checked results from 2 to 100k and they now match the previous solutions (inlinec, pruner, rjnew, limbic). I started at 2 because some of those methods barf when given the input 1. This wouldn't change the performance numbers. I did put in a different version of code 3 which may be faster, but I doubt it would change the timings by a lot. Re divisors vs. factors, I think that is only true for very small inputs. That is, my thinking is that for factors we have lots of ways to speed things up -- e.g. trial division by only primes to square root of n, or better methods (e.g. Rho, P-1, SQUFOF, etc.). For divisors we need to do trial division by all numbers to square root of n and each found divisor isn't pruning the search space. The obvious optimization methods are limited forms of the "find factors, multiply out to get divisors" method. To put this to the test, I used Math::Factor::XS. It has a function `factors` which loops from 2 to sqrt(n) adding the divisors to a list. It also has `prime_factors` which gives the prime factors using a mod-6 wheel trial division. I made two programs: call `factors` and return the middle element. call `prime_factors`, use my code 3 routine to calculate the divisors, return the middle element. Is the first method faster? It's getting an array from an XS routine then returning one element from it. It should be fast. The second gets a smaller array from the XS routine then putzes around in Perl code making the divisor array. Yet the second method is faster once the inputs exceed about 400,000. On the other hand, if the function that returns the divisors generates them via the factors (like the ntheory module does in both C and Perl, and Pari does in C), then we're probably better off just calling it. As the fastest solution on my list shows, as does the Pari divisors vs. various solutions using Pari factors. I could see some exceptions for special cases like primorials where some trimming solution could save some time (e.g. primorial(61) with 18 factors and 262,144 divisors)	[reply]

Replies are listed 'Best First'.

Re^3: OT: Finding Factor Closest To Square Root
by danaj (Friar) on Oct 13, 2014 at 07:49 UTC

Re code 1, I was solving for the largest divisor less than the square root so that was on purpose. Rereading the thread, we want instead <=. I've edited my answer to reflect this. Thanks for pointing that out.

While the results for the random numbers were identical, clearly they didn't include any perfect squares. I checked results from 2 to 100k and they now match the previous solutions (inlinec, pruner, rjnew, limbic). I started at 2 because some of those methods barf when given the input 1.

This wouldn't change the performance numbers. I did put in a different version of code 3 which may be faster, but I doubt it would change the timings by a lot.

Re divisors vs. factors, I think that is only true for very small inputs. That is, my thinking is that for factors we have lots of ways to speed things up -- e.g. trial division by only primes to square root of n, or better methods (e.g. Rho, P-1, SQUFOF, etc.). For divisors we need to do trial division by all numbers to square root of n and each found divisor isn't pruning the search space. The obvious optimization methods are limited forms of the "find factors, multiply out to get divisors" method.

To put this to the test, I used Math::Factor::XS. It has a function factors which loops from 2 to sqrt(n) adding the divisors to a list. It also has prime_factors which gives the prime factors using a mod-6 wheel trial division. I made two programs:

call factors and return the middle element.
call prime_factors, use my code 3 routine to calculate the divisors, return the middle element.

Is the first method faster? It's getting an array from an XS routine then returning one element from it. It should be fast. The second gets a smaller array from the XS routine then putzes around in Perl code making the divisor array. Yet the second method is faster once the inputs exceed about 400,000.

On the other hand, if the function that returns the divisors generates them via the factors (like the ntheory module does in both C and Perl, and Pari does in C), then we're probably better off just calling it. As the fastest solution on my list shows, as does the Pari divisors vs. various solutions using Pari factors. I could see some exceptions for special cases like primorials where some trimming solution could save some time (e.g. primorial(61) with 18 factors and 262,144 divisors)

[reply]