Arithmetic / Fast Exponentiation

Kolay

Sedgewick

Bir taban sayının belirtilen üssünü böl-ve-fethet (Binary Exponentiation) yöntemiyle logaritmik zamanda hesaplar.

Exponentiation (Üs Alma / Hızlı Üs Alma) Algoritması

Exponentiation (Üs Alma / Hızlı Üs Alma) Açıklaması

Üs alma işlemi, bir a sayısının n kere kendisiyle çarpılmasıdır (a^n). Sedgewick, naive yöntemin n adet çarpım yaparak O(n) zamanda çalıştığını, ancak üssün ikili (binary) temsilini kullanan hızlı üs alma yönteminin bunu O(log n) çarpıma indirdiğini anlatır.

Algoritma, üssün tek veya çift olma durumuna göre tabanı karesiyle günceller veya sonucu tabanla çarpar. Bu yöntem, kriptografide özellikle büyük modüler üs alma işlemlerinde (a^n mod m) kritik öneme sahiptir.

Kaynak Notları

Sedgewick: a^n hesaplanmasında n tek ise a * a^(n-1), çift ise (a^(n/2))^2 indirgemesi.
Sedgewick: O(log n) çarpım maliyetiyle çalışan iterative ve recursive akışlar.

Çalışma Prensibi

Üs (n) sıfır ise sonuç 1'dir.
Üs negatif ise tabanı çarpmaya göre tersine çevir (1/a) ve üssü pozitife dönüştür.
n çift ise, tabanı karesiyle değiştir (a = a * a) ve üssü yarıya indir (n = n / 2).
n tek ise, sonucu geçerli tabanla çarpar (result = result * a) ve üssü 1 azalt.
n sıfır olana kadar döngüyü tekrarla.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Exponentiation (Üs Alma / Hızlı Üs Alma) Algoritması - TypeScript

1function fastExponentiation(a: number, n: number): number {
2  if (n === 0) return 1;
3  let result = 1, base = n < 0 ? 1 / a : a, exp = Math.abs(n);
4  while (exp > 0) {
5    if (exp % 2 === 1) { result *= base; exp -= 1; }
6    base *= base;
7    exp = Math.floor(exp / 2);
8  }
9  return result;
10}

Kendi Verilerinizle Test Edin

Taban ve üssü noktalı virgülle ayırın. Örnek: 2; 10 veya 3; 13

Exponentiation Demo

Taban ve üssü noktalı virgülle ayırın. Örnek: 2; 10 veya 3; 13

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(1)

Ortalama Durum: O(log n)

En Kötü Durum: O(log n)

Alan Karmaşıklığı

O(1) - Giriş boyutu ne olursa olsun, algoritma her zaman aynı sürede çalışır.

Neden O(log n) Çarpım?

Her çift adımda üs n değerinden n/2 değerine düşürülür.
Tek adımlarda ise üs 1 azaltılarak çift hale getirilir ve hemen bir sonraki adımda yarıya indirilir.
Bu durum üssün bit uzunluğu kadar adım gerçekleştirileceğini garantiler, yani en fazla 2 * log_2(n) çarpım yapılır.

Avantajlar ve Dezavantajlar

Avantajlar

Büyük üs değerlerinde doğrusal yönteme göre muazzam hız farkı sağlar.
Kriptografik algoritmaların (RSA gibi) modüler aritmetik kısmını uygulanabilir kılar.

Dezavantajlar

Ondalıklı üslerde çalışmaz, sadece tam sayı üsleri için uygundur.
Çok büyük taban veya üslerde sayısal taşma (overflow) yaşanabilir.

İlgili Algoritmalar

Exponentiation (Üs Alma / Hızlı Üs Alma) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Divide and Conquer

Problemi yarıya bölerek çözme stratejisinin temel matematiksel uygulamasıdır.

Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...

Exponentiation (Üs Alma / Hızlı Üs Alma) Algoritması

Exponentiation (Üs Alma / Hızlı Üs Alma) Açıklaması

Kaynak Notları

Sedgewick: a^n hesaplanmasında n tek ise a * a^(n-1), çift ise (a^(n/2))^2 indirgemesi.
Sedgewick: O(log n) çarpım maliyetiyle çalışan iterative ve recursive akışlar.

Çalışma Prensibi

Üs (n) sıfır ise sonuç 1'dir.
Üs negatif ise tabanı çarpmaya göre tersine çevir (1/a) ve üssü pozitife dönüştür.
n çift ise, tabanı karesiyle değiştir (a = a * a) ve üssü yarıya indir (n = n / 2).
n tek ise, sonucu geçerli tabanla çarpar (result = result * a) ve üssü 1 azalt.
n sıfır olana kadar döngüyü tekrarla.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Exponentiation (Üs Alma / Hızlı Üs Alma) Algoritması - TypeScript

1function fastExponentiation(a: number, n: number): number {
2  if (n === 0) return 1;
3  let result = 1, base = n < 0 ? 1 / a : a, exp = Math.abs(n);
4  while (exp > 0) {
5    if (exp % 2 === 1) { result *= base; exp -= 1; }
6    base *= base;
7    exp = Math.floor(exp / 2);
8  }
9  return result;
10}

Kendi Verilerinizle Test Edin

Taban ve üssü noktalı virgülle ayırın. Örnek: 2; 10 veya 3; 13

Exponentiation Demo

Taban ve üssü noktalı virgülle ayırın. Örnek: 2; 10 veya 3; 13

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(1)

Ortalama Durum: O(log n)

En Kötü Durum: O(log n)

Alan Karmaşıklığı

O(1) - Giriş boyutu ne olursa olsun, algoritma her zaman aynı sürede çalışır.

Neden O(log n) Çarpım?

Her çift adımda üs n değerinden n/2 değerine düşürülür.
Tek adımlarda ise üs 1 azaltılarak çift hale getirilir ve hemen bir sonraki adımda yarıya indirilir.
Bu durum üssün bit uzunluğu kadar adım gerçekleştirileceğini garantiler, yani en fazla 2 * log_2(n) çarpım yapılır.

Avantajlar ve Dezavantajlar

Avantajlar

Büyük üs değerlerinde doğrusal yönteme göre muazzam hız farkı sağlar.
Kriptografik algoritmaların (RSA gibi) modüler aritmetik kısmını uygulanabilir kılar.

Dezavantajlar

Ondalıklı üslerde çalışmaz, sadece tam sayı üsleri için uygundur.
Çok büyük taban veya üslerde sayısal taşma (overflow) yaşanabilir.

İlgili Algoritmalar

Exponentiation (Üs Alma / Hızlı Üs Alma) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Divide and Conquer

Problemi yarıya bölerek çözme stratejisinin temel matematiksel uygulamasıdır.