MPE Home Metamath Proof Explorer < Previous   Next >
Nearby theorems
Mirrors  >  Home  >  MPE Home  >  Th. List  >  karatsuba Structured version   Unicode version

Theorem karatsuba 15044
Description: The Karatsuba multiplication algorithm. If  X and  Y are decomposed into two groups of digits of length  M (only the lower group is known to be this size but the algorithm is most efficient when the partition is chosen near the middle of the digit string), then  X Y can be written in three groups of digits, where each group needs only one multiplication. Thus, we can halve both inputs with only three multiplications on the smaller operands, yielding an asymptotic improvement of n^(log2 3) instead of n^2 for the "naive" algorithm decmul1c 11099. (Contributed by Mario Carneiro, 16-Jul-2015.)
Hypotheses
Ref Expression
karatsuba.a  |-  A  e. 
NN0
karatsuba.b  |-  B  e. 
NN0
karatsuba.c  |-  C  e. 
NN0
karatsuba.d  |-  D  e. 
NN0
karatsuba.s  |-  S  e. 
NN0
karatsuba.m  |-  M  e. 
NN0
karatsuba.r  |-  ( A  x.  C )  =  R
karatsuba.t  |-  ( B  x.  D )  =  T
karatsuba.e  |-  ( ( A  +  B )  x.  ( C  +  D ) )  =  ( ( R  +  S )  +  T
)
karatsuba.x  |-  ( ( A  x.  ( 10
^ M ) )  +  B )  =  X
karatsuba.y  |-  ( ( C  x.  ( 10
^ M ) )  +  D )  =  Y
karatsuba.w  |-  ( ( R  x.  ( 10
^ M ) )  +  S )  =  W
karatsuba.z  |-  ( ( W  x.  ( 10
^ M ) )  +  T )  =  Z
Assertion
Ref Expression
karatsuba  |-  ( X  x.  Y )  =  Z

