- •Томский государственный университет систем управления и радиоэлектроники (тусур)
- •Длинные числа
- •Томский государственный университет систем управления и радиоэлектроники (тусур)
- •Задание
- •Содержание
- •Введение
- •Постановка задачи
- •Обзор литературы
- •Аналоги разработки данной программы
- •Существующие алгоритмы
- •Представление целых чисел
- •Сложение и вычитание
- •Умножение
- •Деление
- •Возведение в степень
- •Вывод длинного числа
- •Анализ задания
- •Требования к программе
- •Использование готовых разработок
- •Реализация программы
- •Тип данных
- •Основные процедуры и функции
- •Описание программы для пользователя
- •Заключение
- •Список используемых источников
- •Приложение а
- •Приложение б
- •Пошаговая структура процедуры сложения
- •Приложение в
- •Пошаговая структура процедуры деления
Сложение и вычитание
Практически каждый умеет складывать длинные числа, используя для этого листок бумаги и карандаш. Перенесем имеющееся у нас понимание на язык, понимаемый компьютером. Схема для сложения очень проста: складываем цифры слева направо (цифры хранятся в обратном порядке).
Если зафиксировано переполнение (при сложении получена цифра, которая больше максимально возможной в данной системе счисления), то происходит “перенос” (carry) в следующий разряд.
Вычитание осуществляется аналогично, с той лишь разницей, что осуществляется перенос “заимствования”.
Умножение
В случае с умножение, всё несколько сложнее. Тут необходимо учитывать, что может быть умножение длинного числа на короткое и длинного числа на длинное. Для начала рассмотрим умножение длинного числа на короткое.
В этом случае происходит простое умножение на него каждой цифры. При этом, конечно же, может произойти переполнение, поэтому необходимо вычислять переносы, которые при умножении могут принимать значения от 0 до BASE-1.
Если оба числа длинные, обычно мы умножаем число последовательно на одну цифру за другой, сохраняя временные результаты. Потом временные значения суммируются с учетом разряда. Однако можно ничего не хранить, а сразу прибавлять к окончательному результату.
Умножение (A,B, результатC)
1. Обнулить C
2. i= 0
3. Вычислить временный результат, соответствующий умножению i-ой цифрыAна числоB, в процессе вычисления сразу прибавлять его кC, начиная сi-ой позиции. Если получившаяся цифраCбольше BASE – сделать перенос.
4. Если Aне кончилось,i++ и идти на шаг 3
Деление
Операция деление представляет собой знакомый многим еще со школы алгоритм деления в столбик. Из делимого «выносится» количество цифр, равное количеству цифр делимого, затем делитель последовательно умножается на цифры от 1 до 9, с целью найти такую цифру, при которой произведение этой цифры на делитель не будет больше «вынесенного» числа. Далее от «вынесенного» числа отнимается найденное произведение, и потом к этой разности добавляется следующая цифра делимого, после «вынесенного» числа и алгоритм повторяется до тех пор, пока «вынесенное» число не станет меньше делителя, это оставшееся число становится остатком, а найденные цифры записываются в ряд в порядке их нахождение. Таким образом, находится частное от деления и остаток.
Возведение в степень
Операция возведение в степень очень похожа на операцию умножение длинного числа на длинное, но с одной лишь разницей, умножать приходится не один раз, а столько, сколько это необходимо в поставленной задачи.
Вывод длинного числа
При выводе длинного числа в Delphiможно воспользоваться строковыми данными, путем несложных преобразований, значения чисел в массиве можно последовательно записать в строку, число за числом. А затем уже вывести всю строку целиком, содержащую наше число.
В случае если наше число было отрицательным, в начале строки просто вставляется знак « - » (минус).
Анализ задания
Требования к программе
При написании данной программы были определены некоторые требования, которым должна будет соответствовать данная программа.
Во-первых, это реализация четырех операций сложение, вычитание, умножение и деление, а также операции возведение в степень. Было принято решение реализовать операцию возведение в степень, так как такая операция необходима для полноценной функциональности калькулятора. Например когда требуется возвести большое число в большую степень, когда стандартные методы и различные калькуляторы отказываются работать в полной мере.
Во-вторых, это приведение исходных чисел, а также полученного числа к нормальному виду, то есть к виду 1,23456eN, где количество цифр после запятой определяет необходимая точность вычислений, аN– степень полученного числа.
В-третьих, это возможность, как минимум, складывать, вычитать и умножать не только целые, но и дробные числа. При написании операции деления выявился ряд трудностей, которые более подробно описаны в разделе 7.