「しなぷすのハード製作記」の管理人の日記です。電子工作とカメラの話をしています。足し算と引き算だけで円周率の近似値を求めるアルゴリズム(2)前回から、整数の足し算と引き算だけで円周率の近似値を求めるアルゴリズムについて解説しています。多くの桁を高速で求めるのに適したアルゴリズムではないものの、整数の足し算と引き算しか出てこないので、ハードウェアに実装する場合に、部品数が少なくて済むというメリットがあります。今回はそこまで踏み込みませんが、HDLを使ってFPGAなどに実装するのも容易です。前回は、この連載で説明しているアルゴリズムが、1/4円の面積を、定積分の近似計算で求めている事を説明しました。定積分の近似計算を、浮動小数点を使って行うプログラムを例示しました。今回は、整数演算だけで、ほぼ同様の計算ができる事を説明します。2/4になる事を利用して、円周率の近似値を計算できる事を説明しました。軸が囲む面積を長方形で近似する事により、定積分を近似計算するプログラムの例を挙げました。前回の記事を読み返さなくてもいい様に、定積分の近似計算のアイデアを書いた図と、例示したC++のプログラムを、以下に再掲します。maxは、黄色の長方形の面積の和で求めた円周率で、実際の円周率は、このmaxよりも必ず小さくなります。minは、図の水色の長方形の面積の和で求めた円周率で、実際の円周率は、このminよりも必ず大きくなります。aveは、minとmaxの平均値で、円周率の推測値になります。これで円周率の近似計算を行えるようにはなったのですが、浮動小数点で計算している所や、平方根の計算をしている所などが不満です。パソコンで計算する場合も、これらの重い計算が含まれていると、実行時間が長くなります。ハードウェアに実装する場合は、部品数が増えてしまいます。整数計算によるアルゴリズムそこで、浮動小数点の計算を排除し、整数だけで定積分を行う方法を考えます。同時に平方根の計算をしないで済む方法も考えます。個に分割する話をしました。この操作により、定積分の近似精度が若干下がるものの、整数だけで計算できる様になります。軸方向にも領域を分割するアルゴリズムの大まかな考え方を表したのが上の図です。1/4円内にあるコマの数を数えれば、1/4円の面積の近似値が求まります。1/4円内にあるコマの数を数える時に、コマ全体が1/4円内にある場合のみにコマを数える消極的な手法を取れば、1/4円の面積を小さめに見積もります。=7の場合について作図した物ですが、水色のコマが30個あるので、半径7の1/4円の面積を30と見積もった事になります。半径7の1/4円の正確な面積はπ×72/4≒38.5ですから、確かに面積を8.5だけ小さめに見積もっています。コマの一部にでも1/4円が入っていればコマを数える積極的な手法を取れば、1/4円の面積を大きめに見積もります。上の図の例では、黄色いコマが43個ありますので、半径7の1/4円の面積を43と見積もった事になります。正確な1/4円の面積よりも43-38.5=4.5だけ大きめに見積もっています。=7の場合について、円周率の近似値を計算してみましょう。水色コマで表わした消極的な手法でコマの数を数えたケースですが、1/4円の面積を30と見積もったので、これから円周率の近似値を計算すると、30×4/72≒2.449になります。正確な数ではありませんが、これで円周率が2.449より大きい事が数学的に証明できたことになります。次に、黄色のコマで表わした積極的な手法でコマの数を数えたケースですが、1/4円の面積を43と見積もったので、これから円周率の近似値を計算すると、43×4/72≒3.510になります。これで、円周率が3.510より小さい事が数学的に証明できた事になります。消極的な手法では必ず円周率を実際の値より小さく見積もり、積極的な手法では必ず円周率を実際の値より大きく見積もりますので、それらの値の平均を取れば、より真の円周率に近い値を推測できる事になります。参考:消極的な手法で求めた円周率の近似値と、積極的な手法で求めた円周率の近似値の平均を取るという操作は、定積分の際に、1/4円の中に完全に収まっているコマの面積を1とし、1/4円の中に部分的に収まっているコマの面積は、(実際に1/4円に収まっている部分の面積が0~1の値を取るのを無視して、)一律0.5とみなして計算し、そうして求めた1/4円の面積から円周率を推測するという事に相当します。実際に、消極的な手法と積極的な手法による円周率の推測値の平均を取ると2.980と、より実際の円周率(3.141592・・・)に近い値になっています。参考:前回紹介した最初のプログラムを、Rを7に書き換えて実行すると、実際にmax:3.51020408163265、min:2.44897959183673、ave:2.97959183673469と、ここで紹介したのと同じ値が表示されます。前回の記事のページ上でプログラムを動作させられますので、興味がある方は、是非試してください。大きな値に設定すると、積極的な手法で推測した円周率の値と消極的な手法で推測した円周率の値が近づき、より正確に円周率を推定できる様になります。大きくなると、正確な作図が困難になります。この場合、数式により、純粋に数学的な手法で各コマが1/4円の内部にあるかどうかを判定する事になります。その際に、コマの全体が1/4円の内部にあるケースコマの全体が1/4円の外部にあるケースコマの一部が1/4円の内部にあるケースの3種類を区別できないと、消極的な手法と積極的な手法を使い分けて、円周率の推測値の上限と下限を決める事ができません。扱う関数が第1象限の1/4円弧と、単調減少の単純な関数のため、これから説明する方法で、前述の3つのケースを判別する事ができます。減る関数)なので、コマの全体が1/4円内にあるかどうかは、コマの右上の隅の座標が1/4円内にあるかどうかを判定するだけで、コマ全体が1/4円内にある事を確認できます。(下図参照)コマの全体が1/4円の内部にあるかどうかは右上の隅の座標が1/4円内にあるかどうかで判断できる単調関数ではない一般の関数の場合、その関数の図形内にコマがあるかどうかは、コマ内のどこか1点が図形内にあるかどうかを調べても判断できませんので、厄介です。(下図参照)単調でない関数の場合はコマ全体が図形内にある事を保証するのが難しいコマの全体が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円の外部にあります。コマの一部が1/4円内にあり別の一部が1/4円外にある事の判定法コマが1/4円の内部にあるか外部にあるかの判定法のまとめ以上のように、コマの一部または全体が1/4円の内部にあるか、外部にあるかを判定するには、コマの左下隅および右上隅の座標が1/4円の内部にあるか、外部にあるかを調べればよい事が分かりました。この判定法を表にまとめると、次の様になります。前節で、コマの左下隅と右上隅の座標が1/4円の内部にあるかどうかを調べれば、コマの一部または全部が、1/4円の内部にあるかどうかを判定できる事を説明しました。次に、特定の座標(x,y)が与えられた時に、その点が1/4円の内部にあるかを調べる方法について考えます。前回の式(2)で説明したとおり、半径Rの1/4円の円弧上の点は、次の式を満たします。)が1/4円の内部にあるか外部にあるかが判定できます。)が1/4円の内部にあるか、外部にあるかは、数式により明確に判定できます。)が円弧上にぴったり乗っている場合に、この点が1/4円の内部にあると考えるべきか、外部にあると考えるべきかについて説明します。しなぷす電子工作サイトしなぷすのハード製作記の管理人です。フリーランスのエンジニアですが、大学の非常勤講師もやっています。コメントをキャンセルメールアドレスが公開されることはありません。※サイト次回のコメントで使用するためブラウザーに自分の名前、メールアドレス、サイトを保存する。自己紹介しなぷす電子工作サイトしなぷすのハード製作記の管理人です。フリーランスのエンジニアですが、大学の非常勤講師もやっています。