Proof of Theorem karatsuba
StepHypRef Expression
1 karatsuba.a . . . . . 6  |-  A  e. 
NN0
21nn0cni 10882 . . . . 5  |-  A  e.  CC
3 10nn0 10895 . . . . . . 7  |-  10  e.  NN0
43nn0cni 10882 . . . . . 6  |-  10  e.  CC
5 karatsuba.m . . . . . 6  |-  M  e. 
NN0
6 expcl 12290 . . . . . 6  |-  ( ( 10  e.  CC  /\  M  e.  NN0 )  -> 
( 10 ^ M
)  e.  CC )
74, 5, 6mp2an 676 . . . . 5  |-  ( 10
^ M )  e.  CC
82, 7mulcli 9649 . . . 4  |-  ( A  x.  ( 10 ^ M ) )  e.  CC
9 karatsuba.b . . . . 5  |-  B  e. 
NN0
109nn0cni 10882 . . . 4  |-  B  e.  CC
11 karatsuba.c . . . . . 6  |-  C  e. 
NN0
1211nn0cni 10882 . . . . 5  |-  C  e.  CC
1312, 7mulcli 9649 . . . 4  |-  ( C  x.  ( 10 ^ M ) )  e.  CC
14 karatsuba.d . . . . 5  |-  D  e. 
NN0
1514nn0cni 10882 . . . 4  |-  D  e.  CC
168, 10, 13, 15muladdi 10070 . . 3  |-  ( ( ( A  x.  ( 10 ^ M ) )  +  B )  x.  ( ( C  x.  ( 10 ^ M ) )  +  D ) )  =  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )  +  ( D  x.  B ) )  +  ( ( ( A  x.  ( 10 ^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) ) )
178, 13mulcli 9649 . . . 4  |-  ( ( A  x.  ( 10
^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )  e.  CC
1815, 10mulcli 9649 . . . 4  |-  ( D  x.  B )  e.  CC
198, 15mulcli 9649 . . . . 5  |-  ( ( A  x.  ( 10
^ M ) )  x.  D )  e.  CC
2013, 10mulcli 9649 . . . . 5  |-  ( ( C  x.  ( 10
^ M ) )  x.  B )  e.  CC
2119, 20addcli 9648 . . . 4  |-  ( ( ( A  x.  ( 10 ^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) )  e.  CC
2217, 18, 21add32i 9853 . . 3  |-  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )  +  ( D  x.  B ) )  +  ( ( ( A  x.  ( 10 ^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) ) )  =  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )  +  ( ( ( A  x.  ( 10
^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) ) )  +  ( D  x.  B ) )
238, 12mulcli 9649 . . . . . 6  |-  ( ( A  x.  ( 10
^ M ) )  x.  C )  e.  CC
24 karatsuba.s . . . . . . 7  |-  S  e. 
NN0
2524nn0cni 10882 . . . . . 6  |-  S  e.  CC
2623, 25, 7adddiri 9655 . . . . 5  |-  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  C )  +  S )  x.  ( 10 ^ M
) )  =  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  C )  x.  ( 10 ^ M ) )  +  ( S  x.  ( 10 ^ M ) ) )
272, 7, 12mul32i 9830 . . . . . . . . 9  |-  ( ( A  x.  ( 10
^ M ) )  x.  C )  =  ( ( A  x.  C )  x.  ( 10 ^ M ) )
28 karatsuba.r . . . . . . . . . 10  |-  ( A  x.  C )  =  R
2928oveq1i 6312 . . . . . . . . 9  |-  ( ( A  x.  C )  x.  ( 10 ^ M ) )  =  ( R  x.  ( 10 ^ M ) )
3027, 29eqtri 2451 . . . . . . . 8  |-  ( ( A  x.  ( 10
^ M ) )  x.  C )  =  ( R  x.  ( 10 ^ M ) )
3130oveq1i 6312 . . . . . . 7  |-  ( ( ( A  x.  ( 10 ^ M ) )  x.  C )  +  S )  =  ( ( R  x.  ( 10 ^ M ) )  +  S )
32 karatsuba.w . . . . . . 7  |-  ( ( R  x.  ( 10
^ M ) )  +  S )  =  W
3331, 32eqtri 2451 . . . . . 6  |-  ( ( ( A  x.  ( 10 ^ M ) )  x.  C )  +  S )  =  W
3433oveq1i 6312 . . . . 5  |-  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  C )  +  S )  x.  ( 10 ^ M
) )  =  ( W  x.  ( 10
^ M ) )
358, 12, 7mulassi 9653 . . . . . 6  |-  ( ( ( A  x.  ( 10 ^ M ) )  x.  C )  x.  ( 10 ^ M
) )  =  ( ( A  x.  ( 10 ^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )
362, 12mulcli 9649 . . . . . . . . . . . 12  |-  ( A  x.  C )  e.  CC
3736, 18, 25add32i 9853 . . . . . . . . . . 11  |-  ( ( ( A  x.  C
)  +  ( D  x.  B ) )  +  S )  =  ( ( ( A  x.  C )  +  S )  +  ( D  x.  B ) )
3828oveq1i 6312 . . . . . . . . . . . 12  |-  ( ( A  x.  C )  +  S )  =  ( R  +  S
)
39 karatsuba.t . . . . . . . . . . . . 13  |-  ( B  x.  D )  =  T
4010, 15, 39mulcomli 9651 . . . . . . . . . . . 12  |-  ( D  x.  B )  =  T
4138, 40oveq12i 6314 . . . . . . . . . . 11  |-  ( ( ( A  x.  C
)  +  S )  +  ( D  x.  B ) )  =  ( ( R  +  S )  +  T
)
4237, 41eqtri 2451 . . . . . . . . . 10  |-  ( ( ( A  x.  C
)  +  ( D  x.  B ) )  +  S )  =  ( ( R  +  S )  +  T
)
43 karatsuba.e . . . . . . . . . 10  |-  ( ( A  +  B )  x.  ( C  +  D ) )  =  ( ( R  +  S )  +  T
)
442, 10, 12, 15muladdi 10070 . . . . . . . . . 10  |-  ( ( A  +  B )  x.  ( C  +  D ) )  =  ( ( ( A  x.  C )  +  ( D  x.  B
) )  +  ( ( A  x.  D
)  +  ( C  x.  B ) ) )
4542, 43, 443eqtr2i 2457 . . . . . . . . 9  |-  ( ( ( A  x.  C
)  +  ( D  x.  B ) )  +  S )  =  ( ( ( A  x.  C )  +  ( D  x.  B
) )  +  ( ( A  x.  D
)  +  ( C  x.  B ) ) )
4636, 18addcli 9648 . . . . . . . . . 10  |-  ( ( A  x.  C )  +  ( D  x.  B ) )  e.  CC
472, 15mulcli 9649 . . . . . . . . . . 11  |-  ( A  x.  D )  e.  CC
4812, 10mulcli 9649 . . . . . . . . . . 11  |-  ( C  x.  B )  e.  CC
4947, 48addcli 9648 . . . . . . . . . 10  |-  ( ( A  x.  D )  +  ( C  x.  B ) )  e.  CC
5046, 25, 49addcani 9827 . . . . . . . . 9  |-  ( ( ( ( A  x.  C )  +  ( D  x.  B ) )  +  S )  =  ( ( ( A  x.  C )  +  ( D  x.  B ) )  +  ( ( A  x.  D )  +  ( C  x.  B ) ) )  <->  S  =  ( ( A  x.  D )  +  ( C  x.  B ) ) )
5145, 50mpbi 211 . . . . . . . 8  |-  S  =  ( ( A  x.  D )  +  ( C  x.  B ) )
5251oveq1i 6312 . . . . . . 7  |-  ( S  x.  ( 10 ^ M ) )  =  ( ( ( A  x.  D )  +  ( C  x.  B
) )  x.  ( 10 ^ M ) )
5347, 48, 7adddiri 9655 . . . . . . 7  |-  ( ( ( A  x.  D
)  +  ( C  x.  B ) )  x.  ( 10 ^ M ) )  =  ( ( ( A  x.  D )  x.  ( 10 ^ M
) )  +  ( ( C  x.  B
)  x.  ( 10
^ M ) ) )
542, 15, 7mul32i 9830 . . . . . . . 8  |-  ( ( A  x.  D )  x.  ( 10 ^ M ) )  =  ( ( A  x.  ( 10 ^ M ) )  x.  D )
5512, 10, 7mul32i 9830 . . . . . . . 8  |-  ( ( C  x.  B )  x.  ( 10 ^ M ) )  =  ( ( C  x.  ( 10 ^ M ) )  x.  B )
5654, 55oveq12i 6314 . . . . . . 7  |-  ( ( ( A  x.  D
)  x.  ( 10
^ M ) )  +  ( ( C  x.  B )  x.  ( 10 ^ M
) ) )  =  ( ( ( A  x.  ( 10 ^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) )
5752, 53, 563eqtri 2455 . . . . . 6  |-  ( S  x.  ( 10 ^ M ) )  =  ( ( ( A  x.  ( 10 ^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) )
5835, 57oveq12i 6314 . . . . 5  |-  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  C )  x.  ( 10 ^ M ) )  +  ( S  x.  ( 10 ^ M ) ) )  =  ( ( ( A  x.  ( 10 ^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )  +  ( ( ( A  x.  ( 10 ^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) ) )
5926, 34, 583eqtr3ri 2460 . . . 4  |-  ( ( ( A  x.  ( 10 ^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )  +  ( ( ( A  x.  ( 10 ^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) ) )  =  ( W  x.  ( 10 ^ M ) )
6059, 40oveq12i 6314 . . 3  |-  ( ( ( ( A  x.  ( 10 ^ M ) )  x.  ( C  x.  ( 10 ^ M ) ) )  +  ( ( ( A  x.  ( 10
^ M ) )  x.  D )  +  ( ( C  x.  ( 10 ^ M ) )  x.  B ) ) )  +  ( D  x.  B ) )  =  ( ( W  x.  ( 10
^ M ) )  +  T )
6116, 22, 603eqtri 2455 . 2  |-  ( ( ( A  x.  ( 10 ^ M ) )  +  B )  x.  ( ( C  x.  ( 10 ^ M ) )  +  D ) )  =  ( ( W  x.  ( 10
^ M ) )  +  T )
62 karatsuba.x . . 3  |-  ( ( A  x.  ( 10
^ M ) )  +  B )  =  X
63 karatsuba.y . . 3  |-  ( ( C  x.  ( 10
^ M ) )  +  D )  =  Y
6462, 63oveq12i 6314 . 2  |-  ( ( ( A  x.  ( 10 ^ M ) )  +  B )  x.  ( ( C  x.  ( 10 ^ M ) )  +  D ) )  =  ( X  x.  Y )
65 karatsuba.z . 2  |-  ( ( W  x.  ( 10
^ M ) )  +  T )  =  Z
6661, 64, 653eqtr3i 2459 1  |-  ( X  x.  Y )  =  Z
Colors of variables: wff setvar class
Syntax hints:    = wceq 1437    e. wcel 1868  (class class class)co 6302   CCcc 9538    + caddc 9543    x. cmul 9545   10c10 10668   NN0cn0 10870   ^cexp 12272
This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1665  ax-4 1678  ax-5 1748  ax-6 1794  ax-7 1839  ax-8 1870  ax-9 1872  ax-10 1887  ax-11 1892  ax-12 1905  ax-13 2053  ax-ext 2400  ax-sep 4543  ax-nul 4552  ax-pow 4599  ax-pr 4657  ax-un 6594  ax-cnex 9596  ax-resscn 9597  ax-1cn 9598  ax-icn 9599  ax-addcl 9600  ax-addrcl 9601  ax-mulcl 9602  ax-mulrcl 9603  ax-mulcom 9604  ax-addass 9605  ax-mulass 9606  ax-distr 9607  ax-i2m1 9608  ax-1ne0 9609  ax-1rid 9610  ax-rnegex 9611  ax-rrecex 9612  ax-cnre 9613  ax-pre-lttri 9614  ax-pre-lttrn 9615  ax-pre-ltadd 9616  ax-pre-mulgt0 9617
This theorem depends on definitions:  df-bi 188  df-or 371  df-an 372  df-3or 983  df-3an 984  df-tru 1440  df-ex 1660  df-nf 1664  df-sb 1787  df-eu 2269  df-mo 2270  df-clab 2408  df-cleq 2414  df-clel 2417  df-nfc 2572  df-ne 2620  df-nel 2621  df-ral 2780  df-rex 2781  df-reu 2782  df-rab 2784  df-v 3083  df-sbc 3300  df-csb 3396  df-dif 3439  df-un 3441  df-in 3443  df-ss 3450  df-pss 3452  df-nul 3762  df-if 3910  df-pw 3981  df-sn 3997  df-pr 3999  df-tp 4001  df-op 4003  df-uni 4217  df-iun 4298  df-br 4421  df-opab 4480  df-mpt 4481  df-tr 4516  df-eprel 4761  df-id 4765  df-po 4771  df-so 4772  df-fr 4809  df-we 4811  df-xp 4856  df-rel 4857  df-cnv 4858  df-co 4859  df-dm 4860  df-rn 4861  df-res 4862  df-ima 4863  df-pred 5396  df-ord 5442  df-on 5443  df-lim 5444  df-suc 5445  df-iota 5562  df-fun 5600  df-fn 5601  df-f 5602  df-f1 5603  df-fo 5604  df-f1o 5605  df-fv 5606  df-riota 6264  df-ov 6305  df-oprab 6306  df-mpt2 6307  df-om 6704  df-2nd 6805  df-wrecs 7033  df-recs 7095  df-rdg 7133  df-er 7368  df-en 7575  df-dom 7576  df-sdom 7577  df-pnf 9678  df-mnf 9679  df-xr 9680  df-ltxr 9681  df-le 9682  df-sub 9863  df-neg 9864  df-nn 10611  df-2 10669  df-3 10670  df-4 10671  df-5 10672  df-6 10673  df-7 10674  df-8 10675  df-9 10676  df-10 10677  df-n0 10871  df-z 10939  df-uz 11161  df-seq 12214  df-exp 12273
This theorem is referenced by: (None)
  Copyright terms: Public domain W3C validator