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) ); }
Öklit algoritmasına dayanarak bir sayının asal olup olmadığını test edebilirmiyiz ?
Ö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.
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
Yazıda verilen öklit algoritması zaten özyineli (recursive) yapıdadır. Kast ettiğiniz farklı birşey ise belki biraz açıklarsanız yardımcı olabilirim.
başarılar
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
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
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…)
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
iyi gunler Hocam
sorum o ki : ÖKlit algoritmasının recursive ve non -recursıve şeklindeki en geniş numarası kaçtır?