EECS 477 - 1/16/07
numerical algorithms
multiplying numbers
reduce the problem
grade school way
reduce to addition and 10x10 multiplication table
constant time multiplication??
limited length
divide and conquer
high order bits
low order bits
recursive calls
shrink problem
the "master theorem"
divide and conquer
tree of function calls
read lecture slides*
8T(n/2) + O(n2)
x=8, y=2, n^log2(8)=?
Gauss's complex multiplication
multiply imaginary numbers
(A + Bi)*(C + Di) = (AC - BD) + (AD + BC)i
= (m2-m3)+(m1-m2-m3)i
Karatsuba's algorithm
m1 = (a+b)(c+d)
m2=ac
m3=bd
multiplying matrics
add up products of i'th row and j'th column
divide and conquer
reduce nxn mult. to (n/2)*(n/2) mult
Strassen's algorithms
m1=(R+S)W
M2=R(Y-W)
find multiple algorithms for the same problem
iterative
recursive
seemingly small improvements to divide and conquer algorithms can have a big effect
there's nothing wrong with stealing good ideas
quotes
the secret to creativity is knowing how to hide your sources
there's nothing wrong with stealing good ideas
homework
due next thursday
no handwritten
talk, but no writing
|
| |