อัลกอริทึมรากที่สอง

อัลกอริทึมรากที่สอง คำนวณ รากที่สอง ที่ไม่เป็นลบของจำนวน จริง บวก เนื่องจากรากที่สองของจำนวนธรรมชาติ ทั้งหมด ยกเว้นกำลังสองสมบูรณ์เป็นจำนวนอตรรกยะ^{[ 1 ]} รากที่สองจึงมักจะคำนวณได้เพียงความแม่นยำที่จำกัดเท่านั้นอัลกอริทึม เหล่านี้โดยทั่วไป จะสร้างชุดของการประมาณค่า ที่แม่นยำขึ้นเรื่อย ๆ ${\displaystyle {\sqrt {S}}}$${\displaystyle S}$

วิธีการคำนวณรากที่สองส่วนใหญ่เป็นแบบวนซ้ำ: หลังจากเลือกค่าประมาณเริ่มต้นที่เหมาะสมแล้วจะทำการ ปรับปรุง ค่าแบบวนซ้ำไปเรื่อยๆจนกว่าจะถึงเกณฑ์การยุติที่กำหนดไว้ วิธีหนึ่งในการปรับปรุงค่าคือวิธีของเฮรอนซึ่งเป็นกรณีพิเศษของวิธีของนิวตันหากการหารมีค่าใช้จ่ายสูงกว่าการคูณมาก อาจเป็นการดีกว่าที่จะคำนวณค่าผกผันของรากที่สองแทน ${\displaystyle {\sqrt {S}}}$

นอกจากนี้ยังมีวิธีการอื่น ๆ ในการคำนวณรากที่สองโดยการคำนวณทีละหลักหรือใช้ชุดอนุกรมเทย์เลอร์ส่วนการประมาณค่ารากที่สองที่เป็นจำนวนตรรกยะนั้น สามารถคำนวณได้โดยใช้การกระจายเศษส่วนต่อเนื่อง

วิธีการที่ใช้จะขึ้นอยู่กับความแม่นยำที่ต้องการ เครื่องมือที่มีอยู่ และกำลังการคำนวณ โดยคร่าวๆ แล้ว วิธีการอาจแบ่งออกเป็น วิธีที่เหมาะสำหรับการคำนวณในใจ วิธีที่โดยทั่วไปแล้วต้องใช้กระดาษและดินสอเป็นอย่างน้อย และวิธีที่เขียนเป็นโปรแกรมเพื่อประมวลผลบนคอมพิวเตอร์อิเล็กทรอนิกส์หรืออุปกรณ์คำนวณอื่นๆ อัลกอริทึมอาจคำนึงถึงการลู่เข้า (จำนวนรอบที่จำเป็นเพื่อให้ได้ความแม่นยำที่กำหนด) ความซับซ้อนในการคำนวณของการดำเนินการแต่ละครั้ง (เช่น การหาร) หรือรอบการคำนวณ และการแพร่กระจายของข้อผิดพลาด (ความแม่นยำของผลลัพธ์สุดท้าย)

วิธีการบางอย่าง เช่น การหารสังเคราะห์ด้วยกระดาษและดินสอ และการกระจายอนุกรม ไม่จำเป็นต้องมีค่าเริ่มต้น ในบางกรณี อาจจำเป็นต้องใช้ รากที่สองที่เป็นจำนวนเต็มซึ่งก็คือรากที่สองที่ปัดเศษหรือตัดทิ้งให้เป็นจำนวนเต็มที่ใกล้ที่สุด (อาจใช้วิธีการที่ดัดแปลงในกรณีนี้)

วิธีการหาค่ารากที่สอง (โดยเฉพาะรากที่สองของ 2 ) เป็นที่รู้จักกันมาอย่างน้อยตั้งแต่สมัยบาบิโลนโบราณในศตวรรษที่ 17 ก่อนคริสตกาล นักคณิตศาสตร์ชาวบาบิโลนคำนวณรากที่สองของ 2 ได้ถึงสาม หลักฐาน หกสิบหลังจาก 1 แต่ไม่ทราบแน่ชัดว่าคำนวณอย่างไร พวกเขารู้จักวิธีประมาณค่าด้านตรงข้ามมุมฉากโดยใช้ (เช่น ให้ค่าสำหรับเส้นทแยงมุมของประตูที่มีความสูงเป็นแท่งและความกว้างเป็นแท่ง) และพวกเขาอาจใช้วิธีการที่คล้ายกันในการหาค่าประมาณของ^{[ 2 ]}$${\displaystyle {\sqrt {a^{2}+b^{2}}}\approx a+{\frac {b^{2}}{2a}}}$$${\displaystyle {\frac {41}{60}}+{\frac {15}{3600}}}$${\displaystyle {\frac {40}{60}}}$${\displaystyle {\frac {10}{60}}}$${\displaystyle {\sqrt {2}}.}$

วิธีของเฮรอนจากอียิปต์ในศตวรรษที่ 1 เป็นอัลกอริทึมแรกที่สามารถตรวจสอบได้สำหรับการคำนวณรากที่สอง^{[ 3 ]}

วิธีการวิเคราะห์สมัยใหม่เริ่มได้รับการพัฒนาหลังจากมีการนำ ระบบ ตัวเลขอาหรับมาใช้ในยุโรปตะวันตกในช่วงต้นยุคฟื้นฟูศิลปวิทยา^{[ 4 ]}

ในปัจจุบัน อุปกรณ์คอมพิวเตอร์เกือบทั้งหมดมีฟังก์ชันการหาค่ารากที่สองที่รวดเร็วและแม่นยำ ไม่ว่าจะเป็นในรูปแบบของโครงสร้างภาษา โปรแกรม ฟังก์ชันภายในของคอมไพเลอร์ หรือฟังก์ชันในไลบรารี หรือตัวดำเนินการฮาร์ดแวร์ โดยอาศัยขั้นตอนใดขั้นตอนหนึ่งที่กล่าวมาแล้ว

อัลกอริทึมการหาค่ารากที่สองแบบวนซ้ำหลายๆ วิธี จำเป็นต้องใช้ค่าเริ่มต้น (seed value ) ค่าเริ่มต้นนี้ต้องเป็นจำนวนบวกที่ไม่เป็นศูนย์ ควรอยู่ระหว่าง 1 ถึงn ซึ่งเป็นจำนวนที่ต้องการหาค่ารากที่สอง เพราะค่ารากที่สองต้องอยู่ในช่วงนั้น หากค่าเริ่มต้นอยู่ห่างจากค่ารากมาก อัลกอริทึมจะต้องการการวนซ้ำมากขึ้น หากเริ่มต้นด้วย n = 0 (หรือ n = 0 ) การวนซ้ำประมาณn = 0 จะเสียไปกับการหาค่าประมาณขนาดของราก ดังนั้นจึงเป็นประโยชน์ที่จะมีค่าประมาณคร่าวๆ ซึ่งอาจมีความแม่นยำจำกัด แต่คำนวณได้ง่าย โดยทั่วไป ยิ่งค่าประมาณเริ่มต้นดีเท่าไร การลู่เข้าก็จะยิ่งเร็วขึ้นเท่านั้น สำหรับวิธีของนิวตัน ค่าเริ่มต้นที่มากกว่าค่ารากเล็กน้อยจะลู่เข้าเร็วกว่าค่าเริ่มต้นที่น้อยกว่าค่ารากเล็กน้อย ${\displaystyle S}$${\displaystyle x_{0}=1}$${\displaystyle S}$${\displaystyle {\tfrac {1}{2}}\vert \log _{2}S\vert }$

โดยทั่วไป การประมาณค่าจะขึ้นอยู่กับช่วงเวลาที่กำหนดไว้ซึ่งทราบว่ามีราก (เช่น) อยู่ภายใน ค่าประมาณคือค่าเฉพาะของการประมาณค่าเชิงฟังก์ชันของในช่วงเวลานั้น การได้ค่าประมาณที่ดีขึ้นนั้นเกี่ยวข้องกับการได้ขอบเขตที่แคบลงของช่วงเวลา หรือการหาการประมาณค่าเชิงฟังก์ชันที่ดีกว่าสำหรับ ซึ่งอย่างหลังมักหมายถึงการใช้พหุนามลำดับสูงกว่าในการประมาณค่า แม้ว่าการประมาณค่าทั้งหมดจะไม่ใช่พหุนามก็ตาม วิธีการประมาณค่าที่ใช้กันทั่วไป ได้แก่ แบบสเกลาร์ แบบเชิงเส้น แบบไฮเปอร์โบลิก และแบบลอการิทึม ฐานทศนิยมมักใช้สำหรับการประมาณค่าในใจหรือโดยใช้กระดาษและดินสอ ฐานไบนารีเหมาะสมกว่าสำหรับการประมาณค่าด้วยคอมพิวเตอร์ ในการประมาณค่า เลขชี้กำลังและแมนทิสซาจะถูกแยกออกจากกัน เหมือนกับที่แสดงในสัญกรณ์วิทยาศาสตร์ ${\displaystyle [x_{0},S/x_{0}]}$${\displaystyle f(x)={\sqrt {x}}}$${\displaystyle f(x)}$

โดยทั่วไปแล้ว ตัวเลขจะถูกแสดงในสัญกรณ์วิทยาศาสตร์เป็นโดยที่และnเป็นจำนวนเต็ม และช่วงของรากที่สองที่เป็นไปได้คือโดย ที่${\displaystyle S}$${\displaystyle a\times 10^{2n}}$${\displaystyle 1\leq a<100}$${\displaystyle {\sqrt {a}}\times 10^{n}}$${\displaystyle 1\leq {\sqrt {a}}<10}$

วิธีการแบบสเกลาร์จะแบ่งช่วงออกเป็นช่วงย่อย และค่าประมาณในแต่ละช่วงย่อยจะแสดงด้วยตัวเลขสเกลาร์เพียงตัวเดียว หากพิจารณาช่วงเป็นช่วงย่อยเดียว ค่าเฉลี่ยเลขคณิต (5.5) หรือค่าเฉลี่ยเรขาคณิต ( ) ครั้งจะเป็นค่าประมาณที่สมเหตุสมผล ข้อผิดพลาดสัมบูรณ์และสัมพัทธ์สำหรับค่าเหล่านี้จะแตกต่างกัน โดยทั่วไปแล้ว การใช้ตัวเลขสเกลาร์เพียงตัวเดียวจะมีความแม่นยำต่ำมาก การประมาณค่าที่ดีกว่าจะแบ่งช่วงออกเป็นสองช่วงย่อยขึ้นไป แต่การประมาณค่าแบบสเกลาร์มีความแม่นยำต่ำโดยธรรมชาติ ${\displaystyle {\sqrt {10}}\approx 3.16}$${\displaystyle 10^{n}}$

