Saturday 28 January 2012

How to Program the mth Root Algorithm

If you have read my post on how to find the mth root of a number, you will see that the algorithm converges painfully slowly as m begins to increase the series converges painfully slowly and it is not at all practical to do by hand, so you may be wondering what the point of the algorithm really is at all. Well calculators need an algorithm on how actually to compute the "mth root" of a number, and this is how.

To start with I will note that I am using Visual Basic 2008 to program this, but it shouldn't be too hard to alter the code to the appropriate language as Visual Basic is very similar to pseudocode so it is easy to read. It should also be noted that the original algorithm I devised is so inefficient for larger values of m that even with 1,000,000,000 iterations, it can still be wildly out; the newer, more efficient algorithm is very similar to the older one, as you will see.


Now that the ground work is out of the way it is just the simple matter of translating this into a program. Start by creating two labels (names do not matter as they will not be used in the code), two text boxes (txtNumber and txtRoot) and a button (btnRoot).


Now go into your code and create a function called mth_root with inputs of number and root. The code for this function will be:


You begin the function by declaring the local variables index and calc_use, index is used solely as a loop counter and calc_use is a variable that will change constantly whilst the loop is ongoing, the initial value of calc_use can be anything (except 0), the series converges well so a low starting point is fine. The key part of the function is the loop ("For... Next") as this is where the calculation is done again and again. You may notice that it is done 1,000,001 times and this is not a necessity and it should be just as accurate if repeated a small fraction of this. The Return calc_use ensures that the last result from the loop is kept in the memory.

We now have the function to be used, but it is not being used yet, so we need to have the function to be ran on an event, the event we will use is the click of a button.


The first line of the code is only there to say that this code is to be executed on the click of a button and this can be replicated b double clicking your button on your form. We start again by declaring the variables we will use in this code snippet. We declare the number as the text entered into the txtNumber text box, the root variable is declared as the text entered into the txtRoot text box and the answer variable utilises the function we have created with the user defined variables.

The result of this function is output in a message box including a message as to what the number was and what the root was. You may notice that if you wanted the square root the box would say "The 2th root of...", and this too bugs me, a lot. But for the purposes of keeping this tutorial less complicated I didn't want a long If statement to simply change the suffix of the root.

If you have copied what I have done exactly it should be functioning perfectly and you can test it yourself. 


You can check this answer on your calculator, but it is in fact correct (note it is also correct if we set it to loop just from 0 to 100).

If you do not want to type the code out you can view my source code, feel free to experiment with it, try to utilise it in a calculator you create or anything else you desire. If you would just like to test out the program you can download it and see it in all its brilliance. Note, it may not actually be brilliant. Use at your own discretion.

Sunday 22 January 2012

Algorithm to find the mth root of a number

I did in fact work this algorithm for myself and was reasonably proud at discovering this, only on a later Google search did I realise that the Babylonians discovered the exact same method almost 3000 years ago, my joy was obviously cut short but it is still a pretty cool algorithm nonetheless.

To start with I began thinking what needed to be done to calculate the mth root, I knew it had to be a method that did not involve having to find the root of anything, which means I needed to rewrite the question in a form that can be solved.


But as you may realise, this is no use as it is solely in terms of L. If you have done anything on recurrence relations and sequences and series you will see that L is merely the limit of the series, this limit will be mth root of x.


And that really is it, this gives an equation to find the mth root of any given number, x.

You can try it out for yourself and see how accurate it is, and for square roots (and even cube roots) it converges pretty quickly but as m increases the series converges much slower and is then not very appropriate to use. Also U0 can be anything, the closer to the correct answer the better as it speeds the overall process up.