RR-3805 : Karatsuba Square Root

Abstract : 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.

Résumé : Nous présentons un algorithme calculant la racine carrée avec reste d'un entier de n mots machine en 3\2opérations sur des mots, où K(n) désigne le nombre de telles opérations utilisées par l'algorithme de Karatsuba pour multiplier deux entiers de n mots. Si seul le quotient est recherché, le coût peut être abaissé à K(n) opérations en moyenne. Cet algorithme s'applique également aux nombres flottants ou aux polynômes ; quoique non optimal asymptotiquement, l'expérience montre qu'il est efficace en pratique sur une large plage, allant environ de 50 à un million de chiffres.

RR-3805 - Karatsuba Square Root