пятница, 29 ноября 2013 г.

Доказательство число e - оптимальное основание для позиционной системы счисления

Когда-то давно доказывал на экзамене, сегодня увидел твит:

Долгое время считалось, что бит неделим. Но советские ученые...
— Типичный программист (@tproger) 29 ноября 2013

Заморочился. На wiki тут его нет. В гугле - нет! Думаю кому-нибудь будет полезно.

Пусть p - основание системы счисления (далее с.с.), т.е. кол-во значков-цифр для записи представление числа (например, для 10-ной с.с. это наши любимые 0,1,2,3,4,5,6,7,8,9).
Второй момент, пусть с.с. будет позиционной, т.е. позиция значка при представлении влияет на величину числа (опять же пример для 10-ной с.с. это то, что 110 больше 101, если младший разряд справа). n - количество разрядов для представления числа, т.е. количество мест, куда можно записать значок-цифру (для 10-ной с.с. для числа 10, кол-во разрядов равно двум, ваш кэп).
Тогда первая посылка: количество чисел, которые можно записать с помощью n-разрядов с помощью p-значков-цифр равно p^n (основание степени возведённое в степерь кол-ва разрядов).
Теперь определимся с оптимальностью. Пусть оптимальная с.с. будет такая, чтобы её основание (p) было такое, чтобы число можно было записать с помощью минимального количества разрядов. Это есть функция от количества разрядов n, т.е. отношение количества возможных чисел к количеству используемых разрядов:
f(n) = (p^n)/n;
Тогда задача оптимальности сводиться к задачи нахождения экстремума(минимума) этой функции по переменной n:
f(n) -> extr(min).
Для этого продифференцируем её по n:
df(n)/dn = ((p^n)*ln(p) - p^n)/(n^2);
приравняем к нулю:
((p^n)*ln(p) - p^n)/(n^2) = 0;
умножим обе части на n^2, ведь количество разрядов не может быть равным нулю:
(p^n)*ln(p) - p^n = 0;
вынесем и сократим на p^n:
ln(p) - 1 = 0 или ln(p) = 1 или ln(p) = ln(e) или p = e.
Получается что при p, равным числу Эйлера, функция проходит через точку-кандидат в экстремумы, исследуем её:
При переходе через неё, происходит смена знака с минуса на плюс, т.е. это точка минимума функции, что и требовалось доказать. Поэтому с.с. с основанием равным числу e, является самой оптимальной. Однако, так как использование такой с.с. из-за иррациональности основания проблематично, число e округляют до целого.
Условно говоря, весь мир отбросил дробь и получил систему с основанием 2, а советские инженеры округлили до 3 и мучились с ней, т.к. теория не очень хорошо легла на практику.



1 комментарий:

  1. 1. Производная вычислена неверно
    2. Вы пытаетесь найти минимум функции f(n), то есть такое n0 при котором функция имеет минимум, а в итоге находите p, которая при таком подходе вообще не является переменной
    3. я уже не говорю о подходе к задаче, который в корне неверный

    ОтветитьУдалить