Bolme Algoritmasi

Question

$b$ tabaninda yazilmis iki sayiyi birbirine bolen verimli bir algoritma tarif edin.

Comments

Çıkarma işlemi ile gösterilebilir sanırım.

a/b işlemini.

a-b=x

x-b=y

y-b=w

şeklinde,çıkarma işleminin >=0 olması durumunu kontrol ederek gerçekleştirebiliriz.

---

karmasikligi (complexity) nedir bu algoritmanin?

---

açıkçası derinlemesine düşünmedim,belirlediğin bir problem varsa belirtebilirsin,o problem üstünden devam edelim.

---

$N/D = (Sonuc,Kalan)$  olsun.
Sanirim onerdiginiz algoritma su:

while N ≥ D do
  N := N − D
end
return N

Bu durumda while dongusu $Sonuc$ degeri kadar donecek. Sonucun uzulugu $w$ ise algoritma $O(w)$ dir diyebiliriz. 
Bir bu yontemle bolmeyi deneyin bir de okulda ogrendiginiz yontemle iki ayni sayiyi birbirine. Hangisinde sonucu daha hizli hesaplayacaksiniz ?
Okulda ogrendigimiz algoritmayi yazabilir misiniz ?

 

---

 0.0127saniye ile çalışan kod.

#include<stdio.h>

main()
{
	int a,b,i;
         a=10;
         b=5;
         i=0;
	while(a>=b)
	{
		a=a-b;
		i++;		
	}
	printf("%d",i);
	
}

0.0245 saniyede çalışan kod

main()
{
	int a,b,i;
         a=10;
         b=5;
	i=a/b;
	printf("%d",i);
	
}

 

---

DUZENLEME: (Orjinal metin asagidadir)

 

Bu test kodu

#include<stdlib.h>
#include<stdio.h>
#include<stdint.h>
#include<stddef.h>
#include<time.h>
#include <unistd.h>
#include <sys/time.h>

int64_t naiv_bolme(int64_t a , int64_t b)
{
    int64_t i;
    i=0;
    while(a>=b)
    {
        a=a-b;
        i++;		
    }
    return i;
	
}


int main(){
    srand(time(NULL));

    int64_t MO =  6431238016;

    int64_t res1 = 1;
    int64_t res2 = 2;
    time_t start = time(NULL);
    double time_naiv = 0 ;
    double time_builtin = 0 ;
     
    int64_t j = 1; 
    for(int64_t i = 1 ; i< INT64_MAX ; i+= MO){

                printf("  %ld / %ld \n",i,j);
                start = time(NULL);
                res2 = i/ j;
                time_builtin = (double)(time(NULL) - start);

                printf("      builtin     %lf  \n ",time_builtin);

                start = time(NULL);
                res1 = naiv_bolme(i, j);    
                time_naiv = (double)(time(NULL) - start);

            
                printf("      naiv        %lf  \n",time_naiv);

        }
        exit(0);
}

Bu da sonuclar

~ $ ./a.out
  1 / 1 
      builtin     0.000000  
       naiv        0.000000  
  6431238017 / 1 
      builtin     0.000000  
       naiv        11.000000  
  12862476033 / 1 
      builtin     0.000000  
       naiv        23.000000  
  19293714049 / 1 
      builtin     0.000000  
       naiv        34.000000  
  25724952065 / 1 
      builtin     0.000000  
       naiv        46.000000  
  32156190081 / 1 
      builtin     0.000000  
       naiv        58.000000  
  38587428097 / 1 
      builtin     0.000000  
       naiv        71.000000  
  45018666113 / 1 
      builtin     0.000000  
       naiv        81.000000  
  51449904129 / 1 
      builtin     0.000000  
       naiv        92.000000  
  57881142145 / 1 
      builtin     0.000000  

 

Sonunda beklemeye usendim

__________________________________________________________

(ORJINAL METIN)

 

MO yu 1 e esitlediginizde takilan kod  (derlerken (compile)-O0 bayragi(flag) ile derlemelisiniz yoksa derleyeciniz ne yapmaya calistiginizi anlayip optimize eder)

 

#include<stdlib.h>
#include<stdio.h>
#include<stdint.h>
#include<stddef.h>
#include<time.h>
#include <unistd.h>
#include <sys/time.h>

