Почему возводит в квадрат число быстрее, чем умножение двух случайных чисел?

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

Возведение n-значного числа в квадрат может быть быстрее, чем умножение двух случайных n-значных чисел. Погуглив, я нашел эту статью . Речь идет об арифметике произвольной точности, но это может иметь отношение к тому, о чем вы просите. В нем авторы говорят следующее:

При возведении в квадрат большого целого числа, т.е. X ^ 2 = (xn-1, xn-2, ..., x1, x0) ^ 2 много членов перекрестного произведения вида xi * xj и xj * xi эквивалентны. Oни нужно вычислить только один раз, а затем сдвинуто влево, чтобы быть удвоенным. Операция возведения в квадрат n цифр выполняется с использованием только (n ^ 2 + n) / 2 умножение с одинарной точностью.

Я полагаю, вы имеете в виду возведение в степень возведением в квадрат . Этот метод используется не для умножения, а для возведения в степень x ^ n, где n может быть большим. Вместо того, чтобы умножать x раз себя N раз, выполняется серия операций возведения в квадрат и сложения, которые могут быть отображены в двоичное представление N. Число операций умножения (которые более дороги, чем сложение для больших чисел) уменьшается с N до log (N) относительно наивного алгоритма возведения в степень.

Я думаю, что вы совершенно ошибаетесь в своих утверждениях

Умножение двух двоичных чисел требует n ^ 2 time

Умножение двух 32-битных чисел занимает ровно один такт. На 64-битном процессоре я бы предположил, что умножение двух 64-битных чисел занимает ровно 1 такт. Меня даже не удивит, что 32-битный процессор может умножить два 64-битных числа за 1 такт.

yet squaring a number can be done more efficiently somehow.

Возведение числа в квадрат - это просто умножение числа на себя, так что это простое умножение. В ЦП нет операции «возведения в квадрат».

Возможно, вы путаете «возведение в квадрат» с «умножением на степень 2». Умножение на 2 может быть реализовано сдвигом всех битов на одну позицию влево. Умножение на 4 сдвигает все биты на две позиции влево. По 8, 3 позиции. Но этот трюк применим только к степени двойки.

Если у вас есть двоичное число A, его можно (всегда, доказательство оставлено нетерпеливому читателю) как (2 ^ n + B), это может быть возведено в квадрат как 2 ^ 2n + 2 ^ (п + 1) В + В ^ 2. Затем мы можем повторять разложение до тех пор, пока B не станет равным нулю. Я не особо вдавался в подробности, но интуитивно кажется, что вы можете заставить функцию возведения в квадрат делать меньше алгоритмических шагов, чем умножение общего назначения.

Квадратный корень из 2 ⁿ равен 2 ^{n / 2} или 2 ^{n >> 1} , поэтому если ваше число - это степень двойки, когда вы знаете силу, все становится совершенно просто. Умножить еще проще: 2 ⁴ * 2 ⁸ равно 2 ^{4 + 8} . В ваших заявлениях нет смысла.

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

Для целых чисел произвольной длины умножение обычно составляет O (N²), но есть алгоритмы, которые уменьшают это для больших целых чисел.

Если вы предположите простой подход O (N²) для умножения a на b , то для каждого бита в a необходимо сдвинуть b и добавить его в аккумулятор, если этот бит равен единице. Для каждого бита в a вам нужно 3N сдвигов и сложений.

Обратите внимание, что

( x - y )² = x² - 2 xy + y²

Следовательно,

x² = ( x - y )² + 2 xy - y²

Если каждый y является наибольшей степенью двойки, не превышающей x, это дает уменьшение до нижнего квадрата, две смены и две прибавки.

У меня есть!

2 * 2

дороже, чем

2 << 1

(с оговоркой, что он работает только в одном случае.)

Прежде всего, отличный вопрос! Хотелось бы, чтобы таких вопросов было больше.

Получается, что метод, который я придумал, - это O (n log n) для общего умножения только в арифметической сложности. Вы можете представить любое число X как

X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0

, где

x_i, y_i \in {0,1}

, затем

XY = sum _ {k=0} ^ m+n r_k 2^k

, где

r_k = sum _ {i=0} ^ k x_i y_{k-i}

, которое представляет собой простое приложение БПФ для нахождения значений r_k для каждого k в (n + m) log (n + m) время.

Затем для каждого r_k вы должны определить, насколько велико переполнение, и соответственно сложить его. Для возведения числа в квадрат это означает O (n log n) арифметических операций.

Вы можете более эффективно сложить значения r_k, используя алгоритм Шёнхаге-Штрассена, чтобы получить O (n log n log log n ) граница битовой операции.

Точный ответ на ваш вопрос уже опубликован Эриком Бейнвиллем.

Однако,