Круглые числа.

(или «Зачем программисту логарифм»)

Начнем с постановки практической задачи: Необходимо организовать удобный интерфейс для ввода диапазона числовых значений.
На практике это может потребоваться при создании «фильтров» для товарных каталогов: подвергаться фильтрации могут такие характеристики, как «диагональ телевизора», «минимальная температура в морозильной камере холодильника», «частота процессора».
В самом общем случае это могут быть положительные и отрицательные, целые и дробные числа, покрывающие некоторое недискретное пространство значений.

Очевидное и самое простое в реализации решение:

Такой интерфейс обладает рядом недостатков, среди которых выделим три наиболее важных:

Все эти недостатки легко устраняются применением инструмента «слайдер» из состава большого количества современных javascript фреймворков. Мы для примера возьмем один из наиболее популярных: jQuery UI Slider.

Воспользовавшись примером из документации, получаем легкое и удобное решение:

Отсюда и далее все примеры будем приводить на базе этих трех характеристик: целочисленной, целочисленной отрицательной и дробной

Хорошо. Все три недостатка мы устранили. Но можно лучше. Избавим пользователя от необходимости «прицеливаться» ползунком, оглядываясь на значение числового индикатора. Для этого нанесем шкалу значений:

Ещё лучше. Но что-то в этих числах явно не так — это не те числа, которыми привык пользоваться человек. Это не круглые числа! На их месте так и просится что-то вроде: «500, 800, 1100, 1400, …», «-24, -22, -20, -18, …»

Википедия нам говорит о двух близких, по сути, трактовках термина «Круглые числа»: «10, 100, 1000, …» и «10, 20, 30, …». В общем виде круглое число в десятичной системе счисления имеет вид ±N×10k, где N — десятичная цифра, а k любое натуральное число. Для нашей задачи мы вынуждены будем расширить понятие круглого числа множеством чисел с отрицательными k (0.1, 0.2, …, 0.007, …), т.к. исчислять коэффициент аэродинамического сопротивления целыми числами не представляется возможным.

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

Очевидно, что в этом случае наша шкала станет немного шире или уже, т.к. граничные значения сместятся в круглые позиции. Сужать — недопустимо: мы не можем позволить себе «выкинуть товар» из поиска. Следовательно, левую границу будем округлять до меньшего, правую границу и шаг — до большего круглого числа.
Важно также понимать, что для нашей задачи, при вычислении минимального значения, говорить о ближайшем круглом для, например, 517, — в отрыве от всего диапазона не имеет смысла. На его роль могло бы пойти число 500, будь у нас интервал от 517 до 3000 или, например, 510, будь у нас интервал от 517 до 550.

Верным решением задачи будем считать такой набор значений минимального (MINo), максимального числа (MAXo) и величины шага (STEPo), который удовлетворяет условиям:

MINo ≤ MIN // новый минимум не больше исходного
MAXo ≥ MAX // новый максимум не меньше исходного
STEPo × N = MAXo - MINo

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

STEP = (MAX-MIN) / N
STEP_EXP = floor( log10(STEP) )
STEP_POWER = 10STEP_EXP
STEP_MANTISSA = STEP / STEP_POWER
// STEP = STEP_MANTISSA * 10STEP_EXP

Затем округлить мантиссу до меньшего целого и увеличить на 1

STEPo = (floor(STEP_MANTISSA) + 1) * STEP_POWER

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

MINo = floor(MIN / STEP_POWER) * STEP_POWER
MAXo = MINo + STEPo × N

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

STEP = (MAX-MIN) / N
VALID = false; // флаг «верное решение найдено»
while not VALID
begin
    STEP_EXP = floor( log10(STEP) )
    STEP_POWER = 10STEP_EXP
    STEP_MANTISSA = STEP / STEP_POWER
    STEPo = (floor(STEP_MANTISSA) + 1) * STEP_POWER

    MINo = floor(MIN / STEP_POWER) * STEP_POWER
    MAXo = MINo + STEPo × N

    VALID = MAXo ≥ MAX

    STEP = STEPo// для перехода следующему круглому числу на следующей итерации цикла
end

Применяя этот алгоритм, получаем:

Такой интерфейс уже можно назвать user friendly, но в нём возник новый недостаток, не свойственный предыдущим примерам: при некоторых значениях MIN, MAX и количества засечек может возникать ситуация, когда интервалы между несколькими последними засечками выходят за пределы [MIN: MAX].
Примером такой ситуации может служить попытка отобразить диапазон значений [0 : 110] на шкале с десятью интервалами (11 засечек): шаг по 10 не покроет весь диапазон, а шаг по 20 сделает пустыми правые интервалы. Простого решения этой проблемы нет, однако, есть способ существенно снизить вероятность появления таких отрезков за счет расширения понятия круглого числа.

В текущем решении круглыми являются только те числа, мантисса которых входит в множество натуральных чисел от 1 до 9. Т.е. круглыми считаются только числа:

123456789
102030405060708090
100200300400500600700800900

А что, если расширить это множество числами, с мантиссой 1.2, 1.5 и 2.5? В тех самых случаях «пустого» отрезка мы получим более короткие значения (например, округлив 135, вместо 200 — получим 150)

11.21.522.53456789
101215202530405060708090
100120150200250300400500600700800900

Описывать алгоритм поиска ближайшего круглого по «новым правилам» не буду, полагая, что это не будет сложной задачей. Сразу покажу результат такого апгрейда:

Итог

Я мог бы сам подвести итог под всем сказанным выше, но думаю, что своим глазам читатель верит больше, поэтому — сводный пример:

Details

Математика

Помимо привычной десятичной системы счисления, существуют и другие. Им не в меньшей степени свойственно понятие круглого числа. И, хотя это имеет малое практическое значение, всё сказанное действительно и для них. (0xF000 воспринимается проще, чем 0xA48C, да? :-) )

Язык программирования

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

logN(x) = ln(x) / ln(N)
log10(x) = ln(x) / ln(10)

Исходный код

Алгоритмы, описанные в этой статье, и код, иллюстрирующий применение алгоритмов в связке с jQuery UI Slider, вы можете найти реализованными на языке javascript в прилагаемой к статье библиотеке.

Future

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

Есть над чем поработать!

P.S. Показались наши примеры неудачными? Попробуйте свои значения:

Ссылки:

jQuery UI, Экспоненциальная запись, Натуральное число, Логарифм, Круглые числа, Floor and ceiling functions