inria-00072854, version 1
Karatsuba Square Root
N° RR-3805 (1999)
Résumé : We exhibit an algorithm to compute the square-root with remainder of a n-word number in 3\2word operations, where K(n) is the number of words operations to multiply two n-word numbers using Karatsuba's algorithm. If the remainder is not needed, the cost can be reduced to K(n) on average. This algorithm can be used for floating-point or polynomial computations too; although not optimal asymptotically, its simplicity gives a wide range of use, from about 50 to 1,000,000 digits, as shown by computer experiments.
- 1 :
- INRIA – CNRS : UMR7503
- Domaine : Informatique/Autre
- Mots-clés : square root – Karatsuba division – GNU MP – MPFR library
- Référence interne : RR-3805
- inria-00072854, version 1
- http://hal.inria.fr/inria-00072854
- oai:hal.inria.fr:inria-00072854
- Contributeur :
- Soumis le : Mercredi 24 Mai 2006, 11:05:58
- Dernière modification le : Vendredi 20 Avril 2007, 15:25:00




Documents associés

Exporter