Karatsuba Square Root (original) (raw)

Rapport (Rapport De Recherche) Année : 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.

Connectez-vous pour contacter le contributeur

https://inria.hal.science/inria-00072854

Soumis le : mercredi 24 mai 2006-11:05:58

Dernière modification le : mardi 4 novembre 2025-12:01:37

Archivage à long terme le : dimanche 4 avril 2010-23:25:18

Dates et versions

inria-00072854 , version 1 (24-05-2006)

Licence

Identifiants

Citer

Paul Zimmermann. Karatsuba Square Root. [Research Report] RR-3805, INRIA. 1999, pp.8. ⟨inria-00072854⟩

2077 Consultations

8940 Téléchargements