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.

1 comment:

  1. Things like “even”, “threeven” and “mod n” are properties that are more general than individual numbers, and which we can check for consistency. So we can use modulo to figure out whether numbers are consistent, without knowing what they are! help me with math