Bilinen en eski algoritmalardan biri, iki sayının OBEB(ortak bölenlerin en büyüğü)'ini bulan Öklid(Euclid) Algoritması'dır. MÖ 300 yılında Öklid'in bir kitabında geçtiği bilinmektedir. Öklid Algoritması şifrebilimin önemli algoritmalarından RSA Algoritması'nda, Diofant denklemlerinin (Diophantine Equations) çözümünde, sayılar kuramındaki bazı kuramların kanıtlanmasında kullanılmakta.
Ayrıca Genişletilmiş(Extended) Öklid Algoritması denilen algoritma ile sadece OBEB'i değil, OBEB(a,b) = ax + by denklemindeki x ve y tam sayıları da bulunabiliyor.
Aldığım derslerden birinde 0 ile 2^64 -1 arasındaki pozitif tam sayılar için geçerli olacak şekilde bu algoritmaların kodunun yazılması ödev olarak verilmişti. C++ ile yazdım; ancak geç gönderdiğim için benim çözümler değerlendirilmedi. Ben de yazdığım kodları burada paylaşarak değerlendireyim dedim. İki algoritmanın özyinelemeli (recursive) biçimlerini aşağıda paylaşıyorum.
Özyinelemeli Öklid Algoritması
Wikipedia'da Özyinelemeli Öklid Algoritması için verilen sözde kod(pseudocode) şu şekilde
function gcd(a, b)
if b = 0
return a
else
return gcd(b, a mod b)
Benim çözümüm şu şekilde:
...
typedef unsigned long long int PozitifTamSayi;
...
//Oklid(a,b)
//Özyinelemeli Öklid Algoritması kullanarak OBEB bulma algoritması
PozitifTamSayi Oklid(PozitifTamSayi a,PozitifTamSayi b)
{
if (a == 0)
return b;
if (b == 0)
return a;
if (a > b)
return Oklid(a % b, b);
else
return Oklid(a, b % a);
}
Özyinelemeli Genişletilmiş Öklid Algoritması
Wikipedia'da Özyinelemeli Genişletilmiş Öklid Algoritması için verilen sözde kod(pseudocode) şu şekilde:
function extended_gcd(a, b)
if b = 0
return (1, 0)
else
(q, r) := divide (a, b)
(s, t) := extended_gcd(b, r)
return (t, s - q * t)
Benim çözümüm şu şekilde:
...
typedef long long int TamSayi;
...
//GenisletilmisOklid(a,b)
//Özyinelemeli Genişletilmiş Öklid Algoritması kullanarak
//ax + by = OBEB(a,b) şeklindeki denklemden OBEB, x ve y bulma algoritması
//işaretçi(dizi) döndürür
TamSayi* GenisletilmisOklid(TamSayi a, TamSayi b){
TamSayi* sonuclar=new TamSayi[3];
TamSayi q,r;
if (b == 0)
{
sonuclar[0]=a;
sonuclar[1] = 1;
sonuclar[2]=0;
}
else
{
q = a/b;
r = a%b;
sonuclar= GenisletilmisOklid(b,r);
int gecici= sonuclar[1] - sonuclar[2]*q;
sonuclar[1] = sonuclar[2];
sonuclar[2] = gecici;
}
return sonuclar;
}
Kaynaklar
- Wikipedia, Euclidean Algorithm, http://en.wikipedia.org/wiki/Euclidean_algorithm.
- Wikipedia, Extended Euclidean Algorithm, http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm.
