A Perfect Night For Bananafish

だがそれを語るには人生は短すぎる

ユークリッドの互除法

wikipedia:ユークリッドの互除法:2 つの自然数または整式の最大公約数を求める手法
明示的に記述された最古のアルゴリズムだそうだ。

def gcd(a,b)
	if (a < b)
		return gcd(b,a)
	end
	r=a%b
	if (r==0)
		return b
	end
	return gcd(b,r)
end

もう少しスマートに書くと、

def gcd(a,b)
	if (b==0)
		return a
	else
		return gcd(b, a%b)
	end
end

if修飾子を使って書くとさらにコンパクトになるけど少し読みにくいかな。

def gcd(a,b)
	return a if (b==0)
	return gcd(b, a%b) else
end
  • -

whileを使って書いてみる。

def gcd(a, b)
	while (b!=0)
		t=b
		b= a%b
		a =t
	end
	return a
end

拡張されたユークリッドの互除法

am + bn = gcd(m, n) となる整数a,bの組を返す。

def ext_gcd(a,b)
	if(a%b==0)
		return [0,1]
	else
		t=ext_gcd(b,a%b)
		return [t[1],t[0]-t[1]*(a/b)]
	end
end