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.

Sign up for GitHub

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

Jump to bottom

Faster i256 Division #4663

Closed
tustvold opened this issue Aug 7, 2023 · 1 comment · Fixed by #4672
Closed

Faster i256 Division #4663

tustvold opened this issue Aug 7, 2023 · 1 comment · Fixed by #4672
Assignees
@tustvold
Labels
arrow Changes to the arrow crate enhancement Any new improvement worthy of a entry in the changelog

Comments

@tustvold
Copy link
Contributor

tustvold commented Aug 7, 2023 •
edited

Is your feature request related to a problem or challenge? Please describe what you are trying to do.

i256 division is currently implemented using long division, this is simple but its time complexity is linear with respect to the number of digits in the output quotient. As a result it degrades poorly when dividing large numbers by smaller numbers.

Describe the solution you'd like

There are more sophisticated algorithms for multi-digit division, most famously Knuth Algorithm D.

Describe alternatives you've considered

Additional context

I have a draft implementation of this, that provides a non-trivial performance uplift
@tustvold tustvold added the enhancement Any new improvement worthy of a entry in the changelog label Aug 7, 2023
@tustvold tustvold self-assigned this Aug 7, 2023
@tustvold tustvold mentioned this issue Aug 7, 2023
Closed
tustvold added a commit to tustvold/arrow-rs that referenced this issue Aug 9, 2023
@tustvold
Faster i256 Division (2-100x) (apache#4663)
ca0ba08
tustvold added a commit to tustvold/arrow-rs that referenced this issue Aug 9, 2023
@tustvold
Faster i256 Division (2-100x) (apache#4663)
eef08b0
@tustvold tustvold mentioned this issue Aug 9, 2023
Merged
tustvold added a commit to tustvold/arrow-rs that referenced this issue Aug 9, 2023
@tustvold
Faster i256 Division (2-100x) (apache#4663)
189f6ee
tustvold added a commit that referenced this issue Aug 10, 2023
@tustvold
Faster i256 Division (2-100x) (#4663) (#4672)
c618438 
* Faster i256 Division (2-100x) (#4663)

* Clippy

* Use inline assembly

* Fix non-x64

* Add repr(C)

* More docs

* Format
@tustvold tustvold added the arrow Changes to the arrow crate label Aug 15, 2023
@tustvold
Copy link
Contributor Author

label_issue.py automatically added labels {'arrow'} from #4672

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@tustvold tustvold

Labels
arrow Changes to the arrow crate enhancement Any new improvement worthy of a entry in the changelog
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Faster i256 Division (2-100x) (#4663) tustvold/arrow-rs
1 participant
@tustvold