Wednesday, October 28, 2009

Длина числа

Примечание: Если вы не видите математические формулы ниже см. сюда.

Пару дней назад меня на работе коллега, уроженец Израиля, сабра, спросил, как бы я нашёл "длину числа" $n$ ($0\ltn\in\mathbb{N}$) написанную в десятеричной системе исчисления? Например, "длина числа" 578 равняется трём, так как нужно три цифры чтобы записать такое число. Подумав секунд пять я взял ручку и и бумагу и начала писать ответь. Сначала я вспомнил, что это $\mathsf{\mathrm{O(log n)}}$, но в данном случае, этого было недостаточно, нужна была точная формула. Я также помнил, что нужно округлить число либо вверх, либо вниз, и что нужно добавить единицу. Этого оказалось достаточным, чтобы через минуту восстановить формулу $\mathsf{\mathrm{1+[lg n]}}$, где $[x]$ обозначает целая часть от $x$ (например, $[2,3]=2; [15,9]=15)$, а $\mathsf{\mathrm{lg n}}$ это десятичный логарифм, т.е. $\mathsf{\mathrm{lg n}} \mathsf{= log_{10} n}$.

Коллега на меня недоверчиво посмотрел и спросил, откуда я знаю это формулу.

Ниже есть продолжение.

На что я ему резонно ответил, что это простая школьная математика, и эту формулу я ещё со школы помню, очевидно я её прочитал в одной из книжек для школьников. На что он заметил, что, быть может, в бывшем СССР дети и читают такие книжки, но он в детстве подобных книжек не читал. Я ему решил объяснить в чём тут дело. В самом деле, говорил я ему, возьмём любое число, к примеру, $137$. $137= 1*10^2+3*10^1+7*10^0$ "Длина числа" будет $2+1=3$. Таким образом, нам достаточно узнать показатель степени полинома ($2$) и прибавить к нему единицу. Очевидно, что показатель полинома $3$ будет тогда и только тогда числа $100 \leq n \lt 1000 $, не трудно заметить, что $100=10^2 \leq n \lt 10^3=1000 $. Здесь, мне показалось уж совсем просто заметить, что показатель степени полинома есть десятичный логарифм числа, округлённый до ближайшего целого числа (напомню, все числа в рассмотрении натуральные), т.е. $\mathsf{\mathrm{[lg n]}}$.

К моему удивлению, это история имела продолжение. Сегодня, этот коллега ко мне подошёл и сказал, что среди его знакомых ни один не знаком с "моей" формулой и попросил объяснить откуда она берётся. Я был слегка шокирован. Ладно, я понимаю, человек может не помнить этой формулы, может быть он его также никогда и не знал, хотя последнее для меня очень странно, но я ведь ему объяснил на пальцах как её вести. Да, объяснение не было строгим, но не в этом была его претензия, да, я оставил довольно широкие "лакуны" в моём объяснении, но как он не смог их заполнить? Более того, почему никто ему не смог в это помочь?

Пришлось рисовать ему табличку:
число "длина числа"
7 1
12 2
675 3
6784 4
...


Далее я произнёс фразу, что "длина числа" увеличивается на единицу всякий раз когда число увеличивается примерно в десять раз, вывод - это логарифм.

Как оказалось и этого оказалось недостаточно. Очевидно, что товарищ забыл, что такое логарифм...Я ему ещё раз попробовал объяснить уже используя "круглые цифры" и наблюдение, что это является "нижней" границей для всех чисел с "одинаковым количеством цифр".

число "длина числа"
1 1
10=101 2=1+1
100=102 3=1+2
10=103 4=1+3
...

Не заметить, что с увеличением показателя степени на один (а это "нижняя граница") "длина числа" увеличивается на один по-моему нельзя. В принципе приведённых доводов достаточно уже, чтобы это оформить как формальное доказательство (нужно доказать сначала, что для чисел $10^k \lt n \le 10^{k+1}$ "длина числа" не меняется, а затем использовать индукцию по показателя степени полинома и формулу $\mathsf{\mathrm{lg 10x=lg10+lg x=1+lg x}}$). Про индукцию я ему не сказал, но эту формулу я ему написал. На него это не произвело никакого впечатления. Очень странно. Ведь функцию логарифма можно определить через набор свойств и доказав, что существует только одна функция, которая удовлетворяет этим условиям (так, в некоторых областях определяется показательная функция $e^x$, к примеру). Это условие является одним из базовых, натолкнувшись на него лично я думаю сразу про логарифм. Но это я не много вышел за рамки школьной программы. Можно то же самое показать и оставаясь в рамках школьной программы. Как известно, логарифм используется для "превращения" умножения в сложение. Этот трюк использовали в древности, когда надо было перемножить два больших числа (очевидно, об этом, мой коллега не знает). Этот трюк также используется в различных доказательствах вне школьной программы. Состоит он том, что

$lg ab=lg a+lg b$ (это следствие $10^a*10^b=10^{a+b}$)

и таким образом

$ab=10^{lg ab}=10^{(lg a+lg b)}$

Таким образом чтобы перемножить два числа, нужно сложить их десятичные логарифмы и возвести 10 в полученную степень. Замечание: вместо основания 10 можно использовать любое другое основание. Значения логарифмом находились по специально составленных таблицам (типа таблиц Брадеса), также по таблицам находилось значения возведения в степень.

1 comment: