8485 articles  [english version]

inria-00072854, version 1

Karatsuba Square Root

Paul Zimmermann 1

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 :  POLKA (INRIA Lorraine - LORIA)
  • 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
  • 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