s'authentifier
version française rss feed

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.

  • 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
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...