1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Karatsuba method

  1. Apr 30, 2014 #1
    1. The problem statement, all variables and given/known data
    For polynomials f(x),g(x) of degree d = 2(r−1)−1, check that multiplying f(x) and g(x) by the Karatsuba method requires 3(r-1) multiplications in the field F.


    2. Relevant equations
    You can can more clearly see problem on page 383 #10:
    http://igortitara.files.wordpress.com/2010/04/a-concrete-introduction-to-higher-algebra1.pdf


    3. The attempt at a solution
    I understand Karatsuba method is
    (a1r+a0)(b1r+b0) = a1b1r2 +(a1b0+a0b1)r+a0b0
    = a1b1r2 +(a1b1r+a0b0r−(a1−a0)(b1−b0)r)+a0b0
    = (a0b0r+a0b0)+(a1b1r2+a1b1r)−(a1−a1)(b1−b0)r
    but I do not understand how to implement this with only the degree given in the problem.
     
  2. jcsd
  3. Apr 30, 2014 #2

    Zondrina

    User Avatar
    Homework Helper

    Karatsuba multiplication has an advantage over the usual multiplication algorithm when ##n## is large enough.

    For example, take the polynomials ##f(x)## and ##g(x)## and suppose that ##r=1##. Then ##d = 0## and the Karatsuba method requires only ##1## multiplication since ##f(x)## and ##g(x)## are both constant.

    Now to see the effectiveness, suppose ##r = 2##. Then ##d = 1## and the Karatsuba method requires ##3## multiplications. Although by the usual FOIL method, we would require ##4## multiplications.

    I believe induction will be of assistance.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Karatsuba method
  1. Method of Frobenius (Replies: 4)

  2. Frobenius Method (Replies: 1)

  3. Derivative Method (Replies: 3)

  4. Shell Method (Replies: 7)

Loading...