java 计算 2 的极大幂

Calculating Extremely Large Powers of 2

提问by antiquekid3

I have made a program in Java that calculates powers of two, but it seems very inefficient. For smaller powers (2^4000, say), it does it in less than a second. However, I am looking at calculating 2^43112609, which is one greater than the largest known prime number. With over 12 million digits, it will take a very long time to run. Here's my code so far:

我用 Java 编写了一个计算 2 的幂的程序，但它似乎效率很低。对于较小的功率（例如 2^4000），它可以在不到一秒的时间内完成。但是，我正在计算 2^43112609，它比已知的最大素数大 1。超过 1200 万位数，需要很长时间才能运行。到目前为止，这是我的代码：

import java.io.*;

public class Power
{
 private static byte x = 2;
 private static int y = 43112609;
 private static byte[] a = {x};
 private static byte[] b = {1};
 private static byte[] product;
 private static int size = 2;
 private static int prev = 1;
 private static int count = 0;
 private static int delay = 0;
 public static void main(String[] args) throws IOException
 {
  File f = new File("number.txt");
  FileOutputStream output = new FileOutputStream(f);
  for (int z = 0; z < y; z++)
  {
   product = new byte[size];
   for (int i = 0; i < a.length; i++)
   {
    for (int j = 0; j < b.length; j++)
    {
     product[i+j] += (byte) (a[i] * b[j]);
     checkPlaceValue(i + j);
    }
   }
   b = product;
   for (int i = product.length - 1; i > product.length - 2; i--)
   {
    if (product[i] != 0)
    {
     size++;
     if (delay >= 500) 
     {
      delay = 0;
      System.out.print(".");
     }
     delay++;
    }
   }
  }
  String str = "";
  for (int i = (product[product.length-1] == 0) ? 
   product.length - 2 : product.length - 1; i >= 0; i--)
  {
   System.out.print(product[i]);
   str += product[i];
  }
  output.write(str.getBytes());
  output.flush();
  output.close();
  System.out.println();
 }

 public static void checkPlaceValue(int placeValue)
 {
  if (product[placeValue] > 9)
  {
   byte remainder = (byte) (product[placeValue] / 10);
   product[placeValue] -= 10 * remainder;
   product[placeValue + 1] += remainder;
   checkPlaceValue(placeValue + 1);
  }
 }  
}

This isn't for a school project or anything; just for the fun of it. Any help as to how to make this more efficient would be appreciated! Thanks!

这不是为了学校项目或任何东西；就是图个好玩儿。任何有关如何提高效率的帮助将不胜感激！谢谢！

Kyle

凯尔

P.S. I failed to mention that the output should be in base-10, not binary.

PS我没有提到输出应该是base-10，而不是二进制。

回答by Lie Ryan

The key here is to notice that:

这里的关键是要注意：

2^2 = 4
2^4 = (2^2)*(2^2)
2^8 = (2^4)*(2^4)
2^16 = (2^8)*(2^8)
2^32 = (2^16)*(2^16)
2^64 = (2^32)*(2^32)
2^128 = (2^64)*(2^64)
... and in total of 25 steps ...
2^33554432 = (2^16777216)*(16777216)

Then since:

然后因为：

2^43112609 = (2^33554432) * (2^9558177)

you can find the remaining (2^9558177)using the same method, and since (2^9558177 = 2^8388608 * 2^1169569), you can find 2^1169569using the same method, and since (2^1169569 = 2^1048576 * 2^120993), you can find 2^120993using the same method, and so on...

您可以(2^9558177)使用相同的方法找到其余的，并且因为(2^9558177 = 2^8388608 * 2^1169569)，您可以2^1169569使用相同的方法找到，并且因为(2^1169569 = 2^1048576 * 2^120993)，您可以2^120993使用相同的方法找到，依此类推...

EDIT: previously there was a mistake in this section, now it's fixed:

编辑：以前本节有错误，现在已修复：

Also, further simplification and optimization by noticing that:

此外，通过注意到进一步简化和优化：

2^43112609 = 2^(0b10100100011101100010100001)
2^43112609 = 
      (2^(1*33554432))
    * (2^(0*16777216))
    * (2^(1*8388608))
    * (2^(0*4194304))
    * (2^(0*2097152))
    * (2^(1*1048576))
    * (2^(0*524288))
    * (2^(0*262144))
    * (2^(0*131072))
    * (2^(1*65536))
    * (2^(1*32768))
    * (2^(1*16384))
    * (2^(0*8192))
    * (2^(1*4096))
    * (2^(1*2048))
    * (2^(0*1024))
    * (2^(0*512))
    * (2^(0*256))
    * (2^(1*128))
    * (2^(0*64))
    * (2^(1*32))
    * (2^(0*16))
    * (2^(0*8))
    * (2^(0*4))
    * (2^(0*2))
    * (2^(1*1))

Also note that 2^(0*n) = 2^0 = 1

还要注意的是 2^(0*n) = 2^0 = 1

Using this algorithm, you can calculate the table of 2^1, 2^2, 2^4, 2^8, 2^16... 2^33554432in 25 multiplications. Then you can convert 43112609into its binary representation, and easily find 2^43112609using less than 25 multiplications. In total, you need to use less than 50 multiplications to find any 2^nwhere nis between 0 and 67108864.

使用此算法，您可以计算2^1, 2^2, 2^4, 2^8, 2^16...2^33554432的 25 次乘法表。然后你可以转换43112609成它的二进制表示，并且2^43112609使用少于 25 次乘法很容易找到。总的来说，您需要使用少于 50 次乘法才能找到0 到 67108864 之间的任何2^n位置n。

回答by Daniel

Displaying it in binary is easy and fast - as quickly as you can write to disk! 100000...... :D

以二进制形式显示它既简单又快速 - 与写入磁盘一样快！100000…… :D

回答by meriton

Let n = 43112609.

让 n = 43112609。

Assumption:You want to print 2^n in decimal.

假设：您想以十进制打印 2^n 。

While filling a bit vector than represents 2^n in binary is trivial, converting that number to decimal notation will take a while. For instance, the implementation of java.math.BigInteger.toString takes O(n^2) operations. And that's probably why

虽然填充一个比二进制表示 2^n 的位向量是微不足道的，但将该数字转换为十进制表示法需要一段时间。例如，java.math.BigInteger.toString 的实现需要 O(n^2) 次操作。这可能就是为什么

BigInteger.ONE.shiftLeft(43112609).toString()

still hasn't terminated after an hour of execution time ...

执行时间一小时后仍未终止......

Let's start with an asymptotic analysis of your algorithm. Your outer loop will execute n times. For each iteration, you'll do another O(n^2) operations. That is, your algorithm is O(n^3), so poor scalability is expected.

让我们从算法的渐近分析开始。您的外循环将执行 n 次。对于每次迭代，您将执行另一个 O(n^2) 操作。也就是说，您的算法是 O(n^3)，因此预计可扩展性较差。

You can reduce this to O(n^2 log n) by making use of

您可以通过使用将其减少到 O(n^2 log n)

