Путеводитель для влюбленных в математику

10 = 10³, ответ равен 3. Иными словами, lg(1000) = 3.

Несложно уяснить, что происходит, когда мы возводим 10 в степень, равную целому положительному числу, – мы просто перемножаем 10 заданное число раз:

Если мы посчитаем нули в одной из степеней 10, то поймем значение логарифма:

lg(1 000 000 000) = 9.

Возведение 10 в дробную степень несколько сложнее. Ключевая идея здесь – понять, чему равно произведение 10^m и 10ⁿ.

Чему равно произведение 10⁶ × 10⁵? Не бойтесь, перемножать десятки просто. Давайте распишем нашу формулу:

Каков результат? Нет нужды перемножать! Просто посчитайте, сколько раз встречается 10 в правой части формулы: одиннадцать. Иными словами,

10⁶ × 10⁵ = 10¹¹.

Таким образом, для целых положительных степеней

10^m × 10ⁿ = 10^{m +} ⁿ.

Это тождество называется законом умножения степеней.

Ключевая идея вычисления дробной степени – применение данного закона для любых показателей степени. Давайте посмотрим, к чему это приведет.

Возьмем 10^0,5. Мы можем не знать, чему оно равно, но нам известно, чему равно произведение 10^0,5 × 10^0,5. А именно:

10^0,5 × 10^0,5 = 10^{0,5 + 0,5} = 10.

Если умножить 10^0,5 само на себя, получится 10. Таким образом, 10^0,5 равно квадратному корню из десяти[124]:

Так мы можем посчитать все степени 10. На рисунке вы видите график функции 10^х при x от 0 до 1.

При каком значении x выполняется условие 10^х = 2? При взгляде на график функции 10^х кажется, что подойдет x = 0,3. Если мы возьмем калькулятор, то выясним: 10^0,3 ≈ 1,99526… Близко, но не равно точно 2. Чуть-чуть увеличим степень. Попробуем x = 0,301; результат 10^0,301 ≈ 1,99986… Ближе, но все еще мимо цели. Нам нужно число немного больше. Величина x должна быть равна 0,30102999566398114… Это и будет log(2). (Вы уже встречали такое число раньше. Отыщите его!)

Закон умножения степеней 10^m × 10ⁿ = 10^{m +} ⁿ можно переформулировать для логарифмов. Посмотрим, как такое сделать. Допустим, a = 10^m и b = 10ⁿ.

Чему равен десятичный логарифм a? Это степень, в которую нужно возвести 10, чтобы получить a. Иными словами, lg(a) = m. Аналогично lg(b) = n.

Чему равен логарифм произведения ab? Мы знаем, что a = 10^m и b = 10ⁿ. Таким образом, ab = 10^{m +} ⁿ. В какую степень нужно возвести 10, чтобы получить ab? Ответ: m + n. На языке математических символов это выглядит так: lg(ab) = m + n.

Подытожим:

lg(a) = m,

lg(b) = n,

lg(ab) = m + n.

Отсюда мы выводим закон сложения для логарифмов:

lg(ab) = lg(a) + lg(b). (**)

Похоже, мы уже встречали эту формулу…

Завязываем узелки

Давайте подытожим то, что мы узнали из предыдущих разделов. Мы определили функцию f(m) как долю тех величин среди большого количества измерений, мантисса которых меньше m. Эта функция удовлетворяет трем условиям:

f(1) = 0,

f(10) = 1,

f(ab) = f(a) + f(b).

Потом мы обсудили логарифмы и выяснили следующее:

lg(1) = 0,

lg(10) = 1,

lg(ab) = lg(a) + lg(b).

Другими словами, значения f при 0 и 10 совпадает со значением десятичного логарифма от тех же величин. Кроме того, f и логарифм подчиняются одному и тому же правилу в соответствии с формулами (*) и (**). На основе этих фактов (и чисто технической оговорки, что функция f непрерывна) математики могут доказать, что f представляет собой логарифмическую функцию.

Теперь мы наконец готовы указать точную частотность первых значащих цифр при большом количестве измерений.

Какая доля измерений имеет первую значащую цифру 1? Сформулируем вопрос иначе: какая доля этих величин имеет мантиссу меньше 2? Ответ равен f(2) = lg(2) ≈ 0,3010 = 30,1 %.

Какая доля величин начинается с 9? Ответ равен f(10) – f(9), так как мы должны вычесть из общего количества величин те, первая значащая цифра которых меньше 9.

Это дает f(10) – f(9) = lg(10) – lg(9) ≈ 1 – 0,9542 = 0,0458 = 4,58 %.

Когда-то я задавал вопрос о значении f(1,7). Теперь можно уверенно ответить:

f(1,7) = lg(1,7) ≈ 0,23 = 23 %.

Глава 12

Алгоритм

Шеф-повара с фантазией редко руководствуются точными рецептами. Скорее, они следуют за вдохновением. А повара-новички покорно выполняют все указания поваренных книг.

Точно так же водителям с хорошей ориентацией на местности не нужны карты или детальные инструкции, как добраться до места назначения. А неопытным автомобилистам необходимы пошаговые указания.

В этом плане компьютеры похожи на новичков. Скажем, если нужно сложить несколько чисел, они скрупулезно выполняют операцию за операцией, руководствуясь инструкциями программистов. Эти инструкции называют алгоритмами[125]. Компьютерные алгоритмы окружают нас повсюду: они высчитывают проценты для банков, определяют разрывы страниц в текстовых документах, превращают цифровые данные на DVD-диске в кино, предсказывают погоду, рыщут по интернету в поисках рецепта, включающего заданные ингредиенты, и дают советы, сверяясь со спутниками GPS, когда мы ищем дом с хитрым адресом.

Первый математический алгоритм, который изучает большинство людей, – как складывать числа. Когда нужно просуммировать в столбик 25 и 18, мы знаем: вначале нужно к 5 прибавить 8 (и запомнить результат: 13), записать 3 в колонке единиц, а 1 держать в уме. Затем сложить 2 и 1, увеличить результат на 1 и записать 4 в колонке десятков. Получится 43.

Разработчикам алгоритмов недостаточно записать корректную процедуру решения проблемы, им важно, чтобы найденный метод был эффективен. Если алгоритм корректен с математической точки зрения, но требует тысячелетий для осуществления, пользы от него немного. Приглядимся к нескольким примерам.

Сортировка

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

Итак, перед нами встает проблема: имеется стопка тетрадей, перемешанных в хаотичном порядке, необходимо разложить их по алфавиту. Как это сделать наилучшим образом?

Начнем с простой, но неэффективной идеи. Допустим, у меня учится 100 студентов. Я беру из стопки первую тетрадку и смотрю, должна ли она идти первой по алфавиту. Каким образом? Я сравниваю имена на всех тетрадках с именем на этой тетрадке. Если не повезло и тетрадка по алфавиту не первая, я кладу ее в самый низ стопки и начинаю сначала. Я стану действовать так, пока не обнаружу первую по алфавиту тетрадку. Тогда я переложу ее в новую стопку, где тетрадки будут лежать упорядоченным образом.

Дальше я вернусь к неупорядоченной стопке – сейчас там 99 тетрадей – и, как