Karatsuba Çarpım Algoritması

Çarpma işlemi, toplama işlemine göre daha karmaşık yapılı bir işlemdir. Çarpma işleminde sola kaydırma işlemi yaparak alt alta basamak sayısı kadar işlem yapılmış olur. Yani 3 basamaklı bir sayı ile 3 basamaklı bir sayı çarpılırsa 3²=9 kadar çarpma işlemi yapılır. 

4 basamaklı bir sayı ile 4 basamaklı bir sayı çarpılırsa 4²=16 kadar çarpma işlemi yapılır. 5 basamaklı bir sayı ile 5 basamaklı bir sayı çarpılırsa 5²=25 kadar çarpma işlemi yapılır. Bu şekilde devam edildiğinde n basamaklı bir sayı ile n basamaklı bir sayı çarpılırsa n² kadar çarpma işlemi yapılır. Bu nedenle klasik çarpma algoritmasında basamak sayısı arttıkça çarpım sonucunu bulmak daha zor hale gelir. Rus Matematikçi Anatoly Karatsuba, özellikle büyük basamaklı sayıların çarpımını daha kolay hesaplamak için yeni bir çarpım algoritması yazmıştır ve bu yönteme Karatsuba Algoritması adı verilmiştir. Bu algoritmada amaç; çarpılacak sayıları alt gruplara bölerek daha az sayıda işlem yaparak sonuca ulaşmaktır. 

 

Çarpma işlemi bilgisayar aritmetiğindeki en önemli işlemlerden biridir. Karatsuba algoritması, çarpma işlemini basitleştirerek işlemlerin verimliliğini arttırmak, işlem maliyetini ve süreyi azaltmak için geliştirilen algoritmalardan biridir. Klasik yöntemde n bitlik iki tamsayının toplanması O(n) bit işlemi gerektirmektedir. İki n bitlik tamsayının çarpılması ise O(n²) bit işlemi gerektirmektedir. Karatsuba algoritması iki n bitlik sayının çarpılması için böl ve fethet (divide and conquer) tekniğini kullanır ve bu algoritmada O(n^log3) bit işlemi gerekir. Karatsuba algoritması çarpma işleminde bazı çarpmaları yapmak yerine daha az maliyetli olan toplama ve çıkarma işlemleriyle değiştirerek işlem sayısını en aza indirmeyi sağlayarak işlemlerin daha hızlı sonuca ulaştırır. Karatsuba algoritması küçük basamaklı (dijit) sayılar için klasik çarpma algoritmasından daha yavaş çalışmaktayken daha büyük basamaklı sayılar için çarpma işlemi yapıldığında daha hızlı ve verimli bir sonuç sunar.

Karatsuba algoritması çarpma işlemine göre 2 basamaklı iki sayıyı çarpmak istediğimizde, önce sayıları anlamlı bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce onlar basamağındaki iki sayıyı çarparız. (A) Sonra sayıların birler basamaklarındaki sayıları çarparız. (B) Arkasından her iki sayının da basamaklarını toplayıp bunları kendi arasında çarparız.(C) Bütün sonuçlar bulunduktan sonra her iki sayının da basamaklarını toplayıp bunları kendi arasında çarptığımız sonuçtan (C) diğer bulduğumuz iki sonucu çıkartırız. D=(C-A-B). En sonunda ayırma işlemine göre bulunan A,B ve D sonuçlarını blok içinde bulunduğu onluk bölük içinde A.10ⁿ +D.10^(n/2)+B biçiminde yazarak işlemi bitiririz. Burada klasik çarpmada 2 dijitli iki sayının çarpımında 2*2=4 işlem yapmak yerine sadece 3 çarpma işlemi yaparak daha kolay olan toplama ve çıkarma işlemleri ile sonuca ulaşılmış olur. Böylece bilgisayar programlamada büyük basamaklı sayılarda bu işlemleri yapmak zaman açısından daha verimli hale gelir.

Karatsuba algoritması çarpma işlemine göre 3 basamaklı (dijit) olarak verilen iki tane sayıyı çarpmak istediğimizde, önce sayıları anlamlı ikişerli uygun bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce bu bloklarda ayrı ayrı çarpma işlemi uygulayarak sonuca ulaşırız.

 

Karatsuba algoritması çarpma işlemine göre 4 basamaklı (dijit) olarak verilen iki tane sayıyı çarpmak istediğimizde, önce sayıları anlamlı ikişerl ikişer uygun bloklara ayırıp işlemleri kolaylaştırırız. Yukarıda verilen akış şemasına göre önce bu bloklarda ayrı ayrı çarpma işlemi uygulayarak sonuca ulaşırız.

Kaynakça

1.https://www.geeksforgeeks.org/karatsuba-algorithm-for-fast-multiplication-using-divide-and-conquer-algorithm/

2.https://brilliant.org/wiki/karatsuba-algorithm/

3.Karatsuba ve nikhilam çarpma işlemi algoritmalarının farklı bit uzunlukları için performanslarının karşılaştırılması, Can Eyüpoğlu, Ahmet Sertbaş, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi Yıl:14 Sayı: 27 Bahar 2015 s. 55-64 

 

Karatsuba Çarpım Algoritması Konu Anlatım Özetini indirmek için tıklayınız. (PDF)

Kadane Algoritması

