Как узнать число цифр, не вычисляя огромное число

Десятичный логарифм показывает число цифр без записи самого числа.

Дальше вы найдёте число цифр у 2¹⁰⁰⁰ и 1000!, разберётесь с нулём и отрицательными числами и увидите случай, когда обычный калькулятор ошибается на одну цифру из-за округления.

В статье вы узнаете:

• Почему новая цифра появляется на степенях десяти
• Как посчитать цифры большой степени
• Как заменить факториал суммой логарифмов
• Для каких чисел формула не подходит напрямую
• Как проверить результат возле целой границы

Переход от 999 к 1000 выдаёт всё правило

Посмотрите на несколько соседних диапазонов. Числа от 1 до 9 имеют одну цифру. От 10 до 99 две. От 100 до 999 три. Каждая новая цифра появляется ровно на очередной степени десяти.

Четырёхзначное число не меньше 1000 и меньше 10 000. Иначе говоря, оно лежит между 10^3 включительно и 10^4 не включительно. Для числа с d цифрами нижняя граница всегда равна 10^(d - 1), а верхняя 10^d.

Десятичный логарифм отвечает на простой вопрос: в какую степень надо возвести 10, чтобы получить заданное число. У 1000 он равен 3, у 10 000 равен 4. У числа между ними логарифм тоже находится между 3 и 4.

Значит, целая часть логарифма четырёхзначного числа равна 3. Чтобы вернуться к числу цифр, прибавляем единицу:

Слово floor означает округление вниз до ближайшего целого. Например, десятичный логарифм 4872 примерно равен 3,688. Округляем вниз до 3 и прибавляем 1. Получаем четыре цифры, что легко проверить глазами.

Степень десяти не создаёт исключения. Для 1000 логарифм равен ровно 3, формула даёт 3 + 1 = 4. Нижняя граница нового разряда уже принадлежит следующему диапазону.

Для 2¹⁰⁰⁰ достаточно одного логарифма

Число 2¹⁰⁰⁰ настолько длинное, что его неудобно сначала вычислять, а затем пересчитывать цифры. Но логарифм степени можно получить без самой степени. Когда одинаковый множитель повторяется много раз, логарифм произведения превращается в сумму одинаковых слагаемых.

Если основание степени положительно, логарифм a^b равен b × log10 a:

Десятичный логарифм двойки примерно равен 0,3010299957. Умножаем на 1000 и получаем 301,0299957. Целая часть равна 301, прибавляем единицу.

2¹⁰⁰⁰ содержит 302 цифры.

В калькуляторе логарифмов можно выбрать основание 10 и число 2, чтобы увидеть исходное значение примерно 0,301. Для всего выражения удобнее научный калькулятор: наберите 1000 × log(2) и получите примерно 301,03. Для подсчёта программа должна брать целую часть внутреннего неокруглённого значения, а не цифр на экране. К этому ограничению мы ещё вернёмся.

Способ переносится на любую целую степень с положительным основанием и положительным показателем. Например:

Значит, 7²⁰²⁶ содержит 1713 цифр. Мы узнали длину записи, хотя ни одной из этих 1713 цифр не выписывали.

Факториал превращается в сумму коротких логарифмов

Факториал неотрицательного целого n равен произведению целых чисел от 1 до n. У произведения нет одного повторяющегося основания, как у степени, зато логарифм всё равно разбивает его на сумму:

При n = 0 произведение и сумма пусты: 0! = 1, log10(0!) = 0, поэтому запись 0! содержит одну цифру. Для отрицательных целых обычный школьный факториал не определён.

Возьмём 100!. Сумма ста логарифмов равна примерно 157,9700036547. Округляем вниз до 157 и прибавляем единицу. Получается 158 цифр.

Это можно проверить точным вычислением, но оно уже плохо помещается в строку. 100! начинается с 93326215 и заканчивается 24 нулями. Между ними остаётся ещё больше сотни цифр, которые для нашей задачи ничего не меняют.

Для 1000! сумма логарифмов равна примерно 2567,6046442221. Значит, 1000! содержит 2568 цифр. Для этой задачи достаточно сложить тысячу обычных логарифмов, хранить и печатать весь результат не требуется.

Калькулятор факториала помогает увидеть, как быстро растут значения. Например, 25! он уже показывает в короткой записи с показателем степени, а при 171! получает Infinity, поэтому 1000! целиком не вычислит. Точное число цифр надёжнее брать из суммы логарифмов с контролем погрешности.

Ноль, знак и ведущие нули требуют отдельного правила

Формула floor(log10 N) + 1 относится к положительным целым числам. У нескольких похожих записей вопрос меняется.

Ноль. Число 0 записывается одной цифрой, но log10 0 не определён как обычное вещественное число. В программе ноль надо обработать отдельно и сразу вернуть 1.

Отрицательное целое. У числа -73 две цифры. Знак минус сообщает направление на числовой прямой, но цифрой не является. Сначала берут модуль числа, затем применяют формулу: digits(-N) = digits(N).

Ведущие нули. Записи 42 и 00042 обозначают одно целое число с двумя цифрами в обычной математической записи. Если задача просит длину кода, номера заказа или строки, ведущие нули уже считаются символами. Это другая задача, и логарифм там не нужен.

Десятичная дробь. У записи 0,00340 можно отдельно считать значащие цифры, знаки после запятой или все символы. Единого ответа «сколько цифр в числе» здесь нет, пока не выбрано правило.

Эти случаи полезно отделить до расчёта. Иначе точная формула ответит на вопрос, который никто не задавал.

Возле степени десяти округление может изменить ответ на единицу

Математическая формула точна, но обычный электронный калькулятор хранит логарифм с конечной точностью. Обычно маленькая ошибка незаметна. Функция floor делает её важной возле целого числа, потому что две почти одинаковые величины могут попасть по разные стороны границы.

Возьмём точное целое:

В нём 15 цифр, и оно меньше 10¹⁵ всего на единицу. Точный логарифм начинается как 14,9999999999999995657. Обычное машинное вычисление может округлить его до 15. Тогда формула после floor ошибочно даст 16 цифр.

Возможна и обратная ошибка. Приближённый логарифм точного числа 10¹⁵ иногда получается чуть меньше 15, например 14,999999999999998. Округление вниз тогда даст 14, а итоговая формула 15 вместо правильных 16.

Первое правило защиты простое: не округляйте логарифм до трёх или восьми знаков перед floor. Видимое 15 может скрывать и 14,9999999999, и 15,0000000001.

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

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

Если полная десятичная запись ненулевого N уже есть, проще удалить знак и ведущие нули и посчитать оставшиеся символы. Запись нуля после удаления ведущих нулей надо отдельно нормализовать до одной цифры 0. Логарифм нужен именно тогда, когда число задано компактно как степень, произведение или факториал. В обычных примерах калькулятор быстро показывает порядок. Возле целого показателя его округлённый экран служит предупреждением, а не доказательством.

Полезный вопрос перед расчётом звучит так: насколько далеко логарифм от ближайшего целого? Для 2¹⁰⁰⁰ расстояние около 0,03, поэтому несколько верных знаков уверенно дают 302 цифры. Если расстояние сравнимо с погрешностью вычисления, надо повышать точность, а не угадывать сторону границы.

Есть что добавить?

Напишите своё мнение, комментарий или предложение.