Как я могу вычислить логарифм по основанию 2 без использования встроенных математических функций в C#?

Question

Как я могу вычислить логарифм по основанию 2 без использования встроенных математических функций в C#?

Я использую Math.Log и BigInteger.Log несколько раз в приложении миллионы раз, и это становится мучительно медленным.

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

Answer 1

Для BigInteger вы можете использовать метод toByteArray(), а затем вручную найти наиболее значимое 1 и посчитать количество нулей после этого. Это даст вам логарифм base-2 с целочисленной точностью.

Answer 2

Предполагая, что вы заинтересованы только в неотъемлемой части логарифма, вы можете сделать что-то вроде этого:

static int LogBase2(uint value)
{
    int log = 31;
    while (log >= 0)
    {
        uint mask = (1 << log);
        if ((mask & value) != 0)
            return (uint)log;
        log--;
    }
    return -1;
}

(обратите внимание, что возвращаемое значение для 0 неверно; оно должно быть отрицательной бесконечностью, но для целочисленных типов данных такого значения не существует, поэтому я возвращаю -1)

Answer 3

http://graphics.stanford.edu/~seander/bithacks.html

Answer 4

Страница битовых хаков полезна для таких вещей.

• Найти базу лога 2 целого числа с таблицей поиска

Код есть в C, но основная идея будет работать и в C#.

Answer 5

Вы можете попробовать этот алгоритм C, чтобы получить двоичный логарифм (основание 2) двойного N :

      static double native_log_computation(const double n) {
    // Basic logarithm computation.
    static const double euler = 2.7182818284590452354 ;
    unsigned a = 0, d;
    double b, c, e, f;
    if (n > 0) {
        for (c = n < 1 ? 1 / n : n; (c /= euler) > 1; ++a);
        c = 1 / (c * euler - 1), c = c + c + 1, f = c * c, b = 0;
        for (d = 1, c /= 2; e = b, b += 1 / (d * c), b - e /* > 0.0000001 */ ;)
            d += 2, c *= f;
    } else b = (n == 0) / 0.;
    return n < 1 ? -(a + b) : a + b;
}

static inline double native_ln(const double n) {
    //  Returns the natural logarithm (base e) of N.
    return native_log_computation(n) ;
}

static inline double native_log_base(const double n, const double base) {
    // Returns the logarithm (base b) of N.
    // Right hand side can be precomputed to 2.
    return native_log_computation(n) / native_log_computation(base) ;
}

Источник

Answer 6

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