2 ms·
See the book referenced. Basically, if you implement division by Newton-Raphson, using multiplication as a subroutine, the complexity is O(M(n)). In the other
by pfdietz 3y ago
See the book referenced. Basically, if you implement division by Newton-Raphson, using multiplication as a subroutine, the complexity is O(M(n)).
In the other direction, one can use division to do multiplication by: (1) doing reciprocal with division, (2) doing squaring with reciprocal, and (3) doing multiplication with squaring. All these operations (division, multiplication, reciprocal, and squaring) turn out to be equivalent in complexity up to a constant factor. All this is asymptotically in n, the number of bits.
- broupannoiffuto 3y agoAnd we can reduce multiplication to additions, so something does not add up.
- pfdietz 3y agoNot to a constant number of additions (or, more precisely, to a set of additions whose sizes sum to O(n)), no that is not known how to do that.