/ ve * işleçlerini kullanmadan tamsayı bölme işlemi gerçekleştiren bir işlev yazınız. Bu işi hızlı yapsın.

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Bu işi "hızlı yapmayan" çözüm herhalde şöyle olur:

import std.exception;

int böl(int sayı, int bölen)
{
   enforce(bölen != 0, "Sıfıra bölünemez.");

   // Kolaylık olsun diye artı değerlerle çalışacağız ama sonucun işaretini
   // de unutmayacağız.
   bool eksi_mi = false;

   if (sayı < 0) {
       sayı = -sayı;
       eksi_mi = !eksi_mi;
   }

   if (bölen < 0) {
       bölen = -bölen;
       eksi_mi = !eksi_mi;
   }

   int bölüm = 0;
   int toplam = 0;

   // Toplaya toplaya sayıya erişmeye çalışacağız. Kaç kere toplamışsak sonuç
   // odur.
   while (toplam < sayı) {
       ++bölüm;
       toplam += bölen;
   }

   // Sayıyı tam tutturamadıysak tamsayı bölmesinden kalanı silmek gerek.
   const mutlakSonuç = bölüm - (toplam != sayı);

   return eksi_mi ? -mutlakSonuç : mutlakSonuç;
}

unittest
{
   assertThrown(böl(2, 0));

   assert(böl(0, 1) == 0);
   assert(böl(4, 2) == 2);
   assert(böl(5, 2) == 2);
   assert(böl(333, 3) == 111);

   assert(böl(-4, 2) == -2);
   assert(böl(4, -2) == -2);
   assert(böl(-5, 2) == -2);

   assert(böl(-4, -2) == 2);
}

void main()
{}

Yukarıdaki programın sorunu, sonucun büyüklüğü ile doğru orantılı zaman almasıdır! Bakalım:

void main()
{
   import std.stdio;
   import std.datetime;

   auto ölçümler = benchmark!(() { böl(10_000_000, 1); },
                              () { böl(40_000_000, 1); })(100);

   foreach (i, ölçüm; ölçümler) {
       writefln("süre %s: %6s ms", i, ölçüm.to!("msecs", int));
   }
}

Çıktısı dört katı büyük sonucu hesaplamak için dört katı zaman gerektiğini gösteriyor:

'süre 0: 805 ms
süre 1: 3187 ms
'

Yani, bu algoritmanın karmaşıklığı O(sayı/bölen) kadar.

Şimdiki amaç "bu işi hızlı yapmak". :)

Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]

Çözdüm. :)

• Önceki çözümün tersine, 'toplam' adında bir değişkene eklemek yerine elimdeki sayıyı eksilte eksilte sıfıra gitmek daha mantıklı geldi.

• Önceki çözümün yavaşlığının nedeni, ekleme miktarı olarak hep bölen değeri kullanmasıydı. Bu çözüm, kendi miktarını kullanmadan önce onun iki katını kullanıyor. Örneğin, 10'a böleceği zaman sayının içinde kaç tane 10 olduğuna bakmadan önce kaç tane 20 olduğuna bakıyor. Özyinelemeli olarak, 20'ye bakmadan önce de kaç tane 40 olduğuna bakıyor, vs.

Sonuçta O(log(sayı/bölen)) karmaşıklığında bir çözüm bulunmuş oldu.

import std.exception;

/* Sayıdan miktar kadar değer eksiltir ve kaç kere eksilttiği bilgisini
* döndürür. İşi bittiğinde 'sayı' parametresi de değişmiştir. */
private int eksilt(ref int sayı, int miktar)
{
   /* Özyinelemeyi sonlandıran koşul. */
   if (sayı < miktar) {
       return 0;
   }

   /* Kendi işimize bakmadan önce iki katı büyük miktarın kaç kere
    * eskiltildiğini sayalım. */
   const büyükEksiltilen = eksilt(sayı, miktar + miktar);

   /* Şimdi, büyük miktar eksilterek elde ettiğimiz büyük sonuca kendi
    * miktarımızı eksilterek elde edeceğimiz yavaş sonucu ekleyeceğiz. */

   int eksiltilen = 0;

   while (sayı >= miktar) {
       sayı -= miktar;
       ++eksiltilen;
   }

   /* Büyük miktar kendi miktarımızın iki katı olduğuna göre bizden istenen
    * miktarın sonucuna onu iki kere eklemeliyiz. */
   return büyükEksiltilen + büyükEksiltilen + eksiltilen;
}

int böl(int sayı, int bölen)
{
   enforce(bölen != 0, "Sıfıra bölünemez.");

   // Kolaylık olsun diye artı değerlerle çalışacağız ama sonucun işaretini
   // de unutmayacağız.
   bool eksi_mi = false;

   if (sayı < 0) {
       sayı = -sayı;
       eksi_mi = !eksi_mi;
   }

   if (bölen < 0) {
       bölen = -bölen;
       eksi_mi = !eksi_mi;
   }

   const mutlakSonuç = eksilt(sayı, bölen);

   return eksi_mi ? -mutlakSonuç : mutlakSonuç;
}

unittest
{
   import std.conv;
   assertThrown(böl(2, 0));

   assert(böl(0, 1) == 0);
   assert(böl(4, 2) == 2);
   assert(böl(5, 2) == 2);
   assert(böl(333, 3) == 111);

   assert(böl(-4, 2) == -2);
   assert(böl(4, -2) == -2);
   assert(böl(-5, 2) == -2);

   assert(böl(-4, -2) == 2);
}

void main()
{
   import std.stdio;
   import std.datetime;

   auto ölçümler = benchmark!(() { böl(10_000_000, 1); },
                              () { böl(40_000_000, 1); })(100);

   foreach (i, ölçüm; ölçümler) {
       writefln("süre %s: %6s ms", i, ölçüm.to!("msecs", int));
   }
}

Daha önce saniyeler süren main içindeki hesaplar artık milisaniye cinsinden ölçülemeyecek kadar küçük: :)

'süre 0: 0 ms
süre 1: 0 ms
'
Ali

--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]