UnivariatePolynomialMultiplicationPackage(R, U)

poly.spad line 1312 [edit on github]

• R: Ring

• U: UnivariatePolynomialCategory R

This package implements Karatsuba's trick for multiplying (large) univariate polynomials. It could be improved with a version doing the work on place and also with a special case for squares. We’ve done this in Basicmath, but we believe that this out of the scope of FriCAS.

karatsuba: (U, U, NonNegativeInteger, NonNegativeInteger) -> U

karatsuba(a, b, l, k) returns a*b by applying Karatsuba's trick provided that both a and b have at least l terms and k > 0 holds and by calling noKaratsuba otherwise. The other multiplications are performed by recursive calls with the same third argument and k-1 as fourth argument.

karatsubaOnce: (U, U) -> U

karatsuba(a, b) returns a*b by applying Karatsuba's trick once. The other multiplications are performed by calling * from U.

noKaratsuba: (U, U) -> U

noKaratsuba(a, b) returns a*b without using Karatsuba's trick at all.