If you futz around with math like I do, you probably have to compute square roots from time to time. We all know how to do it. Basically you punch the SQR button on your calculator.
Or you type SQRT(A1) in Excel or something like that. But how do you do it by hand? And moreover, why am I discussing this? Well, for the latter question, you'll have to wait a bit. First, square roots.
In school they taught me this: For a given number x choose a smaller number r and square r. If r squared is bigger than x, choose a smaller value for r, if r squared is smaller than x choose a larger value for r. Repeat until you converge on the approximate square root of the number.
So, if x is, say 1200 (for reference sqrt(1200)=34.641…), then I would pick an arbitary value for r. Because I am a computer geek I happen to know that 32^2 = 1024, so r=32 is too low because 1024 < 1200. So then let's set r=33. 33^2 = 1089, too low. If r=34, r^2=1156… closer, but still too low. If r=35, r^2=1225, which is too high. So I know that the square root of 1200 is between 34 and 35, and I can refine my estimate further by choosing fractional values between 34 and 35:
r=34.5, r^2=1190.25
r=34.75, r^2=1207.56
r=34.625, r^2=1198.891
r=34.6875, r^2=1203.22
And so forth. As you can see we've gotten pretty close to the square root now.
This is basically a watered down variant of the Babylonian Method of computing square roots. When I was in Junior High, the above method was easier to understand. But now that I am an adult, the actual Babylonian Method description is more accessible and more concise. Here it is from the wiki:
The most common method of square root calculation by hand is known as the “Babylonian method”. It involves a simple algorithm, which will bring you closer and closer to the actual square root each time it is repeated. To find r, the square root of a real number x:
- Start with an arbitrary positive start value r (the closer to the square root of x, the better).
- Replace r by the average between r and x / r. (It is sufficient to take an approximate value of the average, not too close to the previous value of r and x / r in order to ensure convergence.)
- Repeat steps 2 and 3.
Starting from my original M of 33, it takes only 4 iterations to come within 1/100,000th of the actual square root of 1200:
r=33.00000, r^2=1089.00000. Too low.
r=34.68182, r^2=1202.82851. Too high.
r=34.64104, r^2=1200.00166. Too high.
r=34.64102, r^2=1200.00000. Done.
Interestingly this method works surprisingly fast even if you pick a dreadful starting value for r. If in this example I start with r=1, it takes only 10 iterations to come within 1/100,000th of the square root of 1200.
r=1.00000, r^2=1.00000. Too low.
r=600.50000, r^2=360600.25000. Too high.
r=301.24917, r^2=90751.06084. Too high.
r=152.61629, r^2=23291.73210. Too high.
r=80.23957, r^2=6438.38915. Too high.
r=47.59739, r^2=2265.51190. Too high.
r=36.40443, r^2=1325.28246. Too high.
r=34.68373, r^2=1202.96082. Too high.
r=34.64104, r^2=1200.00182. Too high.
r=34.64102, r^2=1200.00000. Done.
Square Roots and Factorization
Now why am I going on about this? Well I've been thinking about the Weelanders again. I'd like to create a new generation of Weelanders who break numbers down into their prime factors. (As in 1200 = (2^4)(3)(5^2), or 2 x 2 x 2 x 2 x 3 x 5 x 5 = 1200). Because of this I need Weelanders to be able to compute square roots, and the method above will be the one they will use.
Why do I need to do square roots to factor a number?
One rudimentary way to find the factors of a number N is to divide N by values which are < SQRT(N)… if any of them evenly divides the number, then it is a factor. The SQRT portion is important, because it lets you know where you should stop trying factors, without having to keep going all the way up to the value of N itself. This makes sense because any value X<SQRT(N) which is a factor of N, necessarily multiplies by another factor Y>SQRT(N). The only exception to this is when X=SQRT(N). This means that by the time you've reached the SQRT(N), going further will simply yield factors you already could have computed by dividing N by an earlier value of X. We can show this with 1200. Here are all the values of X less than SQRT(1200) which are factors of 1200, and the corresponding factor you must multiply by (Y) to get 1200:
X=1, Y=1200.
X=2, Y=600.
X=3, Y=400.
X=4, Y=300.
X=5, Y=240.
X=6, Y=200.
X=8, Y=150.
X=10, Y=120.
X=12, Y=100.
X=15, Y=80.
X=16, Y=75.
X=20, Y=60.
X=24, Y=50.
X=25, Y=48.
X=30, Y=40.
Note how X and Y both converge toward the SQRT of N. This is why when you are looking for the factors of N, there's no reason to test values of X greater than SQRT(N). The biggest value of X in this case that divides 1200 evenly is 30 which is just a little less than SQRT(1200)–34.641. The factor paired with that X is 40, which is just a little larger than SQRT(1200).
So if for example N was 1201 instead of 1200. You'd know that 1201 was prime by the time you had finished testing 1201/34. Because 1201/X where X is an integer larger than 34 must yield a value Y which is less than 34 which you would have already found.
For doing prime factorization (as opposed to full factorization, which is what you see above), you test even fewer factors (only the primes), and your target endpoint changes with each successful factorization. Consider 1200 again, as with full factorization my endpoint for testing is SQRT(1200). So I try the first prime 2. This works 1200/2 = 600. But that means now I'm no longer really factoring 1200, I'm factoring 600. Which means my endpoint is now really SQRT(600) or 24.5. That means: none of the primes between 24.5 and 34.6 evenly divide 1200 or 600. So now I don't have to test 29 and 31.
Divide by 2 again, and that gives us the result 300, which has a square root of 17.3. So there is no reason now to test beyond the prime 17, and so we no longer need to test 23 as a factor of 1200.
Divide by 2 again and we get 150, with square root 12.2. Which means that 13 and 17 also no longer need to be tested.
Divide by 2 one more time we get 75, with square root 8.66. Which means that 11 doesn't need to be tested. Look how much we figured out! By dividing 1200 by 2 successively we now know that all of its remaining prime factors are less than 8. And since we clearly can't divide by 2 again, all that is left to test is 3, 5, and 7! Isn't that cool?
If N were 1205, we'd find after dividing by 5 that the quotient 241 requires us to test no further than 15. So that would mean we'd test 5, 7, 11, and 13 with no luck, which would tell us that 241 is itself prime.
Prime Factorization and Weelanders
I'd like to recode the Weelanders to do basic square roots, and basic prime factorization, and then build a “rack” of 1000 Weelanders, give them all the same number to factor, and let them all factor it. Any Weelander who gets the wrong answer or no answer gets the axe, and of the remaining Weelanders, the fastest 10% (those who computed the results in the fewest number of steps), would be allowed to reproduce (sexually or asexually, haven't decided yet.) The remaining 90% would also get the axe to make way for the offspring of the top 10%. The top 10% would reproduce until the “rack” was filled again. And then it would be time for another factorization test.
I'd probably not want to select Weelanders based on the results of a single factorization. I'd probably want to do it based on 5 or 10 factorizations. (It's possible that a mutant Weelander might be exceptionally well suited to factor the number 5268, but be incapable of factoring other values at all.) Therefore you'd want to test them a bit and average the results. (But of course you would immediately cull any Weelander that couldn't solve the problem correctly.)
I seriously doubt that I can come up with any novel ways to factor numbers via this method, but I know there are a number of little “tricks” for factorization that I am not familiar with… maybe my Weelanders can teach me those tricks through natural selection? Wouldn't that be cool?