Vés al contingut

Algorisme de Karatsuba

De la Viquipèdia, l'enciclopèdia lliure

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.[1][2][3]

Redueix la multiplicació de dos nombres de n dígits a com a molt multiplicacions d'un dígit en general (i exactament quan n és una potència de 2). És per tant asimptomàticament més ràpid que l'algorisme tradicional, que requereix 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

[modifica]

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.[1]

Referències

[modifica]
  1. 1,0 1,1 A. Karatsuba and Yu. Ofman «Multiplication of Many-Digital Numbers by Automatic Computers». Proceedings of the USSR Academy of Sciences, 145, 1962, pàg. 293–294.
  2. A. A. Karatsuba «The Complexity of Computations». Proceedings of the Steklov Institute of Mathematics, 211, 1995, pàg. 169–183.
  3. Knuth D.E. (1969) The Art of Computer Programming. v.2. Addison-Wesley Publ.Co., 724 pp.

Enllaços externs

[modifica]