Kadane Algoritması, belirli bir sayı dizisi içindeki maksimum alt dizi toplamını bulmak için kullanılan dinamik bir programlama tekniğidir. Dinamik Programlama, karmaşık bir problemi daha basit alt problemlerden oluşan bir koleksiyona bölerek, bu alt problemlerin her birini yalnızca bir kez çözerek ve çözümlerini bellek tabanlı bir veri yapısı (dizi, harita vb.) kullanarak saklayarak çözme yöntemidir. Yani bir dahaki sefere aynı alt problem ortaya çıktığında, çözümünü yeniden hesaplamak yerine, daha önce hesaplanan çözüme bakılır ve böylece hesaplama süresinden tasarruf edilir. Adını mucidi Jay Kadane'den alan algoritma; bilgisayar bilimi ve veri analizinden finans ve görüntü işlemeye kadar çeşitli alanlarda uygulamalara sahiptir. Algoritma 1984 yılında Jay Kadane tarafından önerilmiştir ve O(n) zaman karmaşıklığına sahiptir. 

Kadane Algoritması, belirli bir dizideki maksimum alt dizi toplamını bulmak için kullanılan doğrusal bir zaman algoritmasıdır. Bir alt dizi, dizi içindeki öğelerin bitişik bir alt kümesi olarak tanımlanır. Algoritma, pozitif ve negatif sayıları çok verimli bir şekilde ele alır, bu da onu alt dizileri içeren birçok sorunu çözmek yerine daha pratik çok yönlü bir çözüm aracı haline getirir.Kadane'nin algoritmasından önce, maksimum alt dizi problemini çözmek için tüm olası alt dizileri kontrol eden kaba kuvvet yaklaşımı ve böl ve yönet algoritması gibi başka algoritmalar önerilmişti. Ancak bu algoritmalar daha yüksek zaman karmaşıklığına sahiptir ve Kadane'nin algoritmasından daha az verimlidir. Kadane'nin Algoritmasının altında yatan mekanizmaları, Java kodu uygulamalarını, adım adım süreci, Kadane'nin algoritma leetcode'unu, C, C++'yi, zaman karmaşıklığını, avantajlarını ve dezavantajlarını, pratik uygulamaları ve daha fazlasını anlamanız sizin için faydalı olacaktır.

Kadane Algoritması, dizi üzerinde yineleme yaparak ve her konumda biten alt dizinin maksimum toplamını takip ederek çalışır. Her i konumunda, iki seçeneğimiz vardır: ya i konumundaki elemanı geçerli maksimum alt diziye ekleyin ya da i konumunda yeni bir alt dizi başlatın. Bu iki seçeneğin maksimumu i konumunda biten maksimum altdizidir.

Yazılım dilinde bu algoritma şu şekilde işler: Başlangıç toplamı max_so_far ve max_ending_here değerleri 0 olarak alınıp dizi öğeleri tek tek incelenir. Sırasıyla şu ana kadar görülen maksimum toplamı ve geçerli konumda biten maksimum toplamı takip etmek için max_so_far ve max_ending_here olmak üzere iki değişkeni her dizi elemanında korunur. Algoritma, her iki değişkeni de dizinin ilk öğesinden başlayarak sırasıyla değiştirir. Daha sonra dizinin elemanlarını aldıktan sonra geçerli toplamı maksimum toplamla kıyaslayarak ikinci öğeden dizinin sonuna kadar aynı işlemler tekrarlanır. Her i konumunda, geçerli öğenin maksimumunu ve önceki maksimum alt diziye eklenen geçerli öğeyi alarak max_ending_here'i güncellenir. Daha sonra max_so_far'ı max_so_far ve max_ending_here'nin maksimumu olacak şekilde güncelleme işlemine devam edilir. Geçerli toplam maksimum toplamdan büyük ise artık yeni maksimum toplam değeri buna göre güncellenir aksi halde önceki maksimum toplam aynı kalır. Algoritma, dizideki herhangi bir alt dizinin maksimum toplamı olan max_so_far değerini sürekli olarak döndürür. Dizinin son terimine gelince işlem biter ve maksimum toplamı veren alt dizi elde edilir.

Kadane Algoritmasını şöyle bir sayı dizisi örneğiyle gösterelim:

Giriş Dizisi: [-2, 1, 6, -3, 4, -1, -7, -3, 5] Bu dizinin maksimum altdizi toplamını bulmak istiyoruz. Bu sorunu çözmek için Kadane'nin algoritmasını uygulayabiliriz.

İki değişkeni başlatarak algoritmayı başlatıyoruz:

1) max_so_far: Bu değişken şu ana kadar gördüğümüz maksimum alt dizi toplamını takip edecektir. (Geçerli Toplam)

2) max_ending_here: Bu değişken mevcut endekste biten maksimum toplamı takip edecektir. (Max Toplam)

3) İlk başlangıç toplamı max_so_far ve  max_ending_here=0 olur. Daha sonra ikinci elemandan başlayarak dizi boyunca toplamları yineliyoruz: Öğe -2 ye gidip yeni toplam -2 olur. (0+(-2)=-2) [Sub:-2]

4) Geçerli öğeyi önceki toplama ekleyerek geçerli toplamı güncelleyin: Geçerli Toplam=0+(-2)=-2 [Sub:-2]

5) Şu ana kadar görülen maksimum toplamı güncelleyin: 0+(-2)=-2 olur.(Maksimum Toplam=-2) [Sub:-2, Max:-2]

6) Dizi boyunca ilerleyerek yerel toplam (Geçerli toplam) ve maksimum toplam sonuçlarını yinelemeye başlayalım.

Dizide öğe 1 elemanına gelince: Geçerli toplam -1 olur. (-2+1=-1)  [Sub:-1]

Maksimum toplam, geçerli toplam olan -1, max toplam -2 yi geçtiği için -1 olarak güncellenir. [Sub:-1, Max:-1]

7) Öğe 6 elemanına gidelim: Yeni geçerli toplamı 5 olur. ((-1)+6=5) Maksimum toplamı ise 5 toplamı önceki maksimum toplam olan -1 sayısını geçtiği için güncellenir ve maksimum toplam 5 olur.  [Sub:5, Max:5]

8) Öğe -3'e gelince:Yeni geçerli toplamı 2 olur. (5+(-3)=2) Maksimum toplamı ise 2 toplamı önceki maksimum toplam olan 5 sayısını  sayısını geçemediği için aynı kalır. Yeni maksimum toplam halen 5'tir. [Sub:2, Max:5]

9)Öğe 4'e gelince:Yeni geçerli toplamı 6 olur. (2+4=6) Maksimum toplamı 6 ise önceki max toplam 5'i geçtiği için yeniden güncellenir ve yeni maksimum toplam 6 olur. [Sub:6, Max:6]

10)Öğe -1'e gelince:Yeni geçerli toplamı 5 olur. (6+(-1)=5) Maksimum toplamı ise 5 toplamı önceki maksimum toplam olan 6 sayısını geçemediği için halen aynı kalır ve 6 olur. [Sub:5, Max:6]

11)Öğe -7'e gelince:Yeni geçerli toplamı -6 olur. (5+(-7)=-2) Maksimum toplamı ise -2 önceki maksimum toplam olan 6 sayısını geçemediği için aynı kalır. [Sub:-2, Max:6]

12)Öğe -3'e gelince:Yeni geçerli toplamı -5 olur. ((-2)+(-3)=-5) Maksimum toplamı ise -5 önceki maksimum toplam olan 6 sayısını geçemediği için aynı kalır. [Sub:-5, Max:6]

13)Öğe 5'e gelince:Yeni geçerli toplamı 0 olur. ((-5)+5=0) Maksimum toplamı ise 0 toplamı önceki maksimum toplam olan 6 sayısını artık geçemediği için aynı kalır. [Sub:0, Max:6]

Tüm dizi için bu işleme devam edip en son öğeye gelindiği için işlem biter. Bu örnekteki maksimum alt dizi, toplamının en büyük olduğu değer 6 olduğundan buna uygun bir alt dizi [-2, 1, 6, -3, 4] olur.

Java ve C++ programlamada Kadane Algoritması şöyle çalışır:

1)İki değişkeni, max_so_far ve max_ending_here'i 0'a başlatın.

2)Diziyi soldan sağa doğru yineleyin ve her öğeyi tek tek inceleyin.

3)Her öğe için, maksimum değer ya geçerli öğe ya da geçerli öğe ile max_ending_here'in toplamı olduğundan max_ending_here'i güncelleyin.

4)Max_so_far'ı mevcut max_so_far veya max_ending_here'in maksimumu kadar güncelleyin.

5)Dizideki tüm öğeler için 3. ve 4. adımları tekrarlayın.

6)Yinelemenin sonundaki max_so_far değeri maksimum altdizi toplamı olacaktır.

#include <iostream>

using namespace std;

int maxSubarraySum(int arr[], int size) {

  int maxEndingHere = arr[0];

  int maxSoFar = arr[0];

  for (int i = 1; i < size; i++) {

      maxEndingHere = max(arr[i], maxEndingHere + arr[i]);

      maxSoFar = max(maxSoFar, maxEndingHere);

  }

  return maxSoFar;

}

int main() {

  int nums[] = {-2, -1, -3, 4, -1, 2, 1, -5, 4};

  int size = sizeof(nums) / sizeof(nums[0]);

  int maxSum = maxSubarraySum(nums, size);

  cout << "Maximum subarray sum: " << maxSum << endl;

  return 0;

}

Kaynakça:

https://www.tpointtech.com/kadanes-algorithm

https://www.simplilearn.com/kadanes-algorithm-article

https://www.interviewbit.com/blog/maximum-subarray-sum/

https://www.guru99.com/tr/largest-sum-contiguous-subarray.html

https://www.codecademy.com/resources/docs/general/algorithm/kadanes-algorithm

 

Kadane Çarpım Algoritması Konu Anlatım Özetini indirmek için tıklayınız. (PDF)

Algoritma Örnekleri

Bir problemin çözümüne dair işlem basamakları oluşturulabiliyorsa, o problem çözülmüş demektir. Herhangi bir programlama dilinde, işlem basamaklarını bilgisayarın anlayabileceği şekle dönüştürme yardımıyla problem çözüm işlemi başlamış olur. Bu dönüştürme işlemini kolaylaştırmak için, işlem basamaklarımızı oluştururken bilgisayar diline yakın bir dille yazmak önemlidir. Öyle ki; bilgisayara verilecek iki sayıyı toplayıp, sonucu ekrana yazacak bir program için oluşturulan işlem basamakları, 

1. Sayıları oku 

2. Sayıların toplamlarını hesapla 

3. Toplamlarını ekrana yaz şeklinde olduğunda, bu işlem basamaklarını herhangi bir programlama dilini kullanarak bilgisayara aktarmak, yeterli değişken kullanımı olmadığında daha zor olacaktır. 

Aynı işlem basamakları aşağıdaki gibi yazıldığında programlama açısından daha kolay bir durum verir.

1. Başla 

2. A sayısını oku 

3. B sayısını oku 

4. C = A + B 

5. C sayısını yaz (ekrana yaz) 

6. Dur 

 

Örneğin bir pozitif tamsayının 5 ile tam bölünüp bölünmediği belirlemek için aşağıdaki gibi bir adımlama yapılabilir. 

1. Başla

2. Pozitif bir tamsayı gir

3. sayının birler basamağını bul b=x%10

4. eğer b=5 veya b=0 ise "x, 5 ile tam bölünür" değilse "x , 5 ile tam bölünmez"

5. bitir

 

Algoritmada akış diyagramları

Algoritmada akış diyagramlarından yararlanılarak çözüm basamakları adımlandırılır. Akış diyagramı, algoritmaların şekil ve sembollerle ifade edilmesidir. Akış şemasında her adım birbirinden farklı anlamlar taşıyan şekillerden oluşur ve adımlar arasındaki ilişki oklar ile gösterilir. Kodlanacak programın akış şemasının oluşturulması, sürecin daha kolay çözümlenmesine yardımcı olur. 

Algoritma ve Bilişim konu özeti ders notları için tıklayınız. (PDF)

Algoritma ve Özellikleri

Algoritma, belirli bir problemi çözmek veya belirli bir amaca ulaşmak için çözüm yolunun adım adım tasarlanmasıdır. Bir problemi tanımlama, nedenini açıklama, çözümü için alternatif yolları belirleme ve bu yollar arasından en uygun olanı uygulama süreçlerinin tamamı “problem çözme” olarak adlandırılır. Algoritma, bir problemi çözmek için gerekli yolun basit, net ve belirli bir sıraya göre tasarlanmış hâlidir. Matematikte ve bilgisayar biliminde bir işi yapmak için tanımlanan, bir başlangıç durumundan başladığında, açıkça belirlenmiş bir son durumunda sonlanan, sonlu işlemler kümesi algoritma içinde yer alır. Genellikle bilgisayar programlamada algoritma sıklıkla kullanılır ve tüm programlama dillerinin temeli algoritmaya dayanır. Aynı zamanda algoritma tek bir problemi çözecek davranışın, temel işleri yapan komutların veya deyimlerin adım adım ortaya konulmasıdır ve bu adımların sıralaması algoritmada oldukça önemlidir. Bir problem çözülürken algoritmik ve sezgisel (herustic) olmak üzere iki yaklaşım vardır. Algoritmik yaklaşımda da çözüm için olası yöntemlerden en uygun olan seçilir ve yapılması gerekenler adım adım ortaya konulur. Algoritmayı belirtmek için; metinsel olarak düz ifade ve akış diyagramı olmak üzere 2 yöntem kullanılır. Algoritmalar bir programlama dili vasıtasıyla bilgisayarlar tarafından işletilebilirler. 

Öklid Algoritması

Öklid Algoritması; (Bkz.Euclidin Hayatı) (MÖ.325-MÖ.265) tarafından bulunan kullanışlı bir bölüm işlevidir. EBOB bulma işlemlerinde genellikle asal çarpanlarına ayrılması yönteminden yararlanırız. Lakin bazı durumlarda bu asal çarpanlarına ayırma işlemi sıkıntılı olabilir. Özellikle büyük sayılar verildiğinde EBOB bulma işlemi, asal çarpan yönteminde daha zor hale gelebilir. İki tam sayının en büyük ortak bölenini bulmak için yapılan ardışık bölme işlemine öklit algoritması denir. Ardışık bölme işlemine kalan sıfır oluncaya kadar devam edilir. Sıfırdan önceki en son bölen sayı EBOB u verir. Öklid algoritmasında yapılması gereken temel mantık; ardışık olarak büyük sayıyı küçük sayıya bölerek kalanın 0 olması durumuna kadar devam edilmesidir. Bazı durumlarda kalan 0 olmayabilir bu durumlarda farklı çözüm yolları geliştirilmelidir. 

Smith Sayısı (Wilansky)

1 den büyük asal olmayan bir tamsayının rakamlarının toplamı, sayı asal çarpanlarına ayrılarak yazıldığında bu yazılışta bulunan  tüm asal çarpanların rakamlarının toplamına eşit oluyorsa bu tür   sayılara Smith sayısı denir.

Örnek: ( 121 bir Smith sayısıdır. )

121  = 11 * 11          

1 + 2 + 1  =  1 + 1 + 1 + 1            

4 = 4     

Örnek: ( 166 bir Smith sayısıdır. )

166 = 2 * 83      

1 + 6 + 6  = 2 + 8 + 3               

13  = 13    

Bu sayılarla ilgili çıkmış bir üniversite sorusu bile vardır. 2005 yılında yapılan tek basamaklı sınav sisteminde ÖSS de bu şekilde tanımı verilerek hazırlanmış bir soru karşımıza çıkmaktadır. 

Lehigh Üniversitesi Matematik Bö-lümü’nde öğretim üyesi olan Albert Wilansky, 1982 yılında üvey kardeşi Herold Smith’i aramak için telefonun başına geçer ve numaraları çevirir: 4-9-3-7-7-7-7-5.  Bir yandan kardeşi ile konuşur­ken bir yandan da alışkanlığı nedeniyle telefon numarası 4937775′i asal çarpan­larına ayırmaya başlar. Konuşmalar ola­ğan seyrinde devam ederken bir anda Wilansky durgunlaşır ve kardeşinin söy­lediklerine tepki vermemeye başlar.  Sayı­yı çarpanlarına ayırdığı kağıtta gözü eşit­liğe takılmıştır:

