sec numerical algorithms the fast fourier transform as noted at the beginning of this sectionmultiplication is considerably more difficult than additionbecause the cost to multiply two -bit numbers directly is ( )while addition of two -bit numbers is (nrecall from section that one property of logarithms is log nm log log thusif taking logarithms and anti-logarithms were cheapthen we could reduce multiplication to addition by taking the log of the two operandsaddingand then taking the anti-log of the sum under normal circumstancestaking logarithms and anti-logarithms is expensiveand so this reduction would not be considered practical howeverthis reduction is precisely the basis for the slide rule the slide rule uses logarithmic scale to measure the lengths of two numbersin effect doing the conversion to logarithms automatically these two lengths are then added togetherand the inverse logarithm of the sum is read off another logarithmic scale the part normally considered expensive (taking logarithms and anti-logarithmsis cheap because it is physical part of the slide rule thusthe entire multiplication process can be done cheaply via reduction to addition in the days before electronic calculatorsslide rules were routinely used by scientists and engineers to do basic calculations of this nature now consider the problem of multiplying polynomials vector of values can uniquely represent polynomial of degree expressed as pa (xn- xi = alternativelya polynomial can be uniquely represented by list of its values at distinct points finding the value for polynomial at given point is called evaluation finding the coefficients for the polynomial given the values at points is called interpolation to multiply two -degree polynomials and normally takes th( coefficient multiplications howeverif we evaluate both polynomials (at the same points)we can simply multiply the corresponding pairs of values to get the corresponding values for polynomial ab example polynomial ax polynomial