สำหรับสองช่วงเวลาที่แบ่งตามเรขาคณิต รากที่สองสามารถประมาณได้ดังนี้^{[หมายเหตุ 1 ]}${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 10^{n}}$$${\displaystyle {\sqrt {S}}\approx {\begin{cases}2\times 10^{n}&{\text{ถ้า }}a<10,\\6\times 10^{n}&{\text{ถ้า }}a\geq 10.\end{cases}}}$$

การประมาณค่านี้มีค่าความคลาดเคลื่อนสัมบูรณ์สูงสุดที่และค่าความคลาดเคลื่อนสัมพัทธ์สูงสุด 100% ที่ ${\displaystyle 4\times 10^{n}}$${\displaystyle a=100}$${\displaystyle a=1}$

วิธีการประมาณค่าที่ดีกว่า และเป็นวิธีมาตรฐานที่ใช้กัน คือการประมาณค่าเชิงเส้นของฟังก์ชันบนส่วนโค้งเล็กๆ ถ้าหากว่า ยกกำลังของฐานออกจากจำนวนS ดังที่กล่าวมาข้างต้น และลดช่วงลงเหลือ [1, 100] อาจใช้ เส้นตัดที่ลากผ่านส่วนโค้ง หรือเส้นสัมผัสที่จุดใดจุดหนึ่งตามส่วนโค้งเป็นค่าประมาณได้ แต่เส้นถดถอยกำลังสองน้อยที่สุดที่ตัดกับส่วนโค้งจะมีความแม่นยำกว่า ${\displaystyle y=x^{2}}$

เส้นถดถอยกำลังสองน้อยที่สุดจะลดความแตกต่างเฉลี่ยระหว่างค่าประมาณและค่าของฟังก์ชันให้เหลือน้อยที่สุด สมการของมันคือ ( เรียงลำดับใหม่เป็น) (ปัดเศษสัมประสิทธิ์เพื่อให้คำนวณง่ายขึ้น) ${\displaystyle y=8.7x-10}$${\displaystyle x=0.115y+1.15}$$${\displaystyle {\sqrt {S}}\approx (a/10+1.2)\cdot 10^{n}}$$

นั่นคือค่าประมาณที่ดีที่สุดโดยเฉลี่ยที่สามารถทำได้ด้วยการประมาณเชิงเส้นแบบชิ้นเดียวของฟังก์ชันในช่วง [1, 100] โดยมีข้อผิดพลาดสัมบูรณ์สูงสุด 1.2 ที่a = 100 และข้อผิดพลาดสัมพัทธ์สูงสุด 30% ที่S = 1 และ 10 ^{[หมายเหตุ 2 ]}${\displaystyle y=x^{2}}$

ในการหารด้วย 10 ให้ลบหนึ่งออกจากเลขชี้กำลังของaหรือพูดอีกอย่างคือเลื่อนจุดทศนิยมไปทางซ้ายหนึ่งหลัก สำหรับสูตรนี้ ค่าคงที่บวก 1 บวกกับค่าเพิ่มเล็กน้อยจะทำให้ได้ค่าประมาณที่น่าพอใจ ดังนั้นการจำตัวเลขที่แน่นอนจึงไม่ใช่ภาระ การประมาณค่า (ไม่ว่าจะปัดเศษหรือไม่) โดยใช้เส้นเดียวที่ครอบคลุมช่วง [1, 100] มีความแม่นยำน้อยกว่าหนึ่งหลักสำคัญ ข้อผิดพลาดสัมพัทธ์มากกว่า 1/2² ^{ดังนั้น}จึงมีข้อมูลน้อยกว่า 2 บิต ความถูกต้องถูกจำกัดอย่างมากเนื่องจากช่วงมีขนาดสองลำดับ ซึ่งค่อนข้างใหญ่สำหรับการประมาณค่าประเภทนี้

การประมาณค่าที่ดีกว่ามากสามารถทำได้โดยการประมาณเชิงเส้นแบบแบ่งส่วน: ส่วนของเส้นตรงหลายส่วน แต่ละส่วนประมาณส่วนโค้งย่อยบางส่วนของส่วนโค้งเดิม ยิ่งใช้ส่วนของเส้นตรงมากเท่าไร การประมาณค่าก็จะยิ่งดีขึ้นเท่านั้น วิธีที่พบได้บ่อยที่สุดคือการใช้เส้นสัมผัส ทางเลือกที่สำคัญคือวิธีการแบ่งส่วนโค้งและตำแหน่งของจุดสัมผัส วิธีที่มีประสิทธิภาพในการแบ่งส่วนโค้งจาก^y = 1ถึงy = 100คือการใช้เรขาคณิต: สำหรับสองช่วง ช่วงของขอบเขตจะเป็นรากที่สองของขอบเขตของช่วงเดิม 1×100 นั่นคือ[ 1 , ^2√100 ]และ[ 2√100 , 100 ]สำหรับช่วงสามช่วง ขอบเขตคือรากที่สามของ 100: [1, ³ √ 100 ], [ ³ √ 100 ,( ³ √ 100 ) ² ]และ[( ³ √ 100 ) ² ,100]เป็นต้น สำหรับช่วงสองช่วง² √ 100 = 10ซึ่งเป็นจำนวนที่สะดวกมาก เส้นสัมผัสหาได้ง่าย และอยู่ที่⁠ ⁠${\displaystyle x={\sqrt {1{\sqrt {10}}}}}$และ⁠ ⁠${\displaystyle x={\sqrt {10{\sqrt {10}}}}}$สมการของเส้นสัมผัสคือ: และเมื่อกลับค่า รากที่สองคือ: และดังนั้นสำหรับ: ${\displaystyle y=3.56x-3.16}$${\displaystyle y=11.2x-31.6}$${\displaystyle x=0.28y+0.89}$${\displaystyle x=.089y+2.8}$${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx {\begin{cases}(0.28a+0.89)\cdot 10^{n}&{\text{if }}a<10,\\(.089a+2.8)\cdot 10^{n}&{\text{if }}a\geq 10.\end{cases}}}$$

ค่าความคลาดเคลื่อนสัมบูรณ์สูงสุดเกิดขึ้นที่จุดสูงสุดของช่วง คือที่a = 10 และ 100 โดยมีค่า 0.54 และ 1.7 ตามลำดับ ส่วนค่าความคลาดเคลื่อนสัมพัทธ์สูงสุดเกิดขึ้นที่จุดปลายของช่วง คือที่a = 1, 10 และ 100 โดยมีค่า 17% ในทั้งสองกรณี 17% หรือ 0.17 มีค่ามากกว่า 1/10 ดังนั้นวิธีการนี้จึงให้ความแม่นยำน้อยกว่าหนึ่งตำแหน่งทศนิยม

ในบางกรณี การประมาณค่าแบบไฮเปอร์โบลาอาจมีประสิทธิภาพ เนื่องจากไฮเปอร์โบลาเป็นเส้นโค้งนูนเช่นกัน และอาจวางตัวตามส่วนโค้งของy = x² ได้ดีกว่าเส้น ^{ตรง การประมาณค่าแบบไฮเปอร์โบลามีความซับซ้อนในการคำนวณมากกว่า เนื่องจากจำเป็นต้องใช้การหารแบบลอยตัว การประมาณค่าแบบไฮเปอร์โบ ลา}ที่ใกล้เคียงค่าเหมาะสมที่สุดสำหรับx²ในช่วง [1, 100] คือ⁠ ⁠เมื่อสลับตำแหน่งแล้ว รากที่สองคือ⁠ ⁠ดังนั้นสำหรับ: ${\displaystyle y=190/(10-x)-20}$${\displaystyle x=10-190/(y+20)}$${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx \left(10-{\frac {190}{a+20}}\right)\cdot 10^{n}}$$

การหารจำเป็นต้องมีความแม่นยำเพียงทศนิยมตำแหน่งเดียว เพราะค่าประมาณโดยรวมมีความแม่นยำเพียงเท่านั้น และสามารถทำได้ในใจ ค่าประมาณแบบไฮเปอร์โบลิกนี้โดยเฉลี่ยแล้วดีกว่าค่าประมาณแบบสเกลาร์หรือเชิงเส้น มีข้อผิดพลาดสัมบูรณ์สูงสุด 1.58 ที่a = 100และข้อผิดพลาดสัมพัทธ์สูงสุดที่a = 10โดยที่ค่าประมาณ 3.67 สูงกว่ารากที่สองของ 3.16 ถึง 16.0% หากทำการคำนวณแบบนิวตัน-ราฟสันโดยเริ่มจากค่าประมาณ 10 จะต้องใช้การคำนวณสองครั้งเพื่อให้ได้ 3.66 ซึ่งตรงกับค่าประมาณแบบไฮเปอร์โบลิก สำหรับกรณีทั่วไปเช่น 75 ค่าประมาณแบบไฮเปอร์โบลิก 8.00 ต่ำกว่าความเป็นจริงเพียง 7.6% และจะต้องทำการคำนวณแบบนิวตัน-ราฟสัน 5 ครั้งโดยเริ่มจาก 75 เพื่อให้ได้ผลลัพธ์ที่แม่นยำยิ่งขึ้น

วิธีการที่คล้ายคลึงกับการประมาณค่าเชิงเส้นแบบเป็นช่วง แต่ใช้เพียงเลขคณิตแทนสมการพีชคณิต คือการใช้ตารางการคูณในทางกลับกัน: รากที่สองของจำนวนระหว่าง 1 ถึง 100 จะอยู่ระหว่าง 1 ถึง 10 ดังนั้น ถ้าเรารู้ว่า 25 เป็นกำลังสองสมบูรณ์ (5 × 5) และ 36 เป็นกำลังสองสมบูรณ์ (6 × 6) แล้ว รากที่สองของจำนวนที่มากกว่าหรือเท่ากับ 25 แต่น้อยกว่า 36 จะเริ่มต้นด้วย 5 ในทำนองเดียวกันสำหรับจำนวนระหว่างกำลังสองอื่นๆ วิธีนี้จะให้ตัวเลขหลักแรกที่ถูกต้อง แต่ไม่แม่นยำถึงหนึ่งหลัก: ตัวอย่างเช่น ตัวเลขหลักแรกของรากที่สองของ 35 คือ 5 แต่รากที่สองของ 35 เกือบจะเป็น 6

วิธีที่ดีกว่าคือการแบ่งช่วงออกเป็นช่วงๆ โดยแบ่งครึ่งระหว่างกำลังสอง ดังนั้นสำหรับจำนวนใดๆ ที่อยู่ระหว่าง 25 และครึ่งทางของ 36 ซึ่งคือ 30.5 ให้ประมาณค่าเป็น 5; สำหรับจำนวนใดๆ ที่มากกว่า 30.5 จนถึง 36 ให้ประมาณค่าเป็น 6 ^{[หมายเหตุ 3 ]} ขั้นตอนนี้ใช้การคำนวณเพียงเล็กน้อยเพื่อหาจำนวนขอบเขตที่อยู่ตรงกลางระหว่างผลคูณสองค่าจากตารางการคูณ นี่คือตารางอ้างอิงของขอบเขตเหล่านั้น:

เอ	ช่องสี่เหลี่ยมที่ใกล้ที่สุด	${\displaystyle k={\sqrt {a}}}$ก่อตั้ง
1
	1 (= 1 2 )	1
2.5
	4 (= 2 2 )	2
6.5
	9 (= 3 2 )	3
12.5
	16 (= 4 2 )	4
20.5
	25 (= 5 2 )	5
30.5
	36 (= 6 2 )	6
42.5
	49 (= 7 2 )	7
56.5
	64 (= 8 2 )	8
72.5
	81 (= 9 2 )	9
90.5
	100 (= 10 2 )	10
100

ขั้นตอนสุดท้ายคือการคูณค่าประมาณkด้วยกำลังของสิบหารด้วย 2 ดังนั้นสำหรับ, ${\displaystyle S=a\cdot 10^{2n}}$$${\displaystyle {\sqrt {S}}\approx k\cdot 10^{n}}$$

วิธีการนี้ให้ความแม่นยำโดยปริยายหนึ่งหลักสำคัญ เนื่องจากปัดเศษไปที่หลักแรกที่ดีที่สุด

วิธีการนี้สามารถขยายได้ถึง 3 หลักสำคัญในกรณีส่วนใหญ่ โดยการประมาณค่าระหว่างกำลังสองที่ใกล้ที่สุดที่ล้อมรอบตัวดำเนินการ ถ้าแล้วจะมีค่าประมาณเท่ากับ k บวกเศษส่วน ซึ่งก็คือผลต่างระหว่างaและk² ^หารด้วยผลต่างระหว่างกำลังสองทั้งสอง ${\displaystyle k^{2}\leq a<(k+1)^{2}}$${\displaystyle {\sqrt {a}}}$

$${\displaystyle {\sqrt {a}}\approx k+R}$$ที่ไหน$${\displaystyle R={\frac {a-k^{2}}{(k+1)^{2}-k^{2}}}={\frac {a-k^{2}}{2k+1}}}$$

ขั้นตอนสุดท้าย ดังที่กล่าวมาข้างต้น คือการคูณผลลัพธ์ด้วยเลขยกกำลังของสิบหารด้วย 2 $${\displaystyle {\sqrt {S}}={\sqrt {a}}\cdot 10^{n}\approx (k+R)\cdot 10^{n}}$$

kคือตัวเลขทศนิยม และRคือเศษส่วนที่ต้องแปลงเป็นทศนิยม โดยปกติแล้วเศษส่วนจะมีตัวเลขเพียงหลักเดียวในตัวเศษ และตัวเลขหนึ่งหรือสองหลักในตัวส่วน ดังนั้นการแปลงเป็นทศนิยมจึงสามารถทำได้โดยการคิดในใจ

เมื่อทำงานในระบบเลขฐานสอง (เช่นเดียวกับที่คอมพิวเตอร์ใช้ภายใน) โดยการแสดงS ในรูป โดยที่สามารถประมาณ ค่ารากที่สอง ได้ดังนี้${\displaystyle a\times 2^{2n}}$${\displaystyle 0.1_{2}\leq a<10_{2}}$${\displaystyle {\sqrt {S}}={\sqrt {a}}\times 2^{n}}$$${\displaystyle {\sqrt {S}}\approx (0.485+0.485a)\cdot 2^{n}}$$

ซึ่งเป็นเส้นถดถอยกำลังสองน้อยที่สุดที่มีสัมประสิทธิ์สำคัญ 3 หลักมีค่าความคลาดเคลื่อนสัมบูรณ์สูงสุด 0.0408 ที่และค่าความคลาดเคลื่อนสัมพัทธ์สูงสุด 3.0% ที่ ค่าประมาณที่ปัดเศษซึ่งสะดวกในการคำนวณ (เนื่องจากสัมประสิทธิ์เป็นกำลังของ 2) คือ: ${\displaystyle {\sqrt {a}}}$${\displaystyle a=2}$${\displaystyle a=1}$

${\displaystyle {\sqrt {S}}\approx (0.5+0.5a)\cdot 2^{n}}$^{[หมายเหตุ 4 ]}

ซึ่งมีค่าความคลาดเคลื่อนสัมบูรณ์สูงสุด 0.086 ที่ 2 และค่าความคลาดเคลื่อนสัมพัทธ์สูงสุด 6.1% ที่a = 0.5และa = 2.0

สำหรับการประมาณค่าแบบไบนารีจะได้ค่า ดังนั้นค่าประมาณจึงมีข้อผิดพลาดสัมบูรณ์ 19% และข้อผิดพลาดสัมพัทธ์ 5.3% ข้อผิดพลาดสัมพัทธ์น้อยกว่า 1/2 ⁴เล็กน้อยดังนั้นค่าประมาณจึงแม่นยำถึง 4+ บิต $${\displaystyle S=125348=1\;1110\;1001\;1010\;0100_{2}=1.1110\;1001\;1010\;0100_{2}\times 2^{16}\,,}$$$${\displaystyle {\sqrt {S}}\approx (0.5+0.5a)\cdot 2^{8}=1.0111\;0100\;1101\;0010_{2}\times 1\;0000\;0000_{2}=1.456\times 256=372.8.}$$${\displaystyle {\sqrt {125348}}=354.0}$

สามารถประมาณค่ารากที่สอง ของ 1.8515625 10 ได้อย่างแม่นยำถึง 8 บิต โดยการค้นหาในตารางจาก 8 บิตบนสุดของ ค่า 1.8515625 10 โดยจำไว้ว่าบิตบนสุดนั้นเป็นค่าโดยปริยายในรูปแบบเลขทศนิยมส่วนใหญ่ และบิตล่างสุดของเลข 8 ควรปัดเศษ ตารางนี้มีขนาด 256 ไบต์ ประกอบด้วยค่ารากที่สองที่คำนวณไว้ล่วงหน้าแล้ว 8 บิต ตัวอย่างเช่น สำหรับดัชนี 11101101 ₂ซึ่งแทนค่า 1.8515625 ₁₀ค่าที่ได้คือ 10101110 ₂ซึ่งแทนค่า 1.359375 ₁₀ ซึ่งเป็น รากที่สองของ 1.8515625 ₁₀ที่มีความแม่นยำถึง 8 บิต (2+ หลักทศนิยม)

อัลกอริทึมที่ชัดเจนแรกสำหรับการประมาณค่าเรียกว่าวิธีของเฮรอน ตาม ชื่อของนักคณิตศาสตร์ชาวกรีกในศตวรรษที่ 1 เฮโรแห่งอเล็กซานเดรียผู้ซึ่งอธิบายวิธีการนี้ในงานMetrica ของเขา ในปี ค.ศ. 60 ^{[ 3 ]}วิธีนี้เรียกอีกอย่างว่าวิธีบาบิโลน (ไม่ควรสับสนกับวิธีบาบิโลนสำหรับการประมาณค่าด้านตรงข้ามมุมฉาก ) แม้ว่าจะไม่มีหลักฐานว่า ชาวบาบิโลนรู้จักวิธีนี้ก็ตาม ${\displaystyle \ {\sqrt {S~}}\ }$

กำหนดให้ x₀ > 0 เป็นจำนวนจริงบวก ใดๆ ให้_x₀ > 0เป็นค่าประมาณเริ่มต้น ที่เป็น บวก วิธีของเฮรอนประกอบด้วยการคำนวณซ้ำๆ จนกว่าจะได้ความแม่นยำที่ต้องการ ลำดับที่กำหนดโดยสมการนี้จะลู่เข้าสู่${\displaystyle S}$$${\displaystyle x_{n+1}={\frac {1}{2}}\left(x_{n}+{\frac {S}{x_{n}}}\right),}$$${\displaystyle \ {\bigl (}\ x_{0},\ x_{1},\ x_{2},\ x_{3},\ \ldots \ {\bigr )}\ }$${\displaystyle \ \lim _{n\to \infty }x_{n}={\sqrt {S~}}~.}$

นี่เทียบเท่ากับการใช้วิธีของนิวตันในการแก้ปัญหาอัลกอริทึมนี้ลู่เข้าแบบกำลังสอง : จำนวนหลักที่ถูกต้องจะเพิ่มขึ้นเป็นสองเท่าโดยประมาณในแต่ละรอบ^{[ 5 ]}${\displaystyle x^{2}-S=0}$${\displaystyle x_{n}}$

แนวคิดพื้นฐานคือ ถ้าเป็นค่าประมาณที่สูงเกินไปของรากที่สองของจำนวนจริงบวก แล้วจะเป็นค่าประมาณที่ต่ำเกินไป และในทางกลับกัน ดังนั้นค่าเฉลี่ยของจำนวนทั้งสองนี้จึงอาจคาดได้ว่าจะให้ค่าประมาณที่ดีกว่า (การพิสูจน์อย่างเป็นทางการของข้อความนี้ขึ้นอยู่กับความไม่เท่าเทียมกันของค่าเฉลี่ยเลขคณิตและค่าเฉลี่ยเรขาคณิตที่แสดงให้เห็นว่าค่าเฉลี่ยนี้เป็นค่าประมาณที่สูงเกินไปของรากที่สองเสมอ ดังที่กล่าวไว้ในบทความเกี่ยวกับรากที่สองซึ่งรับประกันการลู่เข้า) ${\displaystyle \ x\ }$${\displaystyle \ S\ }$${\displaystyle \ {\tfrac {\ S\ }{x}}\ }$

กล่าวให้แม่นยำยิ่งขึ้น ถ้าเป็นค่าเริ่มต้นที่เราคาดเดาไว้และเป็นความคลาดเคลื่อนในการประมาณค่าของเรา โดยที่แล้วเราสามารถกระจายทวินามได้ดังนี้: และแก้หาค่าความคลาดเคลื่อน ${\displaystyle \ x\ }$${\displaystyle \ {\sqrt {S~}}\ }$${\displaystyle \ \varepsilon \ }$${\displaystyle \ S=\left(x+\varepsilon \right)^{2}\ ,}$$${\displaystyle \ {\bigl (}\ x+\varepsilon \ {\bigr )}^{2}=x^{2}+2x\varepsilon +\varepsilon ^{2}}$$

${\displaystyle \varepsilon ={\frac {\ S-x^{2}\ }{\ 2x+\varepsilon \ }}\approx {\frac {\ S-x^{2}\ }{2x}}\ ,}$ถ้าเราสมมติว่า${\displaystyle \ \varepsilon \ll x~}$

ดังนั้น เราจึงสามารถชดเชยข้อผิดพลาดและปรับปรุงค่าประมาณเดิมของเราได้ เนื่องจากข้อผิดพลาดที่คำนวณได้ไม่ถูกต้องแม่นยำ นี่จึงไม่ใช่คำตอบที่แท้จริง แต่จะกลายเป็นค่าคาดเดาใหม่ของเราที่จะใช้ในการแก้ไขรอบต่อไป กระบวนการปรับปรุงจะทำซ้ำไปเรื่อยๆ จนกว่าจะได้ความแม่นยำที่ต้องการ $${\displaystyle \ x+\varepsilon \ \approx \ x+{\frac {\ S-x^{2}\ }{2x}}\ =\ {\frac {\ S+x^{2}\ }{2x}}\ =\ {\frac {\ {\frac {S}{\ x\ }}+x\ }{2}}\ \equiv \ x_{\mathsf {revised}}~.}$$

อัลกอริทึมนี้ใช้ได้ผลดีเช่นกันในจำนวนp -adic แต่ไม่สามารถใช้เพื่อระบุว่ารากที่สองของจำนวนจริงตรงกับ รากที่สองของจำนวน p -adic ได้อย่างไร ตัวอย่างเช่น เราสามารถสร้างลำดับของจำนวนตรรกยะโดยใช้วิธีนี้ ซึ่งลู่เข้าสู่+3ในจำนวนจริง แต่ลู่เข้าสู่−3ในจำนวน 2-adic

จากdecimal นำเข้าDecimal , localcontext , getcontextประเภทตัวเลข= จำนวนเต็ม| ทศนิยม| เลขฐานสิบdef sqrt_Heron (s : ประเภทตัวเลข,ความแม่นยำ: int | None = None ,เดา: ประเภทตัวเลข| ไม่มี= ไม่มี) -> ทศนิยม:""" คำนวณค่า sqrt(sqrt) โดยใช้วิธี Heron-Newton ด้วยความแม่นยำตามอำเภอใจ :param s: จำนวนที่ไม่เป็นลบที่ต้องการคำนวณรากที่สอง :param precision: จำนวนหลักที่มีนัยสำคัญ ค่าเริ่มต้นคือบริบททศนิยมปัจจุบัน ความแม่นยำขั้นต่ำที่รองรับคือ 2 (ไม่อนุญาตให้ตั้งค่าความแม่นยำเป็น 1 เพื่อหลีกเลี่ยงความผิดปกติจากการปัดเศษ) :param guess: ค่าคาดเดาเริ่มต้น ค่าเริ่มต้นคือ s / 2 :return: ค่าประมาณของรากที่สอง (sqrt) ที่ปัดเศษตามความแม่นยำที่ระบุ """ถ้าs == 0 :คืนค่า Decimal ( 0 )s = ทศนิยม( s )ถ้าs < 0 :raise ValueError ( "ฟังก์ชัน sqrt(s) ไม่สามารถใช้ได้กับตัวเลขติดลบ" )ถ้าความแม่นยำเป็นNone :precision = getcontext () . prec # ใช้บริบทส่วนกลางปัจจุบันหากไม่ได้ระบุไว้# บังคับใช้ความแม่นยำขั้นต่ำโดยไม่เปิดเผยตัวตนถ้าความแม่นยำ< 2 :ความแม่นยำ= 2ถ้าค่าที่เดาคือNone :เดา= ทศนิยม( s / 2 )guard = 25 # ตัวเลขเสริมชั่วคราวเพื่อความเสถียรภายในจำนวนรอบสูงสุด= 10,000# บริบทเฉพาะที่: แยกการเปลี่ยนแปลงความแม่นยำwith localcontext () as ctx :ctx . prec = precision + guardเดา= ( เดา+ s / เดา) / 2สำหรับ_ ในช่วง( max_iter ):next_guess = ( guess + s / guess ) / 2# หยุดเมื่อผลลัพธ์ที่ได้ไม่ดีขึ้นมากพอถ้าค่าที่เดา- ค่าที่เดาถัดไป< ทศนิยม( f "1e- { precision } " ):หยุดพักเดา= เดาครั้งต่อไปอื่น:raise ArithmeticError ( f "Heron method did not converge within { max_iter } iterations" )# ปัดเศษให้ได้ความแม่นยำตามเป้าหมาย (กำจัดตัวป้องกัน)ctx.prec = ความแม่นยำ​คืนค่า+ เดาครั้งต่อไป

ตัวอย่างต่อไปนี้แสดงการทำงานของsqrt_Heronฟังก์ชันด้วยอินพุตต่างๆ

print ( f "1) { sqrt_Heron ( 125348 , precision = 7 , guess = 600 ) } " ) print ( f "2) { sqrt_Heron ( Decimal ( '3.1415926535897932384626433832795028841971693993' )) } " ) print ( f "3) { sqrt_Heron ( 2 , 1_000_157 ) } " ) print ( f "4) { sqrt_Heron ( 2 , 10_000_005 , 1.414 ) } " ) print ( f "5) { sqrt_Heron ( 2 , 100_000_000 , 1 ) } " )

ซึ่งจะสร้างผลลัพธ์ดังต่อไปนี้:

1) 354.0452 2) 1.772453850905516027298167483 3) 1.4142135623730950488016887242 ... 269732025731849141493880004856742892 4) 1.4142135623730950488016887242 ... ... 872480508054123572727872131589714262 5) 1.4142135623730950488016887242 ... ... ... 023678977744844723443287604232894971 

โฆษณา 1)

การคำนวณค่าให้ ได้ เลขสำคัญเจ็ด หลัก มีขั้นตอนดังนี้: ${\displaystyle {\sqrt {s\,}}}$${\displaystyle s=125348}$$${\displaystyle {\begin{alignedat}{5}x_{0}&=6\cdot 10^{2}=600\\x_{1}&={\frac {1}{2}}\left(x_{0}+{\frac {S}{x_{0}}}\right)&&={\frac {1}{2}}\left(600{\phantom {456666666}}+{\frac {125348}{600}}{\phantom {4566666}}\right)&&\approx 404.456666666\\x_{2}&={\frac {1}{2}}\left(x_{1}+{\frac {S}{x_{1}}}\right)&&={\frac {1}{2}}\left(404.456666666+{\frac {125348}{404.456666666}}\right)&&\approx 357.186837334\\x_{3}&={\frac {1}{2}}\left(x_{2}+{\frac {S}{x_{2}}}\right)&&={\frac {1}{2}}\left(357.186837334+{\frac {125348}{357.186837334}}\right)&&\approx 354.059011038\\x_{4}&={\frac {1}{2}}\left(x_{3}+{\frac {S}{x_{3}}}\right)&&={\frac {1}{2}}\left(354.059011038+{\frac {125348}{354.059011038}}\right)&&\approx 354.045195124\\x_{5}&={\frac {1}{2}}\left(x_{4}+{\frac {S}{x_{4}}}\right)&&={\frac {1}{2}}\left(354.045195124+{\frac {125348}{354.045195124}}\right)&&\approx 354.045194855\end{alignedat}}}$$

ดังนั้นจึงต้องปัดเศษให้เหลือเจ็ดตำแหน่งทศนิยมสำคัญ ${\displaystyle {\sqrt {\,125348\,}}\approx 354.0452}$

โฆษณา 2)การคำนวณ (ใน 6 ขั้นตอนการวนซ้ำ) ให้ได้ความแม่นยำตามค่าเริ่มต้น^{[หมายเหตุ 5 ]}${\displaystyle {\sqrt {\left\lfloor \pi \times 10^{46}\right\rfloor \times 10^{-46}}}}$

โฆษณา 3)การคำนวณ (ใน 22 ขั้นตอนการวนซ้ำ) ถึง1,000,157 หลัก^{[ 6 ]}${\displaystyle {\sqrt {2}}}$

โฆษณา 4)การคำนวณ (ใน 23 ขั้นตอนการวนซ้ำ) ถึง10,000,005 หลัก^{[ 7 ]}${\displaystyle {\sqrt {2}}}$

ข้อ 5)การคำนวณ (ใน 28 ขั้นตอนการวนซ้ำ) ให้ได้ผลลัพธ์ถึง 100 ล้านหลัก ${\displaystyle {\sqrt {2}}}$

ดูเหมือนว่าสำหรับการคาดเดาเบื้องต้นที่สมเหตุสมผลนั้น ไม่จำเป็นต้องมีการทำซ้ำหลายรอบนัก

วิธีการของเฮรอนมีคุณสมบัติดังต่อไปนี้:

${\displaystyle {\begin{array}{rcl}x_{n}<{\sqrt {S}}&\implies &x_{n+1}>{\sqrt {S}}\\x_{n}={\sqrt {S}}&\implies &x_{n+1}=x_{n}\\x_{n}>{\sqrt {S}}&\implies &x_{n+1}<x_{n}\end{array}}}$

กล่าวโดยง่ายคือ เมื่อการวนซ้ำให้ค่าที่มากกว่า(ซึ่งเกิดขึ้นทันทีหาก​​หรือหลังจากหนึ่งขั้นตอนหาก) ค่าประมาณที่ตามมาทั้งหมดจะยังคงอยู่เหนือแต่จะเล็กลงในแต่ละครั้ง ดังนั้นลำดับจะ "เลื่อนลง" ไปสู่​​และลู่เข้าสู่ค่าคงที่ ${\displaystyle {\sqrt {S}}}$${\displaystyle x_{0}>{\sqrt {S}}}$${\displaystyle x_{0}<{\sqrt {S}}}$${\displaystyle {\sqrt {S}}}$${\displaystyle {\sqrt {S}}}$

ในบรรทัดที่ 41 ของโปรแกรมguessกำหนดค่าให้กับตัวแปรจากนั้นในบรรทัดที่ 46 ของโค้ดตัวแปร จะต้องไม่เป็นค่าลบ ${\displaystyle \geq {\sqrt {S}}}$${\displaystyle \delta _{n}=x_{n}-x_{n+1}}$

โดยใช้ความแตกต่างระหว่างค่าประมาณที่ต่อเนื่องกัน

${\displaystyle \delta _{n}=x_{n}-x_{n+1}}$,

โดยใช้เกณฑ์การหยุด วิธีการนี้จะทำให้มั่นใจได้ว่าลำดับของการประมาณค่ากำลังลู่เข้าสู่ค่าที่แท้จริงเมื่อความแตกต่างที่ต่อเนื่องกันมีค่าน้อยลงเพียงพอ เป้าหมายที่กำหนดไว้ก็จะบรรลุผลสำเร็จ แนวคิดหลักคือข้อผิดพลาดสัมบูรณ์${\displaystyle x_{n}}$${\displaystyle {\sqrt {S}}}$${\displaystyle \delta _{n}}$

${\displaystyle \varepsilon _{n}=x_{n}-{\sqrt {S}}}$,

มีความสัมพันธ์โดยตรงกับขนาดของการปรับปรุงที่ต่อเนื่องกันโดยเฉพาะอย่างยิ่ง สำหรับวิธีการวนซ้ำที่ลู่เข้าแบบเชิงเส้นหรือแบบกำลังสอง จะมีค่าคงที่อยู่ค่าหนึ่งซึ่งทำให้ ${\displaystyle \delta _{n}}$${\displaystyle C<1}$

${\displaystyle \varepsilon _{n+1}=C\cdot \delta _{n}}$.

ความสัมพันธ์นี้บ่งชี้ว่า เมื่อค่าลดลง ข้อผิดพลาดสัมบูรณ์ก็จะน้อยลงด้วย ดังนั้น การหยุดการวนซ้ำเมื่อค่าลดลงต่ำกว่าเกณฑ์ที่กำหนด จะช่วยให้มั่นใจได้ว่าข้อผิดพลาดที่แท้จริงจะอยู่ภายในเกณฑ์นั้นอย่างมากที่สุด ${\displaystyle \delta _{n}}$${\displaystyle \varepsilon _{n}}$${\displaystyle \delta _{n}}$

สมมติว่าจากนั้นสำหรับจำนวนธรรมชาติใดๆให้กำหนด ข้อผิดพลาดสัมพัทธ์ใน โดย และดังนั้น ${\displaystyle \ x_{0}>0~~{\mathsf {and}}~~S>0~.}$${\displaystyle \ n:x_{n}>0~.}$${\displaystyle \ x_{n}\ }$$${\displaystyle \ \varepsilon _{n}={\frac {~x_{n}\ }{\ {\sqrt {S~}}\ }}-1>-1\ }$$$${\displaystyle \ x_{n}={\sqrt {S~}}\cdot \left(1+\varepsilon _{n}\right)~.}$$

จากนั้นจึงสามารถแสดงได้ว่า $${\displaystyle \ \varepsilon _{n+1}={\frac {\varepsilon _{n}^{2}}{2(1+\varepsilon _{n})}}\geq 0~.}$$

ดังนั้น การลู่เข้าจึงเกิดขึ้นอย่างแน่นอน และเป็น แบบ กำลัง สอง$${\displaystyle \ \varepsilon _{n+2}\leq \min \left\{\ {\frac {\ \varepsilon _{n+1}^{2}\ }{2}},{\frac {\ \varepsilon _{n+1}\ }{2}}\ \right\}\ }$$

หากใช้การประมาณคร่าวๆ ข้างต้นร่วมกับวิธีการแบบบาบิโลน กรณีที่มีความแม่นยำน้อยที่สุดเรียงลำดับจากน้อยไปมากจะเป็นดังนี้: $${\displaystyle {\begin{aligned}S&=\ 1\ ;&x_{0}&=\ 2\ ;&x_{1}&=\ 1.250\ ;&\varepsilon _{1}&=\ 0.250~.\\S&=\ 10\ ;&x_{0}&=\ 2\ ;&x_{1}&=\ 3.500\ ;&\varepsilon _{1}&<\ 0.107~.\\S&=\ 10\ ;&x_{0}&=\ 6\ ;&x_{1}&=\ 3.833\ ;&\varepsilon _{1}&<\ 0.213~.\\S&=\ 100\ ;&x_{0}&=\ 6\ ;&x_{1}&=\ 11.333\ ;&\varepsilon _{1}&<\ 0.134~.\end{aligned}}}$$

ดังนั้นไม่ว่ากรณีใดก็ตาม $${\displaystyle {\begin{aligned}\varepsilon _{1}&\leq 2^{-2}.\\\varepsilon _{2}&<2^{-5}<10^{-1}~.\\\varepsilon _{3}&<2^{-11}<10^{-3}~.\\\varepsilon _{4}&<2^{-23}<10^{-6}~.\\\varepsilon _{5}&<2^{-47}<10^{-14}~.\\\varepsilon _{6}&<2^{-95}<10^{-28}~.\\\varepsilon _{7}&<2^{-191}<10^{-57}~.\\\varepsilon _{8}&<2^{-383}<10^{-115}~.\end{aligned}}}$$

ข้อผิดพลาดจากการปัดเศษจะทำให้การคำนวณช้าลง แนะนำให้เผื่อตัวเลขอย่างน้อยหนึ่งหลักมากกว่าความแม่นยำที่ต้องการเพื่อหลีกเลี่ยงข้อผิดพลาดจากการปัดเศษอย่าง มีนัยสำคัญ${\displaystyle \ x_{n}\ }$

เมื่ออยู่ในโปรแกรมข้างต้น จะมีการประมาณการไว้ดังนี้ — บรรทัดที่ไฮไลต์คือบรรทัดที่ 41 และ 43 —

เดา= ( เดา+ s / เดา) / 2# ...next_guess = ( guess + s / guess ) / 2

ถูกแทนที่ด้วย

guess *= ( guess * guess + 3 * s ) / ( 3 * guess * guess + s )# ...next_guess = guess * ( guess * guess + 3 * s ) / ( 3 * guess * guess + s )

ฟังก์ชันดังsqrt_Heronกล่าวถูกแปลงเป็นการนำวิธีการของฮัลลีย์ มาใช้ โดยที่

${\displaystyle x_{n+1}=x_{n}\cdot {\frac {x_{n}^{2}+3S}{3x_{n}^{2}+S}}}$

เช่นเดียวกับในวิธีการของแฮลลีย์ การประมาณค่าไม่ได้เคลื่อนไปในทิศทางเดียวเสมอไป บรรทัดที่ 46 จะกลายเป็น

ถ้าabs ( guess - next_guess ) < Decimal ( f "1e- { precision } " ):

วิธีของ Halley มีอัตราการลู่เข้าที่เร็วกว่า — อัตราการลู่เข้าสู่รากเป็นแบบลูกบาศก์ ซึ่งดีกว่าแบบกำลังสอง —เมื่อเทียบกันแบบทีละรอบ แต่ต้องใช้การคูณถึงห้าครั้งต่อรอบ (นับการหารเป็นการคูณสามครั้ง) การคำนวณตัวอย่างทั้งห้าครั้งเสร็จสมบูรณ์ใน 4, 4, 14, 15 และ 19 รอบ ตามลำดับ ในทางตรงกันข้าม วิธีของ Heron ต้องการการหารเพียงครั้งเดียว นั่นคือการคูณสามครั้ง ดังนั้นวิธีของ Heron จึงดีกว่าเล็กน้อยในระยะยาว

วิธีการนี้สำหรับการหาค่าประมาณของรากที่สองได้รับการอธิบายไว้ใน ต้นฉบับ อินเดีย โบราณ ที่เรียกว่าต้นฉบับ Bakhshaliซึ่งเทียบเท่าทางพีชคณิตกับการทำซ้ำสองครั้งของวิธีของ Heron และดังนั้นจึงลู่เข้าแบบควอติก หมายความว่าจำนวนหลักที่ถูกต้องของค่าประมาณจะเพิ่มขึ้นเป็นสี่เท่าโดยประมาณในแต่ละรอบการทำซ้ำ^{[ 8 ]}การนำเสนอแบบดั้งเดิมโดยใช้สัญลักษณ์สมัยใหม่มีดังนี้: ในการคำนวณให้เป็นค่าประมาณเริ่มต้นของจากนั้นทำซ้ำตามลำดับดังนี้: ${\displaystyle {\sqrt {S}}}$${\displaystyle x_{0}^{2}}$${\displaystyle S}$$${\displaystyle {\begin{aligned}a_{n}&={\frac {S-x_{n}^{2}}{2x_{n}}},\\x_{n+1}&=x_{n}+a_{n},\\x_{n+2}&=x_{n+1}-{\frac {a_{n}^{2}}{2x_{n+1}}}.\end{aligned}}}$$

ค่าและนั้นเหมือนกับค่าที่คำนวณได้ด้วยวิธีของเฮรอนทุกประการ เพื่อดูสิ่งนี้ ขั้นตอนที่สองของวิธีเฮรอนจะคำนวณ และเราสามารถใช้คำจำกัดความของและเพื่อจัดเรียงตัวเศษใหม่เป็น: ${\displaystyle x_{n+1}}$${\displaystyle x_{n+2}}$$${\displaystyle x_{n+2}={\frac {x_{n+1}^{2}+S}{2x_{n+1}}}=x_{n+1}+{\frac {S-x_{n+1}^{2}}{2x_{n+1}}}}$$${\displaystyle x_{n+1}}$${\displaystyle a_{n}}$$${\displaystyle {\begin{aligned}S-x_{n+1}^{2}&=S-(x_{n}+a_{n})^{2}\\&=S-x_{n}^{2}-2x_{n}a_{n}-a_{n}^{2}\\&=S-x_{n}^{2}-(S-x_{n}^{2})-a_{n}^{2}\\&=-a_{n}^{2}.\end{aligned}}}$$

