java - java计算极大功率 2

  显示原文与译文双语对照的内容
137 1

我用Java编写了一个计算二值幂的程序,但它看起来很低效。对于较小的功率( 2 ^4000,说),它在不到一秒的。但是,我正在计算 2 ^43112609,它是一个 GREATER,它是已知的最大素数的一个。超过 12万位数字,运行的时间会很长。以下是我的代码:

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);
 }
 } 
}

这不是学校项目或者任何东西;只是为了好玩。关于如何提高效率的任何帮助都是值得感激的 !谢谢!

凯尔

P.S 。我没有提到输出应该在base-10中,而不是二进制文件。

时间:原作者:0个回答

104 1

这里的关键是要注意:

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)

之后:

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

你可以使用相同的方法找到其余的(2^9558177),自(2^9558177 = 2^8388608 * 2^1169569)你可以使用相同的方法查找 2^1169569,因为(2^1169569 = 2^1048576 * 2^120993),你可以使用相同的方法找到 2^120993,等等。

:以前有一个错误,现在它是固定的:

此外,通过注意以下事项,进一步简化和优化:

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

也要注意2^(0*n) = 2^0 = 1

使用这里算法,可以计算 2^12^22^42^82^16的表。2^33554432 在 25乘法中,可以以将 43112609 转换为二进制表示,并且利用小于 25的乘法方便地查找 2^43112609总的来说,你需要使用小于 50乘法来查找任何在和 67108864之间的2^n

原作者:
...