Project 10
Completed (24 days)

Introduction >

Algorithm >

Newton-Raphson method >

Method improvement

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 intended fractional exponentiation approach is expected to account for most of the significant digits of the decimal type. Thus, the corresponding algorithm has to be able to deal with many scenarios involving fractions formed by big numbers (e.g., 0.23456789885 defined by the fraction 23456789885/10^11), what implies that the n-root calculating approach (i.e., Newton-Raphson) has to be able to deal with a huge range of n values (i.e., many integers within the 1-10^28 range).

The complexity of the aforementioned fraction can be reduced by analysing its constituent elements separately: the numerators are used in integer exponentiation (quick and reliable implementation easily dealing with any number) and the denominators in Newton-Raphson (reliability conditioned by the initial guess). Additionally, the ideas in the previous section seem to indicate that somehow reducing the number of n values/denominators (or inter-relating them) could be helpful to find good initial guesses. That's why it soon became clear that the best option was creating multiple-of-10-based fractions.

Even under the aforementioned conditions, the number of different input scenarios might still be too big (i.e., at least, 28 different trends); but the multiple-of-10 reliance proved to also be helpful on this front, via noticeable similarities across different n values (e.g., 10, 1000 or 10^10). I was able to come up with relatively simple approaches delivering acceptably good guesses for all the possible n values.

Math2_Private_New_PowSqrt_RootIni.cs includes all the code calculating the initial guesses for GetNRoot. These algorithms describe the patterns which I saw after analysing a reasonably big number of different input conditions; for example, after writing to a file the roots for 10, 10^2, 10^3, etc. with n = 10, 100, 1000, etc., a simple visual inspection was enough to extract worthy conclusions. All this information is referred by one of the following two main methods:
  • GetBase10IniGuess deals with all the cases where n is a multiple of 10, what includes all the n-root calculations performed by the fractional exponentiation algorithm (i.e., using Math2.PowDecimal with non-integer exponents). By bearing in mind that it is the first version of an innovative approach, this code delivers what is expected (i.e., good enough initial guesses for any possible scenario).
    Although all this part does seem improvable, I have no short-term plans to optimise it. On the other hand, I will submit a CoreFX issue suggesting to add decimal overloads to the System.Math methods Pow/Sqrt (note that a previous similar issue was reviewed and rejected, although not completely); if the .NET team decides to go ahead with that new suggestion, I would certainly work on optimising the current implementation.
  • GetBase2IniGuess deals with the specific scenario where n equals 2 (i.e., when using Math2.SqrtDecimal).
In summary, the described implementation allows the Newton-Raphson method to deal with virtually any input scenario (i.e., any value within the Number range and any exponent within the decimal range, by bearing in mind the aforementioned 25-first-decimal-digits limitation), what implies that a valid result for the target accuracy (i.e., 1e-28m or, under very specific conditions, 5e-28m) will always be found.