Theorem karatsuba 17103

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^(log₂ 3) instead of n^2 for the "naive" algorithm decmul1c 12781. (Contributed by Mario Carneiro, 16-Jul-2015.) (Revised by AV, 9-Sep-2021.)

Hypotheses

Ref	Expression
karatsuba.a	⊢ 𝐴 ∈ ℕ0
karatsuba.b	⊢ 𝐵 ∈ ℕ0
karatsuba.c	⊢ 𝐶 ∈ ℕ0
karatsuba.d	⊢ 𝐷 ∈ ℕ0
karatsuba.s	⊢ 𝑆 ∈ ℕ0
karatsuba.m	⊢ 𝑀 ∈ ℕ0
karatsuba.r	⊢ (𝐴 · 𝐶) = 𝑅
karatsuba.t	⊢ (𝐵 · 𝐷) = 𝑇
karatsuba.e	⊢ ((𝐴 + 𝐵) · (𝐶 + 𝐷)) = ((𝑅 + 𝑆) + 𝑇)
karatsuba.x	⊢ ((𝐴 · (;10↑𝑀)) + 𝐵) = 𝑋
karatsuba.y	⊢ ((𝐶 · (;10↑𝑀)) + 𝐷) = 𝑌
karatsuba.w	⊢ ((𝑅 · (;10↑𝑀)) + 𝑆) = 𝑊
karatsuba.z	⊢ ((𝑊 · (;10↑𝑀)) + 𝑇) = 𝑍

Assertion

Ref	Expression
karatsuba	⊢ (𝑋 · 𝑌) = 𝑍

Proof of Theorem karatsuba

Step	Hyp	Ref	Expression
1		karatsuba.a	. . . . . 6 ⊢ 𝐴 ∈ ℕ0
2	1	nn0cni 12521	. . . . 5 ⊢ 𝐴 ∈ ℂ
3		10nn0 12734	. . . . . . 7 ⊢ ;10 ∈ ℕ0
4	3	nn0cni 12521	. . . . . 6 ⊢ ;10 ∈ ℂ
5		karatsuba.m	. . . . . 6 ⊢ 𝑀 ∈ ℕ0
6		expcl 14102	. . . . . 6 ⊢ ((;10 ∈ ℂ ∧ 𝑀 ∈ ℕ0) → (;10↑𝑀) ∈ ℂ)
7	4, 5, 6	mp2an 692	. . . . 5 ⊢ (;10↑𝑀) ∈ ℂ
8	2, 7	mulcli 11250	. . . 4 ⊢ (𝐴 · (;10↑𝑀)) ∈ ℂ
9		karatsuba.b	. . . . 5 ⊢ 𝐵 ∈ ℕ0
10	9	nn0cni 12521	. . . 4 ⊢ 𝐵 ∈ ℂ
11		karatsuba.c	. . . . . 6 ⊢ 𝐶 ∈ ℕ0
12	11	nn0cni 12521	. . . . 5 ⊢ 𝐶 ∈ ℂ
13	12, 7	mulcli 11250	. . . 4 ⊢ (𝐶 · (;10↑𝑀)) ∈ ℂ
14		karatsuba.d	. . . . 5 ⊢ 𝐷 ∈ ℕ0
15	14	nn0cni 12521	. . . 4 ⊢ 𝐷 ∈ ℂ
16	8, 10, 13, 15	muladdi 11696	. . 3 ⊢ (((𝐴 · (;10↑𝑀)) + 𝐵) · ((𝐶 · (;10↑𝑀)) + 𝐷)) = ((((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀))) + (𝐷 · 𝐵)) + (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵)))
17	8, 13	mulcli 11250	. . . 4 ⊢ ((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀))) ∈ ℂ
18	15, 10	mulcli 11250	. . . 4 ⊢ (𝐷 · 𝐵) ∈ ℂ
19	8, 15	mulcli 11250	. . . . 5 ⊢ ((𝐴 · (;10↑𝑀)) · 𝐷) ∈ ℂ
20	13, 10	mulcli 11250	. . . . 5 ⊢ ((𝐶 · (;10↑𝑀)) · 𝐵) ∈ ℂ
21	19, 20	addcli 11249	. . . 4 ⊢ (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵)) ∈ ℂ
22	17, 18, 21	add32i 11467	. . 3 ⊢ ((((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀))) + (𝐷 · 𝐵)) + (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵))) = ((((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀))) + (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵))) + (𝐷 · 𝐵))
23	8, 12	mulcli 11250	. . . . . 6 ⊢ ((𝐴 · (;10↑𝑀)) · 𝐶) ∈ ℂ
24		karatsuba.s	. . . . . . 7 ⊢ 𝑆 ∈ ℕ0
25	24	nn0cni 12521	. . . . . 6 ⊢ 𝑆 ∈ ℂ
26	23, 25, 7	adddiri 11256	. . . . 5 ⊢ ((((𝐴 · (;10↑𝑀)) · 𝐶) + 𝑆) · (;10↑𝑀)) = ((((𝐴 · (;10↑𝑀)) · 𝐶) · (;10↑𝑀)) + (𝑆 · (;10↑𝑀)))
27	2, 7, 12	mul32i 11439	. . . . . . . . 9 ⊢ ((𝐴 · (;10↑𝑀)) · 𝐶) = ((𝐴 · 𝐶) · (;10↑𝑀))
28		karatsuba.r	. . . . . . . . . 10 ⊢ (𝐴 · 𝐶) = 𝑅
29	28	oveq1i 7423	. . . . . . . . 9 ⊢ ((𝐴 · 𝐶) · (;10↑𝑀)) = (𝑅 · (;10↑𝑀))
30	27, 29	eqtri 2757	. . . . . . . 8 ⊢ ((𝐴 · (;10↑𝑀)) · 𝐶) = (𝑅 · (;10↑𝑀))
31	30	oveq1i 7423	. . . . . . 7 ⊢ (((𝐴 · (;10↑𝑀)) · 𝐶) + 𝑆) = ((𝑅 · (;10↑𝑀)) + 𝑆)
32		karatsuba.w	. . . . . . 7 ⊢ ((𝑅 · (;10↑𝑀)) + 𝑆) = 𝑊
33	31, 32	eqtri 2757	. . . . . 6 ⊢ (((𝐴 · (;10↑𝑀)) · 𝐶) + 𝑆) = 𝑊
34	33	oveq1i 7423	. . . . 5 ⊢ ((((𝐴 · (;10↑𝑀)) · 𝐶) + 𝑆) · (;10↑𝑀)) = (𝑊 · (;10↑𝑀))
35	8, 12, 7	mulassi 11254	. . . . . 6 ⊢ (((𝐴 · (;10↑𝑀)) · 𝐶) · (;10↑𝑀)) = ((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀)))
36	2, 12	mulcli 11250	. . . . . . . . . . . 12 ⊢ (𝐴 · 𝐶) ∈ ℂ
37	36, 18, 25	add32i 11467	. . . . . . . . . . 11 ⊢ (((𝐴 · 𝐶) + (𝐷 · 𝐵)) + 𝑆) = (((𝐴 · 𝐶) + 𝑆) + (𝐷 · 𝐵))
38	28	oveq1i 7423	. . . . . . . . . . . 12 ⊢ ((𝐴 · 𝐶) + 𝑆) = (𝑅 + 𝑆)
39		karatsuba.t	. . . . . . . . . . . . 13 ⊢ (𝐵 · 𝐷) = 𝑇
40	10, 15, 39	mulcomli 11252	. . . . . . . . . . . 12 ⊢ (𝐷 · 𝐵) = 𝑇
41	38, 40	oveq12i 7425	. . . . . . . . . . 11 ⊢ (((𝐴 · 𝐶) + 𝑆) + (𝐷 · 𝐵)) = ((𝑅 + 𝑆) + 𝑇)
42	37, 41	eqtri 2757	. . . . . . . . . 10 ⊢ (((𝐴 · 𝐶) + (𝐷 · 𝐵)) + 𝑆) = ((𝑅 + 𝑆) + 𝑇)
43		karatsuba.e	. . . . . . . . . 10 ⊢ ((𝐴 + 𝐵) · (𝐶 + 𝐷)) = ((𝑅 + 𝑆) + 𝑇)
44	2, 10, 12, 15	muladdi 11696	. . . . . . . . . 10 ⊢ ((𝐴 + 𝐵) · (𝐶 + 𝐷)) = (((𝐴 · 𝐶) + (𝐷 · 𝐵)) + ((𝐴 · 𝐷) + (𝐶 · 𝐵)))
45	42, 43, 44	3eqtr2i 2763	. . . . . . . . 9 ⊢ (((𝐴 · 𝐶) + (𝐷 · 𝐵)) + 𝑆) = (((𝐴 · 𝐶) + (𝐷 · 𝐵)) + ((𝐴 · 𝐷) + (𝐶 · 𝐵)))
46	36, 18	addcli 11249	. . . . . . . . . 10 ⊢ ((𝐴 · 𝐶) + (𝐷 · 𝐵)) ∈ ℂ
47	2, 15	mulcli 11250	. . . . . . . . . . 11 ⊢ (𝐴 · 𝐷) ∈ ℂ
48	12, 10	mulcli 11250	. . . . . . . . . . 11 ⊢ (𝐶 · 𝐵) ∈ ℂ
49	47, 48	addcli 11249	. . . . . . . . . 10 ⊢ ((𝐴 · 𝐷) + (𝐶 · 𝐵)) ∈ ℂ
50	46, 25, 49	addcani 11436	. . . . . . . . 9 ⊢ ((((𝐴 · 𝐶) + (𝐷 · 𝐵)) + 𝑆) = (((𝐴 · 𝐶) + (𝐷 · 𝐵)) + ((𝐴 · 𝐷) + (𝐶 · 𝐵))) ↔ 𝑆 = ((𝐴 · 𝐷) + (𝐶 · 𝐵)))
51	45, 50	mpbi 230	. . . . . . . 8 ⊢ 𝑆 = ((𝐴 · 𝐷) + (𝐶 · 𝐵))
52	51	oveq1i 7423	. . . . . . 7 ⊢ (𝑆 · (;10↑𝑀)) = (((𝐴 · 𝐷) + (𝐶 · 𝐵)) · (;10↑𝑀))
53	47, 48, 7	adddiri 11256	. . . . . . 7 ⊢ (((𝐴 · 𝐷) + (𝐶 · 𝐵)) · (;10↑𝑀)) = (((𝐴 · 𝐷) · (;10↑𝑀)) + ((𝐶 · 𝐵) · (;10↑𝑀)))
54	2, 15, 7	mul32i 11439	. . . . . . . 8 ⊢ ((𝐴 · 𝐷) · (;10↑𝑀)) = ((𝐴 · (;10↑𝑀)) · 𝐷)
55	12, 10, 7	mul32i 11439	. . . . . . . 8 ⊢ ((𝐶 · 𝐵) · (;10↑𝑀)) = ((𝐶 · (;10↑𝑀)) · 𝐵)
56	54, 55	oveq12i 7425	. . . . . . 7 ⊢ (((𝐴 · 𝐷) · (;10↑𝑀)) + ((𝐶 · 𝐵) · (;10↑𝑀))) = (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵))
57	52, 53, 56	3eqtri 2761	. . . . . 6 ⊢ (𝑆 · (;10↑𝑀)) = (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵))
58	35, 57	oveq12i 7425	. . . . 5 ⊢ ((((𝐴 · (;10↑𝑀)) · 𝐶) · (;10↑𝑀)) + (𝑆 · (;10↑𝑀))) = (((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀))) + (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵)))
59	26, 34, 58	3eqtr3ri 2766	. . . 4 ⊢ (((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀))) + (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵))) = (𝑊 · (;10↑𝑀))
60	59, 40	oveq12i 7425	. . 3 ⊢ ((((𝐴 · (;10↑𝑀)) · (𝐶 · (;10↑𝑀))) + (((𝐴 · (;10↑𝑀)) · 𝐷) + ((𝐶 · (;10↑𝑀)) · 𝐵))) + (𝐷 · 𝐵)) = ((𝑊 · (;10↑𝑀)) + 𝑇)
61	16, 22, 60	3eqtri 2761	. 2 ⊢ (((𝐴 · (;10↑𝑀)) + 𝐵) · ((𝐶 · (;10↑𝑀)) + 𝐷)) = ((𝑊 · (;10↑𝑀)) + 𝑇)
62		karatsuba.x	. . 3 ⊢ ((𝐴 · (;10↑𝑀)) + 𝐵) = 𝑋
63		karatsuba.y	. . 3 ⊢ ((𝐶 · (;10↑𝑀)) + 𝐷) = 𝑌
64	62, 63	oveq12i 7425	. 2 ⊢ (((𝐴 · (;10↑𝑀)) + 𝐵) · ((𝐶 · (;10↑𝑀)) + 𝐷)) = (𝑋 · 𝑌)
65		karatsuba.z	. 2 ⊢ ((𝑊 · (;10↑𝑀)) + 𝑇) = 𝑍
66	61, 64, 65	3eqtr3i 2765	1 ⊢ (𝑋 · 𝑌) = 𝑍

