[明らかなものの非自明なアルゴリズム]アルゴリズム1.平方根

一連の投稿[明白ではないものの非自明なアルゴリズム]には、明白で単純に見えるアクションのアルゴリズムが含まれますが、「これはどのように行われますか？」 もちろん、これらのアルゴリズムはすべて文献に記載されています。 カットの下には、平方数Xの根を計算するアルゴリズムがあります。

X平方根

アイデア

長方形は、辺a = 1およびb = Xで形成されます。 この長方形の面積はS = a * b = X * 1 = Xです。長方形を正方形に変換してその面積が同じになるようにすると、辺の長さは図の正方形の平方根に等しくなり、Xに等しくなります。

長方形から正方形への変換の各反復は、次のように実行されます。

S = a ₀ b ₀ ;

現在の四角形の辺の算術平均に等しい1つの辺を持つ新しい四角形が作成されますが、面積は同じです。

S = a ₁ b ₁ 、ここでa ₁ =（a ₀ + b ₀ ）/ 2、およびb ₁ = S / a ₁

S = a ₂ b ₂ 、ここでa ₂ =（a ₁ + b ₁ ）/ 2、およびb ₂ = S / a ₂

...

S = a _n b _n 、ここでa _n =（a _n-1 + b _n-1 ）/ 2、およびb _n = S / a _n

以下同様に| a _n -b _n | <例

機能コード

#define EPS 1e-10 float my_sqrt(float x){ float S=x, a=1,b=x; while(fabs(ab)>EPS){ a=(a+b)/2; b = S / a;} return (a+b)/2; }