Algorisme de Karatsuba

L'algorisme de Karatsuba és un algorisme de multiplicació ràpid. Va ser descobert per Anatoli Karatsuba el 1960, i publicat dos anys més tard.

Redueix la multiplicació de dos nombres de n dígits a com a molt $n^{\log _{2}3}\approx n^{1.58}$ multiplicacions d'un dígit en general (i exactament $n^{\log _{2}3}$ quan n és una potència de 2). És per tant asimptomàticament més ràpid que l'algorisme tradicional, que requereix $n^{2}$ multiplicacions d'un dígit.

Per exemple, l'algorisme de Karatsuba requereix 3¹⁰ = 59049 multiplicacions d'un dígit per multiplicar dos nombres de 1024 dígits (n = 1024 = 2¹⁰), mentre que l'algorisme tradicional requereix (2¹⁰) ² = 1048576 (17.75 vegades més ràpid).

L'algorisme de Karatsuba va ser el primer algorisme de multiplicació asimptòticament més ràpid que l'algorisme quadràtic tradicional. L'algorisme de Toom–Cook (1963) és una generalització més ràpida del mètode de Karatsuba, i l'algorisme d'Schönhage–Strassen (1971) és encara més ràpid per n suficientment grans.

L'algorisme de Karatsuba és un clar exemple del paradigma divideix i venceràs, concretament de l'algorisme de partició binària.

Història

L'any 1960, el matemàtic rus Andrei Kolmogórov va conjecturar durant un seminari a la Universitat Estatal de Moscou que tot algorisme per multiplicar dos nombres de n dígits necessitava n² passos, i que per tant no hi podia haver algorisme més eficient que el tradicional. El llavors encara alumne Anatoli Karatsuba, que havia assistit al seminari, va intentar trobar un algorisme més eficient i va aconseguir fer-ho en només una setmana. Kolmogórov va quedar tan impressionat que va començar a parlar-ne als seus seminaris arreu del món, i dos anys més tard va publicar un article, que incloïa el sistema de Karatsuba juntament amb un altre de similar descobert per Yuri Ofman. L'article, però, anomenava a "A. Karatsuba i Yu. Ofman" com a autors. Karatsuba no va saber de l'existència d'aquest article fins que va rebre les reimpressions de l'editor.

Enllaços externs

• Nemean, "How Karatsuba's algorithm gave us new ways to multiply", a YouTube. [Consulta: 8 octubre 2021]