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

Better algorithms for the multiplication and division functions #45

Open
AaronKutch opened this issue Jul 15, 2019 · 4 comments
Open

Better algorithms for the multiplication and division functions #45

AaronKutch opened this issue Jul 15, 2019 · 4 comments

Comments

@AaronKutch
Copy link
Contributor

This is a continuation of #18 and #27. I am tracking this in one issue, because the specific division algorithm I have in mind uses Karatsuba multiplication. I will post updates here as I experiment more. I will also fix the sprawling technical debt of the division function.

@AaronKutch
Copy link
Contributor Author

As a reminder to myself, I need to check that my unrolling is actually making a difference in the multiplication function

@AaronKutch
Copy link
Contributor Author

Based on problems I have encountered so far, the Karatsuba versions will have to wait for the better constructors and related PRs. However, I am preparing rewrites of the O(n^2) multiplication and division functions using lessons I learned from my slice rotation function. They should be dramatically faster and also reduce cognitive complexity problems.
I will not be PRing them until the reorganization PR is settled.

@Robbepop
Copy link
Owner

Maybe this can be some inspiration for you: paritytech/parity-common#126

@AaronKutch
Copy link
Contributor Author

A new slice::fill method was added which will help me clean up certain parts

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

No branches or pull requests

2 participants