num_bits:=
0
;
end;
inc(num_bits);
dec(div_shift);
Ul_shr_binary(L2_sh,
1
);
end;
UL_sh1_binary(frac,num_bits-
1
);
end;
End;
4.1.6.Uzun sonning kvadrat ildizining butun qismi.
4.1-masala. Uzun son
L bo‘yicha kvadrat ildizining [
] butun qism topilsin. Kiruvchi
ma’lumotlar va natija o‘nlik sistemada yozilsin.
Masala taxlili. Kvadrat ildizning bitta katta raqamini aniqlash uchun kiruvchi sonni ikki razryad
(kichigidan boshlab) bo‘yicha guruhlarga ajratish va katta guruhga qarash yetarli. Ildizning katta
raqami d
k
[
] ga teng, bu yerda d
k
-argumentning katta guruhining qiymati. Boshqacha
aytganda ildizning katta raqami-bu d
k
ning maksimal qiymati, bunda d
k
2
≤d
k
. Masalan, 987654321
sonini guruhlarga ajratishda (o‘nlik sistemada) 9
1
87
1
65
1
43
1
21
1
ko‘rinishiga ega; katta guruh-9,
shuning kvadrat ildizning katta raqami -3 ga teng. Analogik ravishda ildizning kattaligi bo‘yicha
ikkinchi raqami argumentning faqat ikkinchi katta guruhlari bilan aniqlanadi. Uni d
k-1
ning eng
katta qiymati kabi izlash mumkin, bunda (10d
k
+d
k-1
)
2
≤E
k+1
, bu yerda E
k-1
= 100d
k
+d
k-1
ikki katta
guruh qiymati, masalan, 987654321 son uchun E
4
=987 ni olamiz. Bu ketma-ketlikni davom
qildirish qiyinmas- d
k-2
ni eng katta qiymat singari izlash, bunda 100d
k
-10 d
k-1
+ d
k
2
-2
≤E
k-2
, keyin
analogik ravishda
d
k-3
, d
k-4
va shu kabi. Bu raqamlardan har bittasini topish uchun d
i
ning 0 dan 9
gacha qatnashlarini tanlash yetarli: “d
i
ning joriy qiymati to‘g‘ri keladi”, “d
i
ning oldingi
qiymatiga qaytilsin” yoki “davom qildirilsin” kabi yechimlardan bittasini qabul qilish uchun d
k
,
d
k-1
,…, d
k+1
raqamlar oldindan topilgan, d
i
esa tanlab olinadi va E
i
bilan taqqoslanadigan d
k,
d
k-1…
d
i
uzun sonni har safar kvadratga ko‘tarish kerak. Bunday algoritmning amallarining umumiy
miqdorini 0(n
3
) kabi baholash mumkinligiga ishonch hosil qilish qiyin emas, bu yerda n-kiruvchi
sondagi raqamlar miqdori haqiqatdan ham ildizdagi raqamlar miqdori
[n/2]=Ө(n) ga teng,
ularning har birini izlashda O(n) uzunlikdagi sonni bir necha marta kvadratga ko‘tarish kerak,
kvadratga ko‘tarish O(n
2
) bahoga ega bo‘ladi, natijada O(n
3
) ni olamiz. Keltirilgan algoritmni
jiddiy ravishda optimallashtirish mumkin. Ma’lum (a+b)
2
=a
2
+2ab+b
2
formulani quyidagicha
ko‘rinishda yozamiz:
(a+b)
2
=a
2
+(2a+b)·b
(4.1)
Agar (4.1)da a ning o‘rniga d
k
d
k-1…
d
i+0
(uni A
i
deb belgilaymiz) sonni, b o‘rniga tanlanadigan d
i
sonni qo‘ysak, u holda d
i
qiymatini izlash uchun ishlatiladigan formulalarni A
i
2
+(2A
i
+d
i
)·d
i≤
E
i
ko‘rinishda yozish mumkin; A
i
2
ni o‘ngga kiritib, quyidagini olamiz:
(2A
i
+d
i
)·d
i
≤E
i
-A
i
2
(4.2)
(4.2)ning o‘ng qismi
d
i
ga bog‘liq emas. d
i
=0,1,2,3 da chap qismining qiymatlarini esa
quyidagicha ifodalaymiz va shu kabilar.
0
1
2A
i
+1
(2A
i
+2)·2=(2A
i
+1)+2A
i
+1+2,
(2A
i
+3)·3=(2A
i
+2)·2+2A
i
+2+3
ya’ni chap qismining har bir navbatdagi qiymatini oldingisi bo‘yicha qo‘shishlardan,
ayirishlardan va siljishlardan tashqari hech narsa kerak emas, Chunki
E
i
=100E
i+1
+g
i
, A
i
=10(A
i+1
+d
i+1
) va (4.1)dan
2
2
1
1
1
1
1
tan
_
'
_
_
_
100 (
(2
)
)
i
i
i
i
i
i
i
i
oldingidan
langan qiymatning
o ng qismi
oldingi chap qiymati
E
A
E
A
A
d
d
g
(4.2) ning oldingi (4.2)ning oldingi chap qismining tanlangan o‘ng qismi qiymati
Barcha sanab o‘tilganlardan 4.3 – rasmda qo‘llanilish misoli keltirilgan algoritm kelib chiqadi.
O‘rta qismda guruhlarga ajratilgan 987 654 321 argument, o‘rta qismining keyingi qatorlarida
qiymatlari va
ning tanlangan qiymatlari yozilgan. O‘ng qismida
nima uchun aynan qiymatlari tanlanishi ko‘rsatilgan. Chap qismida
va ketma - ketliklar
yozilgan. Natija – 31426; turli xil odimlarda ishlatilgan raqamlarning ketma – ketligi singari yoki
2 ga bo‘lingan 62852 (chapda pastdan) son singari olish mumkin.
4.3 – rasm. Pastda yaxlitlangan kvadrat ildizdan chiqarish misoli
Yangi algoritm amallar miqdorini baholaymiz. Ildizdagi raqamlar miqdori o‘zgarmaydi
, biroq endi
ning qiymati tanlanganida
bahodagi kvadratga ko‘tarish
ishlatilmay, balki
bahodagi qo‘shish ishlatiladi. Qo‘shni qiymatlar orasidagi o‘tish ham
(4.3 - rasm) ga binoan
amallarni talab etiladi. Jami bo‘lib umumiy baho
ga teng.
ni izlashda uzun qo‘shishlar miqdori BASE hisoblash sistemalarining asosiga bog‘liq
bo‘lib qolar ekan (bo‘lish uchun anologik ko‘rsatmaga qarang).
Nihoyat kvadrat ildiz uchun binor izlash (kengroq 5.1-bo‘limda) ham qo‘lash mumkin. Ildizning
bir necha katta raqamlarni kiruvchi sonning katta raqamlari bo‘yicha (odatdagi sqrt yordamida)
hisoblab va ushbu qiymatni qandaydir zahira bilan pastga va yuqoriga yahlitlab dastlabki
intervalni olish mumkin. Izlashning o‘zi ham o‘z-o‘zidan ayon: har bir sinov sonini kvadratga
ko‘tarish va ushbu kvadratning hamda kiruvchi sonning, izlash diapazonini chapga yoki o‘ngga
qiqartirish natijasiga bog‘liq holda, munosabatiga qarash.
Bunday algoritm murakkabligi -
, ya’ni u optimal emas. Agar asosiy maqsad – asosiy
arifmetik amallarning mavjud dasturostilar asosida ishlovchi dasturni tez yozish bo‘lsa bunday
yondashish oqilona bo‘ladi.
Do'stlaringiz bilan baham: 
