とりあえずメモメモ。

2の平方根をけいさん!

プログラミング | 22:07 |

2の平方根とは

面積2の正方形の一辺を求めること。x^2 = 2のxを求める。

某巨大掲示板の某スレッドがにぎわっていたので、色々調べてみましたところ、本当に色々ありました。勉強になったのでまとめてみました。

参考:

1. 2の平方根 - Wikipedia

wolfram alpha

ウルフラムアルファさんに聞いてみます。

1.414213562373095048801688724209698078569671875376948073

1766797379907324784621070388503875343276415727

http://www.wolframalpha.com/input/?i=N%5Bsqrt%5B2%5D%2C101%5D

ニュートン法

x^2 = 2 の右項を左に移して、x^2 - 2 = 0 の方程式を解くことでxを求めます。メジャーな方法です。

use strict;
use warnings;
use bignum p => -110;

my $e = 10 ** -100;

my $x = 2;
my $x_1;
do{
	$x_1 = $x;
	$x = ($x + 2 / $x) / 2;
}while(abs(($x - $x_1) / $x_1) > $e);

print $x;

1.414213562373095048801688724209698078569671875376948073

17667973799073247846210703885038753432764157273501384623

参考:

1. ニュートン法による平方根の計算

連分数を利用

√2を連分数にすると1+1/(2+1/(2+1/...))と、再帰する形になりますので、最初の1を無視して1/(2+1/...)を計算をした後に、1を足せば√2と等しくなります。

use strict;
use warnings;
use bignum p => -110;

my $e = 10 ** -100;

my $x = 0;
my $x_1;
do{
	$x_1 = $x;
	$x = 1 / (2 + $x);
}while(abs(($x - $x_1) / $x_1) > $e);
$x += 1;

print $x;

1.414213562373095048801688724209698078569671875376948073

17667973799073247846210703885038753432764157273071637781

参考:

1. 白銀比 - Wikipedia
2. 数学って面白い！？ : 賭博覇王伝　零 - livedoor Blog（ブログ）

開平方

(x^2)の漸化式はx(n+1) = x(n)+2n+1で、1,3,5,7..という奇数の等差数列になります。平方根を求めたい数から1,3,5,7を順番に引いて行き、引けなくなった所の引いた回数が一桁の平方根になります。次の桁は元の数を100倍、引く数は前の桁の答えを2倍したものを加え10倍にして、順番に求めていきます。

整数の加減算と桁のシフトだけで求まるため、単純な計算機でも求めることができるのが面白いところです。

use strict;
use warnings;
use bigint;

my $d = 0;
my $x = 2;

my @l;
foreach(0..100){
	my $c;
	for($c = 0; $c < 9; $c++){
		my $dx = $x - ($d + 2 * $c + 1);
		($dx < 0) and last;
		$x = $dx;
	}
	$x *= 100;
	$d = ($d + 2 * $c) * 10;
	push(@l, $c);
}

print @l;

1414213562373095048801688724209698078569671875376948073

1766797379907324784621070388503875343276415727

参考:

1. 平方根の求め方
2. http://www3.ocn.ne.jp/~kokoten/sangikeisan4.htm
3. no title