Подсчёт тритов (и других -итов)
Mar. 25th, 2023 09:59 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoТерминология:
Бит = base2
Трит = base3
N-ит = baseN
Я сам себе придумал простую задачку: посчитать распределение разных цифр файле в заданной системе счисления. На входе, по понятным причинам, всегда файлы двоичные. На выходе распределение цифр N-ричной системы так, как если бы тот же файл был записан в N-ричной системе.
В начале я думал, что это тривиально. Потом залез в математику и нашёл формулу log_a(b) = log_c(b)/log_c(a)
log_a(b) и log_c(b) - это число итов в разных системах счисления.
И из этой формулы очевидно вытекает, что кратно совпадать иты могут только если log_c(a) (логарифм по основанию одной системы счисления и основания другой счисления) - это рациональное число. Если этот логарифм иррациональный, то мы никогда не сможем найти такое количество итов одной системы, чтобы точно выразить сколько итов другой системы.
Например, в base4 можно легко представить base2 - мы просто кодируем два бита одним числом в base4. А вот, например, для base3 и base2 не существует такого конечного числа битов, которые бы можно было превратить в триты точно. Точно означает, что любое число с указанным числом тритов превратится в число с указанным числом битов и наоборот. Всегда будут "лишние значения".
Если не понятно, вот простой пример:
3^2=9, максимальное представимое число в два трита - это 8. Чтобы закодировать 8 нам надо 4 бита. Но четыре бита позволяют закодировать число 15, а число 15 требует три трита. Три трита позволяют закодировать число 26, а для этого нам уже нужно 5 бит, а это число 32, которое требует...
Ну вы поняли. До нахождения формулы я почему-то был уверен, что существует "наименьшее общее кратное" для двух разных ритов. Оказалось, что нет (оно называется не "наименьше общее кратное", но я пытаюсь провести аналогию).
Хорошо, мы теперь знаем, что для общего случая мы не можем для двух итов искать "наибольшее общее число".
Как же конвертировать? Мы говорим про поток итов, у нас нет "порядка байт".
... А как не конвертировать? Что такое поток битов? Каждый следующий бит добавляется к "сумме" с новой степенью двойки. То есть, имея счётчик битов pos, мы можем делать sum+=2^pos * value.
Для тройки эквивалентная формула - это sum += 3^pos * value. Поскольку мы работаем с сложением, мы можем уменьшать сумму по мере печати и не перживать по этому поводу:
sum = printed_value + leftover_value.
Для печати нового бита мы должны sum // 2^pos (где // - целочисленное деление).
Для печати нового трита мы должны sum // 3^pos.
Выглядит как алгоритм, но у него есть фатальный недостаток n^pos - число размером с читаемый нами файл, то есть никакого стриминга не получается. При этом мы из sum вычитаем всё большие цифры, то есть sum с одной стороны растёт, с другой стороны всё время ограничена n^(pos+1).
И что-то у меня пока не получается придумать memory bound алгоритма. А, казалось, простая задачка...
Бит = base2
Трит = base3
N-ит = baseN
Я сам себе придумал простую задачку: посчитать распределение разных цифр файле в заданной системе счисления. На входе, по понятным причинам, всегда файлы двоичные. На выходе распределение цифр N-ричной системы так, как если бы тот же файл был записан в N-ричной системе.
В начале я думал, что это тривиально. Потом залез в математику и нашёл формулу log_a(b) = log_c(b)/log_c(a)
log_a(b) и log_c(b) - это число итов в разных системах счисления.
И из этой формулы очевидно вытекает, что кратно совпадать иты могут только если log_c(a) (логарифм по основанию одной системы счисления и основания другой счисления) - это рациональное число. Если этот логарифм иррациональный, то мы никогда не сможем найти такое количество итов одной системы, чтобы точно выразить сколько итов другой системы.
Например, в base4 можно легко представить base2 - мы просто кодируем два бита одним числом в base4. А вот, например, для base3 и base2 не существует такого конечного числа битов, которые бы можно было превратить в триты точно. Точно означает, что любое число с указанным числом тритов превратится в число с указанным числом битов и наоборот. Всегда будут "лишние значения".
Если не понятно, вот простой пример:
3^2=9, максимальное представимое число в два трита - это 8. Чтобы закодировать 8 нам надо 4 бита. Но четыре бита позволяют закодировать число 15, а число 15 требует три трита. Три трита позволяют закодировать число 26, а для этого нам уже нужно 5 бит, а это число 32, которое требует...
Ну вы поняли. До нахождения формулы я почему-то был уверен, что существует "наименьшее общее кратное" для двух разных ритов. Оказалось, что нет (оно называется не "наименьше общее кратное", но я пытаюсь провести аналогию).
Хорошо, мы теперь знаем, что для общего случая мы не можем для двух итов искать "наибольшее общее число".
Как же конвертировать? Мы говорим про поток итов, у нас нет "порядка байт".
... А как не конвертировать? Что такое поток битов? Каждый следующий бит добавляется к "сумме" с новой степенью двойки. То есть, имея счётчик битов pos, мы можем делать sum+=2^pos * value.
Для тройки эквивалентная формула - это sum += 3^pos * value. Поскольку мы работаем с сложением, мы можем уменьшать сумму по мере печати и не перживать по этому поводу:
sum = printed_value + leftover_value.
Для печати нового бита мы должны sum // 2^pos (где // - целочисленное деление).
Для печати нового трита мы должны sum // 3^pos.
Выглядит как алгоритм, но у него есть фатальный недостаток n^pos - число размером с читаемый нами файл, то есть никакого стриминга не получается. При этом мы из sum вычитаем всё большие цифры, то есть sum с одной стороны растёт, с другой стороны всё время ограничена n^(pos+1).
И что-то у меня пока не получается придумать memory bound алгоритма. А, казалось, простая задачка...