Non-floating-point fractional exponentiation approach
Completed on 16-Nov-2016 (24 days)
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.,
), 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
-based version of the aforementioned equation inside a loop exited when the difference between the x_i+1
values is smaller or equal than the target accuracy of
. Note that this is assumed to be the smallest positive value with which the most precise type (i.e.,
) 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.