Rehber Hızlı üs alma yöntemi: Binary Exponentiation

Merhaba,

Algoritma serisini, görece basit yöntemlerden biri olan Binary Exponentiation ile devam ettirmek istedim. Fikrinin basit olmasının yanında oldukça pratik bir yöntem olmasından dolayı eğlenceli olduğunu düşünüyor, sizin de eğleneceğinizi umuyorum.

İyi okumalar.

---

Nedir problem?​

5^11 sayısını hesaplamamız gerektiğini düşünelim. Bunun için akla gelen ilk yöntemlerden biri bir cevap değişkeni tutup bunu 11 kere 5 ile çarpmak olur:

[CODE lang="cpp" title="Genel kuvvet hesaplama kodu"]#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
ll taban, us;
cin >> taban >> us;
ll cevap = 1;
for (ll i = 0; i < us; i++) {
cevap *= taban;
}
cout << taban << "^" << us << " = " << cevap << "\n";
}[/CODE]
[CODE title="Çıktı"]5^11 = 48828125[/CODE]
Ideone bağlantısı.

Yani, bir sıkıntı yok pek. İstediğimiz işlevi yerine getiriyor.

Peki, işleri biraz zorlaştıralım: Üssü 11'den 1 milyara çıkaralım. Biliyorum, biraz ani oldu. Şuradan sonucu inceleyebilirsiniz: Ideone bağlantısı. 0.81 saniyede hesaplamayı yaptı. Overflow (değer 64 bite bile sığmadığı için taşma) yaşandığından dolayı negatif bir sonuç elde ediyoruz (Python'da deneseniz asıl sonucu görürsünüz ama denemeyin bile, oldukça uzun sürer, ben denemeye kalktım.):

[CODE title="Çıktı"]5^1000000000 = -6547081224801363967[/CODE]

Biraz daha abartalım: Üs 10 milyar olsun. Sonucu inceleyebilirsiniz: Ideone bağlantısı. 10 saniyeye çıktı süre:

Bu işin nereye gittiğini tahmin edebiliyorsunuzdur: 10^11, 10^12, 10^13... Daha büyük üsler kısaca.

Bu yöntem pek de verimli değil, anlayacağınız.

---

Nedir daha verimlisi?​

İsmini çoktan verdim: Binary Exponentiation. Olayı da bir sayıyı kendisiyle çarpınca karesinin elde edilmesini avantaja dönüştürmek. İsminin nereden geldiğini merak ediyorsanız da aslında üssün ikili sistemdeki hâlini (binary representation) kullanıyor.

Mesela 5^11 için şunları yapıyor:

1. 5 ile başla.
2. 5 * 5 = 5^2.
3. 5^2 * 5^2 = 5^4.
4. 5^4 * 5^4 = 5^8.
5. 5^11'i elde etmek için 5, 5^2 ve 5^8'i çarp çünkü 1 + 2 + 8 = 11.

5^11 için en fazla 5^8'i hesaplamamız yetti ki o da 4 adım sürdü çünkü 11'in en soldaki 1 biti 4. sırada (1011, 2^3).

Benzer bir mantıkla mesela 5^1000000000 için de en fazla 5^(2^29)'u hesaplamamız gerekecekti ki o da 30 adım sürerdi.

Genel olarak üs n ise (pozitif tam sayı) yaklaşık log2(n) adımda taban fark etmeksizin a^n kuvvetini hesaplayabiliyoruz.

Peki, kare ala ala giderken cevapta hangi ara sonuçların (ara kuvvetler) dahil edileceğini tam nasıl bilebiliriz? Aynı esnada üssün bitlerini gezerek. Bit gezme işlemini de üssü ikiye böle böle giderek yapabiliriz. Bir örnekle açıklayayım, 3^378'i hesaplamaya çalışalım:

