Yazan  : Şadi Evren ŞEKER

Matematikte çok sık kullanılan OBEB (ortak bölenlerin en büyüğü, greatest common divisor, gcd) hesaplamak için öklit’in geliştirdiği bir metottur. Uzatılmış öklit (extended euclid) algoritmasının temelini oluşturur.

Buna göre iki sayının ortak bölenlerinin en büyüğü iki sayı birbirini tam olarak bölene kadar iki sayının birbirinden çıkarılması ile elde edilebilir.

Örneğin sayılarımı 75 ve 30 olsun. Adım adım aşağıdaki işlemler izlenir

75 , 30’a bölünür mü? hayır o halde bölümden kalanı bul

75 mod 30 = 15

30, 15’e tam bölünür mü?  evet o halde en büyük ortak bölen 15’tir.

Bu işlemler sırasında dikkat edilecek bir nokta her zaman büyük sayıyı küçük sayıya bölmeye çalışmak ve çıkarma işlemi sonunda elde edilen en küçük iki sayıyı almaktır.

C dilinde bu çözüm aşağıdaki şekilde kodlanabilir:

int gcd(int a, int b) 
{ 
   return ( b == 0 ? a : gcd(b, a % b) ); 
}

Yorumlar

  1. Şadi Evren ŞEKER Article Author

    Öklit algoritması, iki sayının ortak bölenlerinin en büyüğünü bulur. Bu durumda iki sayının aralarında asal olması için, ortak bölenlerinin en büyüğünün (GCD, greatest common divisor) 1 olması gerekir.

    Aralarında asal (relatively prime) testi için uygun olan öklit algoritmasını, bir sayının asal olup olmadığını bulmak için kullanıyorsanız, bu durumda bir sayının kare köküne kadar olan sayılarla aralarında asal olup olmadığını bulmak için kullanabilirsiniz.

    Örneğin 47 sayısı asal mı?
    47’nin karekökü 6 ve küsurdur. Demek ki 2,3,4,5,6 sayıları ile teker teker öklit algoritması kullanılarak test edilir ve hepsinden sonuç 1 çıkarsa 47 sayısı asaldır denilebilir. Bir tanesinden sonuç 1’den büyük çıkarsa, sayı asal değildir denilebilir.

  2. ali

    Hocam paylaşımlarınız için teşekkür ederim peki bu algoritmanın rekürsif denklemini bulabilirmiyiz?
    çünkü her seferinde a ile b degişkenlerinin ne kadar değişeceğini bilemedim cevabınız için şimdiden teşekkür ederim

  3. ali

    Hocam soruma cevap verdiğiniz için teşekkür ederim benim sormak istediğim mesala
    recursive olarak faktöriyeli hesaplarken genel recursive denklemi T(n)=T(n-1)+1 peki bu algoritmadan da böyle bir denklem çıkartabilirmiyiz fonksiyon kendini çağırırken a ve b nin kaçar değiştiğini bilemiyorum şimdiden teşekkür ederim

  4. Şadi Evren ŞEKER Article Author

    Elbette yazabiliriz. Bir iki noktayı açıklayarak başlayalım. Öncelikle yukarıdaki öklit algoritmasının karmaşıklığı logaritmiktir ve O(lg n) şeklinde yazılabilir.
    Bunun sebebi aşağıdaki formda yazılan bir denklem olmasındandır:

    T(n) = T(n/a) + b

    Diğer bir deyişle sorumuzu şu şekilde soralım, acaba iki sayının ortak bölenlerinin en büyüğünü, yukarıdaki şekilde özyineli olarak (recursive) hesaplama işlemi kaç adımda biter?

    Basit bir örnek ile konuyu anlatalım:

    gcd(70,30) = gcd ( 30, 10) = gcd (10,0) –> 10 olarak bulunur.

    görüldüğü üzere 3 adımda bulduk. Sorumuz şu, 70 sayısı sabit olmak üzere, fonksiyonumuzun ikinci parametresi ne olursa, bu bulma işlemi daha uzun sürer?

    Farklı bir örnek deneyelim:

    gcd( 70 , 57) = gcd ( 57 , 13 ) = gcd ( 13 , 5 ) = gcd ( 5 , 3 ) = gcd ( 3 , 2) = gcd ( 2 , 1) = gcd ( 1, 0) = 1

    iki şeyi gördük, birincisi sayılar aralarında asal olmalı ki çalışma uzun sürsün. İkincisi sayılar arasındaki farkın uzun sürmesi için ilk sayımızın yaklaşık olarak 2/3 değerine yakın bir değer olmalı. Bu koşulları ayrı ayrı ele alırsak:

    gcd ( 70 , 55 ) = gcd ( 55, 15 ) = gcd( 15 , 10 ) = gcd ( 10,5 ) = gcd( 5,0 ) = 5 , 2/3 koşulu için
    gcd ( 70 , 69 ) = gcd ( 69, 1 ) = gcd ( 1, 0 ) = 1 , aralarında asal şartı için

    görüldüğü üzere koşulları ayrı ayrı ele alırsak sonuç daha hızlı bulunuyor.

    Bunun sebebi problem uzayının her seferinde parçalanarak gitmesi ve en uzun çalışma için bizim parçalama işleminden sonra daha büyük parçalar üzerinde çalışmamız gerekir.

    Buradan çıkardığımız sonuç, n değerinin her seferinde bölünerek gittiğidir. Klasik bir özyineli denklem (recursive equation) aşağıdaki şekilde yazılabilir:

    T(n) = T(n/b) + c

    buradaki b değer, başlangıç sayısına göre değişmektedir. Örneğin 70 ve 30 sayıları için farklı veya 70 ve 35 sayıları için daha farklı bir b değeri olur. Denklemdeki c değerini ise 1 olarak kabul edebiliriz. Yani her bölme işlemi bir işlemdir ve toplam işlem sayısı n değeri 1 olana kadar gider.

    Yukarıdaki denkleme göre, karakteristik eşitlikten (characteristic equation) algoritmamızın karmaşıklığının O(log n) olduğunu söyleyebiliriz. Buradaki logaritma teriminin tabanı b değerinde olmalıdır ama b değeri her denklemde değişmektedir. Dolayısıyla öklit’in en büyük ortan bölen denklemi için kesin bir özyineli eşitlik (recursive equation) yazmak mümkün olmamakla birlikte, yukarıda anlatmaya çalıştığım üzere genel bir denklem (generic equation) yazılabilir.

    Başarılar

  5. yeşilbrlu

    2x^4-x^3+x^2+3x+1 ve 2x^3-3x^2+2x+2 polinomlarını lineer kombinasyosyon şeklinde nasıl gösterebiliriz.
    (İlk önce Öklid algoritmasını kullanarak OBEB değerlerini buldum. bir hatam olmadıysa OBEB değeri x-1 çıkıyor. şimdi bunları linner kombinasyon şeklinde nasıl gösterebilirim hocam… birde lineer kombinasyonla bu ifadeyi göstermek ne işimize yarar ki… en sonki sorum bu soru için değil programlamada ne gibi avantaj sağlar bizlere… neyi kolaylaştırıyor acaba…)

  6. Şadi Evren ŞEKER Article Author

    OBEB değerini bularak da olabilir. Öncelikle büyük resmi görelim.

    Linear combinations, bir polynom’un (çok terimli) çarpanları demektir. Bu çarpanlar bize bir polinom’u daha basit formlarda gösterebilme imkanı sağlar. Hatta çarpanlarını kullanarak bir katsayı matrisi elde edilebilir ve problem bir matris işlemeye bie dönüştürülebilir (örneğin bilgisayar grafiklerinde oldukça faydalı bir durumdur).

    Ayrıca klasik linear algebra (doğrusal cebir) problemleri bir polinom’un diğer polinomler cinsinden verilmesi olarak çıkar. Sizin sorunuz eksik gibi.

    Yani sizin verdiğiniz x-1 polinom’unun OBEB olabilmesi için iki polinom’u da bölebilmesi gerekir. Ben yanlış hesaplamadıysam ilk polinumu kalansız bölmüyor (böldüğümde 6 kalanı çıkıyor).

    Ancak P1 = 2x4-x3+x2+3x+1
    olmak üzere
    P1 = (2x + 1)(x3 – x2 + x + 1) şeklinde yazılabilir.

    Ayrıca P2= 2x3-3x2+2x+2
    P2 = (2x + 1)(x2 – 2x + 2) şeklinde yazılabilir.

    Demek ki gcd (P1,P2) = (2x+1) ‘dir denilebilir.

    Yukarıdaki P1 ve P2 açılımları da ikişer polinomun çarpımı şeklinde gösterilmiş olan doğrusal kombinasyonlardır denilebilir.

    Yine de genelde 3 adet polinomun lineer kombinasyonu olarak yazıp 3 boyutlu düzlemden göstermek şeklinde genel bir kanı vardır. Ancak benim bilmediğim kullanım alanları olabilir.

    Yazının burasında sizin için hızlı bir araştırma yaptım. Springer’dan aşağıdaki makaleye bir bakmanızda yarar olabilir (makale open access dolayısıyla sanırım erişiminizde sorun olmaz):

    http://link.springer.com/article/10.1007%2Fs00365-013-9183-5

    Kısaca kullanım alanları olarak, dalga fonksiyonları ile kestirim, öğrenme teorisi ve tomografi gibi alanlar bu makalede sayılmış.

    Genelde böyle temel cebirsel işlemlerin çok sayıda kullanım alanı olmaktadır.

    Başarılar

Şadi Evren ŞEKER için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir