Losing precision on big number calculations

Question

Specifically, the calculation I'm doing right now is the following

Math.Pow(1527768,7)%7281809;

I know the answer to this is 1010101, however, this is not the answer I am receiving. I believe this is due to the fact I am losing precision in the Math.Pow(). I am aware of BigInteger and I know this works but System.Numerics is unavailable in the environment I am using (I am unable to change the environment in any way, so, for now, assume BigInteger is out of the Question).

Is there any other way to perform the above operation to a more accurate precision?

Possible duplicate of [Math.Pow is not calculating correctly](http://stackoverflow.com/questions/4297454/math-pow-is-not-calculating-correctly) — Samuil Petrov, Apr 26 '17 at 09:50
@SamuilPetrov I have seen this question and the marked answer suggests BigInteger which I am unable to use. — Srb1313711, Apr 26 '17 at 09:51
Try the unmarked solution http://stackoverflow.com/a/4297502/4108884 — Samuil Petrov, Apr 26 '17 at 09:51
I have been through all the answers on there and none have worked for me — Srb1313711, Apr 26 '17 at 09:52
did you reference System.Numerics library into your project? I guess that's why you are saying its not available to you (?). by default it is not referenced in projects. you have to do it manually. — M.kazem Akhgary, Apr 26 '17 at 09:52
@M.kazemAkhgary I did but I believe the environment I am using is missing the assembly, and I am unable to change it — Srb1313711, Apr 26 '17 at 09:53
see here http://stackoverflow.com/questions/9824479/how-to-add-a-reference-do-system-numerics-dll after all you know you have to use some library in order to handle big numbers. otherwise you know that it is not easy to do that at all — M.kazem Akhgary, Apr 26 '17 at 09:58
@M.kazemAkhgary thanks for the answer but in my case, this is something I really can't use. I'm wondering if it's at all possible without it? — Srb1313711, Apr 26 '17 at 10:00
This is [modular exponentiation](https://en.wikipedia.org/wiki/Modular_exponentiation). You don't need `BigInteger` to implement that as long as the results themselves aren't large, since you don't need to compute the intermediate powers. — Jeroen Mostert, Apr 26 '17 at 11:11

score 1 · Answer 1 · answered Apr 26 '17 at 10:56

if you are only looking to do this kind of operation, where you need to find modulo of a powerfunction, you could make a simple modPow function like the following

static uint modPow(uint n, uint power, uint modulo)
{
    ulong result = n % modulo;
    for (uint i = power; i > 1; i--)
        result = (result * n) % modulo;
    return (uint)result;
}

Also there are more efficient algorithms if the power variable gets very high EDIT: Actually there generally are more efficient methods if efficency is a factor

score 1 · Answer 2 · answered Apr 26 '17 at 13:48

This might not be the best, but I put some thought to get this. Demo @ https://dotnetfiddle.net/Y2VSvN
NOTE: the function was tested against positive numbers only.

/// <summary>
/// Calculates the modulus of the power of a mutiple. 
/// </summary>
/// <param name="modularBase">Modulus base.</param>
/// <param name="value">Value to be powered</param>
/// <param name="pow">Number of powers</param>
/// <returns></returns>
static long GetModularOfPOW(int modularBase, int value, uint pow)
{
    return GetModularOf(modularBase, (pow > uint.MinValue) ? Enumerable.Repeat(value, (int)pow).ToArray() : new int[] { value });
}

/// <summary>
/// Calculates the modulus of the multiples. 
/// </summary>
/// <param name="modularBase">The modulus base.</param>
/// <param name="multiples">The multiples of the number.</param>
/// <returns>modulus</returns>
static long GetModularOf(int modularBase, params int[] multiples)
{
    /**
    * 1. create a stack from the array of numbers.
    * 2. take the 1st and 2nd number from the stack and mutiply their modulus
    * 3. push the modulus of the result into the stack.
    * 4. Repeat 2 -> 3 until the stack has only 1 number remaining.
    * 5. Return the modulus of the last remaing number.
    *
    * NOTE: we are converting the numbers to long before performing the arthmetic operations to bypass overflow exceptions.
    */
    var result = new Stack(multiples);
    while (result.Count > 1)
    {
        long temp = (Convert.ToInt64(result.Pop()) % Convert.ToInt64(modularBase)) * (Convert.ToInt64(result.Pop()) % Convert.ToInt64(modularBase));                
        result.Push(temp % modularBase);
    }

    return Convert.ToInt64(result.Pop()) % Convert.ToInt64(modularBase);
}

Losing precision on big number calculations

2 Answers2