Фибоначчи в народном хозяйстве
Sep. 18th, 2010 12:57 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
thedeemonВсякий знает, что вычисление чисел Фибоначчи - важнейшая задача программирования, поэтому именно с нее нередко начинают обучение. Некоторые языки программирования, похоже, были созданы специально для решения этой задачи (prooflink). Однако не все еще нашли применение этим чудесным числам в быту.
Понадобилось мне тут недавно уметь компактно представить набор целых чисел: при проверке на наличие новых версий а также при деинсталляции программа передает на сервер номер своей версии, а заодно кое-какую статистику, вроде числа запусков, количества дней с момента установки и т.п. Передавать нужно GET'ом, ибо при деинсталляции это делает не сама программа, а скрипт установщика, к тому же хочется сразу иметь эти данные в логах апача. Чисел получилось много, в явном виде запрос получился бы сильно длинным и некрасивым. Решил применить какое-нибудь простое сжатие.
Числа все неотрицательные, сверху не ограниченные, и вероятность встречи числа быстро уменьшается с ростом самого числа. Для таких данных есть семейство кодов переменной длины, называемое универсальными кодами. Большинство из них сначала кодируют некоторым образом число битов (например, унарно), а затем сами биты кодируемого числа. Но длина таких кодов растет довольно быстро. Зато есть более интересный и для нужных мне значений более эффективный способ представления - коды Фибоначчи. Они основаны на теореме одного зубного врача из бельгийской армии, которая говорит, что всякое натуральное число можно уникальным образом представить в виде суммы чисел Фибоначчи, причем в такой сумме никогда не будет двух последовательных членов ряда. Ряд начинается так: 1, 2, 3, 5, 8, 13, 21... Тогда 6 = 1+5, 15 = 2+13, 31 = 2+8+21. Чтобы закодировать число последовательностью битов, достаточно пройтись по ряду Фибоначчи до требуемого числа и проставить единицы напротив входящих в сумму членов и нули напротив невходящих. Поскольку по построению у нас не может быть подряд двух единиц, этот факт используется для маркировки конца числа: после последней единицы ставим еще одну и код готов, длину числа хранить нигде не надо. Примеры:
В итоге у меня требуемый набор чисел превращается в такую битовую последовательность, которая затем кодируется по пять цифрами и буквами в Base32. Получается обычно по 12-15 символов на 24 исходных инта.
А вот и сам автор теоремы - полковник Эдуард Цекендорф:
Понадобилось мне тут недавно уметь компактно представить набор целых чисел: при проверке на наличие новых версий а также при деинсталляции программа передает на сервер номер своей версии, а заодно кое-какую статистику, вроде числа запусков, количества дней с момента установки и т.п. Передавать нужно GET'ом, ибо при деинсталляции это делает не сама программа, а скрипт установщика, к тому же хочется сразу иметь эти данные в логах апача. Чисел получилось много, в явном виде запрос получился бы сильно длинным и некрасивым. Решил применить какое-нибудь простое сжатие.
Числа все неотрицательные, сверху не ограниченные, и вероятность встречи числа быстро уменьшается с ростом самого числа. Для таких данных есть семейство кодов переменной длины, называемое универсальными кодами. Большинство из них сначала кодируют некоторым образом число битов (например, унарно), а затем сами биты кодируемого числа. Но длина таких кодов растет довольно быстро. Зато есть более интересный и для нужных мне значений более эффективный способ представления - коды Фибоначчи. Они основаны на теореме одного зубного врача из бельгийской армии, которая говорит, что всякое натуральное число можно уникальным образом представить в виде суммы чисел Фибоначчи, причем в такой сумме никогда не будет двух последовательных членов ряда. Ряд начинается так: 1, 2, 3, 5, 8, 13, 21... Тогда 6 = 1+5, 15 = 2+13, 31 = 2+8+21. Чтобы закодировать число последовательностью битов, достаточно пройтись по ряду Фибоначчи до требуемого числа и проставить единицы напротив входящих в сумму членов и нули напротив невходящих. Поскольку по построению у нас не может быть подряд двух единиц, этот факт используется для маркировки конца числа: после последней единицы ставим еще одну и код готов, длину числа хранить нигде не надо. Примеры:
Fib: 1 2 3 5 8 13 21 34 | Code 1: * | 11 2: * | 011 3: * | 0011 4: * * | 1011 10: * * | 010011 16: * * | 0010011 42: * * | 000010011
В итоге у меня требуемый набор чисел превращается в такую битовую последовательность, которая затем кодируется по пять цифрами и буквами в Base32. Получается обычно по 12-15 символов на 24 исходных инта.
А вот и сам автор теоремы - полковник Эдуард Цекендорф:
