Системы счисления произвольного основания
Преобразование чисел между системами счисления: встроенные средства и обобщённый алгоритм с обратным преобразованием
Введение
Представление числа в позиционной системе счисления с основанием m является одной из базовых операций дискретной математики и вычислительной техники. Она лежит в основе кодирования данных, криптографии, сжатия информации и работы с числами произвольной точности. Стандартные библиотеки языков программирования, как правило, предоставляют такую операцию лишь для узкого диапазона оснований (обычно 2–36), поскольку для оснований больше 36 отсутствует общепринятый алфавит цифр.
Данная работа систематизирует три способа решения этой задачи, показывает, что при переходе к «блочному» представлению, когда цифрой считается целое число, а не символ, ограничение на величину основания снимается, а результат приобретает форму, удобную для машинной обработки. Дополнительно рассматривается обратная задача: восстановление исходного числа из вектора цифр, что позволяет проверить корректность прямого алгоритма.
Встроенные средства MATLAB
using MATLAB
dec2base в допустимом диапазоне
Встроенная функция Matlab dec2base возвращает символьное представление числа: для основания 36 цифрами служат 0–9 и A–Z, где Z соответствует значению 35. Параметр digits задаёт минимальную длину строки (дополнение ведущими нулями).
mat"""
num = 35;
base = 36;
digits = 1;
dec2base(num, base, digits)
"""
Ограничение dec2base
Попытка использовать основание 37 приводит к ошибке.
mat"""
num = 38;
base = 37;
digits = 2;
dec2base(num, base, digits)
"""
Функцияdec2base рассчитана только на основания 2–36, поскольку её результат является строкой строка, а для больших оснований не существует стандартного набора символов-цифр.
Встроенные средства Julia
Двоичное представление
Функция string(n; base) возвращает строковое представление числа в заданном основании. Для степени двойки результат ожидаемо содержит одну единицу и три нуля.
число = 8
основание = 2
string(число, base = основание)
Шестнадцатеричное представление
Для основания 16 Julia использует строчные латинские буквы a–f. Результат "ff" соответствует десятичному 255.
число = 255
основание = 16
string(число, base = основание)
Основание 62
Здесь проявляется важное соглашение Julia об алфавите: цифры 0–9, затем A–Z (значения 10–35), затем a–z (значения 36–61). Число , что и даёт "Az". Это тот же алфавит, что используется в распространённых схемах Base62-кодирования.
число = 681
основание = 62
string(число, base = основание)
Ограничение string
Встроенная функция Julia допускает основания лишь до , по той же причине, что и MATLAB: результат строковый, а алфавит ограничен.
число = 61
основание = 256
string(число, base = основание)
Обобщённый алгоритм
Создадим пользовательскую функцию dec2any для перевода чисел из десятичной системы счисления в любую другую.
function dec2any(a, m, c)
n = zeros(typeof(m), c)
k = 1
n[k] = mod(a, m)
r = div(a - n[1], m)
while r != 0
k += 1
n[k] = mod(r, m)
r = div(r - n[k], m)
end
return reverse(n)
end
Функция реализует классический алгоритм перевода в позиционную систему счисления:
-
Младшая цифра получается как остаток
mod(a, m). -
Частное
div(a - n[1], m)используется для следующего шага. -
Процесс повторяется, пока частное не обратится в ноль.
-
Вектор цифр разворачивается, чтобы старшие разряды шли первыми.
-
Параметр
cзадаёт минимальную длину результата (дополнение ведущими нулями).
Основное отличие от встроенных функций заключается в том, что цифра это целое число, а не символ. Поэтому:
-
основание
mможет быть сколь угодно большим; -
число
aможет быть произвольной длины; -
тип вектора результата согласован с типом
mблагодаряzeros(typeof(m), c).
Проверка на основании 16
число = 255
основание = 16
цифр = 2
dec2any(число, основание, цифр)
Результат [15, 15] эквивалентен "ff": две «цифры» со значением 15. Это подтверждает корректность алгоритма.
Основание 256: за пределами встроенных функций
число = 16777182
основание = 256
цифр = 3
число_256 = dec2any(число, основание, цифр)
Число . Результат [255, 255, 222] это три байта в порядке от старшего к младшему. Именно такое представление естественно для работы с двоичными данными, где "цифра" это байт (0–255). Встроенные dec2base и string такое основание не поддерживают. Результат сохраним в переменную число_256 для последующей проверки обратного преобразования.
Обратное преобразование
Определим функцию преобразования чисел из любой системы счисления в десятичную.
any2dec(n, m) = foldl((acc, d) -> acc * m + d, n; init = big(0))
Функция восстанавливает исходное число из вектора цифр n и основания m по схеме Горнера:
Схема Горнера требует умножений и сложений и является наиболее эффективным способом обратного преобразования. Инициализация big(0) гарантирует, что результат будет типа BigInt и не переполнится при больших числах, даже если вектор состоит из обычных Int.
any2dec(число_256, основание)
Восстановленное значение совпадает с исходным . Это подтверждает, что пара функций dec2any/any2dec образует корректное взаимно обратное преобразование: dec2any(any2dec(a, m, c), m) == a для любых допустимых a, m, c (при условии, что число помещается в c цифр).
Заключение
Данная работа наглядно демонстрирует фундаментальное различие между двумя формами представления числа в системе счисления:
-
символьная форма (строки
"Z","ff","Az") удобна для человека, но требует фиксированного алфавита и потому ограничена основаниями 2–36 (MATLAB) или 2–62 (Julia); -
блочная форма (вектор целых чисел) свободна от ограничения на основание и позволяет работать с числами произвольной длины.
Пользовательская функция dec2any реализует вторую форму. Её результат это вектор, каждый элемент которого является "цифрой" в десятичном представлении, а весь вектор представляет исходное число в системе счисления с основанием m. Обратная функция any2dec, построенная по схеме Горнера, восстанавливает число из вектора, замыкая цикл преобразований и позволяя проверять корректность прямого алгоритма. Вместе они образуют полноценный инструмент для работы с системами счисления произвольного основания и большими числами.