Package dk.jonaslindstrom.ruffini.polynomials.algorithms

Class KaratsubaAlgorithm<E>

java.lang.Object

dk.jonaslindstrom.ruffini.polynomials.algorithms.KaratsubaAlgorithm<E>

All Implemented Interfaces:

java.util.function.BiFunction<Polynomial<E>,Polynomial<E>,Polynomial<E>>, java.util.function.BinaryOperator<Polynomial<E>>

public class KaratsubaAlgorithm<E>
extends Object
implements java.util.function.BinaryOperator<Polynomial<E>>

The Karatsuba algorithm for multiplying two polynomials. The algorithm was originally presented in A. Karatsuba and Yu. Ofman (1962). "Multiplication of Many-Digital Numbers by Automatic Computers". Proceedings of the USSR Academy of Sciences 145, and has runtime O(n^{log 3}) = O(n^1.585).

Constructor Summary

Constructors

Constructor	Description
KaratsubaAlgorithm(PolynomialRingOverRing<E> polynomialRing)

Method Summary

Modifier and Type	Method	Description
Polynomial<E>	apply(Polynomial<E> a, Polynomial<E> b)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface java.util.function.BiFunction

andThen

Constructor Details

KaratsubaAlgorithm

public KaratsubaAlgorithm(PolynomialRingOverRing<E> polynomialRing)

Method Details

apply

public Polynomial<E> apply(Polynomial<E> a,
 Polynomial<E> b)

Specified by:

apply in interface java.util.function.BiFunction<Polynomial<E>,Polynomial<E>,Polynomial<E>>