1) Conti-nude Fractions

I assume in this section that you know what a simple continued fraction looks like
[ if not look at i) below]. The a's, b's, c's etc are numbers that when used 
from the lowest part of the fraction result in a number with a whole (integer ) bit
and a fractional part e.g 1 ¾ 
I originally continued fractions to make approximations and used these 
to place elements in a picture. Here's an example 
The root of  3  may be approximated as follows 
2 , 7/4 (i.e. 1 ¾) , 26/15 , 97/56 , 362/209
These are related to the odd numbered convergents of the continued fraction 
approximation to 3. 

You can see that it would be quite easy to place these 
lines on a canvas and since they get closer one might use them say to generate 
perspective, or one could use them to generate boxes much as it is proposed that 
Pieter De Hooch and Vermeer did.
One might also consider using them in applications as diverse as the generation of  approximations 
modelling the behaviour of atoms 
to the storage of 3 dimensional items in a warehouse 
or in the production of calculations for say a computer game.
 
  
How to obtain continued fraction approximation 
to a square root :-
There are three methods :- 

a) conventional method   - approach using smaller numbers
b) unconventional method - approach using larger numbers 
c) a fast approximation

these are detailed below :-

a) the conventional method 

the convention is to start with the nearest (lower) square to the number
in practice this means guessing at its square root (probably iteratively)
example = 33 
5 squared is too small = 25 
and 6 squared is too big = 36
so 5 would be used as a starting point 
(this is sometimes referred to as "floor") 
authors note ... sqrt means square root .. in the bits that follow 

i)  33 - 25 = 8 = (sqrt33 + 5)(sqrt33 - 5)
now since the idea is create a continued fraction of the form 
a +         1
    ____________________
       b     +     1 
                _______________
                  c   +    1 
                         _________________
                           d +  ... etc
i.e sqrt33 = 5 +    1 
                 _______________
                  something
                 
which is the same as sqrt33 - 5 =     1
                                 _________________
                                  something
 so from i) above                                 
 
sqrt33 - 5 = 8 / (sqrt33 + 5 )

ii) which incidentally  =      1
                       __________________
                         (sqrt33 + 5) / 8
                               
the  sqrt33 + 5 is about 10 so nearest whole part divided by 8 is 1 
so (sqrt33 + 5) / 8 is equivalent to  1  + (sqrt33 + 5) - 8
                                           _______________
                                                 8
                                                 
the last bit is equal to  (sqrt33 - 3)/8                                                
so ii) is equivalent to 
                              1
                       ___________________
                        1      +     1
                                 _________________
                                   something
                                   
the something =   8 / (sqrt33 - 3)          1
the bottom bit is not very division friendly but if we multiply 
top and bottom by (sqrt33 + 3) It will get rid of any fiddly bits 
so we get   8(sqrt33 + 3) / (sqrt33 - 3)(sqrt33 + 3)
which is    8(sqrt33 + 3)/ (33 - 9) 
i.e  (sqrt33 + 3)/ 3  which is quite handy
this is just over 8 divided by 3 so the whole part is 2 

and so on... 
the somethings turn out to be 
 5,1,2 which we've already seen .. the 1,10 then the sequence 1,2,1,10 
repeats itself forever
there are plenty of tables with the results in
and indeed there's one on a separate web page associated with this text
 
b) unconventional method - approach from above 

The keen observer will have noticed that we always used the smallest nearest whole part
as for example when we started with 5 and you will have correctly guessed that 
we could just have easily started with 6 
and instead of taking the nearest smaller number used the nearest larger number
this would have resulted in the fraction 
6  -             1
     ____________________________
       4     -      1
                 ________________
                   12  etc
and similarly repeats itself 
with the sequence 
6,4,12 
 
you will probably have noticed that the point at which it repeats itself 
= twice the original number 
at the foot of this page is a list of a few roots using both methods 
you can see lots of symmetry in the results and some numbers which you might 
have thought dissimilar show a lot of similarity .. just like people 

now since I'm a lot less than rational ( and obviously very lazy )
i decided not to take out the 
whole part of the number as we did above 
but to remove it as a fraction 

