Math.Pow(31, 43) % 77 даёт неправильно значение

Question

Компилятор даёт значение 48. Калькулятор 3 - правильное значение. Не совсем пойму - в чём проблема. Возможно, слишком большие числа выходят. Как с этим справиться? Заранее спасибо Вам.

Answer 1

31^43 это число с 64 десятеричными знаками, тип decimal или double не способен столько хранить. Вы можете использовать длинную арифметику, что бы посчитать такое. Например встроенный тип BigInteger с System.Numerics.dll:

Console.WriteLine(BigInteger.ModPow(31, 43, 77));

Выведет 3. Более того, этот метод хорошо оптимизирован.

Answer 2

Дело в том, что Math.Pow работает с типом double, а у него ограниченная точность: он хранит число с точностью в 52 бита, а значит, у больших чисел младшие разряды получаются неточными. А для модуля нужны именно младшие разряды, а старшие не нужны вовсе.

Если бы Math.Pow работал с int, проблема была бы та же: int больше двух с копейками миллиардов будет взят по модулю 2^32, а это явно не то, что вам нужно.

---

Что же делать? А нужно выполнять операции не настолько в лоб. Вы должны представить возведение в степень как несколько умножений, и при каждом умножении брать модуль от результата.

Получится что-то такое:

uint multmod(uint a, uint b, uint mod) => (uint)(((ulong)a * b) % mod);

uint powermod(uint n, uint pow, uint mod)
{
    uint result = 1;
    uint npow = n;
    while (pow != 0)
    {
        if (pow % 2 == 1)
            result = multmod(result, npow, mod);
        pow = pow / 2;
        npow = multmod(npow, npow, mod);
    }
    return result;
}

---

Какой из методов лучше: считать вручную или воспользоваться библиотечным методом BigInteger.ModPow? Вопрос не так уж и тривиален.

С одной стороны, если вычислений немного, то лучше воспользоваться проверенным и отлаженным библиотечным методом. Скорость выполнения составляет величину порядка нескольких сотен наносекунд, это реально очень быстро, так что об этом можно не беспокоиться.

С другой стороны, если вычислений реально много, более миллиона в секунду, то нанооптимизации начинают иметь значение. Какой из методов быстрее: библиотечный или ручной? За библиотечный метод говорит то, что его писали и отлаживали профессионалы, и то, что в новых версиях фреймворка он наверняка ещё будет улучшаться. За ручной метод говорит то, что библиотечный метод слишком общ (он считает числа произвольной величины!), и за счёт этого может делать и слишком много. Тестируем!

Я написал вот такой тест на BenchmarkDotNet:

class Program
{
    static void Main(string[] args)
    {
        Console.ReadKey();
        var summary = BenchmarkRunner.Run<ModPowComparison>();
        Console.ReadKey();
    }
}

public class ModPowComparison
{
    [Params(3, 31, 8181818)]
    public uint A;

    [Params(3, 43, 243)]
    public uint B;

    [Params(2, 77, 1024, 100000)]
    public uint C;

    [Benchmark(Baseline=true)]
    public BigInteger BigNum() => BigInteger.ModPow(A, B, C);

    [Benchmark]
    public BigInteger Manual() => powermod(A, B, C);


    uint multmod(uint a, uint b, uint mod) => (uint)(((ulong)a * b) % mod);

    uint powermod(uint n, uint pow, uint mod)
    {
        uint result = 1;
        uint npow = n;
        while (pow != 0)
        {
            if (pow % 2 == 1)
                result = multmod(result, npow, mod);
            pow = pow / 2;
            npow = multmod(npow, npow, mod);
        }
        return result;
    }
}

Я взял немного маленьких чисел и немного чисел побольше. Вот результирующая таблица:

BenchmarkDotNet=v0.10.10, OS=Windows 7 SP1 (6.1.7601.0)
Processor=Intel Core i7-2600K CPU 3.40GHz (Sandy Bridge), ProcessorCount=8
Frequency=3320371 Hz, Resolution=301.1712 ns, Timer=TSC
  [Host]     : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2053.0
  DefaultJob : .NET Framework 4.7 (CLR 4.0.30319.42000), 64bit RyuJIT-v4.7.2053.0


 Method |       A |   B |      C |      Mean |      Error |     StdDev |    Median | Scaled |
