in reply to OT: Finding Factor Closest To Square Root
Find the two factors in the middle. Their product should be closest to the square root.
Being right, does not endow the right to be rude; politeness costs nothing. Being unknowing, is not the same as being stupid. Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence. Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.
Re^2: OT: Finding Factor Closest To Square Root
by QM (Parson) on Feb 18, 2005 at 23:22 UTC
|
Sorry, I was sloppy before...
Math::Big::Factor::factors_wheel() doesn't give all factors, but the prime factorization.
For instance,
factors_wheel(1000) == (2, 2, 2, 5, 5, 5);
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply] [d/l] |
|
Since you've got them in ascending order, take every other prime factor and multiply. Compare that to the product of the ones you didn't choose. Whichever's closer, there ya go. That's just off the top of my head.
Let's try another way. Pretty clearly, you want roughly half the factors. You can work from the outside in, or the inside out, or do something like this: If you have N factors, take the (N*2)th root of the number. Find the factor closest to that. Divide your number by the square of the chosen factor, decrement N, and repeat until you get further from the square root instead of closer to it.
Caution: Contents may have been coded under pressure.
| [reply] |
|
| [reply] [d/l] |
|
If you get a list of prime factors in ascending order, then I would take every other member of the list, multiply them together and start with that.
In your example, that would give you 20, which isn't too far from the correct result of 31.
Hmm .. Actually, an even better answer would be
- for a list with an odd number of elements, take all of the odd position numbers and multiply them together;
- for a list with an even number of elements, take the odd numbered elements from 1 to (n/2)-1, and the even numbered elements from n down to (n/2)+2, and multiply them together with the harmonic mean of the (n-1)/2 and n/2 elements.
For your example, that would be 2 * sqrt(2*5) * 5, which turns out to be exactly the correct answer, 31.622..
To try out the odd number, we'll try out 2000, which gives us a list of (2, 2, 2, 2, 5, 5, 5) and a result of 2 * 2 * 5 * 5 or 100. Hmm, a little high.
Well, that's a fascinating question, and good luck with that.
Alex / talexb / Toronto
"Groklaw is the open-source mentality applied to legal research" ~ Linus Torvalds
| [reply] [d/l] |
|
For your example, that would be 2 * sqrt(2*5) * 5, which turns out to be exactly the correct answer, 31.622..
I don't need the exact square root, but the largest (possibly composite) integer factor less than or equal to the square root.
Cheers,
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply] |
|
|
|
|
One way to do it, similar to talexb, would be (tested!)
use Math::Big::Factors;
my $val = 2000;
my @x = Math::Big::Factors::factors_wheel( $val );
print "@x\n";
my %factors;
$factors{$_}++ for @x;
use Data::Dumper;
print Dumper \%factors;
my $sqrt = 1;
while (my ($k,$v) = each %factors) {
while ($v > 1) {
$sqrt *= $k;
$v -= 2;
}
if ($v) {
$sqrt *= sqrt( $k );
}
}
print "$sqrt => ", sqrt( $val ), $/;
This is going to be slower that just taking the sqrt of the value. Just to let you know ...
Being right, does not endow the right to be rude; politeness costs nothing. Being unknowing, is not the same as being stupid. Expressing a contrary opinion, whether to the individual or the group, is more often a sign of deeper thought than of cantankerous belligerence. Do not mistake your goals as the only goals; your opinion as the only opinion; your confidence as correctness. Saying you know better is not the same as explaining you know better.
| [reply] [d/l] |
|
This would also give me a practical answer, though it could be off quite a bit for some cases.
For instance, for N=1000, the factorization is 2**3 * 5**3. Your method gives 2**2 * 5**2 = 100, while the closest factor to the square root is 5**2 = 25 (paired with 40). I'd be happy with either 25 or 40.
-QM
--
Quantum Mechanics: The dreams stuff is made of
| [reply] [d/l] [select] |
|
|
|
|
|