Computing N-th Roots using the Babylonian Method

Title:	Computing N-th Roots using the Babylonian Method
Author:	René Thiemann
Submission date:	2013-01-03
Abstract:	We implement the Babylonian method to compute n-th roots of numbers. We provide precise algorithms for naturals, integers and rationals, and offer an approximation algorithm for square roots over linear ordered fields. Moreover, there are precise algorithms to compute the floor and the ceiling of n-th roots.
Change history:	[2013-10-16]: Added algorithms to compute floor and ceiling of sqrt of integers. [2014-07-11]: Moved NthRoot_Impl from Real-Impl to this entry.
BibTeX:	@article{Sqrt_Babylonian-AFP, author = {René Thiemann}, title = {Computing N-th Roots using the Babylonian Method}, journal = {Archive of Formal Proofs}, month = jan, year = 2013, note = {\url{http://isa-afp.org/entries/Sqrt_Babylonian.html}, Formal proof development}, ISSN = {2150-914x}, }
License:	GNU Lesser General Public License (LGPL)
Depends on:	Cauchy
Used by:	Polynomial_Factorization, Polynomial_Interpolation, QR_Decomposition, Real_Impl
Status: [ok]	This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.