Better algorithms for the multiplication and division functions

Robbepop / apint

Arbitrary precision integers library.

Other

26 stars 4 forks source link

Better algorithms for the multiplication and division functions #45

Open AaronKutch opened 5 years ago

AaronKutch commented 5 years ago

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 commented 5 years ago

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

AaronKutch commented 5 years ago

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 commented 5 years ago

Maybe this can be some inspiration for you: https://github.com/paritytech/parity-common/pull/126

AaronKutch commented 4 years ago

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