В 2009/2010 учебном году продолжила свою работу городская творческая группа «Организация дистанционного образования». Участники творческой группы, работающие по направлению разработка в программной оболочке Moodle дистанционных курсов по программированию для учащихся с повышенными образовательными потребностями, собрали учебно-дидактические материалы по различным темам. Учитель информатики школы №53 г. Мурманска Краснов Павел Сергеевич представил материал по теме "Длинная арифметика", в котором рассматриваются некоторые из возможных алгоритмов действий с большими числами, не умещающиеся в стандартные типы данных.
ДЛИННАЯ АРИФМЕТИКА
учебно-дидактические материалы для учащихся 10 классов
Известно, что арифметические действия, выполняемые компьютером в ограниченном числе разрядов, не всегда позволяют получить точный результат. Более того, мы ограничены размером (величиной) чисел, с которыми можем работать. А если нам необходимо выполнить арифметические действия над очень большими числами, например,
30!=265252859812191058636308480000000?
В таких случаях мы сами должны позаботиться о представлении чисел в машине и о точном выполнении арифметических операций над ними.
Числа, для представления которых в стандартных компьютерных типах данных не хватает количества двоичных разрядов, называются «длинными». Реализация арифметических операций над такими «длинными» числами получила название «длинной арифметики».
Организация работы с «длинными» числами во многом зависит от того, как мы представим в компьютере эти числа (Приложение Файл ПРЕЗЕНТАЦИЯ).
«Длинное» число можно записать, например, с помощью массива десятичных цифр, количество элементов в таком массиве равно количеству значащих цифр в «длинном» числе. Но если мы будем реализовывать арифметические операции над этим числом, то размер массива должен быть достаточным, чтобы разместить в нем и результат, например, умножения.
Существуют и другие представления «длинных» чисел. Рассмотрим одно из них.
Представим наше число 30!= в виде:
30!=2 *(10 4) 8 + 6525 * (10 4) 7 + 2859 * (10 4) 6 + 8121 * (10 4) 5 + 9105 * (10 4) 4 + 8636 * (10 4) 3 + 3084 * (10 4) 2 + 8000 * (10 4) 1 + 0000 * (10 4) 0
Это представление наталкивает на мысль о массиве, представленном в табл.1
Таблица 1
Номер элемента в массиве А |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Значение |
9 |
0 |
8000 |
3084 |
8636 |
9105 |
8121 |
2859 |
6525 |
2 |
Мы можем считать, что наше «длинное» число представлено в 10000-10 системе счисления (десятитысячно-десятичная система счисления, приведите аналогию с восьмерично-десятичной системой счисления), а «цифрами» числа являются четырехзначные числа.
Возникают вопросы. Что за 9 в А [0], почему число хранится «задом наперед»? Ответы очевидны, но подождем с преждевременными объяснениями. Ответы на вопросы будут ясны из текста.
Краснов П.С., учитель информатики МОУ СОШ № 53