Оптимальная система счисления
Давно хотел определить с точки зрения банальной эрудиции и формальной математики, какая из позиционных систем счисления является наиболее удобной, в некотором смысле - эргономичной. Потому что - как многим известно - привычная современной цивилизации десятичная система выбрана не из соображений оптимальности, а прямо вытекает из анатомии человека. Было бы не 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 лидеров:
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
___
Как математически определить удобство использования той или иной системы счисления? Во-первых можно рассмотреть, как в них записываются числа. Чем больше основание 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