Büyük Sayı Algoritmaları - Metin Dönüşümleri

Büyük sayı algoritmaları yazı dizisine, sayıdan metne, metinden sayıya dönüşüm fonksiyonları ile devam ediyoruz. Bu yazıda, onluk tabandaki metinler üzerinde işlem yapacağız. Bu fonksiyonlardan yola çıkarak, diğer sayı tabanlarında dönüşüm yapan fonksiyonlar da yazabilirsiniz.

Projenin bu yazıya kadar olan kısmını Github üzerinden indirebilirsiniz

Öncelikle, onluk tabandaki metni, bnz_t'ye çeviren fonksiyonla başlayalım.

Fonksiyon biraz uzun görünüyor, o yüzden parça parça inceleyelim.

Eğer metin eksi işareti ile başlıyorsa, sayının negatif olduğunu hatırlamamız gerek. Eksi işaretini bulursak, bir adım ilerliyoruz.

Varsa, metnin başındaki sıfırları da atlayabiliriz.

Eğer metin boş ise, sıfır döndüreceğiz.

Bu kısımda metinde kaç karakter olduğunu sayıyoruz. Bunun için strlen de kullanabiliriz. Ayrı bir fonksiyon çağrısı kullanmamak için, basit bir döngü ile uzunluğu hesapladım.

Onluk tabanda n haneli bir sayı, ikili tabanda yaklaşık 3.32n haneli bir sayıya karşılık gelir. Metin içindeki karakter sayısını 4 ile çarparak, ihtiyacımız olan bit sayısının biraz fazlasını elde edebiliriz. Elde ettiğimiz sayıyı, bn_digit_t'nin bit sayısına böldüğümüzde, hafızada kaç hanelik yer açmamız gerektiğini tespit etmiş oluyoruz. C'de bölme işleminin sıfıra doğru yuvarlamasından dolayı, +1 ekliyoruz. Böylece işlemin sonucunun sıfır olması ihtimalini ortadan kaldırıyoruz.

Burası fonksiyonun kalbi. Metni soldan sağa doğru tarayıp, her bir karakter için, elimizdeki sayıyı 10 ile çarpıp, o karakterin değerini sayıya ekliyoruz. Aynı zamanda, bn_mul_n1 ve bn_add_n1 fonksiyonlarının carry döndürüp döndürmediğine dikkat etmemiz gerekiyor. Bu fonksiyonlardan carry dönmesi halinde, dönen değeri bir üst haneye taşımamız gerekiyor. Bu sayede, elde ettiğimiz sayının kaç haneli olduğunu da takip etmiş oluyoruz.

bnz'nin hane sayısını ayarlarken, pozitif veya negatif olmasına dikkat ediyoruz. Böylece, char* -> bnz_t dönüşümünü tamamlamış olduk.

bnz_t -> char* dönüşümüne geçmeden önce bölme yazısında atladığım, tek haneli sayı ile bölme fonksiyonuna ihtiyacımız olacak.

Bu fonksiyon standart bölme fonksiyonuna göre oldukça sade, çünkü, bölen tek haneli olduğunda, önceki gibi bölümün tahmini değerini bulup düzeltmek yerine, doğrudan bölümü hesaplayabiliyoruz.

Büyük sayıyı, metne çevirmek için, aşağıdaki fonksiyonu kullanacağız.

Bu fonksiyonu da, küçük parçalar halinde inceleyelim.

Burada, metnin kaç karakterden oluşacağını hesaplıyoruz. Eğer, bnz'nin uzunluğu sıfır ise, fonksiyondan erken çıkma şansımız var. Aksi takdirde, sayının toplam bit sayısını üçe bölerek, metnin karakter sayısını tahmini olarak tespit edebiliriz.

Fonksiyon orjinal sayı üzerinde herhangi bir değişiklik yapmayacağı için, sayıyı geçici bir alana kopyalamamız gerekiyor.

Döngünün her adımında sayıyı 10'a bölüp, kalanı metne ekliyoruz. Her bölme işleminden sonra, tmp içinde kaç karakter kaldığını kontrol ediyoruz. Böylece, döngüden çıkmamız mümkün olacak.

Eğer sayı negatif ise, sayının sonuna eksi işareti atıyoruz. Eksi işaretini daha sonra doğru yerine alacağız.

Metnin sonuna null atıp, işaretçiyi bir adım geri alıyoruz. tds bu adımda, metnin null değerinden önceki karakterine işaret ediyor.

Metni oluştururken, küçük hanesinden büyük hanesine doğru oluşturduğumuz için, metni tersine çevirmemiz gerekiyor. Buradaki döngü ile bunu gerçekleştiriyoruz.

Aşağıdaki gibi bir fonksiyonla, yukarıdaki dönüşümleri test edebiliriz.

Eğer herşey yolunda giderse, bu fonksiyonun çıktısı aşağıdaki gibi olacak;

171428254796861184094610329674505562801 x 298502530806920071071164312285418709253 =
 51171767908676599055325833877649182072670634054758144917604139267629751297653

Performans Üzerine Düşünceler

Bu başlık altında, yukarıdaki iki fonksiyon için yapılabilecek bazı optimizasyonlardan bahsedeceğim. İsterseniz bu kısmı atlayabilirsiniz, ancak, çok fazla okuma/yazma yapacaksanız, optimizasyonun ölçülebilir faydaları olduğunu göreceksiniz.

Yapabileceğimiz ilk optimizasyon aşağıdaki döngü ile ilgili;

