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