วิธีนี้สามารถใช้สร้างค่าประมาณเชิงตรรกะของรากที่สองได้ โดยเริ่มต้นจากจำนวนเต็ม ถ้าเป็นจำนวนเต็มที่เลือกให้มีค่าใกล้เคียงกับและคือผลต่างที่มีค่าสัมบูรณ์น้อยที่สุด การวนซ้ำครั้งแรกสามารถเขียนได้ดังนี้: ${\displaystyle x_{0}=N}$${\displaystyle N^{2}}$${\displaystyle S}$${\displaystyle d=S-N^{2}}$$${\displaystyle {\sqrt {S}}\approx N+{\frac {d}{2N}}-{\frac {d^{2}}{8N^{3}+4Nd}}={\frac {8N^{4}+8N^{2}d+d^{2}}{8N^{3}+4Nd}}={\frac {N^{4}+6N^{2}S+S^{2}}{4N^{3}+4NS}}={\frac {N^{2}(N^{2}+6S)+S^{2}}{4N(N^{2}+S)}}.}$$

วิธี Bakhshali สามารถขยายไปสู่การคำนวณรากใดๆ รวมถึงรากเศษส่วนได้^{[ 9 ]}

บางคนอาจคิดว่าครึ่งหลังของวิธีการของ Bakhshali สามารถใช้เป็นรูปแบบที่ง่ายกว่าของการวนซ้ำของ Heron และใช้ซ้ำได้ อย่างไรก็ตาม วิธีนี้ไม่เสถียรทางตัวเลขหากไม่มีการอ้างอิงถึงค่าอินพุตดั้งเดิมความแม่นยำจะถูกจำกัดด้วยความแม่นยำของการคำนวณดั้งเดิมของและนั่นจะกลายเป็นสิ่งที่ไม่เพียงพออย่างรวดเร็ว $${\displaystyle {\begin{aligned}a_{n+1}&={\frac {-a_{n}^{2}}{2x_{n+1}}},&x_{n+2}&=x_{n+1}+a_{n+1},\\a_{n+2}&={\frac {-a_{n+1}^{2}}{2x_{n+2}}},&x_{n+3}&=x_{n+2}+a_{n+2},{\text{ etc.}}\end{aligned}}}$$${\displaystyle S}$${\displaystyle a_{n}}$

โดยใช้ตัวอย่างเดียวกันกับในตัวอย่างวิธีของเฮรอน การวนซ้ำครั้งแรกจะให้ผลลัพธ์ดังนี้ ${\displaystyle S=125348}$$${\displaystyle {\begin{alignedat}{3}x_{0}&=600\\[1ex]a_{0}&={\frac {125348-600^{2}}{2\times 600}}&&=-195.5433\approx -200\\[1ex]x_{1}&=600+(-200)&&={\phantom {-}}400\\[1ex]x_{2}&=400-{\frac {(-200)^{2}}{2\times 400}}&&={\phantom {-}}350\end{alignedat}}}$$

ในทำนองเดียวกัน การวนซ้ำครั้งที่สองให้ ผลลัพธ์ที่แตกต่างจากวิธีของเฮรอน โดยจะต้องคำนวณให้ได้ 8 หลัก เนื่องจากสูตรสำหรับไม่ได้แก้ไขข้อผิดพลาดใดๆใน $${\displaystyle {\begin{alignedat}{3}a_{2}&={\frac {125348-350^{2}}{2\times 350}}&&={\phantom {00}}4.06857\\[1ex]x_{3}&=350+4.06857&&=354.06857\\[1ex]x_{4}&=354.06857-{\frac {4.06857^{2}}{2\times 354.06857}}&&=354.045194\end{alignedat}}}$$${\displaystyle x_{3}}$${\displaystyle x_{4}}$${\displaystyle x_{3}}$

เทคนิคนี้มาจากผลงานของFrançois Vièteซึ่งตีพิมพ์ราวปี ค.ศ. 1600 ^{[ 10 ]}และอิงตามทฤษฎีบททวินามและโดยพื้นฐานแล้วเป็นอัลกอริทึมผกผันในการแก้ปัญหา วิธีนี้ช้ากว่าวิธีบาบิโลน แต่มีข้อดีหลายประการ: ${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$

• การคำนวณด้วยมืออาจทำได้ง่ายกว่า
• ทุกหลักของรากที่พบนั้นได้รับการยืนยันว่าถูกต้องแล้ว กล่าวคือ ไม่จำเป็นต้องเปลี่ยนแปลงในภายหลัง
• ถ้าการหาค่ารากที่สองมีการกระจายที่สิ้นสุด อัลกอริทึมก็จะสิ้นสุดหลังจากพบหลักสุดท้าย ดังนั้นจึงสามารถใช้ตรวจสอบได้ว่าจำนวนเต็มที่กำหนดเป็นจำนวนกำลังสอง หรือ ไม่
• อัลกอริทึมนี้ใช้ได้กับฐาน ใดก็ได้ และโดยธรรมชาติแล้ว วิธีการทำงานของมันจะขึ้นอยู่กับฐานที่เลือกใช้

ข้อเสียได้แก่:

• รากที่อยู่สูงขึ้นไปจะควบคุมได้ยากขึ้น
• วิธีนี้ไม่ยอมรับการคาดเดาหรือการคำนวณย่อยที่ไม่แม่นยำ เพราะข้อผิดพลาดดังกล่าวจะทำให้ตัวเลขหลักถัดไปของผลลัพธ์ผิดพลาดทั้งหมด ซึ่งแตกต่างจากวิธีของนิวตันที่แก้ไขข้อผิดพลาดในการประมาณค่าได้เองโดยอัตโนมัติ
• แม้ว่าการคำนวณทีละหลักจะดูมีประสิทธิภาพในทางทฤษฎี แต่ก็มีต้นทุนสูงเกินไปสำหรับการนำไปใช้ในซอฟต์แวร์ แต่ละรอบการคำนวณเกี่ยวข้องกับตัวเลขที่ใหญ่ขึ้น ทำให้ต้องใช้หน่วยความจำมากขึ้น แต่จะได้คำตอบที่ถูกต้องเพิ่มขึ้นเพียงหนึ่งหลักเท่านั้น ดังนั้นอัลกอริทึมจึงใช้เวลานานขึ้นสำหรับแต่ละหลักที่เพิ่มเข้ามา

กระดูกของเนเปียร์มีส่วนช่วยในการดำเนินการของอัลกอริทึมนี้ อัลกอริทึมรากที่ n แบบเลื่อนตำแหน่ง เป็นการขยายวิธีการนี้ให้ครอบคลุมมากขึ้น

ก่อนอื่น ให้พิจารณากรณีของการหาค่ารากที่สองของจำนวนSซึ่งก็คือค่ากำลังสองของจำนวนสองหลักฐานสิบXYโดยที่XคือหลักสิบและYคือหลักหน่วย โดยเฉพาะอย่างยิ่ง Sจะประกอบด้วยตัวเลขทศนิยม 3 หรือ 4 หลัก $${\displaystyle S=\left(10X+Y\right)^{2}=100X^{2}+20XY+Y^{2}.}$$

ต่อไปนี้คือขั้นตอนวิธีแบบทีละหลัก เราจะแบ่งตัวเลขของS ออก เป็นสองกลุ่ม กลุ่มละสองหลัก โดยเริ่มจากด้านขวา ซึ่งหมายความว่ากลุ่มแรกจะมี 1 หรือ 2 หลัก จากนั้นเราจะหาค่าของXเป็นตัวเลขที่มากที่สุดที่ทำให้X² น้อยกว่าหรือเท่ากับกลุ่มแรก จาก นั้น เราจะคำนวณผลต่างระหว่างกลุ่มแรกกับ ^{X² และเริ่มต้นการวนซ้ำครั้งที่ สอง}โดยการนำกลุ่มที่สองมาต่อท้าย ซึ่งเทียบเท่ากับการลบออกจากSและเราจะเหลือ S' ไว้เราหารS'ด้วย 10 จากนั้นหารด้วย2Xและเก็บส่วนที่เป็นจำนวนเต็มไว้เพื่อลองเดาค่าYเรานำ2X มาต่อ ท้ายกับค่าY ที่เดาไว้ และคูณด้วยYถ้าการเดาของเราถูกต้อง ซึ่งเทียบเท่ากับการคำนวณ: และดังนั้นเศษเหลือ ซึ่งก็คือผลต่างระหว่างS'กับผลลัพธ์ จะเป็นศูนย์ ถ้าผลลัพธ์สูงกว่าS'เราจะลดค่าที่คาดเดาลง 1 แล้วลองใหม่อีกครั้งจนกว่าเศษเหลือจะเป็น 0 เนื่องจากนี่เป็นกรณีที่ง่ายซึ่งคำตอบคือรากที่สองสมบูรณ์ของXYดังนั้นอัลกอริทึมจึงหยุดทำงานที่นี่ ${\displaystyle 100X^{2}}$${\displaystyle S'=20XY+Y^{2}}$$${\displaystyle (10(2X)+Y)Y=20XY+Y^{2}=S',}$$

แนวคิดเดียวกันนี้สามารถขยายไปใช้กับการคำนวณรากที่สองใดๆ ก็ได้ต่อไป สมมติว่าเราสามารถหารากที่สองของS ได้ โดยการแสดง S ในรูปผลรวมของ จำนวนบวก nจำนวน โดยที่ $${\displaystyle S=\left(a_{1}+a_{2}+a_{3}+\dots +a_{n}\right)^{2}.}$$

โดยการใช้เอกลักษณ์พื้นฐานซ้ำๆ เทอม ทางด้านขวามือสามารถขยายได้ดังนี้ $${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2},}$$$${\displaystyle {\begin{aligned}&(a_{1}+a_{2}+a_{3}+\dotsb +a_{n})^{2}\\=&\,a_{1}^{2}+2a_{1}a_{2}+a_{2}^{2}+2(a_{1}+a_{2})a_{3}+a_{3}^{2}+\dots +a_{n-1}^{2}+2\left(\sum _{i=1}^{n-1}a_{i}\right)a_{n}+a_{n}^{2}\\=&\,a_{1}^{2}+[2a_{1}+a_{2}]a_{2}+[2(a_{1}+a_{2})+a_{3}]a_{3}+\dots +\left[2\left(\sum _{i=1}^{n-1}a_{i}\right)+a_{n}\right]a_{n}.\end{aligned}}}$$

