787有什么特别之处？

Question

在 ghci 中，使用 arithmoi 包：

Math.NumberTheory.Powers.General> :set +s
Math.NumberTheory.Powers.General> integerRoot 786 ((10^32)^786)
100000000000000000000000000000000
(0.04 secs, 227,064 bytes)
Math.NumberTheory.Powers.General> integerRoot 787 ((10^32)^787)

过了五分钟，还是没反应。为什么要花这么长时间？

（从一些临时测试来看，对于大于 787 的所有选择似乎都很慢，而对于所有小于 787 的选择似乎很快。）

Answer 1

arithmoi implements integerRoot 通过获取初始近似根并使用牛顿法改进其猜测。对于 (10³²)⁷⁸⁶，第二个近似得到了一个非常好的起点：

> appKthRoot 786 ((10^32)^786)
100000000000000005366162204393472

对于 (10³²)⁷⁸⁷，第二个近似值的起点非常糟糕。就像，真的 不好。

> appKthRoot 787 ((10^32)^787)   
1797693134862315907729305190789024733617976978942306572734300811577326758055009
6313270847732240753602112011387987139335765878976881441662249284743063947412437
7767893424865485276302219601246094119453082952085005768838150682342462881473913
110540827237163350510684586298239947245938479716304835356329624224137216

它实际上得到了从那里开始的所有东西的近似值。

> length $ nub [appKthRoot x ((10^32)^x) | x <- [787..1000]]
1

无论如何，输入 the important parts of appKthRoot，我们得到：

> let h = 106; k = 786; n = (10^32)^k; !(I# s) = h * k - k in floor (scaleFloat (h - 1) (fromInteger (n `shiftRInteger` s) ** (1/fromIntegral k) :: Double))
100000000000000005366162204393472

> let h = 106; k = 787; n = (10^32)^k; !(I# s) = h * k - k in floor (scaleFloat (h - 1) (fromInteger (n `shiftRInteger` s) ** (1/fromIntegral k) :: Double))
179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216

看看 scaleFloat 中发生了什么：

> let h = 106; k = 786; n = (10^32)^k; !(I# s) = h * k - k in fromInteger (n `shiftRInteger` s) ** (1/fromIntegral k) :: Double
2.465190328815662

> let h = 106; k = 787; n = (10^32)^k; !(I# s) = h * k - k in fromInteger (n `shiftRInteger` s) ** (1/fromIntegral k) :: Double
Infinity

是的，这样就可以了。 (10³²)⁷⁸⁶ ÷ 2⁸²⁵³⁰ ≈ 2^1023.1 适合双精度数，但是 (10³²)⁷⁸⁷ ÷ 2 ⁸²⁶³⁵ ≈ 2^1024.4 没有。