Сравнение вычислительного времени умножения

Question

Пусть a, b два целых числа с n цифрами.Мне интересно, неужели время вычисления квадрата a меньше, чем a * b.

Спасибо за помощь.

Answer 1

Я предполагаю, что ваш вопрос:

* Пусть a, b два целых числа с n цифрами. Мне интересно, если время вычисления квадрата а короче, чем время вычисления а * б. *

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

Answer 2

Я не думаю, что есть способ возвести в квадрат А без использования IMUL на x86.Я могу ошибаться.

Чтобы узнать, сколько времени занимает что-то, сделайте микробенчмарк!

Редактировать: о, подождите, я понял!a b занимает два чтения памяти, а a a - одно!Таким образом, a * a быстрее: -).

Правдивый ответ: нет причины, по которой a * b будет медленнее, если у вас не будет какого-то внешнего фактора, влияющего на вещи.

Answer 3

Взгляните на тесты в "Программировании жемчужин" Бентли , вы можете взломать что-то оттуда, чтобы измерить.