СЧИТАЛО: дробные числа как надстройка над целыми (взгляд с позиции синтаксиса)
Просмотров: 1670
09 апреля 2017 года
Задача заметки
В своей программе - СЧИТАЛО - мы, со временем, реализовали поддержку дробных чисел. Алгоритмы придумали сами и остались очень довольны доработкой: поддержка плавающей запятой потребовала минимального расширения описания класса "большое число", сохранив все базовые алгоритмы арифметических операций неизменными.
Процесс объяснения машине (которая понимала только целые числа) того, как надо работать с дробными числами, помог выработать абстрактное синтаксическое восприятие арифметических операций. Разумеется, я не буду уповать лишь на синтаксис, окончательно выбирая одну из сторон в философском вопросе о синтаксисе и семантике в рамках искусственного интеллекта. Да, простейшая машина лишена понимания смысловой нагрузки информации, вводимой в неё, и процессов, которые в ней (машине) протекают. Тем не менее, иногда очень кстати бывает включить "режим калькулятора" и просто начать шпарить примеры один за другим. К тому же, семантическая картина была бы неполной без формальной синтаксической составляющей.
Лирическое отступление
Где-то в 2006-2007 гг (вот ужас: прошло уже 10 лет!) мне не захотелось возиться с лабораторками по языку ассемблера для некоей учебной виртуальной машины: я честно поработал с регистрами, изучил выделение памяти... однако, на тот момент, удобство IDE (написанная студентом оболочка над утилитами трансляции кода и эмуляции машины) меня угнетало. Забегая вперёд, скажу, что у меня ещё будет и написание программ в байт-коде (то есть ниже некуда - даже транслятор не нужен), и создание синтезатора управляющих слов для процессора, но всё это - потом. А сейчас - мы решили вместо типовых лабораторных работ (которые, при особом желании, можно было и найти у старших курсов) "выехать" на какой-нибудь программе-калькуляторе, разработав её в рамках курсового проекта.
Собственно, кто это - "мы"? Костяк команды был обычный: я занимался кодом и выработкой направления дальнейшего развития программы, Алексей - прорабатывал математические алгоритмы, Андрей - отвечал за графику, примеры расчётов, идущие в комплекте, и сайт программы. К нам ещё присоединились: всегда бодрствующий Константин из группы КА-2, занимавшийся тестированием приложения и отдельных модулей, и (представительница прекрасной части человечества) Виктория из группы КА-4, выполнившая локализацию интерфейса программы и сайта на английский язык. Вот такая "команда мечты", объединившая студентов трёх из четырёх групп на потоке кибернетика:автоматика.
Помню, как мы выбирали название для приложения: среди прочих были "числонавт" и "листочек". "Числонавт" имел какие-то негативные коннотации. "Листочек" нужен был только ради веселья, чтобы на вопрос:"На чём это Вы посчитали 21289?" - отвечать:"На «листочке»".
Разработка велась на Си++. Изначально у нас были алгоритмы (которые несложно найти в Интернете) дающие представление о концепции реализации "больших" целых чисел. Ну а потом понеслось: добавили знак, позволив работать с отрицательными числами, добавили плавающую запятую, добавили операцию возведение в степень (Алексей ещё придумал как оптимизировать процедуру). Затем я добавил поддержку переменных и парсер формул. Парсер использовал уже знакомую мне (после изобретения "велосипеда" в старших классах), так называемую "Обратную польскую запись". В итоге у нас получилась простенькая REPL-система - и вот тут уже было где разгуляться: мы соревновались в придумывании задачи, результатом которой являлось бы абсурдно большое число (например, объём мирового океана в чайных ложках).
Одно из гигантских чисел, полученных на СЧИТАЛО, некоторое время висело над входом на кафедру. Славные (эпизодами) были времена! В прошлом (позапрошлом?) году заглянул на кафедру - нет баннера. Sic transit gloria mundi...
Проблема
Ещё раз повторюсь: на определённом этапе разработки, перед нами встала задача "реализовать поддержку чисел с плавающей запятой, опираясь только на алгоритмы работы с целыми числами".
Сложение
- Определить количество значащих цифр после запятой в обоих слагаемых.
- Выбрать наибольшее из отобранных ранее количеств.
- Добиться, чтобы в числах было одинаковое количество разрядов после запятой (добавить необходимое количество незначащих нулей).
- Сложить числа, не обращая внимания на запятую.
- В результирующем числе отделить запятой справа столько знаков, сколько было выбрано на шаге 2.
Вычитание
- Определить количество значащих цифр после запятой в обоих участвующих числах.
- Выбрать наибольшее из отобранных ранее количеств.
- Добиться, чтобы в числах было одинаковое количество разрядов после запятой (добавить необходимое количество незначащих нулей).
- Вычесть числа, не обращая внимания на запятую.
- В результирующем числе отделить запятой справа столько знаков, сколько было выбрано на шаге 2.
Умножение
- Определить количество значащих цифр после запятой в обоих аргументах.
- Просуммировать отобранные ранее количества.
- Перемножить числа, не обращая внимания на запятую.
- В результирующем числе отделить запятой справа столько знаков, сколько было выбрано на шаге 2.
Деление
- Добиться, чтобы в числах было одинаковое количество разрядов после запятой (добавить необходимое количество незначащих нулей).
- Не обращая внимания на запятую, увеличивать делимое (добавлять нули справа) пока не будет обеспечиваться необходимая точность (в случае, если процесс деления потенциально бесконечен), или пока не будет получен пример деления без остатка (смотри рисунок).
- Выполняем деление без учёта запятой (само деление идёт до целых, возможен остаток).
- В результирующем числе отделить запятой справа столько знаков, сколько было добавлено нулей на шаге 2.
Размышления о сказанном
Приведённые здесь алгоритмы, разумеется, не являются единственно возможными для использования человеком. Так, и в рамках школьного курса, алгоритмы сложения и вычитания не представляют собой ничего сложного: записываем числа одно под другим (соблюдая разряды), складываем или вычитаем, ставим разделитель в соответствующем месте.
С другой стороны, то же умножение можно быстро выполнить, формально перемножив числа без запятых и скорректировав результат.
Деление - самая сложная (из рассмотренных) процедура. На практике она сопряжена с большим количеством всяческих трюков и уловок. Например, делить 7 на 14 по представленному алгоритму излишне сложно: достаточно вспомнить, что 14=2*7, а значит 7 - это половинка от 14, таким образом, 7/14=0,5.
Рекомендую к прочтению главу "Счастливые числа" из книги [1].
Литература
- Вы, конечно, шутите, мистер Фейнман! / Ричард Фейнман; пер. с англ. С.Б. Ильина. - Москва: АСТ, 2014. - 477, [3] с. - (Великие ученые и их открытия).
Комментарии