2017-07-12 9 views
18

、:787の特色は何ですか? <a href="http://hackage.haskell.org/package/arithmoi" rel="noreferrer">arithmoi</a>パッケージを使用してGHCiので

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) 

5分後には、それはまだ応答していません。どうしてそんなに長くかかるのですか?

(いくつかのアドホックテストから、小さく、すべての選択肢のために787を超えると高速のすべての選択肢のために遅いように見える。)

+2

最新のarithmoiバージョンとMac OS 10.12.5のGHCiバージョン8.0.1で ':set + s'オプションを使用してこれを実行すると、セグメント化エラーが発生します。 ':set + s'がなければ、" Bus error:10 "になります。この 'integerRoot'関数のように見えますが、メモリがかなり不思議に動作します。 – Alex

答えて

22

arithmoi implements integerRoot初期おおよそのルートを取得し、ニュートン法との推測を精製することによっては、 。第二近似は本当に悪い開始点を取得し、について

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

(10 ):(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 

ええ、それはそれを行うだろう。 (1)÷2 ; 2 1023.1は二重に収まるが、(1)÷2 & 2 1024.4はありません。

+2

これは本当にイライラしています。私がこれらの大きな「Integer」を最初に置いている(そして私がarithmoiを使用している理由の一部)理由は、私が「Double」を避けるために本当に熱心に働いているからです。 –

+0

@DanielWagner:Yeah私はなぜ彼らが(h - 1)k以上の倍率でスケーリングしているのではないかを考えようとしています。しばらくの間、修正があるかもしれません。 – Ryan

+0

@DanielWagner:たとえば、「let!a @(I#a#)= 1024; h = 106; k = 787; n =(10^32)^ k; (1/fromIntegral k)* 2 **(fromIntegral a/k):(i = s) :Double)) ''は合理的な近似をもたらし、必要に応じてスケーリングを 'a 'に保つことができます。のために問題を提起する価値があるかもしれません。 – Ryan

関連する問題

 関連する問題