x^64 = x^(2*2*2*2*2*2) = ((((((x^2)^2)^2)^2)^2)^2

x^64 = x^(2*2*2*2*2*2) = ((((((x^2)^2)^2)^2)^2)^2

(which requires only 8 multiplications) rather than the 64 multiplications of

（只需要 8 次乘法）而不是 64 次乘法

x^64 = x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x

x^64 = x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x* x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x* x*x*x*x*x*x*x*x*x*x*x*x*x*x*x*x

(Generalizing to arbitrary exponents is left as exercise for you. Hint: Write the exponent as binary number - or look at Lie Ryan's answer).

（推广到任意指数留给您作为练习。提示：将指数写为二进制数 - 或查看 Lie Ryan 的答案）。

For speeding up multiplication, you might employ the Karatsuba Algorithm, reducing the overall runtime to O(n^((log 3)/(log 2)) log n).

为了加速乘法，您可以使用Karatsuba 算法，将总运行时间减少到 O(n^((log 3)/(log 2)) log n)。

回答by Zack Bloom

As mentioned, powers of two correspond to binary digits. Binary is base 2, so each digit is double the value of the previous one.

如前所述，二的幂对应于二进制数字。二进制是以 2 为底的，因此每个数字都是前一个数字的两倍。

For example:

例如：

    1 = 2^0 = b1
    2 = 2^1 = b10
    4 = 2^2 = b100
    8 = 2^3 = b1000
    ...

Binary is base 2 (that's why it's called "base 2", 2 is the the base of the exponents), so each digit is double the value of the previous one. The shift operator ('<<' in most languages) is used to shift each binary digit to the left, each shift being equivalent to a multiply by two.

二进制是基数 2（这就是为什么它被称为“基数 2”，2 是指数的基数），所以每个数字都是前一位值的两倍。移位运算符（在大多数语言中为“<<”）用于将每个二进制数字向左移位，每次移位相当于乘以 2。

For example:

例如：

1 << 6 = 2^6 = 64

Being such a simple binary operation, most processors can do this extremely quickly for numbers which can fit in a register (8 - 64 bits, depending on the processor). Doing it with larger numbers requires some type of abstraction (Bignum for example), but it still should be an extremely quick operation. Nevertheless, doing it to 43112609 bits will take a little work.

作为如此简单的二进制运算，大多数处理器可以非常快速地处理可以放入寄存器中的数字（8 - 64 位，取决于处理器）。用更大的数字来做它需要某种类型的抽象（例如 Bignum），但它仍然应该是一个非常快速的操作。然而，对 43112609 位执行此操作需要一些工作。

To give you a little context, 2 << 4311260 (missing the last digit) is 1297181 digits long. Make sure you have enough RAM to handle the output number, if you don't your computer will be swapping to disk, which will cripple your execution speed.

为了给您一些上下文，2 << 4311260（缺少最后一位数字）的长度为 1297181 位。确保您有足够的 RAM 来处理输出数字，否则您的计算机将交换到磁盘，这将削弱您的执行速度。

Since the program is so simple, also consider switching to a language which compiles directly into assembly, such as C.

既然程序这么简单，也可以考虑改用直接编译成汇编的语言，比如C。

In truth, generating the value is trivial (we already know the answer, a one followed by 43112609 zeros). It will take quite a bit longer to convert it into decimal.

事实上，生成值是微不足道的（我们已经知道答案，一个 1 后跟 43112609 个零）。将其转换为十进制需要更长的时间。

回答by Peter Lawrey

As @John SMith suggests, you can try. 2^4000

正如@John SMith 所建议的那样，您可以尝试。2^4000

    System.out.println(new BigInteger("1").shiftLeft(4000));

EDIT: Turning a binary into a decimal is an O(n^2) problem. When you double then number of bits you double the length of each operation and you double the number of digits produced.

编辑：将二进制转换为十进制是一个 O(n^2) 问题。当您将位数加倍时，您会将每个操作的长度加倍，并将产生的位数加倍。

2^100,000 takes 0.166 s
2^1000,000 takes 11.7 s
2^10,000,000 should take 1200 seconds.

NOTE: The time taken is entriely in the toString(), not the shiftLeft which takes < 1 ms even for 10 million.

注意：所花费的时间在 toString() 中是 entriely，而不是 shiftLeft，即使是 1000 万，它也需要 < 1 毫秒。

回答by mellamokb

The other key to notice is that your CPU is much faster at multiplying ints and longs than you are by doing long multiplication in Java. Get that number split up into long (64-byte) chunks, and multiply and carry the chunks instead of individual digits. Coupled with the previous answer (using squaring instead of sequential multiplication of 2) will probably speed it up by a factor of 100x or more.

另一个需要注意的关键是，与在 Java 中进行长乘法相比，您的 CPU 在整数和长整数相乘方面要快得多。将该数字拆分为长（64 字节）块，然后乘以并携带这些块而不是单个数字。再加上前面的答案（使用平方而不是 2 的顺序乘法）可能会将其加速 100 倍或更多。

Edit

编辑

I attempted to write a chunking and squaring method and it runs slightly slower than BigInteger (13.5 seconds vs 11.5 seconds to calculate 2^524288). After doing some timings and experiments, the fastest method seems to be repeated squaring with the BigInteger class:

我试图编写一个分块和平方的方法，它的运行速度比 BigInteger 稍慢（13.5 秒对 11.5 秒计算 2^524288）。在做了一些计时和实验后，最快的方法似乎是与 BigInteger 类重复平方：

    public static String pow3(int n) {
    BigInteger bigint = new BigInteger("2");
    while (n > 1) {
        bigint = bigint.pow(2);
        n /= 2;
    }
    return bigint.toString();
}

• Some timing results for power of 2 exponents (2^(2^n) for some n)
• 131072 - 0.83 seconds
• 262144 - 3.02 seconds
• 524288 - 11.75 seconds
• 1048576 - 49.66 seconds

• 2 次幂的一些计时结果（某些 n 为 2^(2^n)）
• 131072 - 0.83 秒
• 262144 - 3.02 秒
• 524288 - 11.75 秒
• 1048576 - 49.66 秒

At this rate of growth, it would take approximately 77 hours to calculate 2^33554432, let alone the time storing and adding all the powers together to make the final result of 2^43112609.

按照这样的增长速度，计算2^33554432大约需要77个小时，更不用说将所有的幂一起存储和加在一起得到2^43112609的最终结果的时间了。

Edit 2

编辑 2

Actually, for really large exponents, the BigInteger.ShiftLeft method is the fastest. I estimate that for 2^33554432 with ShiftLeft, it would take approximately 28-30 hours. Wonder how fast a C or Assembly version would take...

实际上，对于非常大的指数，BigInteger.ShiftLeft 方法是最快的。我估计对于带有 ShiftLeft 的 2^33554432，大约需要 28-30 小时。想知道 C 或汇编版本需要多快......

回答by supercat

Because one actually wants all the digits of the result (unlike, e.g. RSA, where one is only interested in the residue mod a number that's much smaller than the numbers we have here) I think the best approach is probably to extract nine decimal digits at once using long division implemented using multiplication. Start with residue equal zero, and apply the following to each 32 bits in turn (MSB first)

因为一个人实际上想要结果的所有数字（不像，例如 RSA，其中一个人只对残差 mod 一个比我们这里的数字小得多的数字感兴趣）我认为最好的方法可能是在一旦使用使用乘法实现的长除法。从残差为零开始，依次对每 32 位应用以下内容（MSB 在前）

  residue = (residue SHL 32)+data
  result = 0

  temp = (residue >> 30)
  temp += (temp*316718722) >> 32
  result += temp;
  residue -= temp * 1000000000;

  while (residue >= 1000000000) /* I don't think this loop ever runs more than twice */
  {
    result ++;
    residue -= 1000000000;
  }

Then store the result in the 32 bits just read, and loop through each lower word. The residue after the last step will be the nine bottom decimal digits of the result. Since the computation of a power of two in binary will be quick and easy, I think dividing out to convert to decimal may be the best approach.

然后将结果存储在刚刚读取的 32 位中，并循环遍历每个较低的字。最后一步后的余数将是结果的后九位十进制数字。由于计算二进制中的 2 的幂将很快且容易，我认为除以转换为十进制可能是最好的方法。

BTW, this computes 2^640000 in about 15 seconds in vb.net, so 2^43112609 should be about five hours to compute all 12,978,188 digits.

顺便说一句，这在 vb.net 中计算 2^640000 大约需要 15 秒，因此 2^43112609 应该大约需要五个小时才能计算所有 12,978,188 位数字。