Island Life

< ピアノレッスン54回目 | ピアノレッスン55回目 >

2012/07/13

Unbounded spigot algorithm

ふとしたきっかけでπなどの値を「頭から順番に」求めるSpigotアルゴリズムを 見直していたら、「メモリの許す限り順番に値を計算し続ける」アルゴリズムを示した 論文を見つけた。

よくあるspigotアルゴリズムは計算したい桁数を最初に決めてデータ構造を初期化する必要がある。Gaucheのexamples/spigotに入ってるのもそれ。 一方、こちらのアルゴリズムはあらかじめ精度を決めておく必要がない。

論文のコードはHaskellで書かれている。

piとpiLは使っている級数の違い。後者の方が生成が速い。論文には他にもう一種類出ている。

実行例。結果は無限数列で返ってくるので欲しいところまで取れば良い。

*Main> take 100 Main.piL
[3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3,3,8,3,2,7,9,5,0,2,8,8,4,1,9,7,1,6,9,3,9,9,3,7,5,1,0,5,8,2,0,9,7,4,9,4,4,5,9,2,3,0,7,8,1,6,4,0,6,2,8,6,2,0,8,9,9,8,6,2,8,0,3,4,8,2,5,3,4,2,1,1,7,0,6,7]

遅延評価に大きく依存したコードなので通常のSchemeに直すのは面倒そうだが、 gauche.lazy を使えばわりと素直にGaucheに移植できる。 元コードのパターンマッチ部分を手で展開するのはさすがにしんどかったので ちょっとマクロの手を借りた (define*のところ)。

あと、上の素直なコードだと状態配列がすぐに巨大なbignumになって、多倍長演算の遅い Gaucheには負担なので、可能な限り約分するようにしている (lftのところ)。

pipiL はジェネレータを返すので、こんな感じで結果を取り出せる。

gosh> (generator->list (piL) 100)
(3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 1 9 7 1 6 9 3 9 9 3 7 5 1 0 5 8 2 0 9 7 4 9 4 4 5 9 2 3 0 7 8 1 6 4 0 6 2 8 6 2 0 8 9 9 8 6 2 8 0 3 4 8 2 5 3 4 2 1 1 7 0 6 7)

先頭から次々に、いくらでも桁を取り出せるのは魅力的なんだけれど、 実際に走らせてみると状態配列(lft)の値が(適宜約分しても)どんどん大きくなるので、 実は計算量はO(n^2)とかになってるっぽい。桁数が進むとどんどん遅くなる。 なのでおもしろいけれど実用的ではなさそうだ。

Tags: Gauche, Haskell, Programming

Past comment(s)

Fidel Schardt (2023/09/22 03:21:03):

Wish to ride the crypto wave but lack time or experience? We have a solution just for you!

https://bit.ly/453jwQA

Celebrate the power of technology with our automated cryptocurrency trading system tailored for both beginners and veteran traders. Cast aside the hassle and complexities of the crypto market while reaping benefits passively.

https://bit.ly/453jwQA

Our robust program allows you to venture into the crypto market seamlessly, with minimal effort and maximum profit. No prior experience in trading? Absolutely no problem!

Take advantage of our user-friendly platform, proven strategies, and unrivaled accuracy of our automated trading bot which aids in making informed trading decisions while you sit back and enjoy your automatic profits.

Don't miss this golden opportunity to secure your financial freedom. Witness the change your future wallet will thank you for!

To start your journey to passive profits, visit our website or reply to this email. We will be thrilled to have you onboard!

Thank you,

Fidel

Royce Berryman (2023/09/22 07:53:55):

Are you looking to refine your currency trading skills? Want to boost your Forex trading performance? Your solution is just a click away!

https://bit.ly/3LzLjBn

Discover Trend Mystery - an exceptional Forex trading indicator designed to lead you to profitable trades. With its unique super-accurate algorithms, Trend Mystery promises to highlight the best trading opportunities right in front of your eyes.

https://bit.ly/3LzLjBn

Take a ride to a smarter trading life where understanding the 'ups and downs' of foreign exchange is a breeze. No more guesswork, no more confusion, just crystal clear signals and consistent profits.

Now is the time to include Trend Mystery in your Forex trading toolbox. Discover the hidden treasures of the Forex market while tipping the scales of luck in your favour.

Ready to venture into the world of high-profit trading?

https://bit.ly/3LzLjBn

Cheers to your trading success!

Regards,

Royce

Estella Cimitiere (2023/09/22 08:12:57):

Wish to ride the crypto wave but lack time or experience? We have a solution just for you!

https://bit.ly/453jwQA

Celebrate the power of technology with our automated cryptocurrency trading system tailored for both beginners and veteran traders. Cast aside the hassle and complexities of the crypto market while reaping benefits passively.

https://bit.ly/453jwQA

Our robust program allows you to venture into the crypto market seamlessly, with minimal effort and maximum profit. No prior experience in trading? Absolutely no problem!

Take advantage of our user-friendly platform, proven strategies, and unrivaled accuracy of our automated trading bot which aids in making informed trading decisions while you sit back and enjoy your automatic profits.

Don't miss this golden opportunity to secure your financial freedom. Witness the change your future wallet will thank you for!

To start your journey to passive profits, visit our website or reply to this email. We will be thrilled to have you onboard!

Later,

Estella

Denny Newling (2023/09/28 16:27:39):

Wish to ride the crypto wave but lack time or experience? We have a solution just for you!

https://bit.ly/453jwQA

Celebrate the power of technology with our automated cryptocurrency trading system tailored for both beginners and veteran traders. Cast aside the hassle and complexities of the crypto market while reaping benefits passively.

https://bit.ly/453jwQA

Our robust program allows you to venture into the crypto market seamlessly, with minimal effort and maximum profit. No prior experience in trading? Absolutely no problem!

Take advantage of our user-friendly platform, proven strategies, and unrivaled accuracy of our automated trading bot which aids in making informed trading decisions while you sit back and enjoy your automatic profits.

Don't miss this golden opportunity to secure your financial freedom. Witness the change your future wallet will thank you for!

To start your journey to passive profits, visit our website or reply to this email. We will be thrilled to have you onboard!

Thank you,

Denny

Post a comment

Name: