Вычисление квадрата BigInteger
Я использую.NET 4 Система. Численные данные. Структура BigInteger.
Я должен вычислить квадрат (x2) очень больших количеств - миллионы десятичных цифр.
Если x a BigInteger, Что является временной сложностью:
x*x;
или
BigInteger.Pow(x,2);
?
Как может умножить такие большие числа в самом быстром способе использовать.NET 4 BigInteger? Существует ли реализация для алгоритма Schönhage-Штрассена?
3 ответа
Это зависит от того, насколько велики ваши числа. Как сообщает страница Википедии:
На практике алгоритм Шёнхаге – Штрассена начинает превосходить более старые методы, такие как умножение Карацубы и Тоома – Кука, для чисел больше 2 2 15 на 2 2 17 (от 10 000 до 40 000 десятичных цифр).
System.Numerics.BigInteger использует алгоритм Карацуба или стандартное умножение из учебника, в зависимости от размера чисел. Карацуба имеет временную сложность O ( n log 2 3 ). Но если ваши цифры меньше, чем приведенные выше цифры, то вы, вероятно, не увидите большого ускорения от внедрения Schönhage – Strassen.
Что касается Pow () , это само по себе возводит в квадрат число по крайней мере один раз во время своих вычислений (и делает это, просто выполняя num * num - поэтому я думаю, что это не будет тоже будь более эффективным.
Вы можете использовать оболочку C # для библиотеки GNU MP Bignum, что, вероятно, настолько быстро, насколько это возможно. Для чистой реализации C # вы можете попробовать IntX .
Самым быстрым алгоритмом умножения на самом деле является алгоритм Фюрера , но я не нашел для него никаких реализаций.
Довольно простой метод для реализации основан на БПФ. Поскольку умножение двух чисел означает выполнение свертки их коэффициентов с последующим проходом для исключения переносов, вы должны иметь возможность выполнять свертку за O (n log n) операций с помощью методов БПФ (n = количество цифр).
В числовых рецептах есть глава об этом. Это определенно быстрее, чем методы «разделяй и властвуй», такие как Карацуба, для таких больших чисел.