Классические алгоритмы целочисленной арифметики и их сложность.

Рассмотрим теперь классические алгоритмы выполнения арифметических операций с длинными целыми числами и их сложность. Как уже отмечалось, нам нужно разработать программное обеспечение для арифметики целых чисел, поскольку компьютер не мажет применять аппаратно реализованные операторы и т.д. к длинным целым числам; поэтому мы говорим, что теперь арифметические операторы и т.д. реализованы программно, и очевидно, что они работают медленнее, чем их аппаратно реализованные аналоги. Ниже, при определении функции времени вычислений алгоритма, читатель должен иметь в виду алгоритмы целочисленной арифметики, которые проходят в средней школе; звено, или ячейка, тогда аналогичны десятичной цифре, и нам просто требуется подсчитывать одноразрядные сложения и/или умножения. Различные операции будут выполняться над двумя длинными целыми , представленными списками.

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

1. Написать процедуру, назвав ее ISUM, для сложения целых чисел (integer .summation), на вход которой подаются , а на выходе получается значение их суммы

2. «Перегрузить» оператор +, т.е. когда встречается оператор проверяется тип переменных, являющихся его аргументами, и если обнаруживаются длинные целые числа» то существует ветвление на процедуру ISUM. (Такой подход мы называем «дружественным к пользователю», поскольку в данном случае пользователю не надо запоминать имена МАЯ процедур, которые ему могут потребоваться.)

Эти два подхода применимы к любым другим операциям с целыми числами и в дальнейшем упоминаться явно не будут.

При рассмотрении сложения выход также является списком, который получается при одновременном сканировании (продвижении вдоль) списков и и сложении малых целых чисел соответствующих звеньев (используя аппаратно реализованный ), учитывал, конечно, переносы. (Напомним, что в соответствии с нашими соглашениями о списочном представлении целого числа для сложения и умножения наименее значимые звенья появляются первыми.) Функция времени вычислений имеет вид это легко следует из того, что мы считаем число сложений одинарной точности и что их имеется не более чем (эта же величина ограничивает число возможных переносов) (см. определение 1.2.3). Кроме того, число ячеек во вновь созданном списке не превосходит

В качестве упражнения мы оставляем читателю проверку того, что, используя школьные алгоритмы целочисленного умножения для вычисления произведения и (двух упомянутых выше длинных целых чисел), получим

Деление значительно сложнее: При делении на мы в действительности ищем целые числа q и , обладающие свойством делимости с остатком Небольшое размышление над школьным процессом деления длинных чисел показывает, что для его выполнения нам достаточно уметь неоднократно делить -значное число на -значный делитель где b основание системы счисления (в компьютерных приложениях где уже использовалось выше). Обычно в компьютерных приложениях — это или какая-нибудь другая степень 2, в этих рассуждениях мы сначала рассматриваем наиболее значимые цифры, так что

Например, если нам нужно разделить 1234 на 23, то мы сначала делим 123 (наше начальное ) на 23 (наше ), получаем 5 и 8 в остатке; затем делим 84 (наше новое ) на 23, получаем 3 и 15 в

остатке. Очевидно, что эта же идея работает и в общем случае. Наиболее очевидный подход к данной задаче состоит в том, чтобы угадывать частное q по наиболее значимым цифрам чисел полученное таким путем частное называется пробным частным и обозначается Стандартный процесс угадывания состоит в делении на наиболее значимую цифру числа , двузначного числа в качестве берем получающееся частное. Таким образом, определяем

где в любом случае (Почему в этих рассуждениях не может быть )

Пример. Обозначим истинное частное через q. Тогда при им имеем:

Если , то , а следовательно, . В этом случае

Если , то . В этом случае

Если , то , а следовательно, . В этом случае каждого рассмотренного выше случая выполняются неравенства не позволяющие нам рассматривать случаи типа или даже и Ограничивает ли это общность? (Для ответа на этот вопрос см. теорему 1.2.5 и следующие за ней комментарии.) Кроме того, отметим, что во всех рассмотренных случаях слишком велико, однако при угаданное значение не так плохо, как при Почему это так, объясняется следующей теоремой.

Теорема 1.2.5. Пусть b — основание системы счисления, и рассмотрим числа

Если мы обозначим через к q (оба — целые числа) пробное частное и частное соответственно при делении на , то более того, если то это значит, что равно либо q, либо либо

Доказательство. В течение доказательства мы будем помнить, что

Из , используя неравенство мы получаем, что следовательно,

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

Для доказательства второй части теоремы предположим, что достаточно в этом случае показать, что т. Пользуясь неравенством получаем

по определению Поскольку имеем и правая часть этого соотношения Таким образом, вторая часть теоремы доказана.

Чтобы добиться выполнения условия, что старшая цифра делителя 6/2, нам нужно нормализовать его, т. е. домножить типна , где - наибольшая степень 2, для которой . Затем делим на . Для демонстрации рассмотрим последний случай предыдущего примера, в котором Вычислим наибольшее , такое, что получаем и нормализованные значения пит равны соответственно. Нормализация не влияет на частное, однако нам следует разделить остаток на .

Отметим, что в теореме 1.2.5 значение основания 6 несущественно. К тому же мы легко можем при необходимости подправить на 1 или 2, чтобы получить правильное частное на каждом шаге длинного деления. Более того, как мы увидим в следующем примере, можно изменить нашу стратегию угадывания и использовать большее количество старших цифр как в , так и в .

Пример. Разделим 272828282 на 3242. Получим

Заметим, что мы использовали две или три старшие цифры делимого.

Такой метод угадывания всегда даст нам либо истинную цифру частного, либо цифру, большую ее на единицу. Доказательство этого факта, а также детали реализации мы оставляем читателю в качестве упражнения по программированию. [Указание. См. упр. 19-21 в книге (Knuth, 1981, р. 235-238, 246); см. также полный текст программ на Паскале длинной целочисленной арифметики в книге (Flanders, 1984, р. 342-357)].

Читателю в качестве упражнения мы оставляем доказательство того, что, используя предыдущий алгоритм с карандашом и бумагой, получаем т. е. время деления на сводящегося к вычислению q и , обладающих свойством делимости, по существу совпадает с временем вычисления произведения см. также упр. по программированию 4 для данного раздела.