Оптимальная система счисления
Давно хотел определить с точки зрения банальной эрудиции и формальной математики, какая из позиционных систем счисления является наиболее удобной, в некотором смысле - эргономичной. Потому что - как многим известно - привычная современной цивилизации десятичная система выбрана не из соображений оптимальности, а прямо вытекает из анатомии человека. Было бы не 10 пальцев на руках - укоренилось бы другое основание. Когда люди считали окружающие предметы буквально по пальцам, десятичная система была разумным выбором, да и то: почему именно пальцы-"штуки"? Кому-то было удобнее по фалангам 4 пальцев одной руки, указывая на них большим - так получила некоторую популярность 12-ричная система. Но дальше - просто сила привычки, QWERTY-эффект в чистом виде: используем не потому, что удобнее всего, а потому, что так сложилось исторически, в силу традиции.
___
Как математически определить удобство использования той или иной системы счисления? Во-первых можно рассмотреть, как в них записываются числа. Чем больше основание n, тем меньше разрядов требует одно и то же число, но при этом растет "алфавит" - количество цифр, что влечет за собой и размеры таблиц сложения и умножения, и все такое прочее. Результирующим будет произведение-комбинация этих факторов: lg(n) * (1/n). Логарифм (все равно какой, взял десятичный) основания системы отражает компактность записи чисел, обратное число - компактность алфавита.
Если проще, можно рассмотреть пример: у нас есть 60 дощечек, на которых можно написать повторяющиеся цифры - как нужно поступить, какую позиционную систему выбрать, чтобы при помощи этого набора выразить максимальное количество чисел? Можно сделать по 30 нулей и единиц, тогда в двоичной системе можно будет записать 2^30 - чуть более миллиарда различных чисел. Если сделать по 20 штук "0", "1" и "2" - то 3^20 - почти 3,5 миллиарда чисел в троичной системе. 4 цифры на 15 разрядов: 4^15=2^30, максимум функции пройден, дальше на убыль: 5^12 - менее четверти миллиарда, 6^10 - 60 миллионов, наконец 10^6 (привычная нам десятичная система) - миллион, совсем смех. 12^5 - вчетверо меньше... А можно просто 60 разных цифр и один разряд, как вавилоняне - вот и будут лишь числа от 0 до 59.
Так вот, эти выкладки - давно уже не секрет, кто их только не делал. В непрерывном случае максимум приходится на число e=2,718..., так что основание 3 выглядит лучше всех, 2 и 4 - одинаково чуть похуже: http://phg.su/basis2/X51.HTM - наглядно.
___
Но этого явно мало. При таком подходе учтено удобство записи чисел, но есть же еще и вычисления, операции над ними. Частично это уже учтено (см. выше фразу про таблицы сложения-умножения). И здесь приходится к месту аргумент, который - если кто в курсе - был основным доводом у сторонников двенадцатеричной системы: 12 делится нацело на 1, 2, 3, 4, 6 и собственно 12 против 1, 2, 5 и 10 у десятки. Это еще Перельман описывал в "Занимательной арифметике". И действительно, чем больше круглых чисел в произведениях и чем меньше периодических дробей в частных - очевидно, тем удобнее и быстрее подсчеты. Таким образом, домножаем нашу комбинацию двух факторов на третий - количество делителей числа d(n).
Итоговая формула: коэффициент эргомичности системы счисления q(n) = lg(n) / n * d(n) * 2,5 - домножил для приведения коэффициента десятичной системы к единице. Мы вправе это делать, поскольку основание логарифма все равно взято произвольно, у абсолютных значений q(n) нет смыслового наполнения. Ниже - таблица 25 лидеров:
Итак, "дозеналисты" были правы, у основания 12 действительно отличная репутация! А привычная нам десятка занимает седьмую позицию - достойную, но существенно уступающую. Если отойти в бытовую сферу, то главный недочет десятки - то, что она не делится на 3, а между тем на 3 делить приходится крайне часто. Ну и чтобы четвертые доли содержали лишь один знак после запятой вместо двух - тоже хороший бонус. Вкупе с сокращением длины больших чисел на 8% это оправдывает заучивание чуть большей таблицы умножения.
А с учетом огромной роли двоичной системы и бинарной логики в нашу компьютерную эпоху (тернарную пытались одно время привить, но не зашло) следует обратить внимание на основания 4, 8, 16. Переводить из них в двоичную - вообще плевое дело. Кстати, у 4 и 8, а также 3 и 9 коэффициенты равны, это не издержки округления.
Само собой, прикидка крайне грубая и многих вещей не учитывает. Но тут, как говорится, выделяйте гранты на дальнейшие исследования.
Тема поста интересна в первую очередь френдам
aaamibor, doncunita, lrlay777, sly2m, spamsink, vmenshov и другим.
ПРОДОЛЖЕНИЕ ПОСТА С УТОЧНЕНИЕМ ФОРМУЛЫ: https://sevabashirov.livejournal.com/270269.html
___
Как математически определить удобство использования той или иной системы счисления? Во-первых можно рассмотреть, как в них записываются числа. Чем больше основание n, тем меньше разрядов требует одно и то же число, но при этом растет "алфавит" - количество цифр, что влечет за собой и размеры таблиц сложения и умножения, и все такое прочее. Результирующим будет произведение-комбинация этих факторов: lg(n) * (1/n). Логарифм (все равно какой, взял десятичный) основания системы отражает компактность записи чисел, обратное число - компактность алфавита.
Если проще, можно рассмотреть пример: у нас есть 60 дощечек, на которых можно написать повторяющиеся цифры - как нужно поступить, какую позиционную систему выбрать, чтобы при помощи этого набора выразить максимальное количество чисел? Можно сделать по 30 нулей и единиц, тогда в двоичной системе можно будет записать 2^30 - чуть более миллиарда различных чисел. Если сделать по 20 штук "0", "1" и "2" - то 3^20 - почти 3,5 миллиарда чисел в троичной системе. 4 цифры на 15 разрядов: 4^15=2^30, максимум функции пройден, дальше на убыль: 5^12 - менее четверти миллиарда, 6^10 - 60 миллионов, наконец 10^6 (привычная нам десятичная система) - миллион, совсем смех. 12^5 - вчетверо меньше... А можно просто 60 разных цифр и один разряд, как вавилоняне - вот и будут лишь числа от 0 до 59.
Так вот, эти выкладки - давно уже не секрет, кто их только не делал. В непрерывном случае максимум приходится на число e=2,718..., так что основание 3 выглядит лучше всех, 2 и 4 - одинаково чуть похуже: http://phg.su/basis2/X51.HTM - наглядно.
___
Но этого явно мало. При таком подходе учтено удобство записи чисел, но есть же еще и вычисления, операции над ними. Частично это уже учтено (см. выше фразу про таблицы сложения-умножения). И здесь приходится к месту аргумент, который - если кто в курсе - был основным доводом у сторонников двенадцатеричной системы: 12 делится нацело на 1, 2, 3, 4, 6 и собственно 12 против 1, 2, 5 и 10 у десятки. Это еще Перельман описывал в "Занимательной арифметике". И действительно, чем больше круглых чисел в произведениях и чем меньше периодических дробей в частных - очевидно, тем удобнее и быстрее подсчеты. Таким образом, домножаем нашу комбинацию двух факторов на третий - количество делителей числа d(n).
Итоговая формула: коэффициент эргомичности системы счисления q(n) = lg(n) / n * d(n) * 2,5 - домножил для приведения коэффициента десятичной системы к единице. Мы вправе это делать, поскольку основание логарифма все равно взято произвольно, у абсолютных значений q(n) нет смыслового наполнения. Ниже - таблица 25 лидеров:
| n | lg(n) | d(n) | q(n) |
| 12 | 1,079 | 6 | 1,349 |
| 6 | 0,778 | 4 | 1,297 |
| 24 | 1,380 | 8 | 1,150 |
| 4 | 0,602 | 3 | 1,129 |
| 8 | 0,903 | 4 | 1,129 |
| 18 | 1,255 | 6 | 1,046 |
| 10 | 1,000 | 4 | 1,000 |
| 30 | 1,477 | 8 | 0,985 |
| 20 | 1,301 | 6 | 0,976 |
| 36 | 1,556 | 9 | 0,973 |
| 16 | 1,204 | 5 | 0,941 |
| 60 | 1,778 | 12 | 0,889 |
| 48 | 1,681 | 10 | 0,876 |
| 14 | 1,146 | 4 | 0,819 |
| 40 | 1,602 | 8 | 0,801 |
| 3 | 0,477 | 2 | 0,795 |
| 9 | 0,954 | 3 | 0,795 |
| 15 | 1,176 | 4 | 0,784 |
| 28 | 1,447 | 6 | 0,775 |
| 72 | 1,857 | 12 | 0,774 |
| 42 | 1,623 | 8 | 0,773 |
| 2 | 0,301 | 2 | 0,753 |
| 32 | 1,505 | 6 | 0,706 |
| 5 | 0,699 | 2 | 0,699 |
| 120 | 2,079 | 16 | 0,693 |
Итак, "дозеналисты" были правы, у основания 12 действительно отличная репутация! А привычная нам десятка занимает седьмую позицию - достойную, но существенно уступающую. Если отойти в бытовую сферу, то главный недочет десятки - то, что она не делится на 3, а между тем на 3 делить приходится крайне часто. Ну и чтобы четвертые доли содержали лишь один знак после запятой вместо двух - тоже хороший бонус. Вкупе с сокращением длины больших чисел на 8% это оправдывает заучивание чуть большей таблицы умножения.
А с учетом огромной роли двоичной системы и бинарной логики в нашу компьютерную эпоху (тернарную пытались одно время привить, но не зашло) следует обратить внимание на основания 4, 8, 16. Переводить из них в двоичную - вообще плевое дело. Кстати, у 4 и 8, а также 3 и 9 коэффициенты равны, это не издержки округления.
Само собой, прикидка крайне грубая и многих вещей не учитывает. Но тут, как говорится, выделяйте гранты на дальнейшие исследования.
Тема поста интересна в первую очередь френдам
aaamibor, doncunita, lrlay777, sly2m, spamsink, vmenshov и другим.ПРОДОЛЖЕНИЕ ПОСТА С УТОЧНЕНИЕМ ФОРМУЛЫ: https://sevabashirov.livejournal.com/270269.html