Составители:
Рубрика:
Если требуется разложить число N на множители, то ситуа-
ция оказывается весьма трудной. Попытка разделить на все про-
стые числа, которые меньше чем N
1/2
, требует O(N
2
log
2
N) опе-
раций, так что если N – целое число из n десятичных цифр, то
получаем порядок O(10
1/2
n
2
), растущий экспоненциально в зави-
симости от длины числа. Имеются более эффективные алгоритмы
с меньшей скоростью роста числа операций, а именно со скоростью
O(exp(n log n)
1/2
). Однако, такая скорость роста всё-таки выше по-
линомиальной; эти алгоритмы пока не применялись в САВ.
Для “реально встречающихся” чисел можно строить алгоритмы
со скоростью O(10
n/6
) (на том, какой размер чисел считать “реально
встречающимся” останавливаться не будем).
3. О представлении обыкновенных дробей
Обыкновенные дроби (т.е. дроби вида p/q где p и q – целые чис-
ла, q 6= 0) представляются в виде пары целых чисел: числителя и
знаменателя.
Без специальных указаний пользователя при работе САВ обык-
новенные дроби не следует заменять их приближёнными значения-
ми (например, на числа с плавающей точкой, которые также обыч-
но допустимы в САВ); ибо это может привести к непредсказуемым
результатам. Например, НОД многочленов
x
3
− 8 и 1/3x
2
− 4/3 (3.1)
равен 1/3x − 2/3, в то время как НОД многочленов
x
3
− 8 и 0.333333x
2
− 1.33333 (3.2)
равен 0.000001 из-за округления
17
Поскольку все вычисления с обыкновенными дробями требуют
вычисления НОД, а это проводит к большим затратам машинного
времени, то следует избегать обыкновенных дробей (если возмож-
но). В частности, вместо вычисления НОД многочленов (3.1) можно
ограничиться вычислением Н ОД многочленов
x
3
− 8 и x
2
− 4 (3.3)
17
Разобрать предложенную ситуацию детально для ЭВМ с шестиразрядной (десятичной)
мантиссой и бесконечным порядком.
41
Страницы
- « первая
- ‹ предыдущая
- …
- 38
- 39
- 40
- 41
- 42
- …
- следующая ›
- последняя »
