2 ms·
Very nice post! I remember helping to port the 128 bit integer functions in compiler-rt to Rust years ago [0], because clang only supported 128 bit integers on
by est31 6y ago
Very nice post! I remember helping to port the 128 bit integer functions in compiler-rt to Rust years ago [0], because clang only supported 128 bit integers on 64 bit platforms, but the goal of Rust was to support them on all platforms that Rust supports.
Since then, all algorithms in compiler-rt have been ported to Rust and live in the compiler-builtins crate. This [1] is the source code file for unsigned division. The actual logic is inside a macro and used to implement both 128 bit division in terms of 64 bit numbers and 64 bit division in terms of 32 bit numbers.
I wonder if similar optimizations can be done to that code.
[1]: https://github.com/rust-lang/rust/pull/38482 https://github.com/rust-lang/rust/pull/38482
[0]: https://github.com/rust-lang/compiler-builtins/blob/master/src/int/udiv.rs https://github.com/rust-lang/compiler-builtins/blob/master/s...
- danlark1 6y agoHi, I believe they can be done for 32 bit platforms also with the multiword division in Knuth https://skanthak.homepage.t-online.de/division.html https://skanthak.homepage.t-online.de/division.html what I've chosen for fallback if not x86_64 platform. I will try to implement the same optimizations in Rust in the upcoming weeks UPD And we opened an issue :) https://github.com/rust-lang/compiler-builtins/issues/368 https://github.com/rust-lang/compiler-builtins/issues/368
- deleted 6y ago[deleted]
- mjcohen 6y agoMany years ago I implemented a set of multiple precision integer routines in fortran. For division, I slavishly copied Knuth's routine, using all the sample divisions in his book to test, and it worked fine.