## Monday, September 26, 2011

### Finding primes with binary search

Here's an algorithm for testing the primality of a number that should be fast on a computer because it uses all operations that are easy in binary.
So say you have a number like: 71
Find the perfect powers of 2 less and more than 71.
2*2*2*2*2*2=64
2*2*2*2*2*2*2=128
What I'm going to do is a binary search between these two numbers looking for 71 which means I look at the number that is halfway between 64 and 128 and see if that is bigger or smaller than the number I'm looking for, if the number I'm looking for is less than that I look at the number halfway between 64 and halfway between 64 and 128 which is 96 and keep proceeding like that until I end up with 71.
2*2*2*2*2*2=64
2*2*2*2*2*2*2=128
Now to find the number halfway between 64 and 128 you look at the largest part they share in common without being the whole of either number such that the remaining two parts have a number halfway between them, like above they both have 5 2's and one is 2*2^5 and the other 4*2^5 so since halfway between 2 and 4 is 3, 3*2^5 is halfway between 2*2^5 and 4*2^5.
3*2*2*2*2*2=96 you can either think of it as replacing 2 from 64 with 3 or 2*2 from 128 with 3.
96 is still bigger than 71 so we want halfway between 64 and 96
If we think of it as 2*2^5 and 3*2^5 there is no number halfway between 2 and 3 so we have to go to halfway between 4*2^4 and 6*2^4 and halfway between 4 and 6 is 5.
5*2*2*2*2 = 80
which is still bigger than 71 so look at halfway between 80 and 64. The largest part they share in common where there is still a number halfway between the part they don't have in common is 2^3 which makes them 2^3*10 and 2^3*8 so halfway between 8 and 10 is 9.
9*2*2*2=72
still bigger than 71so do the same process process but this time the biggest part they have in common that leaves 2 numbers with a number between them is 2^2 which leaves 16*2^2 and 18*2^2 Halfway between 16 and 18 is 17.
17*2*2 = 68 same process again but since 68 is less than 71 do between 68 and the last number we had that was bigger than 71 which was 72
35*2 = 70 35 is halfway between 34 and 36
Then between 70 and 72:
That part of the process can't continue because there is no number between 36 and 35 so you can't take what's common to them which is 2 and halfway between.
The next part is to check the last two numbers 35*2 and 36*2 to see that the 35 and 36 aren't being multiplied by two numbers that there is something halfway in between. In this case there are both multiplied by 2 so that's not a problem. 71 must be prime.

Let's try an odd that's not prime like 93:
2*2*2*2*2*2 = 64
2*2*2*2*2*2*2 = 128
3*2*2*2*2*2 = 96
5*2*2*2*2 = 80
11*2*2*2 = 88
23*2*2 = 92
47*2 = 94
In this case with 23*2*2 and 47*2, 23 and 47 are being multiplied by 2 and 2*2, and there is a number between 2 and 2*2 which is 3 so 93 either divides 3 or is prime.