4937775 = 3 x 5 x 5 x 65837. Eşitliğin her iki tarafındaki ra­kamları topladığında kalbi hızlı hızlı at­maya başlar ve gözlerine inanamaz: 4+9+3+7+7+7+5 = 3+5+5+6+5+8+3+7 = 42. Kardeşine hiçbir şey söylemeden bü­yük bir heyecanla telefonu kapatır ve ay­nı özellikte benzer sayılar aramaya baş­lar. Görür ki keşfettiği özelliğe sahip sonsuz tane sayı bulunmaktadır.  O gü­nün anısına Wilansky, rakamları toplamı asal çarpanlarının rakamlarının toplamı­na eşit olan sayılara “Smith Sayıları” adı­nı verir.

Her asal sayının sadece bir tane asal çarpanı olduğu için (o da sayının kendi­sidir) tüm asal sayılar aslında birer Smith Sayısı’dır. 10000′den küçük sayı­lara baktığımızda da 376 adet Smith Sa­yısı olduğunu görürüz: 

4, 22, 27, 58, 85, 94, 121, 166, 202, 265, 274, 319, 346, 355, 378, 382, 391, 438, 454, 483, 517, 526, 535, 562, 576, 588, 627, 634, 636, 645, 648, 654, 663, 666, 690, 706, 728, 729, 762, 778, 825, 852, 861, 895, 913, 915, 922, 958, 985, 1086, 1111,1165……

Smith Sayıları’nın keşfinin ar­dından yapılan çalışmalarla bu sayılar arasında başka ilginç özelliklere sahip sayı grupları tanımlanmıştır. Örneğin sa­dece iki asal sayının çarpımı şeklinde ya­zılabilen Smith Sayıları’na “Yarı Asal Smith Sayıları” adı verilmiştir. 

121 sayısı bir yarı asal Smith Sayısı’dır. 121 = 11 x 11 ve 1+2+1 = 1+1+1+1. 

Diğer bir ilginç grup ise Palindromik Smith Sayıları’dır. Bu sayılar baştan ve sondan okundukla­rında aynı değeri veren sayılardır. 666 sayısı hem bir Smith Sayısı’dır.

 (666 = 2x3x3x37) hem Smith sayısı hem de palindromik özelliği bulunmaktadır.

Örnek:  Yukarıda bahsi geçen sayıyı 4937775 sayısını kullanırsak; 

4937775 = 3 * 5 * 5* 65837          

4 + 9 + 3 + 7 + 7 + 7 + 5 = 3 + 5 + 5+ 6 + 5 + 8 + 3 + 7                 

42 = 42  (4937775 bir Smith sayısıdır. )

Peşi sıra gelen Smith sayılarına da  728 ve 729,  2964 ve 2965 gibi sayılara da "smith kardeş sayıları" denir.

Bilgisayar yardımıyla bir sayının Smith sayısı olup olmadığı bulunabilir. Bunun için java kodlama sistemine göre aşağıda verilen kodlama yapılarak bir algoritma oluşturulabilir.

public static boolean Smith(int sayi) {

    int gecici = sayi, i;

    int asal_carpanlar = 0;

  

    for (i = 2; gecici > 1; i++) {

     if (gecici % i == 0) {

      gecici /= i;

      asal_carpanlar += i;

      i--;

     }

    }

    return basamak_toplami(asal_carpanlar) == basamak_toplami(sayi);

   }

   public static int basamak_toplami(int sayi){

    int toplam = 0;

    while (sayi > 0) {

     toplam += sayi % 10;

     sayi /= 10;

    }

    return toplam;

   }

El Harezmi (770-840)

Harezmi 770 yılında Özbekistan'ın Karizmi kendinde dünyaya gelmiştir. Tam olarak ismi Ebu Abdullah Muhammed bin Musa El-Harezmi'dir. Kendisini matematik tarihinin en büyük bilim adımı olarak tanımlayabiliriz. Çünkü cebirin ve algoritmanın kurucusudur. El Harezmi sadece matematikle değil aynı zamanda astronomi ve coğrafyayla da ilgilenmiştir. Batı dünyasında en çok etkide bulunan bilim adamı diyebiliriz. Çalışmalarına Abbasi halifesi Mem'un tarafından Bağdat Saray Kütüphanesine getirilmesiyle başlamıştır. Daha sonra burada yabancı eserlerin tercümesini yapmak amacıyla kurulan bir tercüme akademisi olan Beyt'ül Hikme'de göreve başlar. Harezminin bu kadar önemli bir bilim adamı olmasının sebebi sadece cebirin kurucusu olması degildir aynı zamanda geliştiriciside olmasıdır. Hayatındaki bir çok büyük eserini Bağdat Saray Kütüphanesinde yapmıştır.Harezminin ilk eserlerinden biri aritmetik alanındadır. Ancak bu alanda bıraktığı yapıtın orjinali kayıptır. Bu kitabın bu güne kadar gelmesinin sebebi Bathlı Adelard'an tarafından Lâtinciye çevrilmesinden kaynaklanır. Bu kitabın ismi De Numero Indorum (Hint Rakamları Hakkında)'dur. Bu kitabında on rakamlı konumsal Hint rakamlama ve hesaplama sistemini anlatmıştır. Batıdaki matematikçiler Romalılardan bu yana kullanılan harf rakam ve hesap sistemi yerine Hint rakam ve hesap sistemini kullanmayı bu yapıttan öğrenmişlerdir. Bu yapıtı batı dünyasındaki matematikçileri çok etkilemiştir. Daha sonra bu hesaplama sistemine Harezminin isminden türetilen algoritma (algorism) denmiştir. On rakamdan oluşan rakamlama sistemi ise, Harezmi tarafından tanıtıldığı için Arap Rakamları veya kökeni Hindistan olduğu için Hint-Arap Rakamları denmiştir. 

 

