Algoritmo Toom-Cook
O algoritmo Toom-Cook , às vezes chamado de Toom-3 , é um algoritmo de multiplicação devido a Andrei Toom (in) e Stephen Cook , usado para multiplicar dois números grandes. Esses números grandes são divididos em números menores nos quais os cálculos serão realizados. É um refinamento do algoritmo Karatsuba . O algoritmo é baseado no paradigma dividir e conquistar, onde dividimos a escrita de números em k partes. Toom-3 é o algoritmo Took-Cook para k = 3.
Descrição
Multiplicar dois números é como multiplicar dois polinômios
NO(x)=(x2x1x0)(no2no1no0)T{\ displaystyle A (x) = {\ begin {pmatrix} x ^ {2} & x ^ {1} & x ^ {0} \ end {pmatrix}} {\ begin {pmatrix} a_ {2} & a_ { 1} & a_ {0} \ end {pmatrix}} ^ {T}}![A (x) = \ begin {pmatrix} x ^ 2 & x ^ 1 & x ^ 0 \ end {pmatrix} \ begin {pmatrix} a_2 & a_1 & a_0 \ end {pmatrix} ^ T](https://wikimedia.org/api/rest_v1/media/math/render/svg/29e600c9e09543577a5ea63763a76376dd7d4928)
e
B(x)=(x2x1x0)(b2b1b0)T{\ displaystyle B (x) = {\ begin {pmatrix} x ^ {2} & x ^ {1} & x ^ {0} \ end {pmatrix}} {\ begin {pmatrix} b_ {2} & b_ { 1} & b_ {0} \ end {pmatriz}} ^ {T}}![B (x) = \ begin {pmatrix} x ^ 2 & x ^ 1 & x ^ 0 \ end {pmatrix} \ begin {pmatrix} b_2 & b_1 & b_0 \ end {pmatrix} ^ T](https://wikimedia.org/api/rest_v1/media/math/render/svg/067517e2fabea365f94b47d8088dd8700f45e285)
que dá um terceiro polinômio
P(x)=NO(x)B(x)=(x4x3x2x1x0)(p4p3p2p1p0)T{\ displaystyle P (x) = A (x) B (x) = {\ begin {pmatrix} x ^ {4} & x ^ {3} & x ^ {2} & x ^ {1} & x ^ { 0} \ end {pmatrix}} {\ begin {pmatrix} p_ {4} & p_ {3} & p_ {2} & p_ {1} & p_ {0} \ end {pmatrix}} ^ {T}}![P (x) = A (x) B (x) = \ begin {pmatrix} x ^ 4 & x ^ 3 & x ^ 2 & x ^ 1 & x ^ 0 \ end {pmatrix} \ begin {pmatrix} p_4 & p_3 & p_2 & p_1 & p_0 \ end {pmatrix} ^ T](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a6af1039f11b3ecea62891fb0bfc6c7852c22fb)
Avaliando em cinco pontos distintos
P{\ displaystyle P}![P](https://wikimedia.org/api/rest_v1/media/math/render/svg/b4dc73bf40314945ff376bd363916a738548d40a)
(P(∞)P(2)P(-1)P(1)P(0))=(100001684211-11-111111100001)(p4p3p2p1p0){\ displaystyle {\ begin {pmatrix} P (\ infty) \\ P (2) \\ P (-1) \\ P (1) \\ P (0) \ end {pmatrix}} = {\ begin { pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \ end {pmatrix}} {\ begin {pmatrix} p_ {4} \\ p_ {3} \\ p_ {2} \\ p_ {1} \\ p_ {0} \ end { pmatrix}}}![\ begin {pmatrix} P (\ infty) \\ P (2) \\ P (-1) \\ P (1) \\ P (0) \ end {pmatrix} = \ begin {pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \ end {pmatrix} \ begin {pmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \ end {pmatrix}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1dd95b683a89a997c9ae5389b82d01332e70c5b9)
determinamos seus coeficientes por meio de uma interpolação
(p4p3p2p1p0)=(100001684211-11-111111100001)-1(P(∞)P(2)P(-1)P(1)P(0)){\ displaystyle {\ begin {pmatrix} p_ {4} \\ p_ {3} \\ p_ {2} \\ p_ {1} \\ p_ {0} \ end {pmatrix}} = {\ begin {pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \ end {pmatriz}} ^ {- 1} {\ begin {pmatrix} P (\ infty) \\ P (2) \\ P (- 1) \\ P (1) \\ P ( 0) \ end {pmatrix}}}![\ begin {pmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \ end {pmatrix} = \ begin {pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \ \ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \ end {pmatrix} ^ {- 1} \ begin {pmatrix} P (\ infty) \\ P (2) \\ P (-1) \\ P (1) \\ P (0) \ end {pmatriz}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7b210238e69f1f8283bf12f3cb9f51cf64f2c75)
Este cálculo requer cinco multiplicações três vezes mais simples e algumas adições
(p4p3p2p1p0)=(100001684211-11-111111100001)-1(NO(∞)B(∞)NO(2)B(2)NO(-1)B(-1)NO(1)B(1)NO(0)B(0))=(100001684211-11-111111100001)-1(no2b2(4no2+2no1+no0)(4b2+2b1+b0)(no2-no1+no0)(b2-b1+b0)(no2+no1+no0)(b2+b1+b0)no0b0) .{\ displaystyle {\ begin {alinhado} {\ begin {pmatrix} p_ {4} \\ p_ {3} \\ p_ {2} \\ p_ {1} \\ p_ {0} \ end {pmatrix}} & = {\ begin {pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \ end {pmatriz}} ^ {- 1} {\ begin {pmatrix} A (\ infty) B (\ infty) \\ A (2) B (2) \ \ A (-1) B (-1) \\ A (1) B (1) \\ A (0) B (0) \ end {pmatriz}} \ \ & = {\ begin {pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \ end {pmatriz}} ^ {- 1} {\ begin {pmatrix} a_ {2} b_ {2} \\ (4a_ {2} + 2a_ {1} + a_ {0}) (4b_ {2} + 2b_ {1} + b_ {0}) \\ (a_ {2} -a_ {1} + a_ {0}) (b_ {2} -b_ {1} + b_ {0}) \\ (a_ { 2} + a_ {1} + a_ {0}) (b_ {2} + b_ {1} + b_ {0}) \\ a_ {0} b_ {0} \ end {pmatriz}} ~. \ End { alinhado}}}![\ begin {align} \ begin {pmatrix} p_4 \\ p_3 \\ p_2 \\ p_1 \\ p_0 \ end {pmatrix} & = \ begin {pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \ end {pmatrix} ^ {- 1} \ begin {pmatrix} A (\ infty) B (\ infty) \\ A (2) B (2) \\ A (-1) B (-1) \\ A (1) B (1) \\ A (0) B (0) \ end {pmatrix} \\ & = \ begin {pmatrix} 1 & 0 & 0 & 0 & 0 \\ 16 & 8 & 4 & 2 & 1 \\ 1 & -1 & 1 & -1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 \ end {pmatrix} ^ {- 1} \ begin {pmatrix} a_2b_2 \\ (4a_2 + 2a_1 + a_0 ) (4b_2 + 2b_1 + b_0) \\ (a_2-a_1 + a_0) (b_2-b_1 + b_0) \\ (a_2 + a_1 + a_0) (b_2 + b_1 + b_0) \\ a_0b_0 \ end {pmatriz} ~. \ end {align}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ab350774a15eb28a32c042a3919420d0e50f545)
A complexidade é, portanto,
O(nãoregistro3(5))≃O(não1.465){\ displaystyle O (n ^ {\ log _ {3} (5)}) \ simeq O (n ^ {1 {,} 465})}![O (n ^ {\ log_3 (5)}) \ simeq O (n ^ {1 {,} 465})](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2a8820ddbd7de581d0f88c296ec17ace60d4f4d)
.
Referências
-
(ru) Andrei Toom, " О сложности схемы из функциональных элементов, реализующей умножение целых чисел " ( Arquivo • wikiwix • Archive.is • Google • O que fazer? ) , Доклады Академии Наук СССР, T. 150, n o 3, 1963 p. 496-498 , (en) “ A complexidade de um esquema de elementos funcionais realizando a multiplicação de inteiros ” ( Arquivo • Wikiwix • Archive.is • Google • O que fazer? ) , P. 714-716
-
(pt) Donald Knuth , The Art of Computer Programming , Vol. 2, 3 rd ed. , Addison-Wesley, 1997
-
(pt) Richard Crandall , Carl Pomerance , Prime Numbers - A Computational Perspective , 2 th ed. , Springer, 2005
-
(pt) Multiplicação de 3 vias Toom , documentação GMP
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">