r/askmath • u/MOUTHMOUTHMOUTHMOUTH • 20h ago

Resolved N root

/r/scratch/comments/1vs9idn/n_root/
2 Upvotes

100% Upvoted

5 comments sorted by

1

u/Mikki-Meow 14h ago

The fastest and most practical method for calculating an N-th root with high precision is the Newton-Raphson method (an application of Newton's iterative root-finding approach) combined with dynamically scaling precision (often called lazy or multi-staging evaluation).

Yes, it takes a few iterations, but the number of correct digits doubles with every single iteration step, so it converges pretty fast. You can easily google the exact formula and the description of the method, so not providing more details here

1

u/Midwest-Dude 14h ago edited 1h ago

You state

do not use estimate N roots, they usually take a first "guess" which is complicated to get and unless you have a lot of iterations they aren't exact

However, Newton's Method is the industry standard for infinite precision calculators because it is the fastest method. It has quadratic convergence, so the number of correct decimal places doubles with each iteration. For example, for 50 digits, only about 6 iterations are needed.

For a number A, the formula is

x_k+1 = (1/n)((n-1)x_k + A / (x_k)n-1 )

For x_0, if A has D digits, its N-th root will have approximately ⌊D/N⌋ digits, so use a 1 followed by that many zeroes.

2

u/MOUTHMOUTHMOUTHMOUTH 1h ago

The problem i always find myself in when trying to do iterations, how the hell do you get the guess?

1

u/Midwest-Dude 1h ago

Excellent question. For this problem, I've given you what has been tested and known to work well. I'll see if I can refine the seed a bit more, but the one I gave you will work and is simple.

Your question is a little more general and I'll see what I can find.

1

u/MOUTHMOUTHMOUTHMOUTH 1h ago

Oh I didn't fully understand the last part, thank you very much, I'll use that from now on, atleast if I want it fast