Стр. 2 - Скоростные свойства алгоритмов умножения и деления целых чисел произвольного размера

ISSN 2305-5626. Вестник МГТУ им. Н.Э. Баумана: электронное издание. 2013 2
зуются функции ByteBits( ), ByteBitPrint( ), ByteBitMass( ) и InputAB( )
для преобразования обычного строкового вида вводимых чисел к
байтовым массивам хранения и отображения этих чисел. Тексты этих
функций приведены в [2].
Умножение. Для реализации умножения целых десятичных чи-
сел в байтовом представлении ниже приведена программа MI01, в
которой вычисляется произведение c a b= ∗ . Числа a и b вводятся со
знаком с клавиатуры в функции InputAB( ). В подключаемом файле
#include MultCarry.h находится функция MultCarry( ) для переноса
цифр, возникающих в результате поразрядного умножения. В под-
ключаемом файле ByteBitMult.h находится сама функция умножения
ByteBitMult( ), которую рассмотрим далее.
// Program MI01 (Win32)
// Умножение целых байтовых чисел в обратном порядке
#include <conio.h> // _getch
#include <iostream>
using namespace std;
#include <string.h> // strlen
#include "InputAB.h"
#include "MultCarry.h"
#include "ByteBitMult.h"
void main( void )
{ char sa[256]; // символьный буфер целого числа a
unsigned char a[256];
char sb[256]; // символьный буфер целого числа b
unsigned char b[256];
InputAB( sa, a, sb, b); // ввод чисел a и b
int na = strlen( sa ); // длина числа a
int nb = strlen( sb ); // длина числа b
// Умножение байтовых целых чисел
unsigned char c[256]; // для результата умножения
int nc = ByteBitMult( c, a, na, b, nb ); // c = a * b
cout << "c = a * b = "; ByteBitPrint( c, nc ); // листинг c
_getch(); // просмотр результата
}
Если при выполнении программы MI01 ввести числа 59
a = и
999 b = , то на монитор будет выведен результат 58 941 c a b= ∗ = :
sa = +59
a = 00001001 00000101 00101011
sb = +999
b = 00001001 00001001 00001001 00101011
c = 00000001 00000100 00001001 00001000 00000101 00101011
Перенос цифр при одноразрядном умножении. При реализации
умножения могут появляться цифры переноса в старшие разряды.
Обычно умножение многоразрядных чисел проводится поразрядно.
Поскольку одна десятичная цифра занимает в двоичном представле-
нии младшие 4 бита в байте, то одноразрядное умножение не может
выйти за пределы байта. Перенос цифр заключается в том, чтобы
оставить в разряде только биты, относящиеся к младшим цифрам из