. А именно:
100,5 × 100,5 = 100,5 + 0,5 = 10.
Если умножить 100,5 само на себя, получится 10. Таким образом, 100,5 равно квадратному корню из десяти[124]:
Так мы можем посчитать все степени 10. На рисунке вы видите график функции 10х при x от 0 до 1.
При каком значении x выполняется условие 10х = 2? При взгляде на график функции 10х кажется, что подойдет x = 0,3. Если мы возьмем калькулятор, то выясним: 100,3 ≈ 1,99526… Близко, но не равно точно 2. Чуть-чуть увеличим степень. Попробуем x = 0,301; результат 100,301 ≈ 1,99986… Ближе, но все еще мимо цели. Нам нужно число немного больше. Величина x должна быть равна 0,30102999566398114… Это и будет log(2). (Вы уже встречали такое число раньше. Отыщите его!)
Закон умножения степеней 10m × 10ⁿ = 10m+ⁿ можно переформулировать для логарифмов. Посмотрим, как такое сделать. Допустим, a = 10m и b = 10ⁿ.
Чему равен десятичный логарифм a? Это степень, в которую нужно возвести 10, чтобы получить a. Иными словами, lg(a) = m. Аналогично lg(b) = n.
Чему равен логарифм произведения ab? Мы знаем, что a = 10m и b = 10ⁿ. Таким образом, ab = 10m+ⁿ. В какую степень нужно возвести 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 тетрадей – и, как и раньше, начну искать первую по алфавиту тетрадку. Я возьму тетрадку сверху, сравню со всеми остальными и положу в самый низ стопки, если она не подойдет. Когда я найду искомую тетрадку, я положу ее во вторую стопку снизу.
Теперь у меня есть «всего-навсего» 98 тетрадей, и я повторяю все по новой: ищу первую по алфавиту тетрадь и кладу ее в низ второй стопки.
Сколько времени это займет?
Основная операция заключается в том, чтобы сравнить два имени и решить, какое следует первым по алфавиту[126]. Мы будем оценивать эффективность алгоритма по количеству сравнений, которые необходимо провести. У меня 100 учащихся; как долго мне придется сопоставлять имена и решать, какое идет первым?
В неупорядоченной стопке из 100 тетрадей я сравниваю первую с 99 остальными. Необходимо проделать эту операцию со всеми 100 тетрадями (не исключено, что искомая лежит в самом конце). Поиск первой по алфавиту потребует максимум 100 × 99 = 9900 сопоставлений.
Я кладу свою находку во вторую стопку и повторяю процедуру с 99 неотсортированными тетрадями. Я сравниваю верхнюю тетрадь с 98 оставшимися. Поиск второй по алфавиту тетради потребует максимум 99 × 98 = 9702 сопоставления.
Третья тетрадь потребует максимум 98 × 97 сравнений, четвертая – максимум 97 × 96. Не исключено, что придется проделать 100 × 99 + 99 × 98 + 98 × 97 + … + 2 × 1 = 333 300 сравнений.
Мы проанализировали худший случай[127]. На каждой итерации мы нашли максимум из возможного числа операций и посчитали, сколько их всего потребуется. Несомненно, такой результат настраивает нас на пессимистический лад и показывает, насколько неэффективным был наш алгоритм. Давайте попробуем что-нибудь другое.
Мы снова начинаем со стопки из 100 тетрадей, перемешанных случайным образом. Берем первые две тетради. Если они идут не в правильном порядке, меняем их местами (первая станет второй, вторая – первой). Если порядок верный, оставляем все без изменений. Дальше смотрим на вторую и третью тетрадь. Если порядок верный, идем дальше. Если нет, меняем их местами. Так мы действуем по этому алгоритму, пока не доберемся до конца стопки. Один заход требует 99 сравнений.
Когда мы дойдем до конца стопки, тетради с именами из начала алфавита сместятся вверх, а тетради с именами в конце алфавита сместятся вниз. Но одного захода может быть недостаточно. В худшем случае первая по алфавиту тетрадь изначально лежала в самом низу, и в первом заходе мы переместили ее всего-навсего на 99-ю позицию. В этом случае сортировка потребует 99 операций[128].
Таким образом, нам придется проделать максимум 99 × 99 = 9801 операцию. Это гораздо лучше первого метода, но все еще неэффективно. Если сравнение и смена позиции требует двух секунд, я закончу спустя пять часов. Это никуда не годится.
И вот я в расстроенных чувствах выхожу из кабинета, чтобы развеяться. В коридоре я встречаю двух постдоков, которые работают под моим научным руководством. Зловещая улыбка змеится на моих губах. Я спешу обратно в кабинет, делю стопку неотсортированных тетрадей пополам и даю по 50 тетрадей каждому постдоку. «Вот вам стопка тетрадей, – говорю я. – Пожалуйста, рассортируйте их по алфавиту и принесите ко мне в кабинет, когда закончите». После чего с воодушевлением возвращаюсь к основной работе