------- |-------- |---- |------- |----------:|-----------:|-----------:|----------:|-------:|
 BigNum |       3 |   3 |      2 | 149.01 ns |  0.3356 ns |  0.2975 ns | 149.08 ns |   1.00 |
 Manual |       3 |   3 |      2 |  32.51 ns |  0.0581 ns |  0.0544 ns |  32.52 ns |   0.22 |
 BigNum |       3 |   3 |     77 | 149.08 ns |  0.4919 ns |  0.4602 ns | 149.17 ns |   1.00 |
 Manual |       3 |   3 |     77 |  33.00 ns |  0.1314 ns |  0.1229 ns |  32.99 ns |   0.22 |
 BigNum |       3 |   3 |   1024 | 149.17 ns |  0.2275 ns |  0.2128 ns | 149.15 ns |   1.00 |
 Manual |       3 |   3 |   1024 |  33.18 ns |  0.0888 ns |  0.0831 ns |  33.17 ns |   0.22 |
 BigNum |       3 |   3 | 100000 | 149.02 ns |  0.5999 ns |  0.5318 ns | 148.99 ns |   1.00 |
 Manual |       3 |   3 | 100000 |  33.17 ns |  0.0549 ns |  0.0514 ns |  33.18 ns |   0.22 |
 BigNum |       3 |  43 |      2 | 262.27 ns |  0.5958 ns |  0.5573 ns | 262.23 ns |   1.00 |
 Manual |       3 |  43 |      2 |  76.55 ns |  0.1985 ns |  0.1856 ns |  76.56 ns |   0.29 |
 BigNum |       3 |  43 |     77 | 262.12 ns |  0.5056 ns |  0.4729 ns | 262.14 ns |   1.00 |
 Manual |       3 |  43 |     77 |  78.53 ns |  0.2021 ns |  0.1791 ns |  78.56 ns |   0.30 |
 BigNum |       3 |  43 |   1024 | 262.48 ns |  0.7268 ns |  0.6798 ns | 262.42 ns |   1.00 |
 Manual |       3 |  43 |   1024 |  78.66 ns |  0.2674 ns |  0.2502 ns |  78.67 ns |   0.30 |
 BigNum |       3 |  43 | 100000 | 262.35 ns |  0.7756 ns |  0.7255 ns | 262.26 ns |   1.00 |
 Manual |       3 |  43 | 100000 |  79.13 ns |  0.1902 ns |  0.1779 ns |  79.21 ns |   0.30 |
 BigNum |       3 | 243 |      2 | 337.59 ns |  0.8698 ns |  0.8136 ns | 337.52 ns |   1.00 |
 Manual |       3 | 243 |      2 | 114.33 ns | 10.2557 ns | 16.2666 ns | 104.97 ns |   0.34 |
 BigNum |       3 | 243 |     77 | 337.43 ns |  0.8991 ns |  0.8410 ns | 337.53 ns |   1.00 |
 Manual |       3 | 243 |     77 | 106.63 ns |  0.2987 ns |  0.2648 ns | 106.62 ns |   0.32 |
 BigNum |       3 | 243 |   1024 | 337.65 ns |  0.5805 ns |  0.5430 ns | 337.59 ns |   1.00 |
 Manual |       3 | 243 |   1024 | 107.24 ns |  0.1823 ns |  0.1705 ns | 107.24 ns |   0.32 |
 BigNum |       3 | 243 | 100000 | 362.40 ns |  0.9287 ns |  0.7755 ns | 362.21 ns |   1.00 |
 Manual |       3 | 243 | 100000 | 106.85 ns |  0.1600 ns |  0.1419 ns | 106.86 ns |   0.29 |
 BigNum |      31 |   3 |      2 | 149.07 ns |  0.5325 ns |  0.4720 ns | 149.04 ns |   1.00 |
 Manual |      31 |   3 |      2 |  32.54 ns |  0.0861 ns |  0.0805 ns |  32.53 ns |   0.22 |
 BigNum |      31 |   3 |     77 | 149.45 ns |  0.5391 ns |  0.4779 ns | 149.47 ns |   1.00 |
 Manual |      31 |   3 |     77 |  32.73 ns |  0.1518 ns |  0.1420 ns |  32.71 ns |   0.22 |
 BigNum |      31 |   3 |   1024 | 150.40 ns |  0.4437 ns |  0.3934 ns | 150.32 ns |   1.00 |
 Manual |      31 |   3 |   1024 |  33.11 ns |  0.0672 ns |  0.0628 ns |  33.12 ns |   0.22 |
 BigNum |      31 |   3 | 100000 | 150.89 ns |  0.7241 ns |  0.6047 ns | 150.65 ns |   1.00 |
 Manual |      31 |   3 | 100000 |  33.42 ns |  0.3659 ns |  0.3422 ns |  33.25 ns |   0.22 |
 BigNum |      31 |  43 |      2 | 264.31 ns |  1.2552 ns |  1.1741 ns | 264.45 ns |   1.00 |
 Manual |      31 |  43 |      2 |  76.87 ns |  0.2282 ns |  0.2134 ns |  76.91 ns |   0.29 |
 BigNum |      31 |  43 |     77 | 262.70 ns |  1.0268 ns |  0.9605 ns | 262.56 ns |   1.00 |
 Manual |      31 |  43 |     77 |  79.13 ns |  0.2694 ns |  0.2520 ns |  79.08 ns |   0.30 |
 BigNum |      31 |  43 |   1024 | 263.40 ns |  1.3053 ns |  1.2209 ns | 262.74 ns |   1.00 |
 Manual |      31 |  43 |   1024 |  78.98 ns |  0.1876 ns |  0.1755 ns |  78.94 ns |   0.30 |
 BigNum |      31 |  43 | 100000 | 262.73 ns |  0.7095 ns |  0.6290 ns | 262.66 ns |   1.00 |
 Manual |      31 |  43 | 100000 |  78.99 ns |  0.1747 ns |  0.1634 ns |  78.95 ns |   0.30 |
 BigNum |      31 | 243 |      2 | 338.05 ns |  1.4928 ns |  1.3964 ns | 337.56 ns |   1.00 |
 Manual |      31 | 243 |      2 | 105.00 ns |  0.1658 ns |  0.1551 ns | 104.97 ns |   0.31 |
 BigNum |      31 | 243 |     77 | 337.59 ns |  0.7197 ns |  0.6732 ns | 337.53 ns |   1.00 |
 Manual |      31 | 243 |     77 | 106.78 ns |  0.2404 ns |  0.2131 ns | 106.76 ns |   0.32 |
 BigNum |      31 | 243 |   1024 | 338.06 ns |  0.6610 ns |  0.6183 ns | 337.81 ns |   1.00 |
 Manual |      31 | 243 |   1024 | 106.51 ns |  0.3239 ns |  0.3030 ns | 106.44 ns |   0.32 |
 BigNum |      31 | 243 | 100000 | 385.20 ns |  0.7483 ns |  0.7000 ns | 385.16 ns |   1.00 |
 Manual |      31 | 243 | 100000 | 107.31 ns |  0.2380 ns |  0.2227 ns | 107.27 ns |   0.28 |
 BigNum | 8181818 |   3 |      2 | 173.17 ns |  0.4454 ns |  0.4166 ns | 173.23 ns |   1.00 |
 Manual | 8181818 |   3 |      2 |  34.74 ns |  0.0799 ns |  0.0747 ns |  34.75 ns |   0.20 |
 BigNum | 8181818 |   3 |     77 | 172.74 ns |  0.1622 ns |  0.1267 ns | 172.76 ns |   1.00 |
 Manual | 8181818 |   3 |     77 |  33.24 ns |  0.0937 ns |  0.0876 ns |  33.24 ns |   0.19 |
 BigNum | 8181818 |   3 |   1024 | 172.72 ns |  0.3758 ns |  0.3515 ns | 172.73 ns |   1.00 |
 Manual | 8181818 |   3 |   1024 |  32.68 ns |  0.0712 ns |  0.0631 ns |  32.68 ns |   0.19 |
 BigNum | 8181818 |   3 | 100000 | 197.96 ns |  0.4350 ns |  0.4069 ns | 197.88 ns |   1.00 |
 Manual | 8181818 |   3 | 100000 |  33.12 ns |  0.1025 ns |  0.0959 ns |  33.11 ns |   0.17 |
 BigNum | 8181818 |  43 |      2 | 287.34 ns |  0.6073 ns |  0.5681 ns | 287.18 ns |   1.00 |
 Manual | 8181818 |  43 |      2 |  77.66 ns |  0.1319 ns |  0.1233 ns |  77.66 ns |   0.27 |
 BigNum | 8181818 |  43 |     77 | 287.11 ns |  0.9016 ns |  0.8434 ns | 287.30 ns |   1.00 |
 Manual | 8181818 |  43 |     77 |  80.28 ns |  0.1037 ns |  0.0919 ns |  80.28 ns |   0.28 |
 BigNum | 8181818 |  43 |   1024 | 287.15 ns |  0.7190 ns |  0.6725 ns | 287.25 ns |   1.00 |
 Manual | 8181818 |  43 |   1024 |  78.77 ns |  0.1394 ns |  0.1304 ns |  78.79 ns |   0.27 |
 BigNum | 8181818 |  43 | 100000 | 401.59 ns |  0.7218 ns |  0.6398 ns | 401.37 ns |   1.00 |
 Manual | 8181818 |  43 | 100000 |  79.45 ns |  0.1356 ns |  0.1202 ns |  79.39 ns |   0.20 |
 BigNum | 8181818 | 243 |      2 | 362.07 ns |  0.6777 ns |  0.6339 ns | 361.93 ns |   1.00 |
 Manual | 8181818 | 243 |      2 | 105.72 ns |  0.2266 ns |  0.2119 ns | 105.77 ns |   0.29 |
 BigNum | 8181818 | 243 |     77 | 362.05 ns |  0.4713 ns |  0.3936 ns | 362.06 ns |   1.00 |
 Manual | 8181818 | 243 |     77 | 108.33 ns |  0.1698 ns |  0.1589 ns | 108.29 ns |   0.30 |
 BigNum | 8181818 | 243 |   1024 | 362.43 ns |  0.8363 ns |  0.7823 ns | 362.21 ns |   1.00 |
 Manual | 8181818 | 243 |   1024 | 104.96 ns |  0.2377 ns |  0.2224 ns | 104.95 ns |   0.29 |
 BigNum | 8181818 | 243 | 100000 | 506.07 ns |  1.1124 ns |  0.9289 ns | 506.21 ns |   1.00 |
 Manual | 8181818 | 243 | 100000 | 107.34 ns |  0.3394 ns |  0.3175 ns | 107.37 ns |   0.21 |

Тут интересна последняя колонка, которая показывает относительную скорость. Из неё видно, что в данных тестовых условиях ручной метод по времени занимает от 17 до 32% времени, необходимого библиотечному методу.

В других условиях результаты будут, конечно, другими.