- •Глава 3. Машинная арифметика
- •3.1. Машинное представление целых чисел
- •3.2. Арифметика чисел с фиксированной точкой
- •3.3. Арифметика чисел с плавающей точкой
- •3.3.2. Сложение чисел в форме с плавающей точкой
- •3.3.3. Умножение и деление чисел в форме с плавающей точкой
- •3.3.4. Точность арифметических операций с числами в форме с плавающей точкой
- •3.4. Вычисления с многократной точностью
- •3.4.1. Вычисления с большими целыми числами
- •3.4.2. Модулярная арифметика
- •3.4.3. Ускорение процесса умножения
- •3.5. Эффективные алгоритмы вычисления степеней
- •3.5.1. Бинарный метод
- •3.5.2. Метод факторизации показателя
- •3.6. Эффективные действия с дробями
- •3.7. Алгоритм Евклида для больших чисел
- •3.8. Алгоритмы разложения на простые множители
- •3.8.1.Метод пробных делений
- •3.8.2. Метод Ферма
- •3.8.3. Метод Крайчика
3.4. Вычисления с многократной точностью
Разрядность машинного слова определяет стандартную точность арифметических операций с плавающей точкой. В случаях, когда требуется проводить вычисления с большей точностью, для представления чисел в памяти отводится два или более машинных слов, и арифметические операции реализуются уже программными (а не аппаратными) средствами.
При вычислениях с многократной точностью на представление числа отводится несколько машинных слова (при том, что арифметические операции реализуются аппаратно для одного слова). Такие вычисления могут проводиться при работе с числами как с плавающей (чаще), так и с фиксированной запятой.
Для чисел с фиксированной точкой потребность в увеличении точности связана, прежде всего, с потребностью в большом числе точных цифр дробной части в исходных данных. Для чисел с плавающей точкой, бывает необходимо расширить как число разрядов мантиссы, так и диапазон значений порядка.
3.4.1. Вычисления с большими целыми числами
Пусть для представления большого целого числа в -ичной системе счисления используется-разрядных машинных слов. Отдельное слово может представлятьразличных значений (числа отдо), и поэтому его можно рассматривать как один разряд системы счисления с основанием. Тогдамашинных слов представляют-разрядное-ичное число, и арифметические действия, осуществляемые поразрядно («в столбик»), сводятся к следующим элементарным операциям:
– сложение одноразрядных чисел (и вычитание как сложение с обратным знаком) с получением переноса (или);
– умножение одноразрядных чисел с получением двухразрядного результата («два пишем, три в уме»);
– деление двухразрядного числа на одноразрядное с получением одноразрядного неполного частного и одноразрядного остатка. В терминах этих операций формулируются алгоритмы арифметических действий с многоразрядными числами. Поскольку основание системы счисления отлично от, то не применимы «быстрые» двоичные операции сложения/вычитания/умножения, сводимые к сложениям и сдвигам. Приходится использовать традиционные способы выполнения операций по схеме «в столбик». Что касается операции деления, то она и в двоичной арифметике выполняется «в столбик» и является наиболее трудоёмкой.
Сложение неотрицательных чисел. Пусть , и, так что в-ичной записи,.
Алгоритм сложения формирует в -ичной записи сумму. Введём вспомогательные переменные:— номер текущего разряда,— признак переноса, возникающего в текущем разряде (при сложении младших, нулевых разрядов переноса ещё не было:). При сложении в текущем разряде, так что перенос в следующий разряд — целая часть частного — либо нуль, либо единица.
╔
Ш.1. Начальные присваивания. .
Ш.2. Сложение разрядов с текущим номером :
— цифра в текущем разряде;
.
Ш.3. ;
если , то вернуться кШ.2,
в противном случае .
╚
Вычитание неотрицательных чисел. Пусть в -ичной записи,. Поскольку, достаточно иметь алгоритм для случаяс неотрицательной разностью.
Алгоритм вычитания формирует в -ичной записи неотрицательную разность. Введём вспомогательные переменные:— номер текущего разряда,— признак необходимости заимствования из следующего, старшего разряда:присваивается значение, если заимствование необходимо, и значение, если такой необходимости нет. При вычитании в текущем разряде это значение уже было сформировано вычитанием в предшествующем-м разряде; поэтомуновое значение , формируемое в текущем разряде, полагается равным, если при текущем значениивыполняется. Признак играет роль точки, которая ставится над цифрой уменьшаемого слева от текущего разряда, если нужно «занимать единицу».
Наименьшая цифра в текущем разряде уменьшаемого есть. Наибольшая цифрав текущем разряде вычитаемого есть. Разность между ними ещё уменьшается на единицу, если было заимствование (если надстоит точка при вычитании в столбик вручную). Итак, наименьшее значение разности в текущем разряде есть. В свою очередь, наибольшее значение разности в текущем разряде получается, когда из максимально возможной цифрыуменьшаемого вычитается, и не было заимствования (то есть). Поэтому при формировании разности в текущем-м разряде выполняется неравенство
.
Заимствование производится, если
.
Заимствование не производится, если
.
Таким образом, значение признака заимствования совпадает с числом .
╔
Ш.1. Начальные присваивания. .
Ш.2. Вычитание разрядов с текущим номером :
;
.
Ш.3. ;
если , то вернуться кШ.2.
╚
Умножение неотрицательных чисел. Пусть в -ичной записи,.
Алгоритм умножения формирует в -ичной записи неотрицательное произведениекак сумму попарных произведений:с учётом того, что в разрядмог придти ненулевой переносиз предыдущего произведения() и чтоможет оказаться .
Рассмотрим для примера в случае произведение двух разрядовс переносомиз предыдущего произведения. В результате получаем
.
Множитель при(это переносв следующий разряд) есть целая часть от, то есть. Множитель 7 при(в текущем разряде) есть остаток от деленияна, то есть.
Для накопления итогового коэффициента при(посколькуи т. д.) его начальное значение полагается, как обычно при циклическом сложении, равным нулю.
╔
Ш.1. Начальные присваивания.
(для накопления сумм);
—начальный номер разряда множителя , пара-
метр внешнего цикла.
Ш.2. — параметр внутреннего цикла, номер
начального разряда множителя ;
—обнуление переноса.
Ш.3. — произведение текущих
разрядов с учетом уже состоявшегося переноса
без разбивки на два разряда и ;
разбивка на разряды: ;
— перенос в следующий разряд.
Ш.4. ;
если , то
вернуться к Ш.3,
в противном случае
.
Ш.5. ;
если , то
вернуться к Ш.2.
╚