Syntax hints:   = wceq 1539   ∈ wcel 2107  (class class class)co 7413  ℂcc 11135  0cc0 11137  1c1 11138   + caddc 11140   · cmul 11142  ℕ₀cn0 12509  ;cdc 12716  ↑cexp 14084

This theorem was proved from axioms:  ax-mp 5  ax-1 6  ax-2 7  ax-3 8  ax-gen 1794  ax-4 1808  ax-5 1909  ax-6 1966  ax-7 2006  ax-8 2109  ax-9 2117  ax-10 2140  ax-11 2156  ax-12 2176  ax-ext 2706  ax-sep 5276  ax-nul 5286  ax-pow 5345  ax-pr 5412  ax-un 7737  ax-cnex 11193  ax-resscn 11194  ax-1cn 11195  ax-icn 11196  ax-addcl 11197  ax-addrcl 11198  ax-mulcl 11199  ax-mulrcl 11200  ax-mulcom 11201  ax-addass 11202  ax-mulass 11203  ax-distr 11204  ax-i2m1 11205  ax-1ne0 11206  ax-1rid 11207  ax-rnegex 11208  ax-rrecex 11209  ax-cnre 11210  ax-pre-lttri 11211  ax-pre-lttrn 11212  ax-pre-ltadd 11213  ax-pre-mulgt0 11214