นิพจน์นี้ช่วยให้เราหาค่ารากที่สองได้โดยการเดาค่าของs ทีละลำดับ สมมติว่าตัวเลขได้ถูกเดาไปแล้ว พจน์ที่mของด้านขวามือของผลรวมข้างต้นจะกำหนดโดย โดยที่คือค่ารากที่สองโดยประมาณที่พบแล้ว การเดาแต่ละครั้งควรเป็นไปตามความสัมพันธ์เวียนเกิด โดยที่คือผลรวมของทุกพจน์หลังจาก นั่นคือเศษเหลือ โดยที่สำหรับทุกค่าที่มีการเริ่มต้นเมื่อพบค่ารากที่สองที่แน่นอนแล้ว หากไม่พบ ผลรวมของs จะให้ค่าประมาณของรากที่สองที่เหมาะสม โดยที่คือค่าความคลาดเคลื่อนของการประมาณ ${\displaystyle a_{i}}$${\displaystyle a_{1},\ldots ,a_{m-1}}$${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\right]a_{m},}$${\textstyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}}$${\displaystyle a_{m}}$$${\displaystyle X_{m}=X_{m-1}-Y_{m},}$$${\displaystyle X_{m}}$${\displaystyle Y_{m}}$${\displaystyle X_{m}\geq 0}$${\displaystyle 1\leq m\leq n,}$${\displaystyle X_{0}=S.}$${\displaystyle X_{n}=0,}$${\displaystyle a_{i}}$${\displaystyle X_{n}}$

ตัวอย่างเช่น ในระบบเลขฐานสิบ เรามี โดยที่เป็นตัวแทนตำแหน่ง และ เป็นสัมประสิทธิ์ในแต่ละขั้นตอนที่ m ของการคำนวณรากที่สอง ค่ารากโดยประมาณที่พบจนถึงปัจจุบันและพจน์ผลรวมจะกำหนดโดย $${\displaystyle S=\left(a_{1}\cdot 10^{n-1}+a_{2}\cdot 10^{n-2}+\cdots +a_{n-1}\cdot 10+a_{n}\right)^{2},}$$${\displaystyle 10^{n-i}}$${\displaystyle a_{i}\in \{0,1,2,\ldots ,9\}}$${\displaystyle P_{m-1}}$${\displaystyle Y_{m}}$$${\displaystyle P_{m-1}=\sum _{i=1}^{m-1}a_{i}\cdot 10^{n-i}=10^{n-m+1}\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1},}$$$${\displaystyle Y_{m}=\left[2P_{m-1}+a_{m}\cdot 10^{n-m}\right]a_{m}\cdot 10^{n-m}=\left[20\sum _{i=1}^{m-1}a_{i}\cdot 10^{m-i-1}+a_{m}\right]a_{m}\cdot 10^{2(n-m)}.}$$

เนื่องจากค่าประจำหลักของเป็นเลขยกกำลังคู่ของ 10 เราจึงจำเป็นต้องพิจารณาเฉพาะตัวเลขสองหลักที่มีค่ามากที่สุดของเศษเหลือซึ่งพจน์แรกคือในขั้นตอนที่ m ใดๆ ส่วนด้านล่างนี้จะอธิบายขั้นตอนดังกล่าวโดยละเอียด ${\displaystyle Y_{m}}$${\displaystyle X_{m-1}}$${\displaystyle Y_{m}}$

เห็นได้ชัดว่าสามารถใช้วิธีการที่คล้ายกันในการคำนวณรากที่สองในระบบตัวเลขอื่นนอกเหนือจากระบบเลขฐานสิบได้ ตัวอย่างเช่น การหารากที่สองแบบทีละหลักในระบบเลขฐานสองนั้นค่อนข้างมีประสิทธิภาพ เนื่องจากค่าของถูกค้นหาจากชุดตัวเลขฐานสองที่เล็กกว่า {0,1} ซึ่งทำให้การคำนวณเร็วขึ้น เพราะในแต่ละขั้นตอน ค่าของจะเป็นสำหรับหรือสำหรับข้อเท็จจริงที่ว่าเรามีเพียงสองตัวเลือกที่เป็นไปได้สำหรับยังทำให้กระบวนการตัดสินใจค่าของใน ขั้นตอนที่ mของการคำนวณง่ายขึ้น เนื่องจากเราเพียงแค่ต้องตรวจสอบว่า สำหรับถ้าเงื่อนไขนี้เป็นจริง เราจะใช้ถ้าไม่เป็นจริง เราจะใช้ นอกจากนี้ ข้อเท็จจริงที่ว่าการคูณด้วย 2 ทำได้โดยการเลื่อนบิตไปทางซ้ายก็ช่วยในการคำนวณด้วย ${\displaystyle a_{i}}$${\displaystyle Y_{m}}$${\displaystyle Y_{m}=0}$${\displaystyle a_{m}=0}$${\displaystyle Y_{m}=2P_{m-1}+1}$${\displaystyle a_{m}=1}$${\displaystyle a_{m}}$${\displaystyle a_{m}}$${\displaystyle Y_{m}\leq X_{m-1}}$${\displaystyle a_{m}=1.}$${\displaystyle a_{m}=1}$${\displaystyle a_{m}=0.}$

เขียนตัวเลขเดิมในรูปทศนิยม วิธีการเขียนตัวเลขจะคล้ายกับ วิธี หารยาวและเช่นเดียวกับการหารยาว ตัวเลขที่ได้จะเขียนไว้ในบรรทัดด้านบน จากนั้นแยกตัวเลขแต่ละคู่ โดยเริ่มจากจุดทศนิยมและไปทางซ้ายและขวา จุดทศนิยมของตัวเลขที่ได้จะอยู่เหนือจุดทศนิยมของตัวเลขยกกำลังสอง ตัวเลขหนึ่งหลักของตัวเลขที่ได้จะปรากฏอยู่เหนือตัวเลขแต่ละคู่ของตัวเลขยกกำลังสอง

เริ่มจากตัวเลขคู่ซ้ายสุด ให้ทำตามขั้นตอนต่อไปนี้สำหรับแต่ละคู่:

1. เริ่มจากทางซ้าย นำตัวเลขคู่ที่สำคัญที่สุด (ซ้ายสุด) ที่ยังไม่ได้ใช้ (ถ้าใช้ตัวเลขทั้งหมดแล้ว ให้เขียน "00") ลงมาวางไว้ทางขวาของเศษที่เหลือจากขั้นตอนก่อนหน้า (ในขั้นตอนแรกจะไม่มีเศษเหลือ) กล่าวคือ คูณเศษที่เหลือด้วย 100 แล้วบวกตัวเลขทั้งสองเข้าด้วยกัน ค่าที่ได้จะเป็นค่าcในปัจจุบัน
2. จงหาค่าp , yและxดังต่อไปนี้:
   • ให้pเป็นส่วนหนึ่งของรากที่หาได้แล้ว โดยไม่คำนึงถึงจุดทศนิยม (สำหรับขั้นตอนแรกp = 0)
   • จงหาจำนวนเต็มที่มากที่สุดxที่ทำให้. เราจะใช้ตัวแปรใหม่y = x (20 p + x ) ${\displaystyle x(20p+x)\leq c}$
     • หมายเหตุ: 20p + x คือสองเท่าของpโดยเพิ่มเลขxต่อท้ายทางด้านขวา
     • หมายเหตุ: สามารถหาค่าx ได้โดยการเดาว่า c /(20· p ) คืออะไร แล้วทำการคำนวณค่าy แบบทดลอง จากนั้นปรับค่าxขึ้นหรือลงตามความจำเป็น
   • วางตัวเลขนั้นไว้เป็นตัวเลขถัดไปของราก นั่นคือ วางไว้เหนือตัวเลขสองหลักของกำลังสองที่คุณเพิ่งดึงลงมา ดังนั้น p ตัวถัดไปจะเป็น p ตัวเดิมคูณด้วย 10 บวกx${\displaystyle x}$
3. ลบy ออก จากcเพื่อสร้างเศษเหลือใหม่
4. ถ้าเศษเหลือเป็นศูนย์และไม่มีตัวเลขใดให้ดึงลงมาอีกแล้ว แสดงว่าอัลกอริทึมสิ้นสุดลงแล้ว มิเช่นนั้น ให้กลับไปที่ขั้นตอนที่ 1 เพื่อทำซ้ำอีกครั้ง

หาค่ารากที่สองของ 152.2756

 1 2. 3 4 / \/ 01 52.27 56 01 1·1 ≤ 1 < 2·2 x = 1 01 y = x·x = 1·1 = 1 00 52 22·2 ≤ 52 < 23·3 x = 2 00 44 y = (20+x)·x = 22·2 = 44 08 27 243·3 ≤ 827 < 244·4 x = 3 07 29 y = (240+x)·x = 243·3 = 729 98 56 2464·4 ≤ 9856 < 2465·5 x = 4 98 56 y = (2460 + x)·x = 2464·4 = 9856 00 00 อัลกอริทึมสิ้นสุดการทำงาน: คำตอบ = 12.34

ส่วนนี้ใช้รูปแบบจากส่วนการคำนวณทีละหลักด้านบนโดยมีการเปลี่ยนแปลงเล็กน้อยคือ เรากำหนดให้โดยแต่ละค่าเป็นหรือเรา วนซ้ำค่าทั้งหมดตั้งแต่ลงไปจนถึงและสร้างคำตอบโดยประมาณ ซึ่งเป็นผลรวมของค่าทั้งหมดที่เราได้กำหนดค่าไว้แล้ว เพื่อตรวจสอบว่าเท่ากับหรือ หรือไม่ เรากำหนดให้ถ้า(นั่นคือ กำลังสองของคำตอบโดยประมาณของเราที่รวมไม่เกินกำลังสองเป้าหมาย) แล้วมิฉะนั้นและเพื่อ หลีกเลี่ยงการยกกำลังสองในแต่ละขั้นตอน เราจะเก็บผลต่างไว้และอัปเดตทีละน้อยโดยการตั้งค่าด้วยใน ขั้นต้น เราตั้งค่าสำหรับค่าที่มากที่สุด ด้วย${\displaystyle N^{2}=(a_{n}+\dotsb +a_{0})^{2}}$${\displaystyle a_{m}=2^{m}}$${\displaystyle a_{m}=0}$${\displaystyle 2^{m}}$${\displaystyle 2^{n}}$${\displaystyle 2^{0}}$${\displaystyle P_{m}=a_{n}+a_{n-1}+\ldots +a_{m}}$${\displaystyle a_{i}}$${\displaystyle a_{m}}$${\displaystyle 2^{m}}$${\displaystyle 0}$${\displaystyle P_{m}=P_{m+1}+2^{m}}$${\displaystyle P_{m}^{2}\leq N^{2}}$${\displaystyle 2^{m}}$${\displaystyle a_{m}=2^{m}}$${\displaystyle a_{m}=0}$${\displaystyle P_{m}=P_{m+1}}$${\displaystyle P_{m}}$${\displaystyle X_{m}=N^{2}-P_{m}^{2}}$${\displaystyle X_{m}=X_{m+1}-Y_{m}}$${\displaystyle Y_{m}=P_{m}^{2}-P_{m+1}^{2}=2P_{m+1}a_{m}+a_{m}^{2}}$${\displaystyle a_{n}=P_{n}=2^{n}}$${\displaystyle n}$${\displaystyle (2^{n})^{2}=4^{n}\leq N^{2}}$

