Тема «Системы счисления» входит в школьную программу по информатике и начинает изучаться уже с 8 класса. Она включает в себя трудоёмкие вычислительные операции, на проверку которых вручную уходит много времени. Но до сих пор не рассматривалась тема длинной арифметики и перевода большой числовой последовательности в системах счисления. Эти идеи активно используются в криптографии, математике [Будкина], финансах, вычислении общеизвестных трансцендентных чисел с высокой точностью, высококачественном изображении фракталов. Программа, позволяющая производить вычисления и переводы над длинными числовыми последовательностями в системах счисления, может быть полезна для особого круга прикладных задач, когда обычные калькуляторы уже не смогут справляться с объёмом входных данных.
На данный момент существует несколько решений. Первое – длинная арифметика языков программирования Python, Java и других. Они позволяют быстро и эффективно вести подсчёты больших числовых последовательностей, но не поддерживают переводы в системы счисления, превышающие 36. Ещё одним решением является калькулятор командной строки GNU bc. Он позволяет использовать длинную арифметику с возможностью поразрядного вывода в произвольные системы счисления. Однако полученный в системе счисления большей 36 результат повторно использовать не получится: максимальная система счисления входных данных (ibase) не может превышать 36.
Основная цель данной статьи – создать решение, стремящееся совместить быстроту и эффективность длинной арифметики Python с работой в системах счисления больше тридцатишестиричной калькулятора GNU bc.
Главные задачи исследования: на примере данного приложения изучить возможности языка программирования Python; выявить практические сферы применения систем счисления; рассмотреть возможные трудности и нюансы создания приложения.
Для разработки был выбран высокоуровневый язык программирования Python, который позволит: быстро и качественно написать, объединить алгоритмы и элементы кода; создать графический интерфейс программы (в проекте использовалась python библиотека tkinter); собрать проект в исполняемый (exe) файл, готовый к отправке пользователям (при сборке использовалась программа PyInstaller); сохранится возможность добавления новых функций или замены существующих на аналоги, написанные на низкоуровневом языке (например, С++).
Основной экран приложения (Рисунок 1) должен содержать: поля ввода первого и второго числа; списки систем счисления первого, второго числа и результата; кнопки математических операций с введёнными числами (сложение, вычитание, умножение, деление), перевода первого числа, экран вывода результатов. Поля ввода/вывода могут считать последовательность любой длины. Также поддерживается перемещение вправо/влево по введённым данным.
Рисунок 1. Экран приложения.
Для организации работы приложения, упрощения дальнейших улучшений и поддержания программного кода была создана модульная архитектура ПО (Рисунок 2). Она включает 5 основных частей, реализующих математические операции (сложение, умножение, деление, разность и перевод первого числа). Каждый модуль базируется на трёх основных алгоритмах: перевод целой части числа, дробной части в десятичную систему счисления и обратно.
Математические операции осуществляться по одному типовому алгоритму. Введённое число преобразовывается в строковую переменную. По наличию точки определяется наличие дробной части. Строка разбивается на две части: целую и дробную (при наличии). Обе части переводятся в десятичную систему счисления. Определение представления текстовых символов (отличных от цифр) осуществляется с помощью ASCII (разность номера текущего символа в таблице и символа «0») для более приятного восприятия символьного результата. Это позволяет расширить системы счисления дальше тридцатишестиричной (в данной реализации предельная система счисления 93). После символов английского алфавита будут использованы соответствующие символы ASCII (используются лишь однобайтовые символы основной латиницы, начиная с символа «0» и заканчивая «~»). Первый диапазон символов – цифры ASCII (номера 48-57), второй – буквы латинского алфавита в верхнем регистре (65-90), третий – символы и знаки препинания (91-96), четвертый – буквы латиницы в нижнем регистре (97-122), пятый – оставшиеся однобайтовые символы (32-47, 58-64, 123-126). Разбиение ASCII на такие диапазоны и связь их порядковых номеров с основанием системы счисления обусловлена уже устоявшимися обозначениями. Аналогичные операции производятся и со вторым числом. Затем над целым и дробными частями осуществляются математические операции, обе части результата переводятся в нужную систему счисления и выводятся пользователю. Такой способ реализации основан на общепринятых правилах перевода в системах счисления (совпадает с «ручным» переводом), что позволяет проконтролировать основные этапы вычисления.
В дополнение основным реализованы 2 модуля, которые раскрывают историю систем счисления, правила математических операций (Информация) и знакомят пользователя с программой (Инструкция). Итоговая программа состоит из 12 модулей, 1016 строк программного кода, из которых 37 пустых и 30 - комментарии.
Рисунок 2. Архитектура работы приложения.
Рассмотрим предельные данные, с которыми может работать алгоритм. Так как ввод организован через текстовое поле, то программа может считать данные достаточно большого объёма. Единственным ограничением будет объём оперативной и постоянной памяти на компьютере. Алгоритм перевода работает лишь со строковыми представлениями, что позволяет обрабатывать данные без потерь точности (целочисленные типы используются лишь для работы с конкретными элементами строк, хранения их длинны). А для записи чисел в разрядах используются символы таблицы ASCII, чтобы рассматривать большие 36 системы счисления. Сложность вычислений возрастает с каждым новым символом, так как результат перевода равен , где j – количество чисел в исходном, i – разряд, a – цифра в i-ом разряде, b – система счисления результата.
При тестировании алгоритма перевода была написан код, который вводил данные в программу из файла input.txt и записывал результаты в файл output.txt, также фиксируя время работы программы. Для конкретности и определённости сравнения полученных результатов с эталоном все символы файла input.txt состоят из символов «Z» (соответствует числу 35) и переводятся из тридцатишестиричной системы счисления в десятичную. Результаты работы алгоритма стоит считать верными. Объём символов вывода входит в правильный диапазон, определенный количеством чисел в большей степени числа (N = [a * lg(b)] +1, где N – количество цифр, a – степень, b – возводимое в степень число). Проанализировав результат, можно сделать вывод - последние цифры верны. Время работы приемлемое для такого количества вычислительных операций.
Таблица 1. Результаты тестирования алгоритма.
| Число символов «Z»
в input.txt |
Время работы алгоритма с выводом результата, сек. | Кол-во символов в файле output.txt | Результат аналитической и ручной проверки. |
| 1 | 0,109 – 0,114 | 2 | Совпадает с результатом, полученным вручную. |
| 10 | 0,108 – 0,113 | 16 | |
| 100 | 0,113 – 0,119 | 156 | |
| 1000 | 0,116 – 0,121 | 15557 | Кол-во символов результата входит в верный диапазон, последние цифры совпадают с полученными аналитически. |
| 10000 | 1,1 – 1,2 | 15564 | |
| 100000 | 356 | 155631 | |
| 200000 | 2061,9 | 311261 | |
| 300000 | 5819,1 | 466891 |
Данная программа может использоваться как для проверки небольших вычислений, сделанных вручную, так и для длинной арифметики с высокой точностью в различных системах счисления (включая привычную десятичную). Возможно дальнейшее добавление дополнительных функций, реализующих другие математические операции (возведение в степень, вычисление факториала числа и другие), поддержание работы приложения, его оптимизация (например, перевод алгоритма работы на низкоуровневый язык) и увеличение максимальной поддерживаемой системы счисления, путём использования диапазонов символов Unicode.
Системы счисления активно использовались на этапах зарождения ЭВМ, телеграфии (кодирование букв и чисел последовательностью нулей и единиц), создания штрих-кодов [Гашков]. Но в наши дни одна из главных сфер применения данного приложения – кодирование (сжатие) числовой последовательности (например, цепного кода). «…Любую упорядоченную последовательность можно представить в виде ряда упорядоченных множеств и для любого упорядоченного множества можно создать свою позиционную систему счисления…» [Лебедева : 21] Рационально использовать данный алгоритм и для отправки данных, так как при передаче данных используются другие системы счисления (например, кодирование base64), когда есть дополнительные ограничения на то, какие значения могут иметь передаваемые байты (например, это должны быть только печатные символы ASCII). Предположим, есть последовательность из 15565 десятичных чисел в текстовом формате (файл output.txt в результате перевода 10000 «Z»). Результат перевода данной последовательности из десятичной в восьмидесятеричную систему счисления составил 8179 символов, а с помощью base64 - 20755 символов. Гораздо больше исходного файла, так как три восьмерки битов сводятся к четырем шестеркам в виде символов ASCII. Но данный подход всегда менее эффективен, чем использование двоичного формата.
Список литературы
Будкина И. М. Научному прогрессу - творчество молодых: материалы XV международной молодежной научной конференции по естественнонаучным и техническим дисциплинам (Йошкар-Ола, 17-18 апреля 2020 года): в 2 ч. / редкол.: Д. В. Иванов [и др.]. / И. М. Будкина, А. М. Кораблев // Системы счисления. Йошкар-Ола: Поволжский государственный технологический университет, 2020. Ч. 1. С. 14—16.
Гашков С. Б. Системы счисления и их применение. Москва : МЦНМО, 2004. 52 с.
Лебедева А. В. Система счисления рядов упорядоченных множеств // Математика и математическое моделирование: сборник материалов XII всероссийской молодежной научно-инновационной школы. Саратов: Интерконтакт, 2018. С. 21—22.