haskell - tipos - ¿Qué tiene de especial el 787?

tipos de aviones boeing

Question

En ghci, usando el paquete 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)

Después de cinco minutos, todavía no ha respondido. ¿Por qué está tomando tanto tiempo?

(De algunas pruebas ad-hoc, parece ser lento para todas las opciones más grandes que 787 y rápido para todas las opciones más pequeñas).

Answer 1

arithmoi implementa integerRoot obteniendo una raíz aproximada inicial y refinando su adivinación con el método de Newton. Para (10 ³² ) ⁷⁸⁶ , la segunda aproximación obtiene un buen punto de partida:

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

Para (10 ³² ) ⁷⁸⁷ , la segunda aproximación tiene un punto de partida realmente malo. Como, muy mal.

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

En realidad, obtiene esta aproximación para todo lo que comienza allí.

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

De todos modos, al poner en las partes importantes de appKthRoot , obtenemos:

> 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

y echando un vistazo a lo que está pasando en 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

Sí, eso lo haría. (10 ³² ) ⁷⁸⁶ ÷ 2 ⁸²⁵³⁰ ≈ 2 ^1023.1 cabe en un doble, pero (10 ³² ) ⁷⁸⁷ ÷ 2 ⁸²⁶³⁵ 2 ^1024.4 no.