Toom-Cook algoritme
Den algoritme Toom-Kog , undertiden kaldet Toom-3 , er en multiplikation algoritme grund Andrei Toom (i) og Stephen Kog , der anvendes til at multiplicere to store tal. Disse store tal er opdelt i mindre tal, hvor beregningerne udføres. Det er en forbedring af Karatsuba-algoritmen . Algoritmen er baseret på delings- og erobringsparadigmet, hvor vi deler opskriften af tal i k-dele. Toom-3 er Took-Cook-algoritmen for k = 3.
Beskrivelse
At multiplicere to tal er som at multiplicere to polynomer
PÅ(x)=(x2x1x0)(på2på1på0)T{\ displaystyle A (x) = {\ begin {pmatrix} x ^ {2} & x ^ {1} & x ^ {0} \ end {pmatrix}} {\ begin {pmatrix} a_ {2} & a_ { 1} og a_ {0} \ end {pmatrix}} ^ {T}}![A (x) = \ begynder {pmatrix} x ^ 2 & x ^ 1 & x ^ 0 \ slut {pmatrix} \ begynder {pmatrix} a_2 & a_1 & a_0 \ slut {pmatrix} ^ T](https://wikimedia.org/api/rest_v1/media/math/render/svg/29e600c9e09543577a5ea63763a76376dd7d4928)
og
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 {pmatrix}} ^ {T}}![B (x) = \ begynder {pmatrix} x ^ 2 & x ^ 1 & x ^ 0 \ slut {pmatrix} \ begynder {pmatrix} b_2 & b_1 & b_0 \ slut {pmatrix} ^ T](https://wikimedia.org/api/rest_v1/media/math/render/svg/067517e2fabea365f94b47d8088dd8700f45e285)
hvilket giver et tredje polynom
P(x)=PÅ(x)B(x)=(x4x3x2x1x0)(s4s3s2s1s0)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) = \ begynder {pmatrix} x ^ 4 & x ^ 3 & x ^ 2 & x ^ 1 & x ^ 0 \ slut {pmatrix} \ begynder {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)
Ved at evaluere i fem forskellige punkter
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)(s4s3s2s1s0){\ 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 \\ 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)
vi bestemmer dens koefficienter via en interpolation
(s4s3s2s1s0)=(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 {pmatrix}} ^ {- 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 & 1 \ end {pmatrix} ^ {- 1} \ begin {pmatrix} P (\ infty) \\ P (2) \\ P (-1) \\ P (1) \\ P (0) \ end {pmatrix}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c7b210238e69f1f8283bf12f3cb9f51cf64f2c75)
Denne beregning kræver fem multiplikationer tre gange enklere og nogle tilføjelser
(s4s3s2s1s0)=(100001684211-11-111111100001)-1(PÅ(∞)B(∞)PÅ(2)B(2)PÅ(-1)B(-1)PÅ(1)B(1)PÅ(0)B(0))=(100001684211-11-111111100001)-1(på2b2(4på2+2på1+på0)(4b2+2b1+b0)(på2-på1+på0)(b2-b1+b0)(på2+på1+på0)(b2+b1+b0)på0b0) .{\ displaystyle {\ 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_ {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 {pmatrix}} ~. \ End { justeret}}}![\ 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 {pmatrix} ~. \ end {align}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5ab350774a15eb28a32c042a3919420d0e50f545)
Den kompleksitet er derfor
O(ikkelog3(5))≃O(ikke1.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)
.
Referencer
-
(ru) Andrei Toom, " О сложности схемы из функциональных элементов, реализующей умножение целых чисел " ( Arkiv • Wikiwix • Archive.is • Google • Hvad gør? ) , Доклады Академии Наук СССР, T. 150, n o 3, 1963 s. 496-498 , (da) “ Kompleksiteten af en ordning med funktionelle elementer, der realiserer multiplikation af heltal ” ( Arkiv • Wikiwix • Archive.is • Google • Hvad skal jeg gøre? ) , P. 714-716
-
(en) Donald Knuth , The Art of Computer Programming , Vol. 2, 3 rd ed. , Addison-Wesley, 1997
-
(en) Richard Crandall , Carl Pomerance , Prime Numbers - En Computational perspektiv , 2 th ed. , Springer, 2005
-
(da) Toom 3-vejs multiplikation , GMP dokumentation
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">