To'liq kvadrat ildiz - Integer square root - Wikipedia

Yilda sonlar nazariyasi, butun kvadrat ildiz (isqrt) ning a musbat tamsayı n musbat butun son m qaysi kichik yoki teng bo'lgan eng katta butun son uchun kvadrat ildiz ning n,

Masalan, chunki va .

Nyuton usuli yordamida algoritm

Hisoblashning bir usuli va foydalanishdir Nyuton usuli tenglama uchun echim topish , takrorlanadigan formulani berish

The ketma-ketlik yaqinlashadi kvadratik ravishda ga kabi . Agar shunday bo'lsa, buni isbotlash mumkin dastlabki taxmin sifatida tanlanadi, darhol to'xtab qolish mumkin

buni ta'minlash uchun

Faqatgina butun bo'linishni ishlatish

Hisoblash uchun juda katta butun sonlar uchun n, ning keltirilgan qismidan foydalanish mumkin Evklid bo'linishi ikkala bo'linish operatsiyalari uchun. Buning afzalligi shundaki, har bir oraliq qiymat uchun faqat tamsayılar ishlatiladi, shuning uchun suzuvchi nuqta ko'p sonli raqamlar keraksiz. Bu takrorlanadigan formuladan foydalanishga teng

Haqiqatdan foydalanib

bunga erishish mumkinligini ko'rsatish mumkin cheklangan sonli takrorlashlar ichida.

Biroq, shart emas a sobit nuqta yuqoridagi takroriy formuladan. Darhaqiqat, buni ko'rsatish mumkin va agar shunday bo'lsa, qat'iy nuqta mukammal kvadrat emas. Agar mukammal kvadrat bo'lib, ketma-ketlik ikki davr orasida tugaydi va yaqinlashish o'rniga.

Hisoblash sohasi

Garchi bu mantiqsiz ko'pchilik uchun , ketma-ketlik faqat o'z ichiga oladi oqilona shartlar qachon oqilona. Shunday qilib, ushbu usul bilan .dan chiqish kerak emas maydon hisoblash uchun ratsional sonlar , ba'zi bir nazariy afzalliklarga ega bo'lgan haqiqat.

Mezonni to'xtatish

Buni isbotlash mumkin to'xtash mezoniga ega bo'lgan eng katta raqam

ta'minlaydi yuqoridagi algoritmda.

Barcha ratsional raqamlarni to'liq aks ettira olmaydigan (masalan, suzuvchi nuqta) raqamli formatlardan foydalanadigan dasturlarda yumaloq xatolardan himoya qilish uchun birdan kam to'xtash konstantasi ishlatilishi kerak.

Cda misolni amalga oshirish

// Butun sonning kvadrat ildiziimzosiz uzoq int_sqrt ( imzosiz uzoq s ){	imzosiz uzoq x0 = s >> 1;				// Dastlabki taxmin	// Sanitariya holatini tekshirish	agar ( x0 )	{		imzosiz uzoq x1 = ( x0 + s / x0 ) >> 1;	// Yangilash				esa ( x1 < x0 )				// Bu shuningdek tsiklni tekshiradi		{			x0 = x1;			x1 = ( x0 + s / x0 ) >> 1;		}				qaytish x0;	}	boshqa	{		qaytish s;	}}

Raqam bilan raqamli algoritm

An'anaviy qalam va qog'oz algoritmi kvadrat ildizni hisoblash uchun yuqori raqamlardan pastga tushishga qadar ishlashga asoslangan va har bir yangi raqam baribir kvadrat hosil qiladigan eng kattasini tanlaydi . Agar birovning o'rnidan keyin to'xtab qolsa, hisoblangan natija butun kvadrat ildiz bo'ladi.

Bitsel operatsiyalardan foydalanish

Agar ishlayotgan bo'lsa tayanch 2, raqamni tanlash 0 ("kichik nomzod") va 1 ("katta nomzod") o'rtasida soddalashtirilgan bo'lib, raqamli manipulyatsiyalar ikkilik almashtirish operatsiyalari bilan ifodalanishi mumkin. Bilan * ko'paytirish, << chap smenada bo'lish va >> mantiqiy to'g'ri siljish, a rekursiv har qanday kishining butun kvadrat ildizini topish algoritmi tabiiy son bu:

def integer_sqrt(n: int) -> int:    tasdiqlash n >= 0, "sqrt faqat salbiy bo'lmagan kirish uchun ishlaydi"    agar n < 2:        qaytish n    # Rekursiv qo'ng'iroq:    kichik_qandiq = integer_sqrt(n >> 2) << 1    katta_cand = kichik_cand + 1    agar katta_cand * katta_cand > n:        qaytish kichik_qandiq    boshqa:        qaytish katta_cand# teng:def integer_sqrt_iter(n: int) -> int:    tasdiqlash n >= 0, "sqrt faqat salbiy bo'lmagan kirish uchun ishlaydi"    agar n < 2:        qaytish n    # Shift miqdorini toping. Shuningdek qarang [[birinchi to'plamni topish]],    # shift = shift (log2 (n) * 0.5) * 2 = shift (ffs (n) * 0.5) * 2    siljish = 2    esa (n >> siljish) != 0:        siljish += 2    # Bitni belgilaydigan tsiklni echib oling.    natija = 0    esa siljish >= 0:        natija = natija << 1        katta_cand = (            natija + 1        )  # ^ 1 (xor) natijasi bilan bir xil, chunki oxirgi bit har doim 0 ga teng.        agar katta_cand * katta_cand <= n >> siljish:            natija = katta_cand        siljish -= 2    qaytish natija

Raqamma-raqamli algoritmning an'anaviy qalam-qog'oz taqdimotlari yuqoridagi kodda mavjud bo'lmagan turli xil optimallashtirishlarni, xususan, avvalgi raqamlarning kvadratini oldindan chiqarib tashlashning hiyla-nayrangini o'z ichiga oladi, bu esa ko'paytirishning umumiy bosqichini keraksiz qiladi. Qarang Kvadrat ildizlarni hisoblash usullari § Woo abacus misol uchun.[1]

Shuningdek qarang

Adabiyotlar

Tashqi havolalar