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

Question

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

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

Answer 1

1. Существуют алгоритмы, более эффективные, чем O(N^2), для умножения двух чисел (см. Карацуба, Поллард, Шёнхаге – Штрассен и т. д.).

2. Две задачи «умножить два произвольных 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 2N-битный сдвиг)

И, очевидно, у нас есть

x^2 = x * x

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

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

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

Answer 2

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

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

Answer 3

Как отмечали другие, возведение в квадрат может быть примерно в 1,5 или 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 повторяются дважды.

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

Answer 4

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

Answer 5

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

Answer 6

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

2 * 2

дороже, чем

2 << 1

(Однако это работает только в одном случае.)

Answer 7

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

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

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

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

Answer 8

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

Получается, что метод, который я придумал, — это 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).

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

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

Answer 9

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

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

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

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

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

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

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

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

Возможно, есть еще одна лучшая симметрия, которую можно использовать.

Answer 10

a^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

Answer 11

Я бы хотел решить проблему путем N-разрядного умножения для числа

A биты должны быть A(n-1)A(n-2)........A(1)A(0).

B биты должны быть B(n-1)B(n-2)........ B(1)B(0).

для квадрата числа A сгенерированные уникальные биты умножения будут равны для A(0)-> A(0)....A(n-1) A(1)-> A(1)....A (n-1) и так далее таким образом, общее количество операций будет равно

OP = n + n-1 + n-2 .......+ 1 Следовательно, OP = n ^ 2+n/2;таким образом, асимптотическим обозначением будет O (n ^ 2)

и для умножения A и B будет сгенерировано n ^ 2 уникальных умножения таким образом, асимптотическое обозначение будет O (n ^ 2)

Answer 12

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

Answer 13

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

Answer 14

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

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

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

yet squaring a number can be done more efficiently somehow.

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

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