Buzby
Senior Member
Hi All,
For a project I'm working on now I need to take the square root of a 31 bit number. I know I could do it eventually with a PICAXE, but this project has other complex maths requirements as well, so I've jumped ship !.
But before I jumped I investigated another square root method, and wondered if this might have legs in the PICAXE world.
It's based on the fact that the sum of the set of odd numbers is always a square. ( Something I'd never realised, it seems so simple !. )
It was based on the formula that the sum of the first n odd integers is n squared.
Num --> Sum
1 --> 1 = 1
3 --> 4 = 1 + 3
5 --> 9 = 1 + 3 + 5
7 --> 16 = 1 + 3 + 5 + 7
9 --> 25 = 1 + 3 + 5 + 7 + 9
11 --> 36 ..... etc., etc,
13 --> 49
15 --> 64
17 --> 81
19 --> 100
21 --> 121
23 --> 144
25 --> 169
27 --> 196
29 --> 225
31 --> 256
33 --> 289
etc ...
The basic idea is to subtract odd numbers until the result goes negative, then the last number subtracted is close to twice the square root ( or something like that ).
The page I found this on, http://www4.wittenberg.edu/academics/mathcomp/bjsdir/ENIACSquareRoot.htm, shows how ENIAC did it, and shows how to speed the algorithm by orders of magnitude.
Unfortunately the writer of the page has made it too mathsy for me to be bothered following it in detail, but it does look like the idea would translate into a binary world quite easily, with shifts of 2^2 instead of 10^2.
Just a thought, if anyone wants to spend a wet Saturday afternoon twiddling bits.
Cheers,
Buzby
For a project I'm working on now I need to take the square root of a 31 bit number. I know I could do it eventually with a PICAXE, but this project has other complex maths requirements as well, so I've jumped ship !.
But before I jumped I investigated another square root method, and wondered if this might have legs in the PICAXE world.
It's based on the fact that the sum of the set of odd numbers is always a square. ( Something I'd never realised, it seems so simple !. )
It was based on the formula that the sum of the first n odd integers is n squared.
Num --> Sum
1 --> 1 = 1
3 --> 4 = 1 + 3
5 --> 9 = 1 + 3 + 5
7 --> 16 = 1 + 3 + 5 + 7
9 --> 25 = 1 + 3 + 5 + 7 + 9
11 --> 36 ..... etc., etc,
13 --> 49
15 --> 64
17 --> 81
19 --> 100
21 --> 121
23 --> 144
25 --> 169
27 --> 196
29 --> 225
31 --> 256
33 --> 289
etc ...
The basic idea is to subtract odd numbers until the result goes negative, then the last number subtracted is close to twice the square root ( or something like that ).
The page I found this on, http://www4.wittenberg.edu/academics/mathcomp/bjsdir/ENIACSquareRoot.htm, shows how ENIAC did it, and shows how to speed the algorithm by orders of magnitude.
Unfortunately the writer of the page has made it too mathsy for me to be bothered following it in detail, but it does look like the idea would translate into a binary world quite easily, with shifts of 2^2 instead of 10^2.
Just a thought, if anyone wants to spend a wet Saturday afternoon twiddling bits.
Cheers,
Buzby