Как избежать умножения переполнения очень больших чисел с помощью рекурсивной функции (C#, D&C)

Question

Когда рекурсивная функция запускает и возвращает результаты в нужном направлении, происходит сбой из-за переполнения данных. Как я могу использовать этот алгоритм D&C и избежать этой проблемы?

static long long zarb(long a, long b, int n)
{
        Int64 w, x, y, z;
        int s;

        if (a == 0 || b == 0) 
           return 0;

        if (n <25)
            return a * b;
        else
        {
            s = n / 2;
            long p = power(2, s);
            w = a / p;
            x = a % p;
            y = b / p;
            z = b % p;
            return (zarb(w, y, n / 2) * power(2, 2 * s) + p * (zarb(w, z, n / 2) + zarb(x, y, n / 2)) + zarb(x, y, n / 2));
        }
}

static long power(int x, int y)
{
        long sum = 1;

        if (y == 0) 
           return 0;

        for (int i = 1; i <= y; i++)
            sum = sum * x;

        return sum;
}

Answer 1

В вашем коде нет реальной проблемы, он работает для определенного диапазона входных данных. Если вам нужно иметь возможность вводить значения, которые приведут к значениям вне диапазона в int64, попробуйте другой тип. System.Numerics встроен в.NET и имеет тип BigInteger, который утверждает, что "произвольно большое целое число, значение которого в теории не имеет верхних или нижних границ". Может потребоваться некоторое время, чтобы работать с этими крупными входными данными, но это должно быть хорошо.

https://msdn.microsoft.com/en-us/library/system.numerics.biginteger%28v=vs.110%29.aspx