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

13·107 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