Вычисление чисел Ферма. Почему так медленно?

Question

[1ncomparable]

Здравствуйте, свежевыпеченные друзья, сидящие в тостере.
У меня такая проблема: решил ради забавы "поискать" числа Ферма. Воспользовался System.Numerics.BigInteger. В методах этой структуры был Pow, но он мог возводить в степень Int32, поэтому я соорудил такой костыль:

static BigInteger PPow(byte num, BigInteger exp)
        {
            BigInteger result = 1;
            uint n = (uint)(exp / Int32.MaxValue);
            Parallel.For(0, n, i =>
            {
                lock (lockobj)
                {
                    result *= BigInteger.Pow(num, Int32.MaxValue);
                    exp -= Int32.MaxValue;
                }

            });
            result *= BigInteger.Pow(num, (int)exp);
            return result;
        }

Вопрос такой: Можно ли как-нибудь ускорить возведение в степень?

Comments

[Арсений Ефремов]

1. У вас exp может быть больше, чем 2^64, тогда n будет рассчитан неверно.
2. Создайте несколько result (под количество потоков) и умножайте каждую отдельно, без лока.
3. BigInteger несмотря на мощную оптимизацию всё равно очень медленная штука. Может, существуют более быстрые алгоритмы для вашей задачи?

Answer 1

[Sumor]

Используйте алгоритм быстрого возведения в степень Аль-Коши