1. 378 bir çift sayı, en sağdaki biti 0. Dolayısıyla 3^1'i dahil etmiyoruz: cevap = 1.
2. 378 / 2 = 189, 3 * 3 = 3^2. 189 tek sayı olduğu için (en sağdaki bit 1) 3^2'yi dahil ediyoruz: cevap = 3^2.
3. 189 / 2 = 94 (Sondaki biti düşürmek aslında amaç, o yüzden ondalıklı kısmı yok sayıyoruz.), 3^2 * 3^2 = 3^4. 94 çift sayı olduğu için 3^4'ü dahil etmiyoruz.
4. 94 / 2 = 47, 3^4 * 3^4 = 3^8. 47 tek olduğundan dahil ediyoruz: cevap = 3^2 * 3^8 = 3^10.
5. 47 / 2 = 23, 3^8 * 3^8 = 3^16. 23 tek, dahil ediyoruz: cevap = 3^10 * 3^16 = 3^26.
6. 23 / 2 = 11, 3^16 * 3^16 = 3^32. 11 tek, dahil ediyoruz: cevap = 3^26 * 3^32 = 3^58.
7. 11 / 2 = 5, 3^32 * 3^32 = 3^64. 5 tek, dahil ediyoruz: cevap = 3^58 * 3^64 = 3^122.
8. 5 / 2 = 2, 3^64 * 3^64 = 3^128. Pas.
9. 2 / 2 = 1, 3^128 * 3^128 = 3^256. 1 tek, dahil ediyoruz: cevap = 3^122 * 3^256 = 3^378.

Üssün bitlerini gezerken tabanın "aynı hizadaki" kuvvetini hesaplıyor olduğumuza dikkat edin çünkü birini böle böle giderken diğerini çarpa çarpa gidiyoruz. Başka bir deyişle, birini sağa kaydıra kaydıra giderken diğerini sola kaydıra kaydıra gidiyoruz.

Bakın, 378'den 9'a indi adım sayısı çünkü 378'in en son 9. biti 1. Harika bir optimizasyon: n'den log2(n)'e.

Daha fazla baymayayım, buyurun, kodu:

[CODE lang="cpp" title="Binary Exponentiation kodu (C++)"]#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// Binary Exponentiation'ın kısaltması.
ll bin_exp(ll taban, ll us) {
ll cevap = 1;

// Üs 1'den büyükken...
while (us) { // Veya us > 0 / us != 0 vs.
// Üssün sonuncu biti 1 mi?
if (us % 2) { // Veya us & 1
cevap *= taban;
}
// 1 değilse "cevap"ı güncellemeyeceğiz
// ama her türlü "taban"ı kendisiyle çarpacağız.
taban *= taban;

us /= 2; // Üssü de bölmeyi unutmayalım.
// Veya us >>= 1
}

return cevap;
}

int main() {
ll taban, us;
cin >> taban >> us;
cout << taban << "^" << us << " = " << bin_exp(taban, us) << "\n";
}[/CODE]
Ideone bağlantısı.

Üs 10 milyarken programın çalışması 0 saniye sürmüş. Şaka gibi, değil mi? Değil, valla değil. log2(10^10) ~ 33 olunca while döngüsü toplam 33 kere dönmüş oluyor. E içindeki her bir işlem de çok hızlı olunca program acayip hızlı çalışıyor.

Hadi, biraz da hava atalım, madem bu kadar hızlı: 12345678910111213^1000000000000000000 için Ideone bağlantısı. 0.01 saniye sürüyor çalışması:

[CODE title="Çıktı"]12345678910111213^1000000000000000000 = 2448179987917832193[/CODE]

Dediğim gibi overflow'dan ötürü gerçekten çok uzak sonuçlar elde edebiliyoruz.

---

Gerçek sonuçları elde edemeyeceksek olayı ne?​

Elde edebilirsiniz aslında. C++'ta büyük sayılarla işlem yapabileceğiniz bir sınıf yazabilirsiniz veyahut hazır bir kütüphane kullanabilirsiniz. Benim bildiğim bir kütüphane olmadığı için bir kütüphane öneremeyeceğim. Python tarafında işler daha kolay çünkü dilin direkt kendisi destekliyor büyük sayıları (bit limiti olmayan). Hatta buyurun, Python kodunu da paylaşayım:

[CODE lang="python" title="Binary Exponentiation kodu (Python)"]def bin_exp(taban: int, us: int) -> int:
cevap = 1

while us:
if us % 2:
cevap *= taban

taban *= taban
us //= 2

return cevap


taban, us = map(int, input().split())

print(f"{taban}^{us} = {bin_exp(taban, us)}")[/CODE]

Buradaki üzücü durum şu ki kodu yavaşlatan kısım artık çarpım yapılan satırlar oluyor (cevap *= taban ve taban *= taban) çünkü Python büyük sayılarla işlem yaparken zaman alan teknikler kullanıyor. Adım sayısı yine az ama çarpımlar çok yavaşlıyor, sayılar büyüdükçe.