Harezminin en büyük eseri cebirdir. Kendisi İslam bilgileri arasında cebirin kurucusu ve geliştiricisi olarak bilinir. Bu konuda yazılan ilk ve yaygınlaştırılan kitap; El Kitabü'l Muhtasar fi Hisabi'l Cebr ve'l Mukabele 'dir. Harezminin bu eseri kendisine İslam ve batı bilim dünyasında çok ün kazandırmıştır. Batı dünyası ilk kez bu kitap sayesinde cebiri kullanmış ve öğrenmiştir. Bu yapıtta ana konular birinci ve ikinci dereceden denklemlerin çözümleri, binom çarpımları, çeşitli cebir problemleri ve miras hesabıdır. Harezmi cebirle ilgili çalışmalarında ikinci dereceden denklemler konu üzerinde çok durmuştur. Birinci dereceden denklemleri incelerken Yanlış Yolu İle Çözme Yöntemi'ni kullanmıştır. Bu yöntemi kullanırken şu anda ax² + bx + c = 0 biçiminde gösterdiğimiz ve çözümünü ikinci derece denklemlerde kök formülü olarak bilinen diskriminat değerine bağlı olarak üretilen x = - b + √Δ/ 2a eşitliği ile bulduğumuz ikinci dereceden denklemlerin çözümünü negatif nicelikleri incelemeden sadece pozitif değerleri ele alarak üç grupta toplamış ve her grup için Kareye Tamamlama İşlemi'ne dayanan ayrı bir çözüm yöntemi kullanmıştır. Harezminin bu büyük çalışması 12. yüzyılda Chesterlı Robert ve Cremonalı Gerard tarafından Latinceye çevrilmiştir. Batı dünyası bu yapıttan çok fazla etkilenmiş ve cebiri bu sayede öğrenmiştir. 

Cebir batı dünyasında el-cebr isminden algebra'ya dönüştürülmüştür. Daha sonra batı dillerinde cebir algebra olarak tanımlanmıştır. Aynı zaman Harezminin bu yapıtı batı dünyasında cebirin kullanımının yaygınlaşmasında da büyük rol oynamıştır.Harezmi Muhammed ibn İbrahim el-Fizari'nin Sanskrit dilinden Arapça'ya tercüme ettiği el-Sindhind (Siddhanta) adlı yapıtını Batlamyus'un Almagest'inden de yararlanarak düzeltmiştir. Muhtamelen bu yapıt iki ayrı şekilde çoğaltılmıştır. Bu yapıt kuramsal bilgilerde içeriyordu. Daha sonra bu yapıt Endülüslü astronom Meslemetü'l Mecriti tarafından güncelleştirilmiştir. Eserin bu versiyonu Bathlı Adelard'ın ve daha sonra muhtemelen Dalmaçyalı Hermann'ın gayretleriyle Latince'ye çevrilmiştir.Eserdeki en büyük gariplik Harezmi'nin açıları sinüs gibi trigonometrik fonksiyonlarla ifade ettiğini gösteren tablolar olmasıdır. Tabi bu tablolar bir çok soru işaretini ortaya çıkarmıştır çünkü Harezmi trigonometrik fonksiyonları biliyormuydu yoksa daha sonra Meslemetü'l Mecriti tarafındanmı eklenmiştir bilinmiyor. Ancak çoğu bilim tarihçisi sinüs ve kosinüsü ilk kez Harezminin kullandığını söylüyor. Tanjant ve kotanjantı ise Meslemetü'l Mecriti'nin eklediği iddia ediliyor. Ama ne olursa olsun trigonometri İslam bilim dünyasına aittir. Trigonometrinin İslam dünyasının eseri olması bu konuda yeterli bilgiye sahip olamamalarına rağmen islamın bilimi gerilettigini idda edenlere güzel bir cevaptır. Tabi sadece trigonometri değil matematik, astronomi, coğrafya, fizik, tıp gibi bilim dallarında da İslam bilim dünyası çok ilerlemiştir.

