В 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, и быстрый для всех вариантов меньше.)
arithmoi реализует integerRoot, получая исходный приблизительный корень и уточняя его предположение с помощью метода Newtons. Для (10 32) 786 второе приближение становится действительно хорошей отправной точкой:
> appKthRoot 786 ((10^32)^786)
100000000000000005366162204393472
Для (10 32) 787 второе приближение становится очень плохой отправной точкой. Нравится, очень плохо.
> appKthRoot 787 ((10^32)^787)
1797693134862315907729305190789024733617976978942306572734300811577326758055009
6313270847732240753602112011387987139335765878976881441662249284743063947412437
7767893424865485276302219601246094119453082952085005768838150682342462881473913
110540827237163350510684586298239947245938479716304835356329624224137216
Фактически это приближение для всего, что начинается там.
> length $ nub [appKthRoot x ((10^32)^x) | x <- [787..1000]]
1
В любом случае, добавив важные части 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 32) 786 ÷ 2 82530 & approx; 2 1023.1 подходит в двойном, но (10 32) 787 ÷ 2 82635 & approx; 2 1024.4 нет.