เพื่อเพิ่มประสิทธิภาพ เราเก็บค่าและ ซึ่ง เป็น สองพจน์ของในกรณีที่ไม่เป็นศูนย์ ไว้ในตัวแปรแยกกัน:${\displaystyle P_{m+1}2^{m+1}}$${\displaystyle (2^{m})^{2}}$${\displaystyle Y_{m}}$${\displaystyle a_{m}}$${\displaystyle c_{m}}$${\displaystyle d_{m}}$$${\displaystyle c_{m}=P_{m+1}2^{m+1}}$$$${\displaystyle d_{m}=(2^{m})^{2}}$$$${\displaystyle Y_{m}={\begin{cases}c_{m}+d_{m}&{\text{if }}a_{m}=2^{m}\\0&{\text{if }}a_{m}=0\end{cases}}}$$

${\displaystyle c_{m}}$และสามารถอัปเดตได้อย่างมีประสิทธิภาพในแต่ละขั้นตอน: ${\displaystyle d_{m}}$$${\displaystyle c_{m-1}=P_{m}2^{m}=(P_{m+1}+a_{m})2^{m}=P_{m+1}2^{m}+a_{m}2^{m}={\begin{cases}c_{m}/2+d_{m}&{\text{if }}a_{m}=2^{m}\\c_{m}/2&{\text{if }}a_{m}=0\end{cases}}}$$$${\displaystyle d_{m-1}={\frac {d_{m}}{4}}}$$

โปรดทราบว่า: ซึ่งเป็นผลลัพธ์สุดท้ายที่ส่งคืนในฟังก์ชันด้านล่าง $${\displaystyle c_{-1}=P_{0}2^{0}=P_{0}=N,}$$

โปรแกรมPythonคำนวณอัลกอริทึมนี้เป็นวิธีการแบบทีละหลัก (ทีละบิต)สำหรับรากที่สองของจำนวนเต็ม^{[ 11 ]}${\displaystyle \operatorname {isqrt} (n)=\lfloor {\sqrt {n}}\rfloor .}$

def isqrt ( x : int ) -> int : assert x >= 0 , "ค่าที่ป้อนสำหรับคำนวณรากที่สองต้องไม่ติดลบ"op : int = x # X_(n+1) res : int = 0 # c_n# d_n ซึ่งเริ่มต้นที่กำลังสูงสุดของสี่ <= n หนึ่ง: int = 1 ในขณะที่หนึ่ง<= op : หนึ่ง<<= 2 # ตอนนี้ 'หนึ่ง' เป็นกำลังสูงสุดของสี่ <= x หนึ่ง>>= 2# สำหรับ dₙ … d₀ ในขณะที่one != 0 : ถ้าop >= res + one : # ถ้า X_(m+1) ≥ Y_m แล้ว a_m = 2^m op -= res + one # X_m = X_(m+1) - Y_m res += 2 * one # c_m = c_m + 2*d_m res //= 2 # c_(m-1) = c_m / 2 one //= 4 # d_(m-1) = d_m / 4# c_(-1) คืนค่า res

อัลกอริทึมที่เร็วกว่า ทั้งในระบบเลขฐานสอง เลขฐานสิบ หรือฐานอื่นๆ สามารถทำได้โดยใช้ตารางค้นหา ซึ่งในทางปฏิบัติคือการแลกเปลี่ยนพื้นที่จัดเก็บที่มากขึ้นกับเวลาการทำงานที่ลดลง^{[ 12 ]}

เครื่องคิดเลขพกพามักจะมีฟังก์ชันที่ดีในการคำนวณฟังก์ชันเลขชี้กำลังและลอการิทึมธรรมชาติจากนั้นจึงคำนวณรากที่สองของSโดยใช้เอกลักษณ์ที่พบโดยใช้คุณสมบัติของลอการิทึม ( ) และเลขชี้กำลัง( ) : ตัวส่วนในเศษส่วนสอดคล้องกับ รากที่ nในกรณีข้างต้น ตัวส่วนคือ 2 ดังนั้นสมการจึงระบุว่าต้องหารากที่สอง เอกลักษณ์เดียวกันนี้ใช้เมื่อคำนวณรากที่สองด้วยตารางลอการิทึมหรือไม้บรรทัดคำนวณ ${\displaystyle \ln x^{n}=n\ln x}$${\displaystyle e^{\ln x}=x}$$${\displaystyle {\sqrt {S}}=e^{{\frac {1}{2}}\ln S}.}$$

วิธีนี้ใช้ได้ผลดีในการหาค่ารากที่สองของและลู่เข้าได้ดีที่สุดสำหรับอย่างไรก็ตาม นี่ไม่ใช่ข้อจำกัดที่แท้จริงสำหรับการคำนวณด้วยคอมพิวเตอร์ เพราะในการแสดงผลแบบจุดลอยตัวและจุดคงที่ฐาน 2 นั้น การคูณด้วยเลขยกกำลังของ 4 ที่เป็นจำนวนเต็ม และด้วยเลขยกกำลังของ 2 ที่สอดคล้องกันนั้น ทำได้ง่ายโดยการเปลี่ยนเลขชี้กำลังหรือโดยการเลื่อนตำแหน่งตามลำดับ ดังนั้น จึงสามารถย้ายไปอยู่ในช่วง ได้ยิ่งไปกว่านั้น วิธีต่อไปนี้ไม่ได้ใช้การหารทั่วไป แต่ใช้เพียงการบวก การลบ การคูณ และการหารด้วยเลขยกกำลังของ 2 ซึ่งง่ายต่อการใช้งานเช่นกัน ข้อเสียของวิธีนี้คือ ข้อผิดพลาดทางตัวเลขจะสะสมมากขึ้น ซึ่งแตกต่างจากวิธีการวนซ้ำแบบตัวแปรเดียว เช่น วิธีบาบิโลน ${\displaystyle 0<S<3\,\!}$${\displaystyle S\approx 1}$${\displaystyle S\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle S\,\!}$${\textstyle {\tfrac {1}{2}}\leq S<2}$

ขั้นตอนการเริ่มต้นของวิธีนี้คือ ในขณะที่ขั้นตอนการวนซ้ำอ่าน ว่า จากนั้น(ในขณะที่) $${\displaystyle {\begin{aligned}a_{0}&=S\\c_{0}&=S-1\end{aligned}}}$$$${\displaystyle {\begin{aligned}a_{n+1}&=a_{n}-a_{n}c_{n}/2\\c_{n+1}&=c_{n}^{2}(c_{n}-3)/4\end{aligned}}}$$${\displaystyle a_{n}\to {\sqrt {S}}}$${\displaystyle c_{n}\to 0}$

การลู่เข้าของและด้วยเหตุนี้ การลู่เข้าของ จึง เป็นการลู่เข้าแบบกำลังสอง ${\displaystyle c_{n}\,\!}$${\displaystyle a_{n}\,\!}$

การพิสูจน์วิธีการนี้ค่อนข้างง่าย ขั้นแรก เขียนนิยามการวนซ้ำของใหม่เป็น จากนั้นก็สามารถพิสูจน์ได้โดยการอุปมานว่า และด้วยเหตุนี้ การลู่เข้าของไปสู่ผลลัพธ์ที่ต้องการจึงเกิดขึ้นได้จากการลู่เข้าของ ไปสู่ ​​0 ซึ่งเป็นผลมาจาก ${\displaystyle c_{n}}$$${\displaystyle 1+c_{n+1}=(1+c_{n})(1-{\tfrac {1}{2}}c_{n})^{2}.}$$$${\displaystyle S(1+c_{n})=a_{n}^{2}}$$${\displaystyle a_{n}\,\!}$${\displaystyle {\sqrt {S}}}$${\displaystyle c_{n}\,\!}$${\displaystyle -1<c_{0}<2\,\!}$

วิธีนี้ได้รับการพัฒนาขึ้นราวปี 1950 โดยMV Wilkes , DJ WheelerและS. Gill ^{[ 13 ]}เพื่อใช้กับEDSACซึ่งเป็นหนึ่งในคอมพิวเตอร์อิเล็กทรอนิกส์เครื่องแรก^{[ 14 ]}ต่อมาวิธีนี้ได้รับการขยายให้ครอบคลุมมากขึ้น ทำให้สามารถคำนวณค่าที่ไม่ใช่รากที่สองได้^{[ 15 ]}

ต่อไปนี้เป็นวิธีการวนซ้ำสำหรับการหาค่าผกผันของรากที่สองของSซึ่งคือเมื่อพบแล้ว ให้หาค่าโดยการคูณอย่างง่าย: การวนซ้ำเหล่านี้เกี่ยวข้องกับการคูณเท่านั้น ไม่ใช่การหาร ดังนั้นจึงเร็วกว่าวิธีบาบิโลนอย่างไรก็ตาม วิธีเหล่านี้ไม่เสถียร หากค่าเริ่มต้นไม่ใกล้เคียงกับค่าผกผันของรากที่สอง การวนซ้ำจะเบี่ยงเบนออกไปจากค่าเริ่มต้น แทนที่จะลู่เข้าหาค่าเริ่มต้น ดังนั้นจึงอาจเป็นประโยชน์ที่จะทำการวนซ้ำของวิธีบาบิโลนกับค่าประมาณคร่าวๆ ก่อนที่จะเริ่มใช้วิธีเหล่านี้ ${\displaystyle 1/{\sqrt {S}}}$${\displaystyle {\sqrt {S}}}$${\displaystyle {\sqrt {S}}=S\cdot (1/{\sqrt {S}})}$