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

Умножение двух двоичных чисел занимает n ^ 2 раза, но квадратичное число может быть сделано более эффективно каким-то образом. (с n числом бит) Как это могло быть?

Или это невозможно? Это безумие!

Ответ 1

Существуют алгоритмы, более эффективные, чем O (N ^ 2), чтобы умножить два числа (см. Karatsuba, Pollard, Schönhage-Strassen и т.д.)
Две проблемы "умножают два произвольных числа N-бит" и "Квадрат произвольного N-разрядного номера" имеют одинаковую сложность.

Мы имеем

4*x*y = (x+y)^2 - (x-y)^2

Таким образом, если квадратичные N-битовые целые числа принимают O (f (N)), то произведение двух произвольных N-битовых целых чисел может быть получено и в O (f (N)). (это 2x N-разрядных сумм, 2x квадратов N-бит, 1x 2N-разрядная сумма и 1x 2-разрядный сдвиг)

И, очевидно, мы имеем

x^2 = x * x

Итак, если умножение двух N-битовых целых чисел принимает O (f (N)), то квадратичное N-разрядное целое можно сделать в O (f (N)).

Любой алгоритм, вычисляющий произведение (соответственно квадрат), предоставляет алгоритм вычисления квадрата (соответственно произведения) с теми же асимптотическими затратами.

Как отмечено в других ответах, алгоритмы, используемые для быстрого умножения, могут быть упрощены в случае возведения в квадрат. Усиление будет на константе перед f (N), а не на f (N).

Ответ 2

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

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

Ответ 3

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

Ответ 4

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

Ответ 5

Как отмечали другие, возведение в квадрат может быть примерно на 1,5X или 2 раза быстрее обычного умножения между произвольными числами. Откуда взялось вычислительное преимущество? Это симметрия. Позвольте рассчитать квадрат 1011 и попытаться определить шаблон, который мы можем использовать. u0:u3 представляют биты в числе от самого значимого до наименее значимого.

    1011 //                               u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3
   1011  //                     u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3       
  0000   //           u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3                 
 1011    // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3

Если вы считаете элементы ui * ui для i=0, 1, ..., 4 для формирования диагонали и игнорируете их, вы увидите, что элементы ui * uj для i ≠ j повторяются дважды.

Поэтому все, что вам нужно сделать, это рассчитать сумму продукта для элементов под диагональю и удвоить ее, с левым сдвигом. Вы, наконец, добавили диагональные элементы. Теперь вы можете увидеть, откуда происходит ускорение 2X. На практике ускорение составляет около 1,5X из-за диагональных и дополнительных операций.

Ответ 6

У меня есть это!

2 * 2

дороже, чем

2 << 1

(Предостережение заключается в том, что он работает только в одном случае.)

Ответ 7

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

Итак, оказывается, что метод, который я придумал, - это 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}

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

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

Вы можете добавить значения r_k более эффективно, используя алгоритм Schönhage-Strassen, чтобы получить привязку операции бит O (n log n log log n).

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

Однако вы можете получить гораздо лучшую оценку, чем O (n ^ 2), для квадратизации числа просто потому, что существуют гораздо лучшие оценки для умножения целых чисел!

Ответ 8

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

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

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

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

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

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

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

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

Может быть другая лучшая симметрия для использования.

Ответ 9

а ^ 2 (a + b) * (a + b) + b ^ 2, например. 66 ^ 2 = (66 + 6) (66-6) + 6 ^ 2 = 72 * 60 + 36 = 4356

для a ^ n просто используйте правило питания

66 ^ 4 = 4356 ^ 2

Ответ 10

Предположим, вы хотите развернуть умножение (a+b)×(c+d). Он разбивается на четыре отдельных умножения: a×c + a×d + b×c + b×d.

Но если вы хотите развернуть (a+b)², тогда ему нужны только три умножения (и удвоение): a² + 2ab + b².

(Обратите внимание также, что два из умножений сами являются квадратами.)

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

Ответ 11

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

Ответ 12

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

Ответ 13

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

Умножение двух двоичных чисел n ^ 2 раза

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

yet squaring a number can be done more efficiently somehow.

В квадрате числа просто умножается число с самим собой, так что это просто простое умножение. В CPU нет "квадратной" операции.

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