Skip to content
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

Open
pdogr opened this issue Feb 1, 2022 · 2 comments
Open

Improve multiplication #66

pdogr opened this issue Feb 1, 2022 · 2 comments

Comments

@pdogr
Copy link

pdogr commented Feb 1, 2022

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.

@tarcieri
Copy link
Member

tarcieri commented Feb 1, 2022

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.

@pdogr
Copy link
Author

pdogr commented Feb 3, 2022

@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.
Please let me know what you think.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants