質問
C# を使用して PI の値を計算するにはどうすればよいですか?
再帰関数を使用するのではないかと考えていましたが、再帰関数を使用する場合、それはどのようなものになりますか?また、それを裏付ける数式はありますか?
私はパフォーマンスについてはあまりうるさくはなく、主に学習の観点からどのように対処するかについて考えています。
解決
再帰が必要な場合:
PI = 2 * (1 + 1/3 * (1 + 2/5 * (1 + 3/7 * (...))))
いくつか書き直すと、これは次のようになります。
PI = 2 * F(1);
F(i) の場合:
double F (int i) {
return 1 + i / (2.0 * i + 1) * F(i + 1);
}
アイザック・ニュートン (彼については以前に聞いたことがあるかもしれません ;) ) がこのトリックを思いつきました。わかりやすくするために、終了条件を省略していることに注意してください。実生活では、ある程度必要です。
他のヒント
以下を使用してみてはいかがでしょうか:
double pi = Math.PI;
それよりも高い精度が必要な場合は、アルゴリズム システムと Decimal タイプを使用する必要があります。
この非常に優れたガイドをよく読んでみると、次のようになります。
並列プログラミングのパターン:.NET Framework 4 を使用した並列パターンの理解と適用
70 ページに、このかわいい実装が見つかります (私の側から若干の変更を加えています)。
static decimal ParallelPartitionerPi(int steps)
{
decimal sum = 0.0;
decimal step = 1.0 / (decimal)steps;
object obj = new object();
Parallel.ForEach(
Partitioner.Create(0, steps),
() => 0.0,
(range, state, partial) =>
{
for (int i = range.Item1; i < range.Item2; i++)
{
decimal x = (i - 0.5) * step;
partial += 4.0 / (1.0 + x * x);
}
return partial;
},
partial => { lock (obj) sum += partial; });
return step * sum;
}
ここに記載されていないことに驚いた、本当に本当に古いトリックがいくつかあります。
atan(1)== pi/4、したがって、信頼できるアークタンゲント関数が存在するときの古い栗は4*atan(1)です。
古い西部の22/7が汚れのように見えるようにする非常にかわいい固定比率の推定値は355/113であり、これはいくつかの小数点に適しています(少なくとも3つまたは4つはそうだと思います)。場合によっては、整数演算にはこれで十分な場合もあります。355 を掛けて、113 で割ります。
355/113 も記憶に定着しやすいです (とにかく一部の人にとって)。1、1、3、3、5、5 と数えて、分母と分子の数字に名前を付けていることを忘れないでください (どの 3 つが一番上に来るかを忘れたとしても、通常は 1 マイクロ秒考えればすぐに解決します)。
22/7 では次のことが得られることに注意してください。3.14285714、これは千の位が間違っています。
355/113 は 3.14159292 となり、1,000 万分の 1 までは間違っていません。
準拠私のボックスの /usr/include/math.h に、M_PI は次のように #define されます。3.14159265358979323846これは、おそらく行く限り良いことです。
PIを推定することで得られる教訓は、それを行う方法がたくさんあり、完璧なものはなく、使用して使用することで整理する必要があるということです。
355/113 は中国の古い推定値で、22/7 より何年も前の数字だと私は考えています。学生時代に物理学の教授から教えてもらいました。
さまざまなアルゴリズムの概要:
最初のリンクでガウス・ルジャンドル・サラミンアルゴリズムについて主張されている複雑さについてはわかりません (O(N log^2(N) log(log(N))) だと思います。
試してみることをお勧めしますが、収束は 本当に 速い。
また、非常に単純な手続き型アルゴリズムを再帰型アルゴリズムに変換しようとする理由もよくわかりません。
パフォーマンスに興味がある場合は、制限された精度で作業することに注意してください (通常、「double」、「float」などが必要です)。このような場合の明白な答えは値をハードコードするだけであるため、実際には意味がありません。
C# での PI の計算に関する記事は次のとおりです。
PIとは何ですか?円の円周を直径で割ったもの。
コンピュータ グラフィックスでは、初期点 x、y から 0,0 を中心とする円をプロット/描画できます。次の点 x'、y' は、簡単な公式を使用して見つけることができます。x' = x + y / h :y' = y - x' / h
h は通常 2 の累乗なので、シフト (または double の指数から減算) で簡単に除算を行うことができます。h も円の半径 r にする必要があります。簡単な開始点は、x = r、y = 0 から、x <= 0 になるまでステップ数 c を数えて円の 4 分の 1 をプロットすることです。PI は 4 * c/r または PI は 4 * c/h
非常に深い再帰は商用プログラムでは通常非現実的ですが、末尾再帰を使用すると、ループとして実装しながらアルゴリズムを再帰的に表現できます。再帰的検索アルゴリズムは、プロセスのスタックではなくキューを使用して実装される場合があります。検索は行き止まりからバックトラックして別のパスをたどる必要があります。これらのバックトラック ポイントはキューに入れることができ、複数のプロセスがポイントのキューを解除して試行することができます。他の道。
次のように計算します。
x = 1 - 1/3 + 1/5 - 1/7 + 1/9 (... etc as far as possible.)
PI = x * 4
あなたは円周率を持っています!!!
これは私が知っている中で最も簡単な方法です。
PI の値は、徐々に実際の Pi の値 (3.141592165....) に収束します。反復回数が多ければ多いほど良いです。
これは素晴らしいアプローチです(から 円周率に関するウィキペディアのメインエントリ);これは、上で説明した単純な式よりもはるかに速く収束し、学習演習として再帰を追求することを目的とする場合は、再帰的解法に非常に適しています。(学習体験を終えていることを前提として、実際のコードは示しません。)
基本的な式は上記と同じですが、このアプローチでは部分和を平均して収束を加速します。
次のような 2 つのパラメーター関数 pie(h, w) を定義します。
pie(0,1) = 4/1
pie(0,2) = 4/1 - 4/3
pie(0,3) = 4/1 - 4/3 + 4/5
pie(0,4) = 4/1 - 4/3 + 4/5 - 4/7
... and so on
したがって、再帰を検討する最初の機会は、「幅」パラメータが増加するにつれて (「高さ」がゼロの場合)、その「水平」計算をコード化することです。
次に、次の式を使用して 2 番目の次元を追加します。
pie(h, w) = (pie(h-1,w) + pie(h-1,w+1)) / 2
もちろん、これは h の値が 0 より大きい場合にのみ使用されます。
このアルゴリズムの優れた点は、スプレッドシートを使用して簡単にモックアップして、徐々に大きくなるパラメータによって生成される結果を調べながらコードをチェックできることです。pie(10,10) を計算するまでに、ほとんどのエンジニアリング目的に十分な pi の近似値が得られます。
Enumerable.Range(0, 100000000).Aggregate(0d, (tot, next) => tot += Math.Pow(-1d, next)/(2*next + 1)*4)
using System;
namespace Strings
{
class Program
{
static void Main(string[] args)
{
/* decimal pie = 1;
decimal e = -1;
*/
var stopwatch = new System.Diagnostics.Stopwatch();
stopwatch.Start(); //added this nice stopwatch start routine
//leibniz formula in C# - code written completely by Todd Mandell 2014
/*
for (decimal f = (e += 2); f < 1000001; f++)
{
e += 2;
pie -= 1 / e;
e += 2;
pie += 1 / e;
Console.WriteLine(pie * 4);
}
decimal finalDisplayString = (pie * 4);
Console.WriteLine("pie = {0}", finalDisplayString);
Console.WriteLine("Accuracy resulting from approximately {0} steps", e/4);
*/
// Nilakantha formula - code written completely by Todd Mandell 2014
// π = 3 + 4/(2*3*4) - 4/(4*5*6) + 4/(6*7*8) - 4/(8*9*10) + 4/(10*11*12) - (4/(12*13*14) etc
decimal pie = 0;
decimal a = 2;
decimal b = 3;
decimal c = 4;
decimal e = 1;
for (decimal f = (e += 1); f < 100000; f++)
// Increase f where "f < 100000" to increase number of steps
{
pie += 4 / (a * b * c);
a += 2;
b += 2;
c += 2;
pie -= 4 / (a * b * c);
a += 2;
b += 2;
c += 2;
e += 1;
}
decimal finalDisplayString = (pie + 3);
Console.WriteLine("pie = {0}", finalDisplayString);
Console.WriteLine("Accuracy resulting from {0} steps", e);
stopwatch.Stop();
TimeSpan ts = stopwatch.Elapsed;
Console.WriteLine("Calc Time {0}", ts);
Console.ReadLine();
}
}
}
public static string PiNumberFinder(int digitNumber)
{
string piNumber = "3,";
int dividedBy = 11080585;
int divisor = 78256779;
int result;
for (int i = 0; i < digitNumber; i++)
{
if (dividedBy < divisor)
dividedBy *= 10;
result = dividedBy / divisor;
string resultString = result.ToString();
piNumber += resultString;
dividedBy = dividedBy - divisor * result;
}
return piNumber;
}
どのような運用シナリオでも、必要な小数点以下の桁数まで値を検索し、クラスがアクセスできる場所に「const」として保存する必要があります。
(科学的な「Pi」専用のソフトウェアを作成している場合を除きます...)
に関して...
...学習の観点からどのように取り組むか。
科学的手法のプログラミングを学ぼうとしていますか?それとも製品版ソフトウェアを作成しますか?コミュニティがこれをつまらない質問ではなく、正当な質問として捉えてくれることを願っています。
いずれの場合でも、独自の Pi を作成することで問題は解決されたと思います。Dmitry はすでに「Math.PI」定数を示しました。同じ空間で別の問題に挑戦してください!一般的なニュートン近似または洗練されたものを使用してください。
@トーマス・カムマイヤー:
Atan(1.0) は非常に多くの場合ハードコーディングされているため、ライブラリ Atan 関数を呼び出す場合、4*Atan(1.0) は実際には「アルゴリズム」ではないことに注意してください (かなりの数の関数がすでに提案されており、Atan(x) をそれに対する系列 (または無限積) を作成し、それを x=1 で評価します。
また、 数十ビットよりも高い精度の pi が必要になるケースはほとんどありません。 (これは簡単にハードコーディングできます!)。私は数学のアプリケーションに取り組んできましたが、いくつかの (非常に複雑な) 数学的オブジェクト (整数係数を持つ多項式) を計算するには、実数と複素数の算術演算 (円周率の計算を含む) を最大 1 桁の精度で実行する必要がありました。数百万ビット...しかし、これは「実生活では」あまり頻繁ではありません:)
次の例を調べることができます コード.
好き この紙, では、逆正接のテイラー級数展開に基づいて π を計算する方法を説明します。
この論文は次のような単純な仮定から始まります。
Atan(1) = π/4 ラジアン
Atan(x) はテイラー級数を使用して反復的に推定できます。
atan(x) = x - x^3/3 + x^5/5 - x^7/7 + x^9/9...
この論文では、これが特に効率的ではない理由を指摘し、この技術に多くの論理的な改良を加えています。また、必要な無限精度の数学ルーチンを含むソース コードを備えた、π を数千桁まで計算するサンプル プログラムも提供します。
次のリンクは、積分としての定義に基づいて pi 定数を計算する方法を示しており、これは合計の極限として記述することができ、非常に興味深いものです。https://sites.google.com/site/rcorcs/posts/calculationthepicconstantファイル「積分としての Pi」では、この投稿で使用したこの方法について説明しています。
まず、C# は .NET Framework の Math.PI フィールドを使用できることに注意してください。
https://msdn.microsoft.com/en-us/library/system.math.pi(v=vs.110).aspx
ここでの優れた特徴は、これが完全精度の double であり、使用したり、計算結果と比較したりできることです。その URL のタブには、C++、F#、および Visual Basic の同様の定数があります。
より多くの桁を計算するには、独自の拡張精度コードを作成できます。コードをすばやく作成でき、適度に高速かつ簡単にプログラムできるものは次のとおりです。
Pi = 4 * [4 * arctan (1/5) - arctan (1/239)]
この公式と、項ごとに 50 桁など、驚くほど速い速度で収束するものを含む他の多くの公式が Wolfram にあります。
円周率(π) を使用して計算できます 無限シリーズ. 。以下に 2 つの例を示します。
グレゴリー・ライプニッツ系列:
π/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ...
C# メソッド:
public static decimal GregoryLeibnizGetPI(int n)
{
decimal sum = 0;
decimal temp = 0;
for (int i = 0; i < n; i++)
{
temp = 4m / (1 + 2 * i);
sum += i % 2 == 0 ? temp : -temp;
}
return sum;
}
ニラカンタ シリーズ:
π = 3 + 4 / (2x3x4) - 4 / (4x5x6) + 4 / (6x7x8) - 4 / (8x9x10) + ...
C# メソッド:
public static decimal NilakanthaGetPI(int n)
{
decimal sum = 0;
decimal temp = 0;
decimal a = 2, b = 3, c = 4;
for (int i = 0; i < n; i++)
{
temp = 4 / (a * b * c);
sum += i % 2 == 0 ? temp : -temp;
a += 2; b += 2; c += 2;
}
return 3 + sum;
}
入力パラメータ n
どちらの関数でも、 は反復回数を表します。
ニラカンタ級数は、グレゴリー・ライプニッツ級数と比較して、より速く収束します。メソッドは次のコードでテストできます。
static void Main(string[] args)
{
const decimal pi = 3.1415926535897932384626433832m;
Console.WriteLine($"PI = {pi}");
//Nilakantha Series
int iterationsN = 100;
decimal nilakanthaPI = NilakanthaGetPI(iterationsN);
decimal CalcErrorNilakantha = pi - nilakanthaPI;
Console.WriteLine($"\nNilakantha Series -> PI = {nilakanthaPI}");
Console.WriteLine($"Calculation error = {CalcErrorNilakantha}");
int numDecNilakantha = pi.ToString().Zip(nilakanthaPI.ToString(), (x, y) => x == y).TakeWhile(x => x).Count() - 2;
Console.WriteLine($"Number of correct decimals = {numDecNilakantha}");
Console.WriteLine($"Number of iterations = {iterationsN}");
//Gregory-Leibniz Series
int iterationsGL = 1000000;
decimal GregoryLeibnizPI = GregoryLeibnizGetPI(iterationsGL);
decimal CalcErrorGregoryLeibniz = pi - GregoryLeibnizPI;
Console.WriteLine($"\nGregory-Leibniz Series -> PI = {GregoryLeibnizPI}");
Console.WriteLine($"Calculation error = {CalcErrorGregoryLeibniz}");
int numDecGregoryLeibniz = pi.ToString().Zip(GregoryLeibnizPI.ToString(), (x, y) => x == y).TakeWhile(x => x).Count() - 2;
Console.WriteLine($"Number of correct decimals = {numDecGregoryLeibniz}");
Console.WriteLine($"Number of iterations = {iterationsGL}");
Console.ReadKey();
}
次の出力は、ニラカンタ級数が 100 回の反復で PI の正しい 6 進数を返すのに対し、グレゴリー・ライプニッツ級数は 100 万回の反復で PI の 5 つの正しい小数を返すことを示しています。
私のコードはテストできます >> ここ
ここに良い方法があります:x の一連の 1/x^2 を 1 から任意の数値まで計算します。数値が大きいほど、円の結果が良くなります。結果を 6 で乗算し、sqrt() に渡します。C# のコードは次のとおりです (メインのみ)。
static void Main(string[] args)
{
double counter = 0;
for (double i = 1; i < 1000000; i++)
{
counter = counter + (1 / (Math.Pow(i, 2)));
}
counter = counter * 6;
counter = Math.Sqrt(counter);
Console.WriteLine(counter);
}
public double PI = 22.0 / 7.0;