Volker Strassen: Vermeidung von Divisionen, J.fur die reine und Angewandte Mathematik 264 (Jan 1973) 184-202 https://eudml.org/doc/151394 This paper is about evaluating (multivariate) polynomials with algorithms that include divisions, versus algorithms that only include ring operations +,-,*. Strassen upper bounds how much divisions can help. Theorem 2: If the polynomial degree is d, then a division-free algorithm exists with at most (d-1)*d/2 times the complexity of the division-using algorithm. But Strassen says it is unlikely this is optimal. Theorem 5: reduces (d-1)*d/2 to 4*d*log2(d) but where I think a further O(loglog(d)) factor really is needed, i.e. this should be O(d * logd * loglogd). That depends on your exact model of computation and exactly what you allow as operations. Sketch of how does Strassen's proof works: Assume your division-using algorithm has some known input point P which causes all the divisions to be by 1, i.e. not divisions at all. Now replace the inputs by P+x*(Y-P) where Y is the input you want, and x is an indeterminate. When x=1 we'll have the input we want. Now employ the division-using algorithm in the ring of formal power series in x. A division by a formal power series (1+a*x+b*x*x+...) can be done using ring-operations only -- and only order N*logN*loglogN of them if go out to degree N. Now at the end of the day since we know by assumption that the final output is polynomials of degree<=d, we know we did not need to use more than d+1 terms of each power series. Hence the complexity is multiplied by O(d*logd*loglogd) at most in converting the division-using to a division-free algorithm. This actually shows a bit more than Strassen's theorems 2 & 5 said. MY VERSION OF STRASSEN THEOREM: If the division-using algorithm employs D divisions, M multiplications, and A add/subtract operations, and has polynomial degree N, then a division-free algorithm exists employing O((D+M)*N*logN*loglogN + A*N) operations.