Логарифмы для программиста: log2, O(log n) и ловушки math.log

Логарифм числа x по основанию b — это показатель степени, в которую нужно возвести b, чтобы получить x: log_b(x) = y, если b ** y == x. Определен для x > 0 при основании b > 0 и b != 1. Например, log_2(8) = 3, потому что 2 ** 3 = 8.

Программисту логарифм нужен в трех местах: оценка сложности (O(log n)), подсчет битов и шагов деления пополам, вычисления через math.log с их ловушками точности. Код проверен на Python 3.9, функции модуля math в этих примерах работают так же в актуальном Python 3.14.

Три основания, которые встречаются в коде

Обозначения не универсальны: в математике log без основания часто означает натуральный логарифм, в статьях по алгоритмам — двоичный, в инженерных текстах — десятичный. В коде такой неоднозначности нет: math.log(x) в Python, Math.log(x) в JavaScript и Java, log(x) в C — это натуральный логарифм.

Свойства, которые реально пригождаются

Для положительных x, y и допустимого основания b:

• log_b(1) = 0 и log_b(b) = 1;
• log_b(x * y) = log_b(x) + log_b(y) — умножение превращается в сложение;
• log_b(x / y) = log_b(x) - log_b(y);
• log_b(x ** k) = k * log_b(x);
• смена основания: log_b(x) = log_a(x) / log_a(b).

Как это используют в коде. Произведение тысячи вероятностей по 0.001 в float превращается в 0.0 (настоящее значение 1e-3000 меньше наименьшего представимого float), а сумма их логарифмов — обычное число около -6907.76. Поэтому модели и статистика работают с log-вероятностями. Смена основания объясняет, почему в O(log n) основание не пишут: логарифмы по разным основаниям отличаются только постоянным множителем, а в O-нотации константы отбрасываются.

Минимальный пример: логарифмы в Python

import math

print(math.log(8, 2))      # 3.0 - логарифм 8 по основанию 2
print(math.log2(8))        # 3.0 - то же, отдельная функция
print(math.log10(1000))    # 3.0
print(math.log(math.e))    # 1.0 - без основания = натуральный
print(math.log(1000, 10))  # 2.9999999999999996, а не 3.0
print(math.log1p(1e-10))   # 9.999999999500001e-11 - это ln(1 + x) для малых x

Разбор по строкам:

• math.log(x, base) — сначала аргумент, потом основание. Внутри это log(x) / log(base), то есть два округленных результата и деление.
• math.log2 и math.log10 считают логарифм по своему основанию напрямую и обычно точнее, чем math.log(x, 2) или math.log(x, 10).
• Все функции возвращают float, даже когда ответ целый: math.log2(8) дает 3.0, а не 3.
• math.log1p(x) нужен, когда x очень мал: math.log(1 + 1e-10) дает 1.000000082690371e-10 — уже в восьмой значащей цифре ошибка, потому что 1 + 1e-10 округляется при сложении.

Логарифм нуля и отрицательного числа в вещественных числах не определен, и Python выбрасывает исключение: math.log(0) и math.log(-1) дают ValueError. Текст сообщения зависит от версии Python, поэтому ловите тип исключения, а не строку.

O(log n) и бинарный поиск: откуда берется логарифм

log_2(n) отвечает на вопрос: сколько раз n можно поделить пополам, пока не останется 1. Любой алгоритм, который на каждом шаге отбрасывает половину данных, делает порядка log_2(n) шагов. Классический пример — бинарный поиск в отсортированном массиве.

Прогон руками для 8 элементов [0..7] и поиска 7: смотрим середину 3, берем правую половину [4..7]; середина 5, остается [6..7]; середина 6, остается [7]; середина 7 — найдено. Четыре сравнения при log_2(8) = 3: в худшем случае число шагов равно floor(log_2(n)) + 1.

def binary_search(items, target):
    lo, hi, steps = 0, len(items) - 1, 0
    while lo <= hi:
        steps += 1
        mid = (lo + hi) // 2
        if items[mid] == target:
            return mid, steps
        if items[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1, steps

for n in (1_000, 1_000_000, 1_000_000_000):
    data = range(n)  # отсортированная последовательность 0..n-1
    print(n, binary_search(data, n))  # ищем отсутствующее значение

1000 (-1, 10)
1000000 (-1, 20)
1000000000 (-1, 30)

Миллиард элементов — 30 сравнений против миллиарда у линейного поиска в худшем случае: рост данных в тысячу раз добавляет около 10 шагов, потому что 2 ** 10 = 1024.

Граница модели: O(log n) описывает рост числа шагов, а не время в секундах. На маленьких массивах линейный проход может оказаться не медленнее из-за накладных расходов, а бинарный поиск требует отсортированных данных и быстрого доступа по индексу (для связного списка он не дает выигрыша).

Тот же логарифм дает высоту сбалансированного дерева и двоичной кучи (heapq.heappush — O(log n)) и множитель в сортировке слиянием O(n log n).

Биты и цифры: логарифм как длина числа

Двоичный логарифм показывает, сколько битов нужно числу, десятичный — сколько в нем цифр:

• число n > 0 занимает floor(log_2(n)) + 1 битов;
• чтобы закодировать N разных значений, нужно ceil(log_2(N)) битов: 256 значений — 8 битов, 1000 значений — 10 битов;
• положительное целое n содержит floor(log_10(n)) + 1 десятичных цифр.

Формулы верны математически. Проблема в том, что в коде их часто считают через float.

Ловушка точности: логарифм через float для целых чисел

Неверный код: определить степень десятки или число цифр через math.log и int.

import math

n = 1000
print(int(math.log(n, 10)))  # 2 - ожидали 3

big = 2 ** 53 - 1               # 53 единичных бита, старший бит - номер 52
print(math.floor(math.log2(big)))            # 53 - неверно
big10 = 10 ** 15 - 1            # 15 девяток
print(math.floor(math.log10(big10)) + 1)     # 16 цифр - неверно

Фактический результат: 2, 53, 16 вместо 3, 52, 15. Причины разные. В первом случае math.log(1000, 10) возвращает 2.9999999999999996, а int() отбрасывает дробную часть. Во втором и третьем сами числа представимы во float точно, но их настоящие логарифмы (52.99999999999999984 и 14.99999999999999957) ближе к целому, чем соседний float, и результат функции округляется до 53.0 и 15.0.

Исправление: для целых чисел считать длину целочисленными средствами.

n = 1000
big = 2 ** 53 - 1
big10 = 10 ** 15 - 1

print(big.bit_length() - 1)    # 52 - точный floor(log2) для целого > 0
print(big.bit_length())        # 53 - сколько битов занимает число
print(len(str(big10)))         # 15 - число цифр положительного целого
print((1000 - 1).bit_length()) # 10 - битов на 1000 разных значений (N > 1)

def int_log(n, base):
    """Точный floor(log_base(n)) для целых n >= 1, base >= 2."""
    k = 0
    while n >= base:
        n //= base
        k += 1
    return k

print(int_log(1000, 10))       # 3
print(int_log(10 ** 15 - 1, 10))  # 14

Правило выбора: если нужен целочисленный ответ (число битов, цифр, уровень дерева) — считайте целыми: int.bit_length(), len(str(n)), цикл деления. Если нужен дробный логарифм для формулы — берите math.log2/math.log10 вместо math.log(x, base). Сравнивать float-результат с целым через == нельзя, только через math.isclose. Оговорка для len(str(n)): с Python 3.11 перевод в строку целых длиннее 4300 цифр по умолчанию ограничен, для таких чисел используйте цикл деления.

Логарифмы в других языках

Поведение вне области определения различается: Python выбрасывает ValueError, а JavaScript, Java, C и C# по стандарту IEEE 754 возвращают -Infinity для нуля и NaN для отрицательного числа. Ошибка не всплывает сразу, а тихо портит дальнейшие вычисления, поэтому аргумент проверяют до вызова.

Если не получилось

• ValueError в Python. В логарифм попал ноль или отрицательное число: проверьте данные (пустой массив, нулевая частота, отрицательная разница) до вызова.
• Число на единицу меньше ожидаемого. Результат вида 2.9999999999999996 обрезан int(). Для целых задач — целочисленный способ выше.

Выводы

• Логарифм — показатель степени: log_b(x) = y, если b ** y == x; определен для x > 0, b > 0, b != 1.
• В программировании главное основание — 2: деление пополам, биты, высота дерева, O(log n); основание в O-нотации не пишут, потому что оно меняет только константу.
• math.log(x) в Python — натуральный логарифм; для оснований 2 и 10 точнее math.log2 и math.log10, чем math.log(x, base).
• Целочисленные задачи (биты, цифры, степень) решают int.bit_length(), len(str(n)) и циклом деления, а не int(math.log(...)).

Где применяется / связь с практикой

Логарифмы встречаются в разборе алгоритмов на собеседованиях, в анализе данных (логарифмические шкалы), в машинном обучении (функции потерь, log-вероятности) и в теории информации (энтропия в битах).

FAQ

Бывает ли логарифм отрицательного числа?
В вещественных числах нет. В комплексных — да: cmath.log(-1) в Python возвращает 3.141592653589793j, то есть i*pi.

Что такое логарифмическая шкала на графике?
Ось, на которой равные расстояния соответствуют умножению на одно и то же число (1, 10, 100), а не прибавлению. Она удобна, когда данные различаются на порядки.

Почему O(n log n) — предел для сортировки сравнениями?
Существует n! вариантов порядка, а каждое сравнение дает один бит информации, поэтому нужно не меньше log_2(n!) сравнений, что растет как n log n. Сортировки без сравнений (подсчетом, поразрядная) при ограничениях на ключи обходят эту границу.