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?

Furfuraceous

why don't you call the log function? Is this homework? – Promycelium

call log function from a 100000000000000000000000000000 ?! is that possible? – Furfuraceous

absolutely. Pass 1e300 to log with no trouble at all. – Promycelium

Hmmm ... thanks, but I it would be problematic because my long number stored in the char array...how can i pass in function in 1e300 form ? – Furfuraceous

Don't store numbers as text. Convert them to numbers. In this case you want to convert to double. Please don't tell me you have written addition and multiplication routines for char*! – Promycelium

@DavidHeffernan: It's common actually, for accurate bignum support. Then everyone realizes it's hard and finds a good library. – Eldred

@DavidHeffernan, no i have written for int* :) – Furfuraceous

@MooingDuck log(100000000000000000000000000000) sounds like a perfect candidate for floating point arithmetic to me. – Promycelium

Edit changes the question completely. I was answering a different question. – Promycelium

How large is "large"? Is the number a standard floating point value, or some custom type? – Janijania

@DavidHeffernan: Not if you need precision. Then it's a perfect candidate for gmp, ttmath, and similar – Eldred

@MooingDuck Clearly you have a better crystal ball than I do. My bad! ;-) – Promycelium

@KerrekSB, it's only natural number, and answer also must be natural – Furfuraceous

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.

Eldred

Thanks. Please have a look at: https://mcmap.net/q/833393/-log-of-a-very-large-number. – Prenatal

Thank you for taking a look at my question. I believe the answer you presented deserves to be stay up and may help others looking for a .NET perspective. Thanks again. – Prenatal

@RaheelKhan: The other answers already there are faster, and use this same algorithm. They provide good .NET implementations of this already, don't need my mistakes beside them :D – Eldred

This is not accurate to the decimal point for base 10 digits. Is there a fix for that? – Kibitz

For base 10 digits, it's log2( [mostSignificantDigit]*10+[secondMostSignifcantDigit] ) + 3.32192809*[remainingDigitCount]. You can also use *100 and calculate the log with three digits to improve accuracy further. The only trick is you have to make sure you have enough digits, but that's trivial. – Eldred

@MooingDuck Yes, but the problem is that in some cases, you need to inspect all base 10 digits to get a result which is 'accurate to the decimal point'. E.g. log2(129) = 7.01, log2(126) = 6.99 but above method gives 6.91 for both. This is in contrast to base 2 digits, for which the given accuracy holds. Would be nice to have the same accuracy for base 10 digits. – Kibitz

@le_m: My understanding was that 'accurate to the decimal point' effectively meant "within 0.5 of the real value", and in your sample, those are both within 0.09 of the real value. – Eldred

@MooingDuck Thanks for your clarification, it was a misunderstanding on my part then. Maybe you could clarify the meaning of 'accurate for the integeral part' and 'accurate to the decimal point' in your already very helpful answer to avoid others falling for the same trap. – Kibitz

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.

Etheline

Thanks, but I think that calculations using these methods would take too long time, because I have a problem just a binary logarithm. Can I do this?: en.wikipedia.org/wiki/Binary_logarithm – Furfuraceous

@KamilHismatullin: Can you do that? Yes. Will it be slow? Oh yes. – Eldred