Integers exhibit odd behavior at higher values

Question

I have created a program, in C#, to convert a number from one base to any other base (e.g. 10 in Base-10 = A in Base-11).

For each target base, there seems to be a certain point where the program results in an inaccurate value. E.g., when converting from Base-10 to Base-11 then back to Base-10, the miscalculation (which results in a integer one less than what I started) occurs at any value equal to or greater than 45949729863572161 (which is coincidentally equivalent to 11¹⁶; who woulda' thought?).

To make my conversions, I first convert a number to Base-10 then to the target base. I have no real guess as to what point is the cause of this error

The most likely culprits are the primary methods.
A) The method to convert to Base-10

static string toBase10(string origVal, uint origBase)
{
    ulong result = 0;
    //Convert each character to base-ten so that base-ten arithmetic can be used
    ulong[] b10Array = charsToBase10Readable(origVal, findSubArray(origBase));

    //Run through each place value to convert entire number to base-ten
    for (uint n = 0; n < b10Array.Length; n++)
    {
        ulong val = b10Array[n];
        result += val * ((ulong)Math.Pow(origBase, b10Array.Length - n - 1));
    }

        return result.ToString();
    }
}

B) The method to convert from Base-10

static string fromBase10(ulong num, uint targetBase)
{
    string result = string.Empty;
    //Generate the original base
    char[] targetBaseChars = findSubArray(targetBase);
    do
    {
        result = targetBaseChars[num % (ulong)targetBase] + result;
        num /= (ulong)targetBase;
    }
    while (num > 0);

    return result;
}

Other potential methods

static char[] findSubArray(uint i)
{
    char[] subArray = new char[i];
    for (uint n = 0; n < i; n++)
    {
        subArray[n] = masterBase[n];
    }
    return subArray;
}

In case the above methods aren't the issue, a more expansive version of my conversion code is available as a Github Gist.

Any thoughts as to what the issue is? I doubt that it is hitting ulong's max, although beyond that I am unsure.

Thank you for any assistance!

Answer 1

Math.Pow does its arithmetic in doubles. Doubles only have about 16 decimal digits of precision; you'll start getting representation errors accumulating when the numbers are on the order of 10 to the 16. Which yours are.

Use BigInteger.Pow() instead. It has arbitrarily large precision.

Incidentally, you are not the first person to discover this fact about putting 11 to the 16th power into a double:

https://math.stackexchange.com/questions/91583/implementing-fermats-primality-test/91584#91584