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

Theorem karatsuba 13348
 Description: The Karatsuba multiplication algorithm. If and are decomposed into two groups of digits of length (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 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 10362. (Contributed by Mario Carneiro, 16-Jul-2015.)
Hypotheses
Ref Expression
karatsuba.a
karatsuba.b
karatsuba.c
karatsuba.d
karatsuba.s
karatsuba.m
karatsuba.r
karatsuba.t
karatsuba.e
karatsuba.x
karatsuba.y
karatsuba.w
karatsuba.z
Assertion
Ref Expression
karatsuba

Proof of Theorem karatsuba
StepHypRef Expression
1 karatsuba.a . . . . . 6
21nn0cni 10166 . . . . 5
3 10nn0 10179 . . . . . . 7
43nn0cni 10166 . . . . . 6
5 karatsuba.m . . . . . 6
6 expcl 11327 . . . . . 6
74, 5, 6mp2an 654 . . . . 5
82, 7mulcli 9029 . . . 4
9 karatsuba.b . . . . 5
109nn0cni 10166 . . . 4
11 karatsuba.c . . . . . 6
1211nn0cni 10166 . . . . 5
1312, 7mulcli 9029 . . . 4
14 karatsuba.d . . . . 5
1514nn0cni 10166 . . . 4
168, 10, 13, 15muladdi 9417 . . 3
178, 13mulcli 9029 . . . 4
1815, 10mulcli 9029 . . . 4
198, 15mulcli 9029 . . . . 5
2013, 10mulcli 9029 . . . . 5
2119, 20addcli 9028 . . . 4
2217, 18, 21add32i 9217 . . 3
238, 12mulcli 9029 . . . . . 6
24 karatsuba.s . . . . . . 7
2524nn0cni 10166 . . . . . 6
2623, 25, 7adddiri 9035 . . . . 5
272, 7, 12mul32i 9195 . . . . . . . . 9
28 karatsuba.r . . . . . . . . . 10
2928oveq1i 6031 . . . . . . . . 9
3027, 29eqtri 2408 . . . . . . . 8
3130oveq1i 6031 . . . . . . 7
32 karatsuba.w . . . . . . 7
3331, 32eqtri 2408 . . . . . 6
3433oveq1i 6031 . . . . 5
358, 12, 7mulassi 9033 . . . . . 6
362, 12mulcli 9029 . . . . . . . . . . . 12
3736, 18, 25add32i 9217 . . . . . . . . . . 11
3828oveq1i 6031 . . . . . . . . . . . 12
39 karatsuba.t . . . . . . . . . . . . 13
4010, 15, 39mulcomli 9031 . . . . . . . . . . . 12
4138, 40oveq12i 6033 . . . . . . . . . . 11
4237, 41eqtri 2408 . . . . . . . . . 10
43 karatsuba.e . . . . . . . . . 10
442, 10, 12, 15muladdi 9417 . . . . . . . . . 10
4542, 43, 443eqtr2i 2414 . . . . . . . . 9
4636, 18addcli 9028 . . . . . . . . . 10
472, 15mulcli 9029 . . . . . . . . . . 11
4812, 10mulcli 9029 . . . . . . . . . . 11
4947, 48addcli 9028 . . . . . . . . . 10
5046, 25, 49addcani 9192 . . . . . . . . 9
5145, 50mpbi 200 . . . . . . . 8
5251oveq1i 6031 . . . . . . 7
5347, 48, 7adddiri 9035 . . . . . . 7
542, 15, 7mul32i 9195 . . . . . . . 8
5512, 10, 7mul32i 9195 . . . . . . . 8
5654, 55oveq12i 6033 . . . . . . 7
5752, 53, 563eqtri 2412 . . . . . 6
5835, 57oveq12i 6033 . . . . 5
5926, 34, 583eqtr3ri 2417 . . . 4
6059, 40oveq12i 6033 . . 3
6116, 22, 603eqtri 2412 . 2
62 karatsuba.x . . 3
63 karatsuba.y . . 3
6462, 63oveq12i 6033 . 2
65 karatsuba.z . 2
6661, 64, 653eqtr3i 2416 1
 Colors of variables: wff set class Syntax hints:   wceq 1649   wcel 1717  (class class class)co 6021  cc 8922   caddc 8927   cmul 8929  c10 9990  cn0 10154  cexp 11310 This theorem was proved from axioms:  ax-1 5  ax-2 6  ax-3 7  ax-mp 8  ax-gen 1552  ax-5 1563  ax-17 1623  ax-9 1661  ax-8 1682  ax-13 1719  ax-14 1721  ax-6 1736  ax-7 1741  ax-11 1753  ax-12 1939  ax-ext 2369  ax-sep 4272  ax-nul 4280  ax-pow 4319  ax-pr 4345  ax-un 4642  ax-cnex 8980  ax-resscn 8981  ax-1cn 8982  ax-icn 8983  ax-addcl 8984  ax-addrcl 8985  ax-mulcl 8986  ax-mulrcl 8987  ax-mulcom 8988  ax-addass 8989  ax-mulass 8990  ax-distr 8991  ax-i2m1 8992  ax-1ne0 8993  ax-1rid 8994  ax-rnegex 8995  ax-rrecex 8996  ax-cnre 8997  ax-pre-lttri 8998  ax-pre-lttrn 8999  ax-pre-ltadd 9000  ax-pre-mulgt0 9001 This theorem depends on definitions:  df-bi 178  df-or 360  df-an 361  df-3or 937  df-3an 938  df-tru 1325  df-ex 1548  df-nf 1551  df-sb 1656  df-eu 2243  df-mo 2244  df-clab 2375  df-cleq 2381  df-clel 2384  df-nfc 2513  df-ne 2553  df-nel 2554  df-ral 2655  df-rex 2656  df-reu 2657  df-rab 2659  df-v 2902  df-sbc 3106  df-csb 3196  df-dif 3267  df-un 3269  df-in 3271  df-ss 3278  df-pss 3280  df-nul 3573  df-if 3684  df-pw 3745  df-sn 3764  df-pr 3765  df-tp 3766  df-op 3767  df-uni 3959  df-iun 4038  df-br 4155  df-opab 4209  df-mpt 4210  df-tr 4245  df-eprel 4436  df-id 4440  df-po 4445  df-so 4446  df-fr 4483  df-we 4485  df-ord 4526  df-on 4527  df-lim 4528  df-suc 4529  df-om 4787  df-xp 4825  df-rel 4826  df-cnv 4827  df-co 4828  df-dm 4829  df-rn 4830  df-res 4831  df-ima 4832  df-iota 5359  df-fun 5397  df-fn 5398  df-f 5399  df-f1 5400  df-fo 5401  df-f1o 5402  df-fv 5403  df-ov 6024  df-oprab 6025  df-mpt2 6026  df-2nd 6290  df-riota 6486  df-recs 6570  df-rdg 6605  df-er 6842  df-en 7047  df-dom 7048  df-sdom 7049  df-pnf 9056  df-mnf 9057  df-xr 9058  df-ltxr 9059  df-le 9060  df-sub 9226  df-neg 9227  df-nn 9934  df-2 9991  df-3 9992  df-4 9993  df-5 9994  df-6 9995  df-7 9996  df-8 9997  df-9 9998  df-10 9999  df-n0 10155  df-z 10216  df-uz 10422  df-seq 11252  df-exp 11311
 Copyright terms: Public domain W3C validator