Harezminin önemli eserlerinden olan usturlabın yapımı ve kullanımını anlatan eseri kayıptır. Harezmi sadece matematikle değil coğrafyayla da ilgilenmiştir. Batlamyus'un Coğrafya adlı yapıtını Kitabu Sureti'l Ard (Yer'in Biçimi Hakkında) olarak tercüme etmiştir. Bu sayede yunanlıların matematiksel coğrafya hakkındaki bilgilerin İslam bilim dünyasına girmesinde büyük rol oynamıştır. Bu yapıt tercüme edilirken üzerinde eklemeler yapıldığından orijinalliğini biraz kaybetmiştir. Harezminin bu yapıtı önemli yerlerin enlem ve boylamlarını bildiren çok sayıda tablo içermektedir. Harezminin en ilgi çekici eserlerinden biride Nil'in kaynağını gösteren haritasının bulunmasıdır. Bu yapıt daha sonra Batlamyus-Harizmi Kuramı diye tanınmıştır. Harezmi 70 tane bilim adamıyla çalışarak 830 yılında dünya haritası çizmiştir. Dünyanın çevresini ve hacmini hesaplama çalışmalarında da yer almıştır.

Güneş saatleri, usturlaplar ve saatler üzerine yazılmış eserleri de vardır. Coğrafyanın yanı sıra astronomi biliminde de eserler bırakmıştır. Astronomik cetvellerle ilgili kitaplar yazmış ve bu eserler 12. y.y. da Latince' ye çevrilmiştir.Muhtemelen Türk olan Harezmi İslam bilim dünyasındaki yerini almıştır. Özellikle matematik alanında eserler bırakmış olan Harezminin eserleri Batı bilim dünyasında hala kullanılmakta ve öğretilmektedir. Bu büyük İslam alimi 840 yılında vefat etmiştir.

Matematik ile alakalı eserleri: El- Kitab'ul Muhtasar fi'l Hesab'il Cebri ve'l Mukabele (Bkz. Harezminin Cebir Kitabı), Kitab al-Muhtasar fil Hisab el-Hind,El-Mesahat,  Kitabün fil-Hisab vel-Hendese vel-Mûsiki Astronomi ile alakalı eserleri: Kitabun fit-Tarikati Marifet-il-Vakt bi Vesatat-iş-Şems, Ziyc'ul Harezmi, Kitab al-Amal bi'l Usturlab, Sun-il-Usturlab, Kitab'ul Ruhname, Coğrafya ve Tarih ile alakalı eserleri: Kitabun fil Coğrafya, Kitab surat al-arz, Kitab'ul Tarih, Kitabu Takvim-il-Büldan.

Harezmi'ye Ün Kazandıran "Cebir Kitabi"

Harzemli'nin bilim tarihinde kısaca, "Cebir Kitabı" adı ile anılan eseri, " Kitab-ül Muhtasar Fi Hesab al-Cebr Ve'l Mukabele" , Türkçe deyişle; "Özetlenmiş , Benzer terimleri yoketme-Mukabele ve Bilinenleri bir tarafta toplama-Cebir, Hesaplamasının Elkitabi " dir. Harzemli Dar Ül Hikmede , çesitli matematiksel problemlerin çözümü üzerinde çalışırken, Hindli matemetikçilerin yeni bir aritmetik üzerinde çalıştıklarını öğrenir. M.S. 825 Tarihlerinde Halife Memun'un izni ile, Hint matematiğini izlemek üzere Hindistan'a gider. Hint matemetikçilerinin kullandığı yeni sayı sistemini ve aritmetiği bütün yönleri ile inceler, notlar alır ve bilgi yükü ile Bağdat'a döner.

Bilim tarihçilerinin bir konuyu işleme zenginliğini görmek ve bu yaklaşımın ulaşımlarını değerlendirmek için, bilim tarihçisi B. K. Stonaker'in , "Famous Mathematicians" (1966, N.York) isimli kitabından Harzemli'nin Bağdat dönüşü hikayesini okuyalım: " Kervan Bağdat'a doğru tekrar yola çıktı. Havanın sıcaklığından, çölde yolculuk çok zor geçiyordu. Kervan bin güçlükle Bağdat'a ulaştı. Harzemli'yi Halife Memun karşıladı. Ve Harzemli  " Allah, bana çok yararlı ve başarılı bir gezi bahşetti. dedi. Harzemli koltuğunda bir deste kağıt ve kitap taşıyordu. Bir ara kağıtların bir bölümü yere düştü. Birinin üzerinde şifre gibi bilinmeyen simgeler vardı. Halife bu acayip şekilleri görünce kızar gibi oldu ve "Bunlar nedir?"diye sordu. Harzemli." Bunlar Hint sayılarıdır." Diye cevapladı. "Bunlar sayıların tanımlanmasını ve aritmetik işlemleri çok kolaylaştıracaktır efendim." şeklinde niyetini açıkladı. Halife, Harzemli'nin Hindistan'dan getirdiği yenilikleri bundan sonra daha iyi karşıladı ve "geliştirip herkese yararlı hale getirmesini ve diğerlerine öğretmesini buyurdu."

Harzemli, Hint gezisi dönüşünde, orada matematik işlemlerde kullanımını incelediği onlu sayı birimleri (1,2,3,.,9 )ile kurulan sayıların işlemsel kullanımı yöntemlerini kendi çabalarıyla geliştirdi. Harezmi'nin çalışmalarından sonra bu sayı sistemleri, sonradan Arap sayıları diye anılan onlu sayı sistemini oluşturmuştur. Aritmetiğe onlu sayı sisteminin girişi Harzemli'nin eserinin çevirileri ile dünyaya yayılmıştır. Cebirde denklem çözümü ve güncel problemlerin çözümünde kullanmak için çalışmalar yaptı. Kendine özgü sözlü biçimde denklem çözümünü içeren bir yöntem geliştirdi. Denklem çözme yöntemini öğretmeyi amaçlayan bir kitap hazırladı. 

Harzemli "Cebir Kitabı"nın önsözünde :" Lütüfkar ve merhametli Allah adına, bu eser Harzemli Musa Oğlu Muhammed tarafından yazılmıştır. O şöyle bir başlangıç yapmak ister: Allah'a şükürler olsun ki, onun iyilikseverliğine ve korumacılığına sığınabildim. Onun emirlerine uydum. Şükürler olsun ki, görevimi yapmak için Onun değerli ve sürekli yardım severliğinden yararlandım. Onun kudretli, eksilmeyen yüceliğini ve saygın büyüklüğünü kabul ederim. O Muhammedi Allah'ın elçisine yakışır bir görevle görevlendirdi. Ne zaman haklılık zayıflasa, doğru yolda ilerlemek çaresiz kalsa, Onun yardımları yetişti. Allah, sadık komutan Al-Memun 'u ilim sevgisi ile ünlü kıldı öyle ki, O bilim adamlarından yardım ve desteğini hiç eksik etmedi. Onları güçlüklerden korudu. O halifeliği yanında, yüceltmede, ödünlendirmede , adalet ve hak dağıtmada da çömertti.. Beni "bir araya getirme-cebr ve sadeleştirme-mukabele" kuralları ile hesaplama üzerine özlü bir eser yazmaya teşvik etti, bana cesaret verdi.."

Bir kaynağa göre, Harzemli "cebir Kitabı"nı yazar ve Halife Memun'a sunar. Memun: " Harzemli çok güzel ama bunları halkım anlayıp kullanamaz. Haydi git yeniden, öyle yaz ki herkes bu kurallarla problem çözebilsin" der. Bu buyrukla, Harzemli konuyu yeniden inceler ve kitabını yeniden herkesin anlayıp, uygulayabileceği sistemli bir anlatım yapısı düzeni ile düzenler. Gerek, Harzemli' nin önsözünde belirttiği; Memun'un "Özlü bir kitap yaz." Gerekse, yukarda sözü edilen; " yeniden öyle yaz ki herkes anlayıp kullanabilsin" cümlelernin içinde yatan anlamı, Harzemli öylesine değerlendirmiş ki, özgün bir anlatım yöntemi oluşturarak, çığır açan üç kavramı birbirinin bütünleyicisi olarak ortaya koymuştur. Bunlar; onlu sayı sistemi , denklem kuramı ile çözüm ve yeni çözümleme yöntemi ya da algoritmik anlatımlardır ve bütün bunlar ayrı ayrı önem taşıyan Ortaçağ biliminin ilklerindendir.

Harzemli'nin çalıştığı ortam gereği Arapça el yazması ile hazırladığı "Cebir Kitabı", 11. Yüzyılın sonlarında, İspanya yolu ile Avrupa'ya ulaştıktan sonra , birkaç kez Latince, Italyanca ve sonra İngilizce'ye, çevrilmiş, bu çevirilerde özgün elyazmasının farklı kopyaları kullanılmıştır. Ayrıca sayısı yüzden fazla araştırmacı, Harezmi'nin kitabı üzerine değerlendirme ve yorum yayımlamıştır. Çevirilerden en yaygın kullanılanı; M.S. 1145 yılında Chester'lı Robert sanı ile tanınan araştırmacının İspanya'nın Segova kentinde Latinceye çevirdiği "Al-Khwraizmi's Al-Jabr" isimli kitabı ile Frederic Rosen'ın 1831 deki İngilizce çevirisi " The Algebra of Muhammed Ben Musa" isimli kitabıdır. 19. Yüzyılda en çok yararlanılan kaynaklar ise, L.C. Karpinski'nin Chester çevirisinden yararlanarak , 1915 deki İngilizce, " Robert of Chester's Latin Translation of Al-Khowarizmi" çeviri ve değerlendirmesi ile 1989 Yılında Barnabas B. Hughes'in değerlendirme, karşılaştırma ve yorumu içeren İngilizce "Robert of Chester's Latin Translation of Al-Khwarizmi's Al-Jabr " adlı eserleridir.

Harezmî önce bu denklemlerin analitik çözümlerini verir, daha sonra katışık denklemlerin geometrik ispatını yapar. Kitaptaki denklem çözümlerinden birine örnek olarak x²+21=10x denkleminin iki farklı kökünü geometrik modellemeyle vermiştir. x²-2x-5x= 6=0 denkleminde iyileştirme ile negatif terimleri diğer tarafa atmayı ifade ederek denklemi x²=+5x+2x+6 şekline dönüştürerek modellemiştir. Sadeleştirme ile benzer terimlerin birleştirilmesini ifade eder ve bu durumda denklem; x² = +7x+6 şekline dönüştürerek denklemlerin sade hallerinden geometrik modellemelerini alan hesabından yararlanarak açıklamıştır. Harezmî özel olarak x² +10x-39=0 denkleminin çözümünü geometrik olarak aşağıdaki gibi bulmuştur.

Harzemli'nin "Cebir Kitabı" kısaca tanımlamak gerekirse; On tabanlı sayı sisteminin ve dört işleminin tanımı, birinci ve ikinci derece denklem oluşturma öğelerinin tanımı. (kök-bilinmeyen, kare- bilinmeyenin karesi, kare ya da kök olmayan yalın sayı), birinci ve ikinci derece eşitlik- ya da denklem kurma, cebr ve mukabele işlemleri, cebirsel ifadeler üzerine çeşitli işlemler, karekök, İkinci derece denklemin kökünü bulma yöntemi, denklem çözümlerinin geometrik ispat ve modellemelerini içerir. Yer alan, birinci ve ikinci derece denklem türleri: bx = c, ax = c, ax² = bx, ax²+bx=c, ax²+c = bx ve ax² = bx+c tanımı ile denklem kurma yolu ile çözümü verilen, miras, alan, faiz ve arazi problemlerinin sistemli-açıklamalı, çok sayıda çözüm örnekleri sözel biçimde aktararak, çeşitli matematiksel ve geometrik modellemelerle eserde sıralanmaktadır.