Logarithm of the very-very large number

Question

I have to find log of very large number.

I do this in C++

I have already made a function of multiplication, addition, subtraction, division, but there were problems with the logarithm. I do not need code, I need a simple idea how to do it using these functions.

Thanks.

P.S. Sorry, i forgot to tell you: i have to find only binary logarithm of that number

P.S.-2 I found in Wikipedia:

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;

}

if I remade it under the big numbers, it will work correctly?

Answer 1

I assume you're writing a bignum class of your own. If you only care about an integral result of log2, it's quite easy. Take the log of the most significant digit that's not zero, and add 8 for each byte after that one. This is assuming that each byte holds values 0-255. These are only accurate within ±.5, but very fast.

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

If your values hold base 10 digits, that works out to 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)

If you used the algorithm you found on wikipedia, it will be IMMENSELY slow. (but accurate if you need decimals)

It's been pointed out that my method is inaccurate when the MSB is small (still within ±.5, but no farther), but this is easily fixed by simply shifting the top two bytes into a single number, taking the log of that, and doing the multiplication for the bytes less than that number. I believe this will be accurate within half a percent, and still significantly faster than a normal logarithm.

[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)

For base 10 digits, it's log2( [mostSignificantDigit]*10+[secondMostSignifcantDigit] ) + 3.32192809*[remainingDigitCount].

If performance is still an issue, you can use lookup tables for the log2 instead of using a full logarithm function.

Answer 2

I assume you want to know how to compute the logarithm "by hand". So I tell you what I've found for this.

Have a look over here, where it is described how to logarithmize by hand. You can implement this as an algorithm. Here's an article by "How Euler did it". I also find this article promising.

I suppose there are more sophisticated methods to do this, but they are so involved you probably don't want to implement them.