Project 10
Completed (24 days)

Introduction >

Algorithm >

Newton-Raphson method >

Method overview

Completed (57 days)
Completed (26 days)
Completed (47 days)
Completed (19 days)
Completed (14 days)

Non-floating-point fractional exponentiation approach

Completed on 16-Nov-2016 (24 days)

Project 10 in full-screenProject 10 in PDF

The Newton-Raphson method is an iterative methodology for finding the roots of real functions, defined by x_i+1 = x_i - f(x_i) / f'(x_i) and starting from an initial guess x0. In the current implementation (i.e., GetNRoot), the goal is solving the function f(x) = x^n - value, what yields:
f(x) = x^n - value
f'(x) = n*x^(n-1)
x_i+1 = ((n - 1) * x_i + value / x_i^(n-1)) / n

GetNRoot includes a Number-based version of the aforementioned equation inside a loop exited when the difference between the x_i+1 and x_i values is smaller or equal than the target accuracy of 1e-28m. Note that this is assumed to be the smallest positive value with which the most precise type (i.e., decimal) can reliably deal.

This approach has only one relevant limitation: the initial guess x0 has to be similar enough to the final result. A bad initial guess would provoke (practically speaking) infinite loops in quite a few scenarios. The methodology with which I came up to address this issue is undoubtedly the most important part of the current implementation. The following two sections (Exponential proportionality and Method improvement) include detailed explanations about it, but some points should already be clear:
  • The calculations in GetNRoot are always started from an acceptably good initial guess (i.e., a right solution for the target accuracy will always be found quickly).
  • Under very specific conditions (and, presumably, only when being called from Math2.SqrtDecimal), the calculations might have to be exited before reaching convergence in order to avoid an infinite loop. The accuracy in these cases (5e-28m) is very similar to the usual one.