-
Notifications
You must be signed in to change notification settings - Fork 56
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improve multiplication #66
Comments
Yes indeed, it's listed as a TODO and we'd be happy to switch to Karatsuba (see also #1). There are a few other algorithms I've seen that also may be potentially faster than Karatsuba, although I don't have references to them offhand and Karatsuba is a perfectly reasonable starting place. |
@tarcieri I've tried to implement Toom-Cook multiplication. The current impl uses arguments of the form &[Limb], &mut [Limb], there is definitely a much better way to do this. |
As of #649 we support Karatsuba. Closing. |
The current implementation of mul_wide uses schoolbook multiplication, which has complexity of the order of O(n*m) where n, m are the number of limbs in the operands.
Perhaps we should switch to an asymptotically better algorithm like karatsuba multiplication. If so I would be happy to work on this.
The text was updated successfully, but these errors were encountered: