Количество чисел с плавающей точкой между двумя заданными

Question

Есть ли какой-то трюк, позволяющий относительно быстро вычислить или хотя бы оценить количество чисел с плавающей точкой, заключённых между двумя заданными числами? На C++ это можно сделать так:

#include <cmath>
#include <iostream>

using namespace std;

int main()
{
    double a= 1, b= 1.00000001; // a - первое число, b - второе число
    long long count = 0;
    for (double x = a; x < b; x = nextafter(x, numeric_limits<double>::max()))
    {
        count++;
    }
    cout << count << endl;
    return 0;
}

Но это слишком медленно. Вычисление точного количества не требуется, вполне допустима погрешность -50+200%

Answer 1

Могу предложить "грязный трюк" :)

Каждый возможный 64-битный битовый паттерн кодирует некоторое значение с плавающей точкой формата binary64 стандарта IEEE 754. С другой стороны, этот же паттерн кодирует некоторое целое число типа std::uin64_t. Если перебирать все битовые паттерны в порядке возрастания целых беззнаковых начиная с нулевого, то соответствующие числа с плавающей точкой также будут возрастать.

Порядок следования таков: положительный ноль, положительные денормализованные значения от меньшего к большему, положительные нормализованные значения от меньшего к большему, положительная бесконечность, "положительные" NaN'ы.

Затем происходит скачок к отрицательным значениям. За последним "положительным" NaN'ом следуют отрицательные значения: отрицательный ноль, отрицательные денормализованные значения от большего к меньшему, отрицательные нормализованные значения от большего к меньшему, отрицательная бесконечность, "отрицательные" NaN'ы.

Можно сказать, что все числа с плавающей точкой естественным образом пронумерованы начиная с положительного нуля. Если нам известен номер числа a и номер числа b, то не составит труда вычислить количество номеров между числами a и b, т.е. количество чисел с плавающей точкой между числами a и b.

#include <cstdint>
#include <cstring>
#include <limits>

//Возвращает количество чисел с плавающей точкой - 1 из отрезка [a; b].
std::uint64_t count_float64(double a, double b)
{
    static_assert(sizeof(double) == sizeof(std::uint64_t) && std::numeric_limits<double>::is_iec559);

    std::uint64_t val_a, val_b, sign_a, sign_b, res;
    std::uint64_t mask = static_cast<std::uint64_t>(1) << (std::numeric_limits<std::uint64_t>::digits - 1);

    std::memcpy(&val_a, &a, sizeof(val_a));
    std::memcpy(&val_b, &b, sizeof(val_b));
    sign_a = val_a & mask;
    sign_b = val_b & mask;
    if (sign_a ^ sign_b) //Если знаки a и b различаются
    {
        mask = std::numeric_limits<std::uint64_t>::max() >> 1;
        res = (val_a & mask) + (val_b & mask) + 1;
    }
    else
    {
        if (val_a > val_b)
            res = val_a - val_b;
        else
            res = val_b - val_a;
    }
    return res;
}

Приведённый код предполагает, что порядок байтов у типов std::uint32_t и double является согласованным: младшие байты соответствуют младшим, старшие старшим. Естественно, это зависит от конкретной платформы.

БЛОГ НА HUSL

Количество чисел с плавающей точкой между двумя заданными

Ответы (1 шт):