int64_t naiv_bolme(int64_t a , int64_t b)
{
    int64_t i;
    i=0;
    while(a>=b)
    {
        a=a-b;
        i++;		
    }
    return i;
	
}



int main(){
    srand(time(NULL));

    int64_t MAX_ITER = 1024;
    int64_t MO =  6431238016;
  
    int64_t res1 = 1;
    int64_t res2 = 2;
    time_t start = time(NULL);
    double time_naiv = 0 ;
    double time_builtin = 0 ;
    
         for(int64_t j = 1 ; j < MAX_ITER ; j++){
            for(int64_t i = INT64_MAX/MO ; i > INT64_MAX/MO - j ; i--){

                printf("  %ld / %ld \n",i,j);
                start = time(NULL);
                res2 = i/ j;
                time_builtin = (double)(time(NULL) - start);

                printf("      builtin     %lf  \n ",time_builtin);

                start = time(NULL);
                res1 = naiv_bolme(i, j);    
                time_naiv = (double)(time(NULL) - start);

            
                printf("      naiv        %lf  \n",time_naiv);
               
            }
        }
        exit(0);
}

 

biraz uzun oldu ama kisaca MAX_INT i kucuk bir sayiya bolmeye calisin arasindaki hiz farkini anlayacaksiniz

---

hocam yeni uyandık,sadede gelelim :F

---

kisaca diyorum ki yazdigin kodda $10/2$ hesaplamak yerine $MAX\_INT/1$ hesapla. Kodunu da optimizasyon olmadan derle (-O0 bayragi (flag) ile). Sonra kac dakika surdugunu paylas bizimle

---

benım basit kodlarımdaki eksik ne tam olarak ?

---

Kodunda bir eksik yok. Verdigin algoritma calisiyor ama verimli degil.

Normalde yazdigimiz kodlari test etmek icin birden fazla ornek kullaniriz. Bu sayede yazdigimiz algoritmanin hem degisik girdilere gore hizinda ne gibi degisimler oldugunu gorebiliriz hem de diger girdiler icin de dogru sonuc verip vermediginden emin olabiliriz. Hatta bazen ayni girdileri birden fazla defa verip calisma suresinin ortalamasini aliriz ki zaman olcumlerimiz gercege yakin olsun. (Bilgisayarinizin isletim sistemi sadece tek bir program calistirmiyor birden fazla program calistiriyor ve her program sirasini bekliyor. Ya tam test ettigimiz zaman isletim sistemi bizim programimizi uyutmaya karar verirse? Bu nedenle tek zaman olcumu saglikli degil )

Kodunu test etmek icin tek bir ornek kullanmissin ve tahminimce derlerken optimize eden bir c derleyicisi kullanmissin (cogu c derleyecisinin kutudan cikmis hali verdigin programi optimize ederek derler).

Kullandigin ornek $10/5$ (cok kucuk degerler) oldugu icin ve muhtemelen optimize edildigi icin yazdigin kod, verdigin algoritmanin hizi hakkinda bilgi sahibi mumkun olmuyor. Dedigim gibi $MAX\_INT/1$ i test edersen kodunda aradaki zaman farkini goreceksin.

---

max int / 1 = bölme algoritması ile 2,938 sn sürdü

sadece / operatörü ile 0,0135 saniye civarı sürdü.

burdaki farkın sebebi nedir sence,30 kat filan varda.

---

$MAX\_INT$ defa while loop dondu ve cikarma yapti cunku :)

---

Verdigin algoritma ilk akla gelen ama ayni zamanda cok verimsiz bir algoritma. Baska algoritma geliyor mu aklina mesela kalem kagitla bolme yaparken de burada yazdigin gibi mi yapiyorsun? Yada belki carparak bolebiliriz: $a/b$ kesirini oyle bir genisletelim ki $b$, $10$un herhangi sifirdan buyuk bir ussune yakin olsa gibi.

---

şöyleki "/" operatörü hangi algoritma ile sistemi çalıştırıyor ?  bunu biliyor muyuz ?

---

Kullandiginiz cipe gore degisir

---

mesela intel x86 ailesi icin sorulmus bu soru stackoverflow da.

Bu makalede anlatilan algoritma kullaniliyormus.

---

radix-16 diye bir sistemmiş.

içerisinde multiplexer var sanki (mux) kısaltımı gördüm.

ancak CSA filan anlamadım pek.öğrenim seviyemin üzerinde olabilir :D