Подсчёт тритов (и других -итов)
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 алгоритма. А, казалось, простая задачка...
no subject
Date: 2023-03-25 08:32 pm (UTC)А, целый файл превратить в триты? Да, логично.
no subject
Date: 2023-03-26 04:58 pm (UTC)Так что логично-то? Я вот пытаюсь второй день придумать алгоритм o(1) по памяти, и не могу.
no subject
Date: 2023-03-26 05:59 pm (UTC)Да, не похоже, чтоб линейно было. Там умножение на степень двойки Ну типа берем k=log2(N), с округлением вверх; и нужно в процессе умножать большое число на N-2^k... что-то такое. Поэкспериментировать бы надо, конечно.
no subject
Date: 2023-03-26 06:53 pm (UTC)В целом, мы в одном месте на 2^pos умножаем, в другом на 3^pos делим, то есть итоговое число (для очередого ита) вполне себе маленькое. Но как делать "перенос" остатка информации от предыдущего деления в новое - я не понимаю.
no subject
Date: 2023-03-26 09:32 pm (UTC)Ну да; дело в переносе, и, похоже, там нелинейно. Хотя... наверно, можно найти что-то быстрее, чем квадрат.
no subject
Date: 2023-03-25 10:28 pm (UTC)Кстати, лично я бы рассматривал файл не как целое число, а как fixed point value из [0;1).
no subject
Date: 2023-03-26 05:01 pm (UTC)А что это улучшит, кроме усложнения процесса?
no subject
Date: 2023-03-26 09:42 pm (UTC)Чтобы переводить в другое основание дробное число <1, нужно каждый раз умножать его на новое основание, выписывать и отбрасывать целую часть. При этом результаты получаются "с начала" - начиная со старшего знака.
Второе несколько более похоже на стрим, чем первое. Плюс умножение в столбик несколько проще, чем деление в столбик. В первом случае тоже можно приловчиться получать вначале старшие знаки, но это немного более трудозатратно.
no subject
Date: 2023-03-27 03:30 pm (UTC)no subject
Date: 2023-04-01 09:58 am (UTC)То есть ты предлагаешь считать, что входящий поток битов - это знаки после запятой?
0.1 - это 0.5 в десятичной системе. 0.1 - это 0.(3) в десятичной.
Что-то у меня плохие предчувствия...
no subject
Date: 2023-04-01 01:06 pm (UTC)no subject
Date: 2023-04-01 03:38 pm (UTC)Выбрать любую из них можно в том случае, если мы заранее знаем, что хотели представить именно 0.13, до одного знака. А исходная постановка, кажется, предполагала отсутствие необходимости знания выходной длины.
Алгоритм, знающий входную последовательность
4, входное основание 10 и выходное основание 3, без дополнительной информации, сгенерирует на выход бесконечную последовательность10121012….no subject
Date: 2023-04-01 04:40 pm (UTC)no subject
Date: 2023-04-01 04:57 pm (UTC)Можно сказать, что преобразование обратимо с точностью до незначащих ведущих нулей. А в случае дроби придётся либо задавать требуемую точность представления на входе, либо расширять алфавит скобками и учить алгоритм находить период дроби.
no subject
Date: 2023-04-01 05:46 pm (UTC)Допустим, мы знаем число битов на входе. Это немного меняет задачу, но в рамках конкретной задачи "посчитать число каждого типа ита в файле" работает, т.к. мы знаем размер файла.
Хорошо, пусть будет поток данных для которого заведомо известен размер и он больше размера оперативной памяти в разы или на порядки.
no subject
Date: 2023-04-01 06:29 pm (UTC)no subject
Date: 2023-04-01 07:55 pm (UTC)Ну, я на самом деле хотел считать частоту символов, то есть "вывода" нет, есть только статистика по распределению.
Если иметь доступ к уже напечатанному, то это читерство. С учётом, что потенциальный объём проходящих данных - терабайты, "доступ к напечатанному" в терабайты размером... Нет.
no subject
Date: 2023-04-01 09:48 pm (UTC)Читерство, конечно, но все равно любопытно, сработает такой чит или нет.
no subject
Date: 2023-04-01 05:57 pm (UTC)no subject
Date: 2023-04-01 06:12 pm (UTC)Гм. В том смысле, что 1, 10 и 100 — это разные входные строки, задающие число 0.110 с точностью ±0.05, ±0.005 и ±0.0005 соответственно? Да, такая постановка непротиворечива.
no subject
Date: 2023-03-26 09:33 pm (UTC)Об этом и речь.