Доклад: Арифметика сверхбольших натуральных чисел в параллельных вычислительных системах

В . Умножение

Алгоритм умножения несколько сложнее в реализации, но напоминает собой умножение в столбик.

Система инициализирует двойных слов. При этом распределение ячеек памяти при инициализации можно представить в виде таблицы 1:

Таблица 1. - Распределение ячеек памяти при инициализации

	…		0	…		…		0	0
	…		0	…		…		0	0
ячеек				…	ячеек
ячеек

Сначала вычисляются одновременно числа, представляющие собой умножение на число , по следующему алгоритму: устройство

В1 . Считывает данные из ячеек памяти.

В2 . Выполняет умножение (, j ).

В3 . Записывает в младшие байты слов:, .

В4 . Записывает в старшие байты слов: .

В5 . Для каждой -ки происходит сложение по алгоритму А .

После шага В5 в старших байтах слов будут содержаться (таблица 2):

Таблица 2. - Распределение ячеек памяти после операции умножения

	…			…		…			…	0
ячеек				…	ячеек
				…

Результат умножения формируем из сложением со сдвигом на разрядов.

Количество шагов варьируется от 1 до , в то время как последовательное вычисление произведения займет шагов.

Предлагаемые алгоритмы могут быть реализованы на однородных вычислительных средах, систолических структурах, нейронных сетях.

Литература

1.Юров В. Assembler. – СПб.: Издательство «Питер», 2000.

2.Акритас А . Основы компьютерной алгебры с приложениями. – М: Мир, 1994.

3.Макоха А.Н ., Ионисян А.С . Компьютерная эмуляция арифметических операций над целыми и рациональными числами в СОК. // Вестник СГУ. – Ставрополь: Изд-во СГУ, вып. 20, 1999.