Составители:
Рубрика:
возможности отразить отдельные детали рассматриваемой ситуа-
ции и дать доказательства приводимых утверждений. Более того,
многие утверждения в этих условиях не удаётся даже точно сфор-
мулировать.
С другой стороны полезность такого обзора несомненна: он поз-
воляет понять основные трудности и обратиться к их изучению в
нужной последовательности.
Здесь мы кратко рассмотрим фундаментальную проблему наи-
более эффективного представления данных в максимально универ-
сальной постановке, т.е без технических деталей. Многие из рас-
сматриваемых результатов носят характер рецептов, объяснение
или доказательства которых иной раз являются результатами об-
ширных теорий и потому выходят за рамки настоящего курса.
К моменту чтения этого параграфа читателю уже известны ре-
зультаты изучения быстрого преобразования Фурье (см. предыду-
щий параграф), и это существенно облегчает понимание последу-
ющего материала.
2. Представление целых чисел
Представление целых чисел представляет собой определённую
проблему в САВ, поскольку при проведении аналитических преоб-
разований промежуточные результаты требуют значительной па-
мяти, хотя исходные данные невелики.
В САВ обычно рассматриваются точные аналитические преобра-
зования (и это имеет глубокий смысл в ряде исследований). Поэто-
му никакие округления или другие искажения целых чисел недо-
пустимы. Для иллюстрации приведём известный пример (Knuth,
Broun) вычисления НОД двух многочленов
P (x) = x
8
+ x
6
− 3x
4
− 3x
3
+ 8x
2
+ 2x − 5, (2.1)
Q(x) = 3x
6
+ 5x
4
− 4x
2
− 9x + 21, (2.2)
В результате деления 3
3
P (x) на Q(x) в остатке получится число
12593338795500743100931151992187500, (2.3)
содержащее 35 десятичных цифр (117 бит), откуда следует, что
многочлены P и Q взаимно просты. Полученный ответ (“просто-
та”,“непростота”) требует для хранения 1 бит, а число (2.3) можно
рассматривать как результат промежуточных вычислений.
39
Страницы
- « первая
- ‹ предыдущая
- …
- 36
- 37
- 38
- 39
- 40
- …
- следующая ›
- последняя »
