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

Implement faster multiplication algorithm #1

Open
isaacholt100 opened this issue Jun 21, 2022 · 0 comments
Open

Implement faster multiplication algorithm #1

isaacholt100 opened this issue Jun 21, 2022 · 0 comments

Comments

@isaacholt100
Copy link
Owner

isaacholt100 commented Jun 21, 2022

Currently, the multiplication algorithm for integers is long multiplication, which is slow for large numbers (O(n^2)). For integers of size beyond a given threshold, faster algorithms should be used such as Karatsuba, Toom-Cook, and maybe also Schonage-Strassen. This will also allow a divide and conquer division to be used which will have the same time complexity as the multiplication algorithm.

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

1 participant