Составители:
Рубрика:
Отсюда следует, что необходимо рассматривать целые числа про-
извольной
величины. Поэтому САВ обычно допускает такую возможность
и для представления таких чисел (называемых “bignums”) выбира-
ют в качестве основания некоторое число N и представляют числа
относительно этого основания (с помощью “цифр” из диапазона от
0 до N − 1), к которым добавляется знаковый бит. Используются
обычно два представления: десятичное и двоичное, так что в каче-
стве N употребительны 10
9
и 2
30
(или 2
31
).
Для вычитания и сложения чисел используются обычные алго-
ритмы поразрядного сложения с переносом из одного разряда в
другой, а для результата умножения требуется два слова.
Деление представляет собой значительные трудности, связанные
с необходимостью угадывания цифры частного (Knuth предложил
достаточно надёжный алгоритм получения этой цифры, который
почти всегда даёт правильный или близкий к правильному резуль-
тат). Что касается времени счёта, то для сложения и вычитания это
время пропорционально числу n цифр (будем писать в этом случае
O(n)), а для умножения это время пропорционально числу n
2
т.е.
O(n
2
). Согласно предыдущему параграфу использование быстрого
дискретного преобразования Фурье (см. §1) позволяет довести это
время до
O(n log n log log n).
Однако следует заметить, что фактически последнее выражение
имеет вид
20n log n log log n,
так что исследования БПФ в этой ситуации эффективно для n по-
рядка нескольких тысяч. В большинстве САВ такой алгоритм не
используется.
Для вычисления НОД двух целых чисел требуется время O(n
3
);
его достаточно просто снизить до O(n
2
) и даже до
O(n log
2
n log log n),
однако алгоритм, связанный с последней оценкой, в САВ чаще все-
го не используется.
Отсюда следует, что всегда следует стремиться к работе с чис-
лами минимальной длины.
40
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
