| |
| Polynomial multiplication: |
| Bit operations |
| | | |
| Error-correcting codes: |
| McBits |
|
|
Minimum number of bit operations for multiplication
Define M(n) as the minimum number of bit operations (ANDs and XORs)
needed to multiply an n-bit polynomial f[0] + f[1] t + ... + f[n-1] t^(n-1)
by another n-bit polynomial g[0] + g[1] t + ... + g[n-1] t^(n-1),
producing a (2n-1)-bit polynomial h[0] + h[1] t + ... + h[2n-2] t^(2n-2).
Schoolbook multiplication implies that M(n) ≤ 2n^2-2n+1.
However, better bounds are known for all n ≥ 6.
For example:
-
Schoolbook: M(64) ≤ 8065.
2006 Weimerskirch--Paar: M(64) ≤ 4593 (3864 XORs and 729 ANDs).
2007 Peter--Langendoerfer "classic Karatsuba multiplication": M(64) ≤ 4593.
2007 Peter--Langendoerfer "improved iterative Karatsuba": M(64) ≤ 4250.
2006 von zur Gathen--Shokrollahi Table 1: M(64) ≤ 3945.
2003 Rodriguez-Henriquez--Koc Table 1: M(64) ≤ 3945.
2000.08 Bernstein: M(64) ≤ 3725.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(64) ≤ 3682.
-
Schoolbook: M(113) ≤ 25313.
2006 Weimerskirch--Paar: M(113) ≤ 12657 (10665 XORs and 1992 ANDs).
2006 von zur Gathen--Shokrollahi Table 1: M(113) ≤ 11522.
2005 Chang--Kim--Park--Lim "non-redundant Karatsuba-Ofman algorithm": M(113) ≤ 11138.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(113) ≤ 9534.
-
Schoolbook: M(128) ≤ 32513.
2006 Weimerskirch--Paar: M(128) ≤ 14287 (12100 XORs and 2187 ANDs).
2007 Peter--Langendoerfer "classic Karatsuba multiplication": M(128) ≤ 14287.
2007 Peter--Langendoerfer "improved iterative Karatsuba": M(128) ≤ 13146.
2006 von zur Gathen--Shokrollahi Table 1: M(128) ≤ 12343.
2003 Rodriguez-Henriquez--Koc Table 1: M(128) ≤ 12343.
2000.08 Bernstein: M(128) ≤ 11620.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(128) ≤ 11486.
-
Schoolbook: M(131) ≤ 34061.
2005 Chang--Kim--Park--Lim "non-redundant Karatsuba-Ofman algorithm": M(131) ≤ 15939.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(131) ≤ 11961.
-
Schoolbook: M(163) ≤ 52813.
2005 Chang--Kim--Park--Lim "non-redundant Karatsuba-Ofman algorithm": M(163) ≤ 21791.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(163) ≤ 16923.
-
Schoolbook: M(193) ≤ 74113.
2003 Rodriguez-Henriquez--Koc Section 4.1: M(193) ≤ 29725 (20524 XORs and 9201 ANDs).
2005 Chang--Kim--Park--Lim "non-redundant Karatsuba-Ofman algorithm": M(193) ≤ 27803.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(193) ≤ 21865.
-
Schoolbook: M(194) ≤ 74885.
2006 von zur Gathen--Shokrollahi Section 3: M(194) ≤ 26575.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(194) ≤ 21906.
-
Schoolbook: M(251) ≤ 125501.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(251) ≤ 33096.
-
Schoolbook: M(256) ≤ 130561.
2007 Peter--Langendoerfer "classic Karatsuba multiplication": M(256) ≤ 43881 (37320 XORs and 6561 ANDs).
2007 Peter--Langendoerfer "improved iterative Karatsuba": M(256) ≤ 40415.
2003 Rodriguez-Henriquez--Koc Table 1: M(256) ≤ 38049.
2000.08 Bernstein: M(256) ≤ 35753.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(256) ≤ 34079.
-
Schoolbook: M(283) ≤ 159613.
2005 Chang--Kim--Park--Lim "non-redundant Karatsuba-Ofman algorithm": M(283) ≤ 52828.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(283) ≤ 38735.
-
Schoolbook: M(512) ≤ 523265.
2003 Rodriguez-Henriquez--Koc Table 1: M(512) ≤ 116191 (81199 XORs and 34992 ANDs).
2000.08 Bernstein: M(512) ≤ 109048.
2009.05 Bernstein "Batch binary Edwards" Section 2: M(512) ≤ 98018.
The following table presents upper bounds on M(1), M(2), ..., M(1000).
The links in the table are to straight-line code justifying the upper bounds.
Version
This is version 2009.05.31 of the m.html web page.
|