Алгоритм - умножение
Cтраница 3
При выполнении алгоритмов деления, как и алгоритмов умножения, на место одной из переменных записывается результат, в то время как место другой переменной освобождается. [31]
При программировании более сложных алгоритмов, например алгоритма умножения вектора на матрицу или матрицы на матрицу, возникает необходимость в использовании нескольких индекс-регистров для запоминания констант переадресации, изменяющихся различными шагами. [32]
Лемма 6.2 важна тем, что указывает возможность построения алгоритма умножения ( пХ / г) - матриц из алгоритмов умножения ( 2х2) - матриц и ( ( п / 2) х ( п / 2)) - матриц. [33]
Такое вычисление, примененное рекурсивно, привело бы к алгоритму умножения целых чисел со сложностью 0Б ( п log n), который был бы лучше всех известных. К сожалению, как мы покажем, для вычисления этих выражений в любом поле требуется не менее трех умножений. [34]
Данный метод является основой оригинального способа Шенхаге, используемого в алгоритме быстрого умножения чисел. Преимущество преобразований из СОК в ПСС через обобщенную полиадическую систему счисления состоит в том, что нахождение констант ОПС осуществляется только при помощи арифметики СОК. [35]
Стеки С и W используются в этом алгоритме для контроля рекурсивного механизма алгоритма умножения довольно простым способом, который представляет собой частный случай общей процедуры, рассматриваемой в гл. [36]
На первый взгляд трудно поверить, что этот метод может иметь какие-либо преимущества, поскольку алгоритм умножения, базирующийся на модулярной арифметике, помимо собственно операции умножения должен включать в себя выбор модулей и перевод чисел в модулярное представление и обратно. [37]
В конце этой главы мы показываем, как можно с помощью динамического программирования повысить эффективность рекурсивных алгоритмов и алгоритмов умножения матриц за счет выбора порядка, в котором они умножаются. [38]
Лемма 6.2 важна тем, что указывает возможность построения алгоритма умножения ( пХ / г) - матриц из алгоритмов умножения ( 2х2) - матриц и ( ( п / 2) х ( п / 2)) - матриц. [39]
 |
Условное графическое обозначение КР1802ВР2. [40] |
Устройство управления У / 7 вырабатывает в определенной последовательности сигналы, необходимые для приема операндов и инициации операции, реализации алгоритмов умножения и деления, выдачи результатов по кодам операции чтения. [41]
Подводя итог, скажем, что алгоритм Шенхаге-Штрассена применим для перемножения больших целых чисел, а для маленьких чисел более применим алгоритм умножения столбиком. Пока неясно, какой из алгоритмов наиболее приемлем для чисел определенной длины. Таким образом, для того чтобы программы на квантовом компьютере работали более эффективно, необходимо нацелиться на наилучшую реализацию элементарных алгебраических операций на таком квантовом компьютере. Имеет место один любопытный факт. Алгоритм Шенхаге-Штрассена быстрого перемножения использует быстрое преобразование Фурье, которое также является базисом для всех ныне известных быстрых алгоритмов для квантового компьютера. Можно спрогнозировать, что само по себе умножение целых чисел может быть сильно ускорено на квантовом компьютере, и возможно, это еще более асимптотически ускорит факторизацию целых чисел на квантовом компьютере, и возможно, это приведет к тому, что взлом системы RSA на квантовом компьютере будет производиться асимптотически быстрее, чем кодирование RSA на классическом компьютере. [42]
Однако, хотя в принципе доказана возможность нормализации для всех известных в настоящее время алгоритмов, фактическое выполнение нормализации даже для относительно простых алгоритмов ( например, для алгоритма умножения двух целых чисел) является весьма нелегким делом. Это означает, что программирование для машины, моделирующей универсальный нормальный алгоритм, было бы чрезвычайно громоздко и непрактично. Поэтому на практике машины, дающие возможность реализовать работу любого алгоритма, строятся на основании использования других алгоритмических систем, отличных от системы нормальных алгоритмов. Эти системы описаны в гл. [43]
На самом деле если бы можно было умножать две ( 2х2) - матрицы с помощью только шести умножений в некоммутативном кольце, то у нас мог бы быть алгоритм умножения матриц со сложностью 0A ( ftlog6) OA ( rt2 59) независимо от того, сколько тратится на умножение ( 2х2) - матриц сложений и вычитаний. [44]
Двоично-десятичное умножение сводится к образованию и многократному сложению двоично-десятичных произведений. Алгоритм умножения таких чисел выполняется в следующем порядке. [45]
Страницы: 1 2 3 4