OBEB için Özyinelemeli Öklid Algoritmaları

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.