Üs Alma İşleminin En Az Sayıda Çarpım ile Gerçekleştirilmesi

(Sayısal Yöntemler)

Bu yazıda üs alma işleminin en az sayıda çarpım ile nasıl gerçekleştirilebileceğini araştırıyoruz. Uygulamalarda üs alma işlemleri için hazır sistem işlevleri olmasına karşın biz bunun nasıl olduğunu öğrenmeye çalışacağız.

 
Hız derdi olmayan bir hesap makinesine 3 üzeri 36'nın kaç olduğunu sorduğunuzda 3'ü 35 kez kendisi ile çarpıp size sonucu söyleyebilir. Zaten el ile kullanılan bir aletin böyle bir derdi de yoktur. (Üs alma özelliği bulunmayan bir hesap makinesinin ise hiç yoktur.)

En alttaki C++ kodunda, üsler hesaplanırken ara sonuçların yeniden kullanılabilir olacağını göz önüne aldık.

Örneğin 3^8 değerini kaç adet çarpım yaparak bulabilirsiniz? Aşağıdaki gibi 7 kez çarpım yaparak bulunabilir.

Veya 3 çarpım yaparak.

Peki 3^12 değeri nasıl bulunabilir?

Bunun için yukarıdaki b ve c değerlerini çarpabilirsiniz. Bu yüzden bu yöntem, basitçe, ezberlenmiş çarpımların yeniden kullanılması şeklinde adlandırılabilir. Buradaki toplam çarpım sayısı 3^8 bulunana kadar geçen 3 adım ve b*c çarpımı dahil 4 olmaktadır.

Aşağıda görüldüğü gibi, sonuç, üs değerinin 2-üslü üslerinin çarpımı şeklinde ifade edilmektedir.

Çok kısa sürdüğü için 3 üzeri 12'nin hesaplanma süresini bulurken programımızdaki fonksiyonumuzu 1.000.000 kez çalıştırdık. Bu sayıdaki tekrarın toplam süresi -pek de hızlı olmayan bu bilgisayarımda- 110 milisaniye (yani 0,110 saniye) oldu. C++'deki POW() işlevi ise aynı değerler için aynı sayıdaki tekrarı 210 milisaniyede gerçekleştirdi.

GENELLEŞTİRME

Üs değeri ikili tabanda yazıldıktan sonra ikinin üslerinin toplamı olacak şekilde açılır.

Aşağıda 15 üssü için toplam 6 adet çarpım yapılmıştır.

Örneğin 1024 için 10 çarpımda sonuç bulunabilir. Burada ikili tabanda yazıldığında oluşan 1 rakamları çarpım adedini etkilemektedir.

Sayı üzeri 1024 değeri 1.000.000 kez yeniden hesaplandığında fonksiyonumuz POW() fonksiyonundan genel olarak daha kısa zaman almaktadır. 1024 üs değeri için toplam 10 adet çarpım yapmak yeterlidir.  ( LOG(2)1024 )

Toplam çarpım sayısı genel olarak LOG(2)ÜS + [İkili tabandaki 1'lerin sayısı -1 ]   kadardır. [ LOG(2)(log(2)ÜS) ]

ÜS HESAPLAMA İŞLEVİ

[VC++ 6.0]

double UsHesapla(double taban, int us)
{
/*
  Üs alma işlemini İkinin katlı üsleri yöntemiyle gerçekleştirir.
  POW işlevine göre kısıtlı olmasına karşın genel olarak daha hızlı olabilir.
  Serkan Şahinoğlu, 22.01.2005, http://BilgiTeknoloji.net
*/

  double sonuc = 1;
  double katli_us = taban;

  while (us>0)   //döngü adedi = ( log(us)/log(2) ) + 1;
  { 
    if ( (us & 1)==1 )  //en sağdaki bit 1 ise.
	sonuc = sonuc * katli_us;

    us = us/2;  // ikiye bölünce 1 bit sağa kayar.  (us=us>>1)
    if (us==0) break;

    katli_us *=katli_us;
  }

  return sonuc;
}

İşlevimizin bazı eksiklikleri vardır. Örneğin ondalıklı ve eksi üs değerleri için sonuç vermez. Ayrıca üssün 0, tabanın 1 olması gibi kontroller eklenebilse de amacımız yalnızca üs alma işlemini kısaltabilecek matematiksel bir yol araştırmaktır.

Örnek VC++ 6.0 projesini yüklemek için aşağıdaki bağlantıyı tıklatın.

uscarp.zip (54 kb.)

Serkan Şahinoğlu
22.01.2005