Urganch davlat universiteti axborot texnologiyalari kafedrasi

procedure ULdiv(const L1,L2:ULong;var frac,remain:ULong); 

  

var i:IDX_TYPE 

      v:DIG_TYPE; 

      L2_sh, subprev, sub_this:ULong; 

      cmp:

integer

; 

  

Begin 

    remain:=L1; 

    

if UL_cmp(L1,L2)<

0 

then begin 

      UL_init(frac,

0

);

exit 

    

end; 

    frac.used:=L1.used-L2used+

1

; 

    

for i:=frac.used downto 

1 

do begin 

      L2_sh:=L2; 

      UL_shift_left(L2_sh,i-

1

); 

      sub_this:=L2_sh; 

      UL_init(sub_prev,

0

); 

      v:=

0

; 

      cmp:=UL_cmp(remain,sub_this); 

      

while cmp>=

0 

do begin 

        sub_prev:=sub_this; 

        UL_add(subprev,L2_sh,sub_this); 

---

        inc(v); 

        cmp:=UL_cmp(remain,sub_this); 

       

end; 

      frac.mass[i]:=v; 

      UL_sub(remain,subprev,remain) 

     

end; 

     

if (frac.used>

0

) 

and (frac.mass[frac.used]=

0

) 

then 

dec(frac.used); 

    

End;

 

Biroq  ushbu  algoritmda  bo‘linma  raqamini  tanlash  bo‘yicha  qadamlar  miqdorining  BASE 

hisoblash  sistemasining  asosiga  o‘ta  murakkab  bo‘lganligi  vujudga  keladi  (murakkab  hollarda 

L2_sh, 2xL2_sh, 3xL2_sh,…, BASExL2_sh ning barcha qiymatlarini tanlab olish to‘g‘ri keladi). 

Nazariy jihatdan, BASR=O(1) (BASE ning konkret konstanti qiymati dasturni yozishda tiklanadi 

va n ga bog‘liq bo‘lmaydi), shuning uchun BASEga ko‘paytirish amallar miqdorining asimptotik 

bahosiga ta’sir qilmaydi. Biroq bu nazariy mulohazalar ichki asosni 10 dan 10000 gacha oshirish 

4.4-listingda  protsedutaning  ishini  2-40  marta  sekinlashtirish  to‘g‘risidagi  amaliy  faktni  rad 

etmaydi(qo‘shish,  ayirish  va  ko‘paytirish  uchun  raqamlar  miqdorining  kamayishi  hisobiga 

tezlashtirilgan  bo‘lsada).  Algoritm  amallari  miqdori  hisoblash  sistemasi  asosiga  yetarlicha 

bog‘liq  bo‘lishidan  to‘xtashi  maqsadga  muvofiq  v  ni  koldan  emas  balki  yanada  yaqinroq 

baholashdan.  Masalan,  remain  qoldig‘ining  bir-ikki  katta  raqamlarini  butun  bo‘linmani 

bo‘luvchining  katta  raqamiga  almashtirish  bilan  tanlash  mumkin.  Qat’iy  kunga  nazardan  bu 

yerda murakkabchilik yo‘q, biroq ba’zi nozik jarayonlar to‘g‘risida o‘ylab ko‘rish kerak: qachon 

ming bitta raqamini, qachon ikkita al ni olishni nazorat qilish kerak; b arabcha raqamlar bo‘yicha 

olingan  bo‘linma  raqamlarining  “haqiqiy”  qiymatidan  katta  bo‘lmasligi  uchun  katta  raqamlar 

bo‘linmasini qanday yaxlitlash kerak va shu kabilar.  

Uzoq  bo‘lishni  tezlashtirishning  boshqa  usuli  ikkilik  sistema  uchun  raqamni  tanlash  juda 

oddiyligini  tanlashga  asoslangan.  Hammasi  bo‘lib  ikkita  imkoniyatdan  (0  yoki  1)  bittasini 

tanlash kerak, buni esa bitta UL_cmp  (remain, L2_sh)≥0 taqqoslash bilan qilish mumkin. Katta 

BASE asosda bo‘linmaning raqamini bir necha anologik taqqoslashlar orqali ifodalashga harakat 

qilamiz.  Avvalo  remain  ni  [BASE/2]xL2_sh  bilan  taqqoslash  mumkin;  uning  natijasiga  bog‘liq 

holda v≥[BASE/2] yoki v<[BASE/2]ni olamiz; birinchi holda darhol remain ni [BASE/4]xL2_sh 

va  shu  kabilar  bilan  taqqoslash  mumkin.  Yozilgan  g‘oyani  istalgan  hisoblash  sistemasida 

qo‘llash  mumkin.  Biroq  uning  amalga  oshirilishi  BASE  ning  darajasi  bo‘lganida  oddiyroq  va 

qulayliroq (4.5-listing). 

 4.5-listing.  Uzun  butun  sonlarni  bo‘lishning  optimallashgan  prosedurasi  (2

TWO-POWER 

asos 

uchun)