Ana Sayfa
Matematikçiler
Makaleler
Matematik Seçkileri
Fraktallar
Paradokslar
Sayılar Teorisi
=> Algebraic Curves-Mordell Curve
=> Algebraic Curves-Ochoa Curve
=> Algebraic Integer
=> Algebraic Number
=> Algebraic Number Theory
=> Chebotarev Density Theorem
=> Class Field
=> Cyclotomic Field
=> Dedekind Ring
=> Fractional Ideal
=> Global Field
=> Local Field
=> Number Field Signature
=> Picard Group
=> Pisot Number
=> Weyl Sum
=> Casting Out Nines
=> A-Sequence
=> Anomalous Cancellation
=> Archimedes' Axiom
=> B2-Sequence
=> Calcus
=> Calkin-Wilf Tree
=> Egyptian Fraction
=> Egyptian Number
=> Erdős-Straus Conjecture
=> Erdős-Turán Conjecture
=> Eye of Horus Fraction
=> Farey Sequence
=> Ford Circle
=> Irreducible Fraction
=> Mediant
=> Minkowski's Question Mark Function
=> Pandigital Fraction
=> Reverse Polish Notation
=> Division by Zero
=> Infinite Product
=> Karatsuba Multiplication
=> Lattice Method
=> Pippenger Product
=> Reciprocal
=> Russian Multiplication
=> Solidus
=> Steffi Problem
=> Synthetic Division
=> Binary
=> Euler's Totient Rule
=> Goodstein Sequence
=> Hereditary Representation
=> Least Significant Bit
=> Midy's Theorem
=> Moser-de Bruijn Sequence
=> Negabinary
=> Negadecimal
=> Nialpdrome
=> Nonregular Number
=> Normal Number
=> One-Seventh Ellipse
=> Quaternary
=> Radix
=> Regular Number
=> Repeating Decimal
=> Saunders Graphic
=> Ternary
=> Unique Prime
=> Vigesimal
Ziyaretçi defteri
 

Karatsuba Multiplication

It is possible to perform multiplication of large numbers in (many) fewer operations than the usual brute-force technique of "long multiplication." As discovered by Karatsuba (Karatsuba and Ofman 1962), multiplication of two n-digit numbers can be done with a bit complexity of less than n^2 using identities of the form

 (a+b·10^n)(c+d·10^n)=ac+[(a+b)(c+d)-ac-bd]10^n+bd·10^(2n).
(1)

Proceeding recursively then gives bit complexity O(n^(lg3)), where lg3=1.58...<2 (Borwein et al. 1989). The best known bound is O(nlgnlglgn) steps for n>>1 (Schönhage and Strassen 1971, Knuth 1998). However, this algorithm is difficult to implement, but a procedure based on the fast Fourier transform is straightforward to implement and gives bit complexity O((lgn)^(2+epsilon)n) (Brigham 1974, Borodin and Munro 1975, Borwein et al. 1989, Knuth 1998).

As a concrete example, consider multiplication of two numbers each just two "digits" long in base w,

N_1 = a_0+a_1w
(2)
N_2 = b_0+b_1w,
(3)

then their product is

P = N_1N_2
(4)
= a_0b_0+(a_0b_1+a_1b_0)w+a_1b_1w^2
(5)
= p_0+p_1w+p_2w^2.
(6)

Instead of evaluating products of individual digits, now write

q_0 = a_0b_0
(7)
q_1 = (a_0+a_1)(b_0+b_1)
(8)
q_2 = a_1b_1.
(9)

The key term is q_1, which can be expanded, regrouped, and written in terms of the p_j as

 q_1=p_1+p_0+p_2.
(10)

However, since p_0=q_0, and p_2=q_2, it immediately follows that

p_0 = q_0
(11)
p_1 = q_1-q_0-q_2
(12)
p_2 = q_2,
(13)

so the three "digits" of p have been evaluated using three multiplications rather than four. The technique can be generalized to multidigit numbers, with the trade-off being that more additions and subtractions are required.

Now consider four-"digit" numbers

 N_1=a_0+a_1w+a_2w^2+a_3w^3,
(14)

which can be written as a two-"digit" number represented in the base w^2,

 N_1=(a_0+a_1w)+(a_2+a_3w)w^2.
(15)

The "digits" in the new base are now

a_0^' = a_0+a_1w
(16)
a_1^' = a_2+a_3w,
(17)

and the Karatsuba algorithm can be applied to N_1 and N_2 in this form. Therefore, the Karatsuba algorithm is not restricted to multiplying two-digit numbers, but more generally expresses the multiplication of two numbers in terms of multiplications of numbers of half the size. The asymptotic speed the algorithm obtains by recursive application to the smaller required subproducts is O(n^(lg3)) (Knuth 1998).

When this technique is recursively applied to multidigit numbers, a point is reached in the recursion when the overhead of additions and subtractions makes it more efficient to use the usual O(n^2) multiplication algorithm to evaluate the partial products. The most efficient overall method therefore relies on a combination of Karatsuba and conventional multiplication.

 

Bugün 178 ziyaretçi (212 klik) kişi burdaydı!
Bu web sitesi ücretsiz olarak Bedava-Sitem.com ile oluşturulmuştur. Siz de kendi web sitenizi kurmak ister misiniz?
Ücretsiz kaydol