c) fast approximation 
(happens to be using an approximation from above like b)
to get the root of 33
you could use the nearest root = 6 
this leaves 3/ (6 * 2) = 3/12 .. 
[notice that I've used double the nearest root to define the remainder]

the structure is 
6         -             3
          ______________________________________
            12      -      1
                      ___________________________
                       12       -     3
                                  __________________________
                                   12         -     1
                                   
this is effectively a repeating pattern of the form 6; 3:1
and for good reason you will always end up with a minimalist 
pattern of this form  .. 
so now I'll calculate a few approximations :-                                 
                                   
6 - 3/12  = (72 - 3) / 12 = 
so                      69 /12 = 33.0625

(12/3) - (1/12) = 4 - (1/12) = 47/12 ... 
so          6 - (12/47)        = 33.001358

12 - (3/12) = 141/12 
(12/3) - (12/141) = 1656/423  
so          6 - (423/1656)     = 33.00002953

the next is 6 - (4968/19449)   = 33.000000624
the next is 6 - (58347/228420) = 33.0000000139
the next is                    = 33.0000000003039
and so on ..

you can see that this rapidly converges to the root of 33
In practice it doesn't matter much which nearest square ( we used 6 )
you start with as the algorithm gets there to about 13 decimal places within 
11 - 13 iterations max. depending on how far away your first guess is
and how small the number is .. small numbers fare worse but I suppose 
you could always multiply the number by say 100 which reduces the number
of iterations by a factor of 4 .. this is very rapid 
as the calculation for each iteration is extremely simple
Incidentally you might be surprised to find that this algorithm 
doesn't just apply to integers .. you can find the root of say 33.125
using exactly the same algorithm
It is also possible to modify the algorithm slightly and generate 
oscillatory approximations to the root without loss of rapidity.
This whole approach, for those of you who know about such things, 
is not too dissimilar from techniques like those employed by Newton.
Convergence is about as quick as it possible using a quadratic method.

You may have noticed that there are also solutions to Pells equations 
These are equations of the form 
....        N(a**2) – (b**2) = +/- 1 (well any number actually)
(note: the ** means squared, times itself , etc  )

Rather conveniently the central part of the continued fraction may be computed
(leaving off the whole part of the number and its double at the tail)
and gives a solution to Pells equations which by rearrangement 
gives N = [ b**2) +/- 1 ] / (a**2)
If we assume that   b**2 is a lot bigger than 1 and ignore it we can then 
take the square root of each side of the equation to get

.....             sqrt(N) ~ b/a 

If you look at the table you'll see that sqrt of 13 has both a smaller 
and next largest solution  the pair 5 , 18 and the next pair 180 , 649
First perhaps you'll have noticed that 
    2*5*18 = 180
   the other solution is 2*18*18 +/- 1 = 649
Once you have the first solution its the very easy to get a much closer 
approximation
This you do by calculating 2*a*b as above .. this gives the next 'a' 
The new 'b' may be obtained from 2*b**2 +/- 1  

You only have to repeat this operation a few times and you can create a ratio
which will exceed the accuracy of your computer.
 
Incidentally it may interest you to know that I didn't calculate the solutions to 
Pells equations using continued fractions as its too long-winded for me.  
I used a predictive algorithm to find most of them .. particularly those with large 
solutions and maybe I'll put some details on the web at a later date but in the meantime 
perhaps you'd like to try something similar as I'm certain that something better is just 
waiting to be discovered.


Now I'd like to ask you if you could find a way to calculate the 
cube root of a number. This is more difficult as you don't have the generous symmetry
of the quadratic ... but  
Supposing I make a square of the form (x + 1)**2

this expansion = x**2 + 2x + 1 and you might note that this is 
reflected in our algorithm above.
You might already know that the cubic expansion of (x + 1)**3 
= x**3 + 3x**2 + 3x + 1 and so you might want to use something of
this form as the basis for your algorithm particularly as you can already
find approximations to 3x**2 + 3x + 1.
When the 16th century mathematicians solved these equations they 
reduced the problem to the form x**3 + Bx + C which might be another 
possible method 
as might a consideration of the form x**3 + Ax**2 + C