# N-th Root

###### tags: `Math`

## How did i came up with this topic :question:

I have read about ancient people struggled to calculate
the number $\sqrt[12]{2}$ needed for all the half steps
in 12 equal temperament in musical tuning.

And this raise my attention one day.
Because, as we know, ancient people **DO** knew
how to calculate square root and cube root and this is enough for that.

## The old way

### Let us first implement this idea with Newton\'s Method in python:exclamation:

### First we have to explain what is Newton\'s Method

It is a method to approximate square root of a positive number,
despite called Newton's Method, the method predates him by thousands of years

## Assume we want to approximate the number $\sqrt{m}$

1. Make a guess $k$
2. Divide $m$ with guess $k$ to the desired precision
3. Calculating the estimate by taking the average between your guess k
and the result from **step 2** to the desired precision
4. Go back to **step 2** and use the previous estimate as your new guess
until the new estimate do not change to the previous estimate

### Now I will add an example so the explanation so it is clearer

### Try to Estimate $\sqrt{2}$ with 3 digits after decimal point

1. Guess $1.000$
2. Divide $2$ with guess $1.000$, which is $\frac{2}{1}=2.000$
3. Calculate the average between the guess $1$ and **step 2's result** $2$,
which is $\frac{1+2.000}{2} = 1.500$ as estimate

In the next few loops the new estimate will be $1.416, 1.414,1.414$
and we get our estimate of $1.414$

## There are also a more generalized method to calculate any $\sqrt[n]{m}$

1. Make a guess $k$
2. Divide $m$ with guess $k^{n-1}$ to the desired precision
3. Calculating the estimate by taking the weighed average,
which is $\frac{k× (n-1) + \frac{x}{m^{n-1} }}{n}$ with your guess k
and the result from **step 2** to the desired precision
4. Go back to **step 2** and use the previous estimate
as your new guess until the new estimate do not change

>Description rewrote from [here](https://www.calculator.net/root-calculator.html)

## With these knowledge\, we can *finally* write the following code in python

# i is the desired precision, default to the thousandth digit
def estimate_newton(n:int, m, i:int = 3):
    MAXLOOP = 500
    val = 1 # first crude estimate
    acc = 0 # to keep in track of loops
    
    while True:
        newval = np.round(m / val**(n-1),i)
        newval = np.round((val*(n-1) + newval)/n,i)
        acc += 1
        diff = abs(val - newval)
        if acc > MAXLOOP:
            print(f'Exceed Maximum Number of Loops')
            return
        if diff == 0:
            return newval
        else:
            val = newval

## So... how many steps to calculate with hand\?

It took 5 loops to calculate $\sqrt[12]{2}\approx1.059463$
Within these 5 loops you will have to:

1. multiply the estimate by 11 times and divide the number $m$ once
2. times the estimate to a number and do a minus and a plus,
and then do a division
3. compare to the previous result(zero work)

:::success
So that's **60** multiplications, **10** divisions and **10** additions
(subtraction is just addition with sign changed)
in the most optimized route,
which is not impossible.
Just need some extra time I guess.
:::

### Okay this is enough, but I am curious about its capabilities

:::danger
When i tried to run this with larger numbers I got
:::

OverflowError                             Traceback (most recent call last)
~\AppData\Local\Temp\ipykernel_13736\879349673.py in <module>
----> 1 estimate_newton(100,123456789012345,3)

~\AppData\Local\Temp\ipykernel_13736\3503608325.py in estimate_newton(n, m, i)
      5 
      6     while 1:
----> 7         newval = round(m / val**(n-1),i)
      8         newval = round((val*(n-1) + newval)/n,i)
      9         acc += 1

OverflowError: (34, 'Result too large')
    

Which showed the following problem:

1. When $k^{n-1}$ term in **step 2** is becoming too large
the convergent of the number series is slow when it comes to larger n and m
2. like $\sqrt[100]{12345}$ took a whopping **474** loops to run

- - -

## A better idea ... or Not ⁉️

### Power of logarithm

Since n\-th root of a number can be generalized as power of m
to the reciprocal of n, we can derive the following equation:

$$\sqrt[n]{m} = m^{\frac{1}{n}} = e^{\ln{m^{\frac{1}{n}}}} = e^{\frac{\ln{m}}{n}}$$

Now the $\ln{m}$ in $e^{\frac{\color{red}\ln{\color{red}m}}{n}}$ should be
calculated first, in this case, most human will compute this with a log table
as Taylor series of log convergent **very slowly**.
Although CPUs have many ways to implement this based on their architecture,
but log tables are, surprisingly quite commonly used like this
[reference code](https://svnweb.freebsd.org/base/head/lib/msun/src/s_exp2.c?view=markup&pathrev=251024).
And there's a whole rabbit hole to discover we will skip this for today.
**Anyways**,
Is this a cheat or not? I would left for reader's own judgement.
Alright, after $\frac{\ln{m}}{n}$ is calculated,
we can calculate the real answer $e^\frac{\ln{m}}{n}$ with Taylor expansion,
given the following formula:

:::info
$$
e^{x} = \sum\limits_{n=0}^\infty{\frac{x^{n}}{n!}} = 1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\ldots$$
:::

#### *way* better

Since $\ln{m}$ means it can deal with a much larger $m$ than the $k^{n-1}$ term
in the Newton's Method before the *OverflowError* and the converge of the number
series
is guaranteed by the factorial growth in the denominator

## With these knowledge\, we can write the similar following code in python

# i is the desired precision, default to the thousandth digit
def estimate_euler(n:int, m, i:int = 3):
    MAXLOOP = 500
    x = np.log(m)/n #math.log() works, too
    fac = 1
    acc = 0
    sol = 0
    
    while 1:
        newtern = round(x**acc / fac, i)
    
        if abs(newtern) <=  0.5*10**(-i):
            return sol
    
        if acc > MAXLOOP:
            print(f'Exceed Maximum Number of Loops')
                  
        sol += newtern
        fac *= acc+1                 
        acc += 1

> The python module of numpy or math is needed for both round and log function

:::success
Which could accurately estimate the test case of $\sqrt[100]{123456789012345}\approx1.383296$
:::

With the same parameter given, only 4 loops are needed
to calculate $\sqrt[100]{12345}$

- - -

## Summary

Alright, Let us sort all the previous results
into a table for a straightforward comparison:

| Name | Big Numbers | Don't Use Log Table | Fewer Steps | Easy to Understand |
| -------------------- | ----------- | ----------------- | ---------------- | ------------------ |
| Newton's method | :x: | :o: | :x: | :o: |
| Log+Taylor expansion | :o: | :x:† | :o:‡ | :wavy_dash: |

<font color=gray>
†it's quick though<br/>
‡kinda like a cheat
</font>

note
revised in 2023/Feb/16 for extra info
in logarithm and the Newton's method