Логарифм очень-очень большого числа - PullRequest
Новая
       23

Логарифм очень-очень большого числа

3 голосов
/ 22 ноября 2011

Я должен найти журнал очень большого числа.

Я делаю это в C ++

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

Спасибо.

P.S. Извините, я забыл вам сказать: мне нужно найти только двоичный логарифм этого числа

P.S.-2 Я нашел в Википедии : 

int floorLog2(unsigned int n) {

if (n == 0)

  return -1;

int pos = 0;

if (n >= (1 <<16)) { n >>= 16; pos += 16; }

if (n >= (1 << 8)) { n >>=  8; pos +=  8; }

if (n >= (1 << 4)) { n >>=  4; pos +=  4; }

if (n >= (1 << 2)) { n >>=  2; pos +=  2; }

if (n >= (1 << 1)) {           pos +=  1; }

return pos;

}

если я переделал его под большие числа, он будет работать правильно?

Ответы [ 2 ]

7 голосов
/ 23 ноября 2011

Полагаю, вы пишете свой собственный класс bignum.Если вы заботитесь только о интегральном результате log2, это довольно просто.Возьмите журнал самой значимой цифры, которая не равна нулю, и добавьте 8 для каждого байта после этого.Это предполагает, что каждый байт содержит значения 0-255.Они точны только в пределах ± 0,5, но очень быстро. 

[0][42][53] (10805 in bytes)
    log2(42) = 5
    + 8*1    = 8    (because of the one byte lower than MSB)
             = 13  (Actual: 13.39941145)

Если ваши значения содержат основную цифру 10, то получается log2(MSB)+3.32192809*num_digits_less_than_MSB. 

[0][5][7][6][2] (5762)
 log2(5)        =  2.321928095
 + 3.32192809*3 =  9.96578427  (because 3 digits lower than MSB)
                =  12.28771  (Actual: 12.49235395)
(only accurate for numbers with less than ~10 million digits)

Если вы использовалиалгоритм, который вы нашли в Википедии, он будет НЕМЕДЛЕННО медленным.(но точный, если вам нужны десятичные дроби)

Было отмечено, что мой метод является неточным, когда MSB маленький (все еще в пределах ± .5, но не дальше), но это легко исправить, просто сдвинув верхнюю частьдва байта в одно число, беря лог , который , и делая умножение для байтов меньше, чем это число.Я полагаю, что это будет с точностью до полпроцента, и все же значительно быстрее, чем обычный логарифм. 

[1][42][53] (76341 in bytes)
    log2(1*256+42) = ?
    log2(298) = 8.21916852046
    + 8*1     = 8    (because of the one byte lower than MSB)
              = 16.21916852046  (Actual: 16.2201704643)

Для базовых 10 цифр это log2( [mostSignificantDigit]*10+[secondMostSignifcantDigit] ) + 3.32192809*[remainingDigitCount].

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

3 голосов
/ 23 ноября 2011

Полагаю, вы хотите знать, как вычислить логарифм "вручную". Итак, я расскажу вам, что я нашел для этого.

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

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

...