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?

call log function from a 100000000000000000000000000000 ?! is that possible? — Kamil Hismatullin, Nov 22 '11 at 20:00
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 ? — Kamil Hismatullin, Nov 22 '11 at 20:06
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*`! — David Heffernan, Nov 22 '11 at 20:07
@DavidHeffernan: It's common actually, for accurate bignum support. Then everyone realizes it's hard and finds a good library. — Mooing Duck, Nov 22 '11 at 20:10
@MooingDuck `log(100000000000000000000000000000)` sounds like a perfect candidate for floating point arithmetic to me. — David Heffernan, Nov 22 '11 at 20:11
Edit changes the question completely. I was answering a different question. — David Heffernan, Nov 22 '11 at 20:14
How large is "large"? Is the number a standard floating point value, or some custom type? — Kerrek SB, Nov 22 '11 at 20:19
@DavidHeffernan: Not if you need precision. Then it's a perfect candidate for [gmp](http://gmplib.org/), [ttmath](http://www.ttmath.org/), and similar — Mooing Duck, Nov 22 '11 at 20:19
@MooingDuck Clearly you have a better crystal ball than I do. My bad! ;-) — David Heffernan, Nov 22 '11 at 20:20
@KerrekSB, it's only natural number, and answer also must be natural — Kamil Hismatullin, Nov 22 '11 at 20:22

Mooing Duck · Accepted Answer · 2017-03-22T16:36:24.333

8

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.

edited Mar 22 '17 at 16:36

answered Nov 22 '11 at 20:09

Mooing Duck

64,318
19
100
158

Thanks. Please have a look at: http://stackoverflow.com/questions/12003719/log-of-a-very-large-number. – Raheel Khan Aug 17 '12 at 10:04
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. – Raheel Khan Aug 17 '12 at 19:44
@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 – Mooing Duck Aug 17 '12 at 19:50
This is not *accurate to the decimal point* for base 10 digits. Is there a fix for that? – le_m Mar 21 '17 at 21:04
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. – Mooing Duck Mar 21 '17 at 21:12
@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. – le_m Mar 21 '17 at 22:02
@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. – Mooing Duck Mar 21 '17 at 23:54
@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. – le_m Mar 22 '17 at 13:38

score 4 · Answer 2 · edited Oct 18 '22 at 18:13

4

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.

edited Oct 18 '22 at 18:13

Glorfindel

21,988
13
81
109

answered Nov 22 '11 at 20:05

phimuemue

34,669
9
84
115

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?: http://en.wikipedia.org/wiki/Binary_logarithm – Kamil Hismatullin Nov 22 '11 at 20:32
@KamilHismatullin: Can you do that? Yes. Will it be slow? Oh yes. – Mooing Duck Nov 22 '11 at 23:13

Logarithm of the very-very large number

2 Answers2

Linked