Bu döngüde, metindeki her bir karakter için bn_mul_n1 ve bn_add_n1fonksiyonları çalıştırılıyor. bn_mul_n1 içinde, length adet çarpma işlemi yapılıyor. Benzer şekilde, bn_add_n1 içinde ise, length adet toplama işlemi yapılıyor. İşlediğimiz sayı büyüdükçe, bu iki fonksiyonun ağırlığını hissetmeye başlarız. Bu iki fonksiyonu her karakterden sonra çağırmak yerine, metni küçük gruplar halinde işleyip, bu iki fonksiyonu her gruptan sonra birer kez çağırmak yeterli olacaktır. bn_digit_t 32 bit iken, 9 haneli gruplar halinde çalışabiliriz. Bu optimizasyon ile birlikte, yukarıdaki fonksiyonun ilgili kısmı aşağıdaki hali alacaktır.

Yapılabilecek bir diğer optimizasyon da, bnz_tods içindeki, aşağıdaki döngü ile ilgili.

Eğer onluk hane sayısı en baştan düzgün hesaplansaydı, fonksiyon sonunda metni ters çevirmek yerine, metni sağdan sola doğru oluşturabilirdik. Malesef, sadece sayının bit sayısına bakarak, onluk hane sayısını tespit etmek mümkün değil. Aşağıdaki tabloyu inceleyelim;

+------------+-----------+-----------+-----------+
| İkili H.S. | Min. Onlu | Max. Onlu | Onlu H.S. |
+------------+-----------+-----------+-----------+
| 1          | 1         | 1         | 1         |
+------------+-----------+-----------+-----------+
| 2          | 2         | 3         | 1         |
+------------+-----------+-----------+-----------+
| 3          | 4         | 7         | 1         |
+------------+-----------+-----------+-----------+
| 4          | 8         | 15        | 1-2 (%80) |
+------------+-----------+-----------+-----------+
| 5          | 16        | 31        | 2         |
+------------+-----------+-----------+-----------+
| 6          | 32        | 63        | 2         |
+------------+-----------+-----------+-----------+
| 7          | 64        | 127       | 2-3 (%44) |
+------------+-----------+-----------+-----------+
| 8          | 128       | 255       | 3         |
+------------+-----------+-----------+-----------+
| 9          | 256       | 511       | 3         |
+------------+-----------+-----------+-----------+
| 10         | 512       | 1023      | 3-4 (%4)  |
+------------+-----------+-----------+-----------+
| 11         | 1024      | 2047      | 4         |
+------------+-----------+-----------+-----------+
| 12         | 2048      | 4095      | 4         |
+------------+-----------+-----------+-----------+
| 13         | 4096      | 8191      | 4         |
+------------+-----------+-----------+-----------+
| 14         | 8192      | 16383     | 4-5 (%77) |
+------------+-----------+-----------+-----------+
| 15         | 16384     | 32767     | 5         |
+------------+-----------+-----------+-----------+
| 16         | 32768     | 65535     | 5         |
+------------+-----------+-----------+-----------+

Yukarıdaki tabloya göre, ikili hane sayısını bildiğimiz bir sayının, onluk hane sayısını yaklaşık %70 ihtimalle kesin olarak tespit edebiliriz. Kesin olarak tespit edemediğimiz durumlarda ise, iki ihtimalden birini seçmek zorundayız. Yukarıdaki tabloda, büyük sayının seçilmesi halinde, doğru tahminde bulunma oranını parantez içinde belirttim. Parantez içindeki değerleri incelediğimizde, ne küçük seçenek, ne de büyük seçenek diğerinden daha avantajlı görünüyor. Her zaman büyük seçeneği tercih ederek, %50 ihtimalle doğru tahminde bulunduğumuzu varsayarsak, toplamda %70 + %30 * %50 = %85 ihtimalle, ikili hane sayısına bakarak, onluk hane sayısını tespit edebileceğimiz yönünde bir tahminde bulunabiliriz.

C ile yukarıdaki tablonun son sütununu tespit etmek için, ikili hane sayısını \(\frac{ln 10}{ln 2} \approx 3.3219 \) sayısına bölmemiz gerekiyor. float sayılara ve bölme işlemine başvurmadan işlemin sonucunu aşağıdaki gibi bulabiliriz.

Devam etmeden önce, 1292913986 sayısını nasıl elde ettiğimize de değinelim. Bu sayı aslında 1 / 3.3219... * 2^32 sayısının aşağıya yuvarlanmış hali. İşlemi bu şekilde yapmak, genellikle float sayılar üzerinde bölme işlemi yapmaktan daha hızlı olacaktır.

Yukarıdaki hesabın doğru sonuç vermesi için, bit sayısını da doğru hesaplamalıyız. Bunun için, daha önce tanımladığımız nlz fonksiyonunu kullanacağız.

Eğer sayı negatif ise, eksi işareti için de bir yer ayırdık. Fonksiyonun ilk halinde, metni soldan sağa oluşturuyorduk, artık sağdan sola oluşturabiliriz.

Bu aşamada, yaklaşık %15 ihtimalle, metnin ilk karakterinde anlamsız bir değer olacaktır. Bunu düzeltmek için, hafızayı 1 karakter sola kaydırmamız gerek.

Böylece, bu optimizasyonu da uygulamaya geçirmiş olduk.

Bir sonraki yazıda, doğal sayılar üzerinde yaptığımız dört işlemi kullanarak, tam sayılar üzerinde dört işlem yapan fonksiyonlarla devam edeceğiz.