Aslına bakarsanız bu yöntemin asıl sonuçları bulmak için kullanıldığını ben görmedim. Bu yöntem, rekabetçi programlama (competitive programming) camiasında modüler aritmetikle birlikte kullanılır ve asıl cevabın yeterince büyük bir sayıya bölümünden kalan istenir ki böylelikle kullanılan yöntemin doğruluğunun kontrolü sağlanmış olur. Bundan bahsetmişken bu söz konusu "yeterince büyük sayılar"dan yaygın olan bir tanesini söyleyeyim: 10^9 + 7. Kendisi yeterince büyük bir asal sayıdır ve aynı kalan değerini yöntemin herhangi bir yerinde yanlışlık yaparak ya da farklı bir yanlış yöntemle bulma ihtimali oldukça düşüktür. İhtimal söz konusu aslında. İmkansız diye bir şey yok.

E bu kalan muhabbetinden de bahsetmişken yöntemin asıl kullanım şeklini göstereyim:

[CODE lang="cpp" title="Kalanlı Binary Exponentiation kodu (C++)"]#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// "mod" diye yeni bir parametre geldi.
// Sonucun "mod"a bölümünden kalanı döndüreceğiz.
ll bin_exp(ll taban, ll us, ll mod) {
// İpucu: Uygunsa Fermat'ın küçük teoremini, üssü küçültmek için kullanabilirsiniz.

// ÖNEMLİ: Başta şunu yapıyoruz ki sonradan bir overflow meydana gelmesin.
// Basit bir modüler aritmetik bilgisini uyguluyoruz.
taban %= mod;

ll cevap = 1;

while (us) {
if (us % 2) {
(cevap *= taban) %= mod;
}

(taban *= taban) %= mod;
us /= 2;
}

return cevap;
}

int main() {
ll taban, us, mod;
cin >> taban >> us >> mod;
cout << taban << "^" << us << " mod " << mod << " = " << bin_exp(taban, us, mod) << "\n";
}[/CODE]
Ideone bağlantısı.

Evet, yine 0 saniye görüyoruz, hem de 10^18 ^ (10^18) mod (10^9 + 7) için. Çok ama çok hızlı:

[CODE title="Çıktı"]1000000000000000000^1000000000000000000 mod 1000000007 = 504853526[/CODE]

WolframAlpha'mız da yardıma yetişiyor:

Eğlenceli bir bilgi: Python'daki pow fonksiyonunun 3 parametre alan hâli tam olarak bu yöntemi uyguluyor. Buyurun: Ideone bağlantısı.

---

Recursive implementasyonu​

Basitçe şu fikri de kodlayarak aynı işlevi yerine getirebilirsiniz: a^b = a^(b/2)^2 * (b tek ise a, değilse 1). Bu recursive bir tanım olduğu için (Tanımlamak için yine kendisini kullanıyoruz, örneğin n! = n * (n - 1)!.) fonksiyonu da recursive yazmamız gerekiyor:

[CODE lang="cpp" title="Recursive Binary Exponentiation kodu (C++)"]#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll bin_exp_recursive(ll taban, ll us, ll mod) {
// Base case (durmamız gereken durum).
if (!us)
return 1;

taban %= mod;

ll alt_cevap = bin_exp_recursive(taban, us / 2, mod);
ll carp = us % 2 ? taban : 1;

return alt_cevap * alt_cevap % mod * carp % mod;
}

int main() {
ll taban, us, mod;
cin >> taban >> us >> mod;
cout << taban << "^" << us << " mod " << mod << " = " << bin_exp_recursive(taban, us, mod) << "\n";
}[/CODE]
Ideone bağlantısı.

---

Çözebileceğiniz bir problem​

LeetCode üzerinden şu problemi kendiniz çözmeye çalışabilirsiniz: LeetCode - The World's Leading Online Programming Learning Platform. Burada taban bir ondalıklı sayı olabiliyor fakat sonucun belli bir aralığın içinde olacağı garantisi verilmiş yani kalanlı hesaba gerek yok.

---

Umarım başta umduğum üzere eğlenmişsinizdir ve yeni bir şeyler öğrenebilmiş veya keşfedebilmişsinizdir.

Ha, unutmuştum, hemen belirteyim: Takıldığınız herhangi bir yer olursa sormaktan asla çekinmeyin, seve seve cevaplarım.

Okuduğunuz için teşekkürler ve...

İyi Sosyal'ler! ​