「しなぷすのハード製作記」の管理人の日記です。電子工作とカメラの話をしています。足し算と引き算だけで円周率の近似値を求めるアルゴリズム(4)前回は、注目する点がちょうど円弧上にあった時に、その点が1/4円の内部にあると解釈するべきか、外部にあると解釈するべきかという、細かい点について説明しました。今回は、いよいよ整数演算だけで円周率を計算するプログラムを作ってみます。1/4円の内部にあるか、外部にあるかを判定し、1/4円の内部のコマの数から円周率を求めるプログラムを作ります。積極的な手法と消極的な手法について振り返る1/4円の内部にあるコマを数えるにあたっては、コマの左下の隅が1/4円の内部であれば、コマが1/4円の内部にあると考える積極的な手法と、コマの右上の隅が1/4円の内部であって初めて、コマが1/4円の内部にあると考える消極的な手法により円周率を求めます。実際の円周率は、積極的な手法で推定した円周率と、消極的な手法で推定した円周率の間にある事が、理論的に保証されます。)が1/4円の内部にあるか、外部にあるかを判定する事になります。)は1/4円の外部にあると判定します。)が1/4円の内部にあるか、外部にあるかを判定する事になります。)は1/4円の内部にあると判定します。1/4円内にあるかどうかは、次の表に示す判定法で判定できます。)は1/4円の内部にあるただこの判定法では、平方根の計算が必要となり、浮動小数点の、時間のかかる計算が必要になります。そこで、等式あるいは不等式の両辺を2乗して、次の様な判定法に改めると、整数の掛け算(2乗の計算は同じ数同士の掛け算と考える)と引き算しか出てこない、高速な判定ができます。)は1/4円の内部にあるC言語でのプログラム例この様な方針で1/4円の面積を求め、その面積から円周率の推定値を求めるプログラムをC言語で作ると、次の様になります。大きくするほど円周率が精度よく求まる。整数の掛け算、足し算、および引き算のみでプログラムを組めています。2倍して円周率を換算する部分については、浮動小数点演算を使っています。2で割る操作は2進数の小数点を左に移動する操作に相当します。2進数の固定小数点演算をする場合は、実質的には割り算の演算が不要です。2で割る操作は10進数の小数点を左に移動する操作に相当します。10進数の固定小数点演算をする場合は、実質的には割り算の演算が不要です。先ほどのプログラムをpaiza.IOで動作させられるようにしたのが、次の画面です。10000に設定して実行すると、max(積極的な手法で推測した円周率)が3.14199016、min(消極的な手法で推測した円周率)が3.14119052となっており、それらの平均のaveが3.14159034と求まります。aveを正確な円周率の3.14159265・・・と比較すると、円周率が6桁計算できている事が分かります。上の画面中で、Rの値を10000U(末尾のUはunsignedの意味)とは別の値に書き換えて実行すると、半径Rを変えて計算できます。paiza.IOには、コンパイルと実行の時間が2秒以内という制約があるため、Rを大きくしすぎると、タイムアウトしてしまいます。R=60000Uではタイムアウトしてしまいます。Rを大きくして円周率を高精度で求めたい場合は、アルゴリズムを改良して、高速化する必要があります。2個のコマについて、1/4円の内部にあるかどうかを判定していました。2回の計算が必要でした。1万の時は、1億回の計算をする事になってしまいます。(それを実際に2秒以内に実行するPaiza.IOはすごいです)実は、次の様な点に注目すれば、もっと計算回数を減らす事ができます。あるコマが1/4円の内部にある(あるいは外部にある)事が分かればその下(あるいはその上)のコマが1/4円の内部にあるかどうかを判定する必要はない上の図は、消極的な手法で1/4円内部のコマの数を数えている一場面を表しています。特定のx座標に注目し、同じx座標の列の中に、1/4円内部のコマがいくつあり、1/4円内部のコマがいくつあるかを調べています。水色のコマが1/4円の内部にあると先に判定したら、その下2つのコマは、数式により1/4円の内部にあると判定しなくても、当然1/4円の内部にあるはずです。紫色のコマが1/4円の外部にあると先に判定したら、その上1つのコマは、数式により1/4円の外部にあると判定しなくても、当然1/4円の外部にあるはずです。これらの事から、うまくやれば、1列全てのコマについて1/4円の内部にあるか、外部にあるかを判定しなくても、もっと少ないコマを判定するだけで、その列にある1/4円内のコマ数を数える事ができそうです。1/4円の内部にあるか外部にあるかを判定するコマの数が減れば、プログラムは高速化します。この様なアイデアを積極的に利用すると、プログラムが劇的に高速化するのですが、説明が長くなってきたので、詳細は次回に説明します。しなぷす電子工作サイトしなぷすのハード製作記の管理人です。フリーランスのエンジニアですが、大学の非常勤講師もやっています。コメントをキャンセルメールアドレスが公開されることはありません。※サイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。自己紹介しなぷす電子工作サイトしなぷすのハード製作記の管理人です。フリーランスのエンジニアですが、大学の非常勤講師もやっています。