View Single Post
Old 2007-12-19, 14:30   #9
alpertron's Avatar
Aug 2002
Buenos Aires, Argentina

2·691 Posts

Originally Posted by vector View Post
... On theoretical grounds this is the only multiplication algorithm I know which is both faster than exponential and slower than O(n^2) trial multiplication.
Well, you can also compute the logarithm of the absolute value of both numbers to multiply, add them, and then find its antilogarithm. Finally adjust the sign as appropiate. This is slower than O(n^2) but not exponential.
alpertron is offline   Reply With Quote