Điều gì đặc biệt về 787?

Question

Trong ghci, bằng cách sử dụng gói 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) 

Sau năm phút, nó vẫn chưa trả lời. Tại sao phải mất quá lâu?

(Từ một số thử nghiệm ad-hoc, nó dường như là chậm đối với tất cả các lựa chọn lớn hơn 787 và nhanh chóng cho tất cả những lựa chọn nhỏ hơn.)

Answer 1

arithmoi implements integerRoot bởi nhận được một gốc xấp xỉ ban đầu và cải tiến đoán của nó với phương pháp của Newton . Đối với (10) , xấp xỉ thứ hai được một điểm thực sự tốt bắt đầu:

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

Đối (10) , xấp xỉ thứ hai được một điểm khởi đầu thực sự tồi tệ. Giống như, thực sự là xấu.

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

Nó thực sự nhận được sự gần đúng này cho mọi thứ bắt đầu từ đó.

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

Dù sao, đưa vào the important parts of appKthRoot, chúng tôi nhận được:

> 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 

và tham gia một cái nhìn vào những gì đang diễn ra vào 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 

Yeah, mà muốn làm điều đó. (10) ÷ 2 & xấp xỉ; 2 ^1023.1 phù hợp với đôi, nhưng (10) ÷ 2 & xấp xỉ; 2 ^1024.4 thì không.