This theorem depends on definitions:  df-bi 207  df-an 396  df-or 848  df-3or 1087  df-3an 1088  df-tru 1542  df-fal 1552  df-ex 1779  df-nf 1783  df-sb 2064  df-mo 2538  df-eu 2567  df-clab 2713  df-cleq 2726  df-clel 2808  df-nfc 2884  df-ne 2932  df-nel 3036  df-ral 3051  df-rex 3060  df-reu 3364  df-rab 3420  df-v 3465  df-sbc 3771  df-csb 3880  df-dif 3934  df-un 3936  df-in 3938  df-ss 3948  df-pss 3951  df-nul 4314  df-if 4506  df-pw 4582  df-sn 4607  df-pr 4609  df-op 4613  df-uni 4888  df-iun 4973  df-br 5124  df-opab 5186  df-mpt 5206  df-tr 5240  df-id 5558  df-eprel 5564  df-po 5572  df-so 5573  df-fr 5617  df-we 5619  df-xp 5671  df-rel 5672  df-cnv 5673  df-co 5674  df-dm 5675  df-rn 5676  df-res 5677  df-ima 5678  df-pred 6301  df-ord 6366  df-on 6367  df-lim 6368  df-suc 6369  df-iota 6494  df-fun 6543  df-fn 6544  df-f 6545  df-f1 6546  df-fo 6547  df-f1o 6548  df-fv 6549  df-riota 7370  df-ov 7416  df-oprab 7417  df-mpo 7418  df-om 7870  df-2nd 7997  df-frecs 8288  df-wrecs 8319  df-recs 8393  df-rdg 8432  df-er 8727  df-en 8968  df-dom 8969  df-sdom 8970  df-pnf 11279  df-mnf 11280  df-xr 11281  df-ltxr 11282  df-le 11283  df-sub 11476  df-neg 11477  df-nn 12249  df-2 12311  df-3 12312  df-4 12313  df-5 12314  df-6 12315  df-7 12316  df-8 12317  df-9 12318  df-n0 12510  df-z 12597  df-dec 12717  df-uz 12861  df-seq 14025  df-exp 14085

This theorem is referenced by:  dpmul4  32836