21.07.2026 08:05
DrArgentum 1 5500 Источник

Представьте: вы пишете парсер, который обходит сотни миллионов URL. Каждую новую ссылку нужно проверить — посещали ли мы её раньше? Заводить гигабайтный хеш-набор для хранения всех адресов — расточительно и медленно.

Но существует вероятностная структура данных, которая способна ответить на вопрос «видели ли мы этот URL?», занимая при этом в десятки раз меньше памяти, чем полное множество строк. Плата за такое - мизерная возможность ложноположительного срабатывания, где алгоритм заявит что URL существует, хотя на самом деле он новый. Зато на вопрос «не видели?» она не ошибётся никогда.

Это и есть Фильтр Блума, созданный Бёртоном Блумом аж в 1970 году. Более полсотни лет этому алгоритму! В принципе, никогда не помешает освежить знания и вспомнить, как писать реально оптимизированное ПО.

Ещё одну вероятностную структуру под названием HyperLogLog я разбирал в этой статье. HyperLogLog позволяет подсчитать количество уникальных элементов в огромном массиве данных с минимальным использованием памяти.

Фильтр Блума сам по себе устроен до неприличия просто. В основе лежит битовый массив фиксированной длины m, каждый бит которого равен нулю, и набор из k независимых хеш-функций h_1, h_2, \dots, h_k. Все операции с ним сведены к манипуляциям с отдельными битами - взять хеши, установить биты, проверить биты.

Когда мы добавляем новый элемент, мы пропускаем его через k независимых хеш-функций.

Я взял MurmurHash3 — современную некриптографическую хеш-функцию, которая известна своей скоростью и отличным распределением.

Каждая хеш-функция возвращает число в диапазоне от нуля до размера массива за вычетом единицы ([0, m-1]), то есть фактически индекс бита. Мы вычисляем все k хешей для элемента и устанавливаем каждый полученный бит в единицу. Если какой-то бит уже был установлен ранее — ничего страшного, он остаётся единицей; несколько элементов могут пересекаться по одним и тем же позициям.

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

По нотации большого O время занимает O(k), где k — число хеш-функций, которое обычно находится в диапазоне от нескольких единиц до пары десятков. Это означает, что фильтр Блума работает за константное время, не зависящее от количества уже добавленных элементов. Пространственная сложность — O(m) бит, что в большинстве практических сценариев на порядки меньше, чем хранение самих элементов или даже их хешей.

Но! У фильтра Блума есть ограничение: из него нельзя удалять элементы. Биты в массиве не привязаны к конкретным элементам, один и тот же бит может быть установлен разными элементами. Если попытаемся удалить элемент, обнулив его биты, мы рискуем поломать и другие элементы, что приведёт к ложноотрицательным срабатываниям, а это для фильтра Блума неприемлемо по определению.

В ответ на этот недостаток появилась модификация под названием Counting Bloom Filter, которая заменяет битовый массив на массив счётчиков. При добавлении элемента все соответствующие счётчики инкрементируются, при удалении — декрементируются. Это позволяет удалять элементы без риска задеть другие, но платой становится дополнительная память: вместо одного бита на позицию требуется несколько бит (обычно от 2 до 4) для хранения счётчика. Впрочем, даже в таком виде структура остаётся значительно компактнее полноценного хеш-набора, и на практике эту модификацию используют там, где удаления действительно необходимы и часты. Для классического же однобитного фильтра Блума правило остаётся неизменным: добавление — да, удаление — нет.

❯ Математика

Увы, без неё не обойтись. Поведение Фильтра Блума описывается формулами — для того чтобы узнать, сколько памяти выделить и сколько хеш-функций использовать, чтобы добиться приемлемой вероятности ложноположительного срабатывания при заданном ожидаемом количестве элементов.

Начнём с чистого листа. У нас есть:

  • n — количество элементов, которые мы планируем добавить в фильтр (например, 10 миллионов URL).

  • m — размер битового массива, наша основная структура данных. Измеряется в битах.

  • k — количество хеш-функций. Для каждого элемента мы вычисляем k индексов в битовом массиве.

Наша цель — понять, как, зная n, подобрать m и k, чтобы вероятность ошибки была не выше заданной, но при этом не потратить лишнюю память.

После добавления всех n элементов каждый из k хешей выставил случайный бит в 1. Выберем один конкретный бит в массиве. Какова вероятность, что он остался равен нулю?

Одна хеш-функция для одного элемента имеет вероятность 1/m попасть в этот бит. Значит, вероятность не попасть в него равна 1 - 1/m. Нам нужно, чтобы все kn операций (каждый из n элементов, помноженный на k хеш-функций) прошли мимо нашего бита. Так как операции независимы, вероятности перемножаются:

\left(1 - \frac{1}{m}\right)^{kn}

Работать с этим выражением напрямую неудобно. К счастью, в реальных задачах m — это миллионы или миллиарды, то есть очень большое число. Срабатывает известный математический предел: выражение (1 - 1/m)^m при больших m стремится к 1/e, где e — число Эйлера (\approx 2.718).

Это позволяет нам записать исходную вероятность в эквивалентной, но более простой форме. Представим (1 - 1/m)^{kn} как ((1 - 1/m)^m)^{kn/m}. Заменяя внутреннюю часть на 1/e, получаем изящную экспоненциальную форму:

\left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}

Что означает kn/m в показателе? Это среднее количество попаданий хеш-функций на одну ячейку массива. Если это число равно 2, то в каждую ячейку в среднем «прилетело» два хеша. Логично, что чем выше эта плотность, тем меньше у ячейки шансов уцелеть и остаться нулём.

Мы знаем шанс бита остаться нулём (e^{-kn/m}). Тогда вероятность, что он уже установлен в единицу, равна:

1 - e^{-kn/m}

Теперь — ключевой момент для понимания ложного срабатывания. Мы проверяем элемент, которого в фильтре заведомо нет. Мы вычисляем для него k хеш-функций и получаем k индексов в массиве. Ложная тревога произойдёт, только если биты по всем этим индексам случайно оказались единицами. Считая эти события независимыми, мы получаем итоговую вероятность ошибки P:

P \approx \left(1 - e^{-kn/m}\right)^k

Это и есть основная формула фильтра Блума.

При фиксированных n и m у нас есть свобода выбора k. Наша задача — найти такое k, при котором вероятность ошибки P минимальна. Для этого нам не нужно перебирать числа наугад. Мы можем взять производную функции P(k) и найти её минимум. Опуская детали дифференцирования, результат оказывается на удивление простым:

k = \frac{m}{n} \cdot \ln 2

То есть оптимальное число хеш-функций напрямую зависит от того, сколько бит массива мы можем выделить на один элемент (m/n). Если подставить это оптимальное k обратно в формулу вероятности пустого бита (e^{-kn/m}), мы получим e^{-\ln 2} = 1/2. Это важное следствие: в оптимально настроенном фильтре Блума ровно половина битов будет единицами, а половина — нулями.

На практике задача ставится иначе. Мы знаем n (ожидаемое число элементов) и P (допустимую вероятность ошибки). Нам нужно найти минимальный размер массива m. Для этого мы берём нашу основную формулу для P, подставляем в неё выражение для оптимального k и решаем получившееся уравнение относительно m:

P = \left( \frac{1}{2} \right)^{(\frac{m}{n} \ln 2)}

Выражая отсюда m, получаем практическую, инженерную формулу:

m = - \frac{n \cdot \ln P}{(\ln 2)^2}

Эта формула сразу даёт ответ в битах, и рост памяти здесь логарифмический относительно 1/P. Это объясняет эффективность фильтра: чтобы снизить вероятность ошибки в 100 раз, объём памяти нужно увеличить на константу, а не в 100 раз.

Закрепим на конкретных цифрах. Допустим, у нас n = 10 миллионов URL, и мы готовы мириться с вероятностью ошибки P = 10^{-3} (одно ложное срабатывание на тысячу проверок).

Сначала давайте посчитаем память (m):

m = - \frac{10^7 \cdot \ln(10^{-3})}{(\ln 2)^2} \approx - \frac{10^7 \cdot (-6{,}9078)}{0{,}48045} \approx 143{,}8 \cdot 10^6 \text{ бит}

Делим на 8 и на 10^6, чтобы получить мегабайты: \approx 17{,}2 \text{ МБ}. Для сравнения, хранение 10 миллионов строк в Set заняло бы сотни мегабайт, если не гигабайты.

Считаем оптимальное число хеш-функций (k):

k = \frac{m}{n} \cdot \ln 2 \approx \frac{143{,}8 \times 10^6}{10^7} \cdot 0{,}693 = 14{,}38 \times 0{,}693 \approx 9{,}96

Округляем до ближайшего целого: k = 10.

Теперь у нас есть конкретный технический дизайн: массив в 17,2 МБ и 10 хеш-функций.

❯ Реализация хеширования

Прежде чем говорить о самом фильтре Блума, нужно уделить внимание хеш-функции. От её качества зависит всё: если хеш-функция распределяет биты неравномерно или имеет зависимости между битами, все наши мечты о гарантиях алгоритма рушатся.

Я выбрал MurmurHash3, ибо его лавинный эффект и равномерность распределения изучены вдоль и поперёк, и отлично подходят для вероятностных алгоритмов.

static inline uint64_t murmur3_fmix64(uint64_t k) {
    k ^= k >> 33;
    k *= 0xff51afd7ed558ccdULL;
    k ^= k >> 33;
    k *= 0xc4ceb9fe1a85ec53ULL;
    k ^= k >> 33;
    return k;
}

static inline uint64_t murmur3_64(const void* key, size_t len, uint64_t seed) {
    const uint8_t* data = (const uint8_t*)key;
    const int nblocks = len / 16;
    uint64_t h1 = seed;
    uint64_t h2 = seed;

    const uint64_t c1 = 0x87c37b91114253d5ULL;
    const uint64_t c2 = 0x4cf5ad432745937fULL;

    const uint64_t* blocks = (const uint64_t*)data;

    for (int i = 0; i < nblocks; i++) {
        uint64_t k1 = blocks[i * 2];
        uint64_t k2 = blocks[i * 2 + 1];

        k1 *= c1;
        k1 = (k1 << 31) | (k1 >> 33);
        k1 *= c2;
        h1 ^= k1;
        h1 = (h1 << 27) | (h1 >> 37);
        h1 += h2;
        h1 = h1 * 5 + 0x52dce729;

        k2 *= c2;
        k2 = (k2 << 33) | (k2 >> 31);
        k2 *= c1;
        h2 ^= k2;
        h2 = (h2 << 31) | (h2 >> 33);
        h2 += h1;
        h2 = h2 * 5 + 0x38495ab5;
    }

    const uint8_t* tail = data + nblocks * 16;
    uint64_t k1 = 0;
    uint64_t k2 = 0;

    switch (len & 15) {
        case 15: k2 ^= (uint64_t)tail[14] << 48;
        case 14: k2 ^= (uint64_t)tail[13] << 40;
        case 13: k2 ^= (uint64_t)tail[12] << 32;
        case 12: k2 ^= (uint64_t)tail[11] << 24;
        case 11: k2 ^= (uint64_t)tail[10] << 16;
        case 10: k2 ^= (uint64_t)tail[9] << 8;
        case 9:  k2 ^= (uint64_t)tail[8];
                 k2 *= c2;
                 k2 = (k2 << 33) | (k2 >> 31);
                 k2 *= c1;
                 h2 ^= k2;
        case 8:  k1 ^= (uint64_t)tail[7] << 56;
        case 7:  k1 ^= (uint64_t)tail[6] << 48;
        case 6:  k1 ^= (uint64_t)tail[5] << 40;
        case 5:  k1 ^= (uint64_t)tail[4] << 32;
        case 4:  k1 ^= (uint64_t)tail[3] << 24;
        case 3:  k1 ^= (uint64_t)tail[2] << 16;
        case 2:  k1 ^= (uint64_t)tail[1] << 8;
        case 1:  k1 ^= (uint64_t)tail[0];
                 k1 *= c1;
                 k1 = (k1 << 31) | (k1 >> 33);
                 k1 *= c2;
                 h1 ^= k1;
    }

    h1 ^= len;
    h2 ^= len;
    h1 += h2;
    h2 += h1;

    h1 = murmur3_fmix64(h1);
    h2 = murmur3_fmix64(h2);
    h1 += h2;
    h2 += h1;

    return h1;
}

static inline uint64_t murmur3_64_string(const char* str, uint64_t seed) {
    return murmur3_64(str, strlen(str), seed);
}

Алгоритм обрабатывает блоками по 16 байт, используя два независимых 64-битных регистра, а финальное перемешивание выполняет функция fmix64, миксуя биты с помощью умножений и сдвигов. На выходе мы получаем 64 бита, которые ведут себя как равномерно случайные, — идеальное сырьё для нашего вероятностного алгоритма.

Кстати, этот алгоритм в виде ГПСЧ я описывал в одной из своих статей.

❯ Реализация Фильтра Блума на C

Наконец-то мы достигли практической части, где опустим занудную математику и достанем не менее занудный C!

Структура фильтра Блума на C выглядит вот так:

typedef struct {
    uint64_t size;          /* размер битового массива в битах */
    uint64_t hash_count;    /* число хеш-функций */
    uint64_t items_count;   /* количество добавленных элементов */
    uint8_t *bit_array;     /* упакованный битовый массив */
} BloomFilter;

Размеры полей выбраны 64-битными, потому что фильтр Блума часто работает с миллионами и миллиардами элементов, и 32-битных значений для размера массива может не хватить. Поле bit_array — это указатель на область памяти, где биты упакованы по 8 штук в байт. Такой подход сокращает потребление памяти в 8 раз по сравнению с массивом bool, а также улучшает локальность данных при последовательном обходе.

Инициализация фильтра происходит через функцию bloom_filter_create, которая выделяет память под структуру и под битовый массив, заполняя его нулями:

BloomFilter* bloom_filter_create(uint64_t size, uint64_t hash_count) {
    if (size == 0 || hash_count == 0) {
        return NULL;
    }
    BloomFilter *bf = (BloomFilter*)malloc(sizeof(BloomFilter));
    if (!bf) {
        return NULL;
    }
    bf->size = size;
    bf->hash_count = hash_count;
    bf->items_count = 0;
    bf->bit_array = (uint8_t*)calloc((size + 7) / 8, sizeof(uint8_t));
    if (!bf->bit_array) {
        free(bf);
        return NULL;
    }
    return bf;
}

Выражение (size + 7) / 8 — стандартный приём округления вверх при делении на 8: для хранения, скажем, 20 бит нужно 3 байта (24 бита), потому что 20 нацело на 8 не делится, а два байта дадут только 16. Именно поэтому мы добавляем 7 перед делением — гарантируем, что байтов будет ровно столько, сколько нужно для размещения всех битов, включая последний неполный байт.

Функция bloom_filter_from_expected — это удобная обёртка, которая принимает как аргументы ожидаемое число элементов и желаемую вероятность ложного срабатывания, а затем вычисляет оптимальные параметры по формулам из предыдущего раздела:

BloomFilter* bloom_filter_from_expected(uint64_t expected_elements, double false_positive_rate) {
    if (expected_elements == 0 || false_positive_rate <= 0.0 || false_positive_rate >= 1.0) {
        return NULL;
    }
    double ln2 = 0.6931471805599453;
    double size_d = -(expected_elements * log(false_positive_rate)) / (ln2 * ln2);
    uint64_t size = (uint64_t)ceil(size_d);
    if (size < 1) size = 1;
    double hash_count_d = (size / (double)expected_elements) * ln2;
    uint64_t hash_count = (uint64_t)round(hash_count_d);
    if (hash_count < 1) hash_count = 1;
    return bloom_filter_create(size, hash_count);
}

Здесь расчётный размер округляется вверх через ceil, а число хеш-функций — до ближайшего целого через round. Обработка крайних случаев, когда размер или число хешей оказывается меньше единицы, присутствует на всякий случай, хотя при корректных входных данных этого не происходит.

Работа с отдельными битами реализована через две простые inline-функции. set_bit устанавливает бит с индексом index в единицу, get_bit проверяет, установлен ли он:

static inline void set_bit(uint8_t *array, uint64_t index) {
    array[index >> 3] |= (1 << (index & 7));
}

static inline bool get_bit(const uint8_t *array, uint64_t index) {
    return (array[index >> 3] & (1 << (index & 7))) != 0;
}

Операция index >> 3 — это деление на 8, то есть номер байта. Выражение index & 7 даёт остаток от деления на 8, то есть позицию бита внутри байта. Установка бита выполняется через побитовое ИЛИ с маской, сдвинутой на нужную позицию. Проверка — через побитовое И с той же маской и сравнение с нулём.

Для вычисления индексов битов используется техника двойного хеширования. Вместо того чтобы вычислять k независимых хеш-функций, что было бы дорого, мы вычисляем два 64-битных хеша (h_1 и h_2) и генерируем все необходимые индексы по формуле:

static inline uint64_t double_hash(uint64_t h1, uint64_t h2, uint64_t i, uint64_t size) {
    return (h1 + i * h2) % size;
}

При обходе значений i от 0 до hash_count - 1 эта формула даёт последовательность псевдослучайных чисел, равномерно распределённых в диапазоне [0, \text{size}-1]. Это стандартный приём для фильтров Блума, он опирается на теорему о том, что линейная комбинация двух хороших хешей даёт результат, неотличимый от независимых хеш-функций. Главное требование — чтобы h_2 не было равно нулю, иначе последовательность выродится в одно и то же число. Поэтому в коде есть проверка и принудительная установка h_2 = 1 в случае нуля.

Добавление элемента в фильтр выглядит так:

void bloom_filter_add(BloomFilter *bf, const char *item) {
    if (!bf || !item) {
        return;
    }
    uint64_t seed1 = 0x123456789ABCDEF0ULL;
    uint64_t seed2 = 0xFEDCBA9876543210ULL;
    uint64_t h1 = murmur3_64_string(item, seed1);
    uint64_t h2 = murmur3_64_string(item, seed2);
    if (h2 == 0) h2 = 1;
    bool was_new = false;
    for (uint64_t i = 0; i < bf->hash_count; i++) {
        uint64_t idx = double_hash(h1, h2, i, bf->size);
        if (!get_bit(bf->bit_array, idx)) {
            was_new = true;
            set_bit(bf->bit_array, idx);
        }
    }
    if (was_new) {
        bf->items_count++;
    }
}

Мы вычисляем два базовых хеша с разными солями, затем в цикле проходим по всем hash_count индексам. Для каждого индекса проверяем бит: если он был нулевым, значит, мы действительно добавляем новый элемент или, по крайней мере, устанавливаем хотя бы один бит, который раньше не был установлен. Флаг was_new позволяет увеличить счётчик добавленных элементов только в том случае, если элемент действительно что-то изменил в фильтре. Это важно для корректного подсчёта items_count, который используется в формуле оценки вероятности ложного срабатывания.

Проверка принадлежности элемента строится на той же логике, но без модификации состояния:

bool bloom_filter_contains(const BloomFilter *bf, const char *item) {
    if (!bf || !item) {
        return false;
    }
    uint64_t seed1 = 0x123456789ABCDEF0ULL;
    uint64_t seed2 = 0xFEDCBA9876543210ULL;
    uint64_t h1 = murmur3_64_string(item, seed1);
    uint64_t h2 = murmur3_64_string(item, seed2);
    if (h2 == 0) h2 = 1;
    for (uint64_t i = 0; i < bf->hash_count; i++) {
        uint64_t idx = double_hash(h1, h2, i, bf->size);
        if (!get_bit(bf->bit_array, idx)) {
            return false;
        }
    }
    return true;
}

Если хотя бы один бит равен нулю, функция немедленно возвращает false — элемента гарантированно нет. Если все биты единицы — возвращает true, что означает вероятное присутствие.

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

double bloom_filter_fill_ratio(const BloomFilter *bf) {
    if (!bf || bf->size == 0) {
        return 0.0;
    }
    uint64_t filled = 0;
    uint64_t bytes = (bf->size + 7) / 8;
    for (uint64_t i = 0; i < bytes; i++) {
        uint8_t byte = bf->bit_array[i];
        while (byte) {
            filled += byte & 1;
            byte >>= 1;
        }
    }
    return (double)filled / (double)bf->size;
}

bloom_filter_current_fp_rate вычисляет текущую оценку вероятности ложного срабатывания по формуле, которую мы вывели в разделе математики, используя актуальные значения hash_count, items_count и size:

double bloom_filter_current_fp_rate(const BloomFilter *bf) {
    if (!bf || bf->items_count == 0) {
        return 0.0;
    }
    double exponent = -((double)bf->hash_count * (double)bf->items_count) / (double)bf->size;
    return pow(1.0 - exp(exponent), (double)bf->hash_count);
}

Для красивого вывода всей статистики есть функция bloom_filter_stats, которая печатает данные в формате JSON.

Запустим этот код! Пример из main создаёт фильтр с параметрами, рассчитанными на 1000 элементов и вероятность ложного срабатывания 1%, добавляет в него семь названий фруктов, а затем проверяет слово «watermelon», которого там нет:

Optimal size: 9586
Optimal hash count: 7

'watermelon' in filter: false
Statistics: {
  "size": 9586,
  "hash_count": 7,
  "items_added": 7,
  "fill_ratio": 0.005112,
  "estimated_fp_rate": 0.000000
}

Фильтр честно сообщает, что элемента нет — все 7 битов, соответствующих «watermelon», оказались нулевыми. Заполненность битового массива составляет чуть больше половины процента, что ожидаемо при семи добавленных элементах из тысячи возможных.

Второй пример показывает, что происходит при неудачном выборе параметров: фильтр размером 20 бит с двумя хеш-функциями, в который добавили 10 строк. Заполненность достигает 70%, а расчётная вероятность ложного срабатывания — почти 40%, и проверка на слово «watermelon» даёт ложное срабатывание:

Small filter: 'watermelon' in filter: true
Small filter statistics: {
  "size": 20,
  "hash_count": 2,
  "items_added": 10,
  "fill_ratio": 0.700000,
  "estimated_fp_rate": 0.399576
}

Когда я строил этот алгоритм впервые, я тоже удивился поначалу, как работает ложноположительное срабатывание.

❯ Графики

По аналогии со статьёй про HyperLogLog я решил провести тесты с изменёнными константами и нарисовать графики. Полный набор сырых данных доступен по этой ссылке.

По этим графикам можно сделать вывод, что использовать фильтр Блума при количестве элементов менее 500 стоит избегать. Используйте конфигурации high_fp, когда важна скорость (на 10–35% быстрее), и применяйте для них hash_count = 4, а для low_fp используйте hash_count = 7.

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

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩

Комментарии (1)


  1. wataru
    21.07.2026 08:40
    #30245166

    Статья отличная, все детально и по делу написано. Но есть несколько мелких замечаний:

    Выражение (size + 7) / 8 — стандартный приём округления вверх при делении на 8: для хранения, скажем, 20 бит нужно 3 байта (24 бита), потому что 20 нацело на 8 не делится, а два байта дадут только 16. Именно поэтому мы добавляем 7 перед делением — гарантируем, что байтов будет ровно столько, сколько нужно для размещения всех битов, включая последний неполный байт.

    Тут вы не совсем ясно объясняете. Лучше было бы написать почему это работает. Если size уже делиться на 8 на цело, то прибавление 7 не изменит результат, ведь /8 - это деление с округлением вниз. 7/8 отбросятся. Если же size не делится на 8, то там остаток хотя бы 1. прибавив к нему 7 мы точно соберем 8 до следующего делящегося на 8 и результат /8 будет на 1 больше, т.е. мы округлим вниз, а потом прибавим 1, получив округление вверх.

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