非常大的数的对数 [英] Logarithm of the very-very large number

问题描述

我必须找到非常大的日志。

我在C ++中这样做

已经做了乘法，加法，减法，除法的函数，但是对数有问题。我不需要代码，我需要一个简单的想法如何使用这些功能。

谢谢。

PS
对不起，我忘了告诉你：我必须找到

的只有二进制对数

PS-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; （n> =（1 <4））{n> = 4;} 
 
 if pos + = 4;如果（n> =（1 << 2））{n> = 2;} 
 
 if pos + = 2; } 
 
 if（n> =（1<< 1））{pos + = 1; } 
 
 return pos; 
 
} 
  

如果我重新下载大数字，正确？

解决方案

我假设你正在写一个自己的bignum类。如果你只关心log2的整数结果，这很容易。取不为零的最高有效数字的日志，并在该字节之后添加8。这假设每个字节保存值0-255。这些只对整数部分准确，但速度非常快。

  [0] [42] [53] ）
 log2（42）= 5 
 + 8 * 1 = 8（由于低于MSB的一个字节）
 = 13（实际：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（因为低于MSB的3个数字）
 = 12.28771（实际：12.49235395）
（仅适用于小于〜10百万个数字）
  

如果你使用在维基百科上找到的算法， （但如果您需要小数点，则准确）

已经指出，当MSB很小（仍然精确到小数点，但不再更远）时，我的方法不准确，但是这可以通过简单地将顶部两个字节移位到单个数字，取 的日志，并对小于该数字的字节进行乘法来容易地固定。我相信这个准确度会在半个百分点之内，而且仍然比正常对数快很多。

  [1] [42] [53]（76341字节）
 log2（1 * 256 + 42）=？ 
 log2（298）= 8.21916852046 
 + 8 * 1 = 8（由于低于MSB一个字节）
 = 16.21916852046（实际：16.2201704643）
  

如果性能仍然是一个问题，您可以使用查找表为log2，而不是使用完整的对数函数。

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?

解决方案

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 for the integeral part, 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 accurate to the decimal point, 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)

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

这篇关于非常大的数的对数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！