寻找一个数的极大幂次

Question

我正在为学生们创建一个小游戏，在其中一个地方，它需要显示2^7830457+1的值。

如果这个数字不是如此之大，我可以调用BigInteger的pow()方法。但是由于这个数字非常大，那个方法就没用了。我该如何找到这种数的巨大幂次方呢？请帮帮我！

- PeakGen

---

为什么不用指数形式来显示它？这个数字无法在电脑屏幕上显示。 - Daniel

如果你只是展示两百万个随机数字，没有人会注意到其中有什么问题——即使他们知道这些数字有误差也不会在意。那么这两百万个数字的精确顺序有什么教育价值呢？ - Marko Topolnik

只有前几个数字将会被显示出来。完整的数字将会被写入一个文件中。至少，那是我建议做的。而且，答案必须是正确的。有一位大师在等待着准确的答案。 - PeakGen

这与 Project Euler 有关系吗？ - Jonathan Lam

Answer 1

在二进制中，它只是一个有7830456个零的10000...01。

在十进制中，将会有大约200万位数字，大约需要2兆字节的存储空间。这在具有默认堆大小的BigInteger中是可行的。

实际上，它甚至使用平方法进行乘幂运算来快速计算（虽然这不被规范保证）。但是将其转换为String将需要一些时间，因为它是一个线性时间操作。

import java.math.BigInteger;

public class BigPow {
    public static void main(String[] args) {
        BigInteger result = (new BigInteger("2")).pow(27830457).add(BigInteger.ONE);
        System.out.println(result);
    }
}

这是一个逐步打印数字的版本：

import java.math.BigInteger;

public class BigPow {
    public static void main(String[] args) {
        BigInteger result = (new BigInteger("2")).pow(27830457).add(BigInteger.ONE);
        BigInteger powten = BigInteger.TEN.pow(2357202);

        while(powten.compareTo(BigInteger.TEN) > 0) {
            BigInteger digit = result.divide(powten).mod(BigInteger.TEN);
            System.out.print(digit);
            powten = powten.divide(BigInteger.TEN);
        }
    }
}

前几位数字是：

27337386390628313557307248857732033008168556429738078791761607160549944954510637855005417718646965163546351365984857761796847950377880836291434244529029919271706271982523405687134334692691344477538489450971091437463160940371624647030064741968436401566711255284353690448270545402444641547030399228243743315193608710148721648879085592699913299745785392609301774185427367430782834290629265859073814466687714408436025809604629262756100873545959924360001872161529545427749915099923749855388798808096264004516279149230434834365144195444133063912785293036501127732975020906194591678856327407158784862308588006709196891123629673211925293749715276954157951615065942499704196821312245056836412197647426909791063564122792292339809224240975555411598585583101545920478039147059154328126737371655627225938668386453826392239872360221038001514053321002759136195595635758294983698069570315260772582363105186254269056811134135133350936924294101345294335698866339561918857584229744277901180792029180156485000086528174400878657004645726892816943589969701053158760210512171516969813345080894134663207988962182426459128577282934948790911691329475034324656384238413230485050607666988301932660490870167246016897007835866691705399794247746213819662270451531049826029606671683482160663572103374

由WolframAlpha确认。

- tskuzzy

---

好的。你介意举个例子吗？我实际上没明白。 - PeakGen

该死！那是什么样的网络资源！！！它怎么可能这么快啊？？？？？？？？？？？ - PeakGen

@Sepala 这就是先进算法的威力。Java使用O(n^2)算法进行乘法和转换。WolframAlpha使用GMP，其乘法具有O(n*log(n))，转换具有O(n*log(n)^2)。 - Mysticial

太棒了！我不知道GMP是什么。那是一种编程语言吗？当我谷歌它时，显示的是药房、药品和“良好制造”结果。如果它是一种语言，我很高兴学习它！请给我更多信息！ - PeakGen

+1 对于指数平方的解决方法，它解决了我的问题。 - Maggie

Answer 2

您应该能够使用BigInteger进行计算。

 System.out.println(BigInteger.ONE.shiftLeft(7830457).add(BigInteger.ONE));

- Peter Lawrey

---

在这种情况下，使用移位和或操作。BigInteger.ONE.shift(7830457).add(BigInteger.ONE) 或者类似的东西。 - Wug

Answer 3

我不知道你为什么认为 BigInteger 不足以胜任这项任务：

import java.math.BigInteger;

public class Test {
    public static void main(String[] args) throws Exception {
        BigInteger big = BigInteger.valueOf(2)
            .pow(7830457)
            .add(BigInteger.ONE);
        System.out.println(big);
    }
}

需要一点时间（特别是最后的字符串转换），但这是完全合理的。

正如Peter所指出的，将ONE左移7830457要简洁得多。不过我认为这有点不太清晰，当然在字符串转换部分也没有帮助。

编辑：几乎所有的时间都花在了字符串转换上。它最终在我的电脑上完成了。我已经看不到它的开始了，但它是以...结束的。

08570502260645006898157834607641626568029302766491883299164453304032280181734737
79366998940913082443120328458954436211937775477966920836932628607888755839700303
873

- Jon Skeet

---

无法使用。这将需要数年才能给出结果。 - PeakGen

你的机器花了多少分钟？你在IDE中运行它了吗？你的RAM是多少？请回答 :) - PeakGen

转换为字符串或控制台输出哪个占用时间更长？当您将输出重定向到文件时，它需要运行多长时间？ - Daniel Fischer

@DanielFischer：相对于转换所花费的时间，控制台输出并不需要那么长时间。 - tskuzzy

迄今为止，转换是最大的问题。据我所知，Java 7仍然使用O(n^2)算法进行转换。因此，对于长度为200万位数的东西，它能够完成转换，我感到非常惊讶。 - Mysticial

Answer 4

尝试类似这样的东西：

BigInteger mant = new BigInteger("2");
BigInteger result = mant.pow(7830457).add(BigInteger.ONE);

- marktani