diff options
| author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 09:22:09 +0000 |
|---|---|---|
| committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-07 09:22:09 +0000 |
| commit | 43a97878ce14b72f0981164f87f2e35e14151312 (patch) | |
| tree | 620249daf56c0258faa40cbdcf9cfba06de2a846 /third_party/rust/num-integer | |
| parent | Initial commit. (diff) | |
| download | firefox-43a97878ce14b72f0981164f87f2e35e14151312.tar.xz firefox-43a97878ce14b72f0981164f87f2e35e14151312.zip | |
Adding upstream version 110.0.1.upstream/110.0.1upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to 'third_party/rust/num-integer')
| -rw-r--r-- | third_party/rust/num-integer/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/num-integer/Cargo.toml | 51 | ||||
| -rw-r--r-- | third_party/rust/num-integer/LICENSE-APACHE | 201 | ||||
| -rw-r--r-- | third_party/rust/num-integer/LICENSE-MIT | 25 | ||||
| -rw-r--r-- | third_party/rust/num-integer/README.md | 64 | ||||
| -rw-r--r-- | third_party/rust/num-integer/RELEASES.md | 112 | ||||
| -rw-r--r-- | third_party/rust/num-integer/benches/average.rs | 414 | ||||
| -rw-r--r-- | third_party/rust/num-integer/benches/gcd.rs | 176 | ||||
| -rw-r--r-- | third_party/rust/num-integer/benches/roots.rs | 170 | ||||
| -rw-r--r-- | third_party/rust/num-integer/build.rs | 13 | ||||
| -rw-r--r-- | third_party/rust/num-integer/src/average.rs | 78 | ||||
| -rw-r--r-- | third_party/rust/num-integer/src/lib.rs | 1386 | ||||
| -rw-r--r-- | third_party/rust/num-integer/src/roots.rs | 391 | ||||
| -rw-r--r-- | third_party/rust/num-integer/tests/average.rs | 100 | ||||
| -rw-r--r-- | third_party/rust/num-integer/tests/roots.rs | 272 |
15 files changed, 3454 insertions, 0 deletions
diff --git a/third_party/rust/num-integer/.cargo-checksum.json b/third_party/rust/num-integer/.cargo-checksum.json new file mode 100644 index 0000000000..52b0e246de --- /dev/null +++ b/third_party/rust/num-integer/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"01a1f6e6771981ddeaf682be79918c45a88d032d887f188fdcb1ee7eedcf63a6","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"6485b8ed310d3f0340bf1ad1f47645069ce4069dcc6bb46c7d5c6faf41de1fdb","README.md":"68f533703554b9130ea902776bd9eb20d1a2d32b213ebadebcd49ed0f1ef9728","RELEASES.md":"21252a72a308b4dfff190bc4b67d95f2be968fab5d7ddb58cd5cfbcdab8c5adf","benches/average.rs":"94ceeb7423bcd18ab0476bc3499505ce12d9552e53fa959e50975d71300f8404","benches/gcd.rs":"9b5c0ae8ccd6c7fc8f8384fb351d10cfdd0be5fbea9365f9ea925d8915b015bf","benches/roots.rs":"79b4ab2d8fe7bbf43fe65314d2e1bc206165bc4cb34b3ceaa899f9ea7af31c09","build.rs":"575b157527243fe355a7c8d7d874a1f790c3fb0177beba9032076a7803c5b9dd","src/average.rs":"a66cf6a49f893e60697c17b2540258e69daa15ab97d8d444c6f2e8cac2f01ae9","src/lib.rs":"b77bd1a04555b180da9661d98d69fb28eb59a02f02abbaaa332c2b27c4e753c9","src/roots.rs":"2a9b908bd3666b5cffc58c1b37d329e46ed02f71ad6d5deea1e8440c10660e1a","tests/average.rs":"5f26a31be042626e9af66f7b751798621561fa090da48b1ec5ab63e388288a91","tests/roots.rs":"a0caa4142899ec8cb806a7a0d3410c39d50de97cceadc4c2ceca707be91b1ddd"},"package":"225d3389fb3509a24c93f5c29eb6bde2586b98d9f016636dff58d7c6f7569cd9"}
\ No newline at end of file diff --git a/third_party/rust/num-integer/Cargo.toml b/third_party/rust/num-integer/Cargo.toml new file mode 100644 index 0000000000..51a1a3e2f8 --- /dev/null +++ b/third_party/rust/num-integer/Cargo.toml @@ -0,0 +1,51 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g., crates.io) dependencies. +# +# If you are reading this file be aware that the original Cargo.toml +# will likely look very different (and much more reasonable). +# See Cargo.toml.orig for the original contents. + +[package] +name = "num-integer" +version = "0.1.45" +authors = ["The Rust Project Developers"] +build = "build.rs" +exclude = [ + "/bors.toml", + "/ci/*", + "/.github/*", +] +description = "Integer traits and functions" +homepage = "https://github.com/rust-num/num-integer" +documentation = "https://docs.rs/num-integer" +readme = "README.md" +keywords = [ + "mathematics", + "numerics", +] +categories = [ + "algorithms", + "science", + "no-std", +] +license = "MIT OR Apache-2.0" +repository = "https://github.com/rust-num/num-integer" + +[package.metadata.docs.rs] +features = ["std"] + +[dependencies.num-traits] +version = "0.2.11" +default-features = false + +[build-dependencies.autocfg] +version = "1" + +[features] +default = ["std"] +i128 = ["num-traits/i128"] +std = ["num-traits/std"] diff --git a/third_party/rust/num-integer/LICENSE-APACHE b/third_party/rust/num-integer/LICENSE-APACHE new file mode 100644 index 0000000000..16fe87b06e --- /dev/null +++ b/third_party/rust/num-integer/LICENSE-APACHE @@ -0,0 +1,201 @@ + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + +TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + +1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + +2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + +3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + +4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + +5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + +6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + +7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + +8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + +9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + +END OF TERMS AND CONDITIONS + +APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + +Copyright [yyyy] [name of copyright owner] + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/third_party/rust/num-integer/LICENSE-MIT b/third_party/rust/num-integer/LICENSE-MIT new file mode 100644 index 0000000000..39d4bdb5ac --- /dev/null +++ b/third_party/rust/num-integer/LICENSE-MIT @@ -0,0 +1,25 @@ +Copyright (c) 2014 The Rust Project Developers + +Permission is hereby granted, free of charge, to any +person obtaining a copy of this software and associated +documentation files (the "Software"), to deal in the +Software without restriction, including without +limitation the rights to use, copy, modify, merge, +publish, distribute, sublicense, and/or sell copies of +the Software, and to permit persons to whom the Software +is furnished to do so, subject to the following +conditions: + +The above copyright notice and this permission notice +shall be included in all copies or substantial portions +of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF +ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED +TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A +PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT +SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY +CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION +OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR +IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/third_party/rust/num-integer/README.md b/third_party/rust/num-integer/README.md new file mode 100644 index 0000000000..5f638cd0f4 --- /dev/null +++ b/third_party/rust/num-integer/README.md @@ -0,0 +1,64 @@ +# num-integer + +[](https://crates.io/crates/num-integer) +[](https://docs.rs/num-integer) +[](https://rust-lang.github.io/rfcs/2495-min-rust-version.html) +[](https://github.com/rust-num/num-integer/actions) + +`Integer` trait and functions for Rust. + +## Usage + +Add this to your `Cargo.toml`: + +```toml +[dependencies] +num-integer = "0.1" +``` + +and this to your crate root: + +```rust +extern crate num_integer; +``` + +## Features + +This crate can be used without the standard library (`#![no_std]`) by disabling +the default `std` feature. Use this in `Cargo.toml`: + +```toml +[dependencies.num-integer] +version = "0.1.36" +default-features = false +``` + +There is no functional difference with and without `std` at this time, but +there may be in the future. + +Implementations for `i128` and `u128` are only available with Rust 1.26 and +later. The build script automatically detects this, but you can make it +mandatory by enabling the `i128` crate feature. + +## Releases + +Release notes are available in [RELEASES.md](RELEASES.md). + +## Compatibility + +The `num-integer` crate is tested for rustc 1.8 and greater. + +## License + +Licensed under either of + + * [Apache License, Version 2.0](http://www.apache.org/licenses/LICENSE-2.0) + * [MIT license](http://opensource.org/licenses/MIT) + +at your option. + +### Contribution + +Unless you explicitly state otherwise, any contribution intentionally submitted +for inclusion in the work by you, as defined in the Apache-2.0 license, shall be +dual licensed as above, without any additional terms or conditions. diff --git a/third_party/rust/num-integer/RELEASES.md b/third_party/rust/num-integer/RELEASES.md new file mode 100644 index 0000000000..05c649b91c --- /dev/null +++ b/third_party/rust/num-integer/RELEASES.md @@ -0,0 +1,112 @@ +# Release 0.1.45 (2022-04-29) + +- [`Integer::next_multiple_of` and `prev_multiple_of` no longer overflow -1][45]. +- [`Integer::is_multiple_of` now handles a 0 argument without panicking][47] + for primitive integers. +- [`ExtendedGcd` no longer has any private fields][46], making it possible for + external implementations to customize `Integer::extended_gcd`. + +**Contributors**: @ciphergoth, @cuviper, @tspiteri, @WizardOfMenlo + +[45]: https://github.com/rust-num/num-integer/pull/45 +[46]: https://github.com/rust-num/num-integer/pull/46 +[47]: https://github.com/rust-num/num-integer/pull/47 + +# Release 0.1.44 (2020-10-29) + +- [The "i128" feature now bypasses compiler probing][35]. The build script + used to probe anyway and panic if requested support wasn't found, but + sometimes this ran into bad corner cases with `autocfg`. + +**Contributors**: @cuviper + +[35]: https://github.com/rust-num/num-integer/pull/35 + +# Release 0.1.43 (2020-06-11) + +- [The new `Average` trait][31] computes fast integer averages, rounded up or + down, without any risk of overflow. + +**Contributors**: @althonos, @cuviper + +[31]: https://github.com/rust-num/num-integer/pull/31 + +# Release 0.1.42 (2020-01-09) + +- [Updated the `autocfg` build dependency to 1.0][29]. + +**Contributors**: @cuviper, @dingelish + +[29]: https://github.com/rust-num/num-integer/pull/29 + +# Release 0.1.41 (2019-05-21) + +- [Fixed feature detection on `no_std` targets][25]. + +**Contributors**: @cuviper + +[25]: https://github.com/rust-num/num-integer/pull/25 + +# Release 0.1.40 (2019-05-20) + +- [Optimized primitive `gcd` by avoiding memory swaps][11]. +- [Fixed `lcm(0, 0)` to return `0`, rather than panicking][18]. +- [Added `Integer::div_ceil`, `next_multiple_of`, and `prev_multiple_of`][16]. +- [Added `Integer::gcd_lcm`, `extended_gcd`, and `extended_gcd_lcm`][19]. + +**Contributors**: @cuviper, @ignatenkobrain, @smarnach, @strake + +[11]: https://github.com/rust-num/num-integer/pull/11 +[16]: https://github.com/rust-num/num-integer/pull/16 +[18]: https://github.com/rust-num/num-integer/pull/18 +[19]: https://github.com/rust-num/num-integer/pull/19 + +# Release 0.1.39 (2018-06-20) + +- [The new `Roots` trait provides `sqrt`, `cbrt`, and `nth_root` methods][9], + calculating an `Integer`'s principal roots rounded toward zero. + +**Contributors**: @cuviper + +[9]: https://github.com/rust-num/num-integer/pull/9 + +# Release 0.1.38 (2018-05-11) + +- [Support for 128-bit integers is now automatically detected and enabled.][8] + Setting the `i128` crate feature now causes the build script to panic if such + support is not detected. + +**Contributors**: @cuviper + +[8]: https://github.com/rust-num/num-integer/pull/8 + +# Release 0.1.37 (2018-05-10) + +- [`Integer` is now implemented for `i128` and `u128`][7] starting with Rust + 1.26, enabled by the new `i128` crate feature. + +**Contributors**: @cuviper + +[7]: https://github.com/rust-num/num-integer/pull/7 + +# Release 0.1.36 (2018-02-06) + +- [num-integer now has its own source repository][num-356] at [rust-num/num-integer][home]. +- [Corrected the argument order documented in `Integer::is_multiple_of`][1] +- [There is now a `std` feature][5], enabled by default, along with the implication + that building *without* this feature makes this a `#[no_std]` crate. + - There is no difference in the API at this time. + +**Contributors**: @cuviper, @jaystrictor + +[home]: https://github.com/rust-num/num-integer +[num-356]: https://github.com/rust-num/num/pull/356 +[1]: https://github.com/rust-num/num-integer/pull/1 +[5]: https://github.com/rust-num/num-integer/pull/5 + + +# Prior releases + +No prior release notes were kept. Thanks all the same to the many +contributors that have made this crate what it is! + diff --git a/third_party/rust/num-integer/benches/average.rs b/third_party/rust/num-integer/benches/average.rs new file mode 100644 index 0000000000..649078c39d --- /dev/null +++ b/third_party/rust/num-integer/benches/average.rs @@ -0,0 +1,414 @@ +//! Benchmark sqrt and cbrt + +#![feature(test)] + +extern crate num_integer; +extern crate num_traits; +extern crate test; + +use num_integer::Integer; +use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul}; +use std::cmp::{max, min}; +use std::fmt::Debug; +use test::{black_box, Bencher}; + +// --- Utilities for RNG ---------------------------------------------------- + +trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} + +impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} + +// Simple PRNG so we don't have to worry about rand compatibility +fn lcg<T>(x: T) -> T +where + u32: AsPrimitive<T>, + T: BenchInteger, +{ + // LCG parameters from Numerical Recipes + // (but we're applying it to arbitrary sizes) + const LCG_A: u32 = 1664525; + const LCG_C: u32 = 1013904223; + x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_()) +} + +// --- Alt. Implementations ------------------------------------------------- + +trait NaiveAverage { + fn naive_average_ceil(&self, other: &Self) -> Self; + fn naive_average_floor(&self, other: &Self) -> Self; +} + +trait UncheckedAverage { + fn unchecked_average_ceil(&self, other: &Self) -> Self; + fn unchecked_average_floor(&self, other: &Self) -> Self; +} + +trait ModuloAverage { + fn modulo_average_ceil(&self, other: &Self) -> Self; + fn modulo_average_floor(&self, other: &Self) -> Self; +} + +macro_rules! naive_average { + ($T:ident) => { + impl super::NaiveAverage for $T { + fn naive_average_floor(&self, other: &$T) -> $T { + match self.checked_add(*other) { + Some(z) => Integer::div_floor(&z, &2), + None => { + if self > other { + let diff = self - other; + other + Integer::div_floor(&diff, &2) + } else { + let diff = other - self; + self + Integer::div_floor(&diff, &2) + } + } + } + } + fn naive_average_ceil(&self, other: &$T) -> $T { + match self.checked_add(*other) { + Some(z) => Integer::div_ceil(&z, &2), + None => { + if self > other { + let diff = self - other; + self - Integer::div_floor(&diff, &2) + } else { + let diff = other - self; + other - Integer::div_floor(&diff, &2) + } + } + } + } + } + }; +} + +macro_rules! unchecked_average { + ($T:ident) => { + impl super::UncheckedAverage for $T { + fn unchecked_average_floor(&self, other: &$T) -> $T { + self.wrapping_add(*other) / 2 + } + fn unchecked_average_ceil(&self, other: &$T) -> $T { + (self.wrapping_add(*other) / 2).wrapping_add(1) + } + } + }; +} + +macro_rules! modulo_average { + ($T:ident) => { + impl super::ModuloAverage for $T { + fn modulo_average_ceil(&self, other: &$T) -> $T { + let (q1, r1) = self.div_mod_floor(&2); + let (q2, r2) = other.div_mod_floor(&2); + q1 + q2 + (r1 | r2) + } + fn modulo_average_floor(&self, other: &$T) -> $T { + let (q1, r1) = self.div_mod_floor(&2); + let (q2, r2) = other.div_mod_floor(&2); + q1 + q2 + (r1 * r2) + } + } + }; +} + +// --- Bench functions ------------------------------------------------------ + +fn bench_unchecked<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) +where + T: Integer + Debug + Copy, + F: Fn(&T, &T) -> T, +{ + b.iter(|| { + for (x, y) in v { + black_box(f(x, y)); + } + }); +} + +fn bench_ceil<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) +where + T: Integer + Debug + Copy, + F: Fn(&T, &T) -> T, +{ + for &(i, j) in v { + let rt = f(&i, &j); + let (a, b) = (min(i, j), max(i, j)); + // if both number are the same sign, check rt is in the middle + if (a < T::zero()) == (b < T::zero()) { + if (b - a).is_even() { + assert_eq!(rt - a, b - rt); + } else { + assert_eq!(rt - a, b - rt + T::one()); + } + // if both number have a different sign, + } else { + if (a + b).is_even() { + assert_eq!(rt, (a + b) / (T::one() + T::one())) + } else { + assert_eq!(rt, (a + b + T::one()) / (T::one() + T::one())) + } + } + } + bench_unchecked(b, v, f); +} + +fn bench_floor<T, F>(b: &mut Bencher, v: &[(T, T)], f: F) +where + T: Integer + Debug + Copy, + F: Fn(&T, &T) -> T, +{ + for &(i, j) in v { + let rt = f(&i, &j); + let (a, b) = (min(i, j), max(i, j)); + // if both number are the same sign, check rt is in the middle + if (a < T::zero()) == (b < T::zero()) { + if (b - a).is_even() { + assert_eq!(rt - a, b - rt); + } else { + assert_eq!(rt - a + T::one(), b - rt); + } + // if both number have a different sign, + } else { + if (a + b).is_even() { + assert_eq!(rt, (a + b) / (T::one() + T::one())) + } else { + assert_eq!(rt, (a + b - T::one()) / (T::one() + T::one())) + } + } + } + bench_unchecked(b, v, f); +} + +// --- Bench implementation ------------------------------------------------- + +macro_rules! bench_average { + ($($T:ident),*) => {$( + mod $T { + use test::Bencher; + use num_integer::{Average, Integer}; + use super::{UncheckedAverage, NaiveAverage, ModuloAverage}; + use super::{bench_ceil, bench_floor, bench_unchecked}; + + naive_average!($T); + unchecked_average!($T); + modulo_average!($T); + + const SIZE: $T = 30; + + fn overflowing() -> Vec<($T, $T)> { + (($T::max_value()-SIZE)..$T::max_value()) + .flat_map(|x| -> Vec<_> { + (($T::max_value()-100)..($T::max_value()-100+SIZE)) + .map(|y| (x, y)) + .collect() + }) + .collect() + } + + fn small() -> Vec<($T, $T)> { + (0..SIZE) + .flat_map(|x| -> Vec<_> {(0..SIZE).map(|y| (x, y)).collect()}) + .collect() + } + + fn rand() -> Vec<($T, $T)> { + small() + .into_iter() + .map(|(x, y)| (super::lcg(x), super::lcg(y))) + .collect() + } + + mod ceil { + + use super::*; + + mod small { + + use super::*; + + #[bench] + fn optimized(b: &mut Bencher) { + let v = small(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y)); + } + + #[bench] + fn naive(b: &mut Bencher) { + let v = small(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y)); + } + + #[bench] + fn unchecked(b: &mut Bencher) { + let v = small(); + bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y)); + } + + #[bench] + fn modulo(b: &mut Bencher) { + let v = small(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y)); + } + } + + mod overflowing { + + use super::*; + + #[bench] + fn optimized(b: &mut Bencher) { + let v = overflowing(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y)); + } + + #[bench] + fn naive(b: &mut Bencher) { + let v = overflowing(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y)); + } + + #[bench] + fn unchecked(b: &mut Bencher) { + let v = overflowing(); + bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y)); + } + + #[bench] + fn modulo(b: &mut Bencher) { + let v = overflowing(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y)); + } + } + + mod rand { + + use super::*; + + #[bench] + fn optimized(b: &mut Bencher) { + let v = rand(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.average_ceil(y)); + } + + #[bench] + fn naive(b: &mut Bencher) { + let v = rand(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.naive_average_ceil(y)); + } + + #[bench] + fn unchecked(b: &mut Bencher) { + let v = rand(); + bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_ceil(y)); + } + + #[bench] + fn modulo(b: &mut Bencher) { + let v = rand(); + bench_ceil(b, &v, |x: &$T, y: &$T| x.modulo_average_ceil(y)); + } + } + + } + + mod floor { + + use super::*; + + mod small { + + use super::*; + + #[bench] + fn optimized(b: &mut Bencher) { + let v = small(); + bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y)); + } + + #[bench] + fn naive(b: &mut Bencher) { + let v = small(); + bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y)); + } + + #[bench] + fn unchecked(b: &mut Bencher) { + let v = small(); + bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y)); + } + + #[bench] + fn modulo(b: &mut Bencher) { + let v = small(); + bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y)); + } + } + + mod overflowing { + + use super::*; + + #[bench] + fn optimized(b: &mut Bencher) { + let v = overflowing(); + bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y)); + } + + #[bench] + fn naive(b: &mut Bencher) { + let v = overflowing(); + bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y)); + } + + #[bench] + fn unchecked(b: &mut Bencher) { + let v = overflowing(); + bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y)); + } + + #[bench] + fn modulo(b: &mut Bencher) { + let v = overflowing(); + bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y)); + } + } + + mod rand { + + use super::*; + + #[bench] + fn optimized(b: &mut Bencher) { + let v = rand(); + bench_floor(b, &v, |x: &$T, y: &$T| x.average_floor(y)); + } + + #[bench] + fn naive(b: &mut Bencher) { + let v = rand(); + bench_floor(b, &v, |x: &$T, y: &$T| x.naive_average_floor(y)); + } + + #[bench] + fn unchecked(b: &mut Bencher) { + let v = rand(); + bench_unchecked(b, &v, |x: &$T, y: &$T| x.unchecked_average_floor(y)); + } + + #[bench] + fn modulo(b: &mut Bencher) { + let v = rand(); + bench_floor(b, &v, |x: &$T, y: &$T| x.modulo_average_floor(y)); + } + } + + } + + } + )*} +} + +bench_average!(i8, i16, i32, i64, i128, isize); +bench_average!(u8, u16, u32, u64, u128, usize); diff --git a/third_party/rust/num-integer/benches/gcd.rs b/third_party/rust/num-integer/benches/gcd.rs new file mode 100644 index 0000000000..082d5ee09d --- /dev/null +++ b/third_party/rust/num-integer/benches/gcd.rs @@ -0,0 +1,176 @@ +//! Benchmark comparing the current GCD implemtation against an older one. + +#![feature(test)] + +extern crate num_integer; +extern crate num_traits; +extern crate test; + +use num_integer::Integer; +use num_traits::{AsPrimitive, Bounded, Signed}; +use test::{black_box, Bencher}; + +trait GcdOld: Integer { + fn gcd_old(&self, other: &Self) -> Self; +} + +macro_rules! impl_gcd_old_for_isize { + ($T:ty) => { + impl GcdOld for $T { + /// Calculates the Greatest Common Divisor (GCD) of the number and + /// `other`. The result is always positive. + #[inline] + fn gcd_old(&self, other: &Self) -> Self { + // Use Stein's algorithm + let mut m = *self; + let mut n = *other; + if m == 0 || n == 0 { + return (m | n).abs(); + } + + // find common factors of 2 + let shift = (m | n).trailing_zeros(); + + // The algorithm needs positive numbers, but the minimum value + // can't be represented as a positive one. + // It's also a power of two, so the gcd can be + // calculated by bitshifting in that case + + // Assuming two's complement, the number created by the shift + // is positive for all numbers except gcd = abs(min value) + // The call to .abs() causes a panic in debug mode + if m == Self::min_value() || n == Self::min_value() { + return (1 << shift).abs(); + } + + // guaranteed to be positive now, rest like unsigned algorithm + m = m.abs(); + n = n.abs(); + + // divide n and m by 2 until odd + // m inside loop + n >>= n.trailing_zeros(); + + while m != 0 { + m >>= m.trailing_zeros(); + if n > m { + std::mem::swap(&mut n, &mut m) + } + m -= n; + } + + n << shift + } + } + }; +} + +impl_gcd_old_for_isize!(i8); +impl_gcd_old_for_isize!(i16); +impl_gcd_old_for_isize!(i32); +impl_gcd_old_for_isize!(i64); +impl_gcd_old_for_isize!(isize); +impl_gcd_old_for_isize!(i128); + +macro_rules! impl_gcd_old_for_usize { + ($T:ty) => { + impl GcdOld for $T { + /// Calculates the Greatest Common Divisor (GCD) of the number and + /// `other`. The result is always positive. + #[inline] + fn gcd_old(&self, other: &Self) -> Self { + // Use Stein's algorithm + let mut m = *self; + let mut n = *other; + if m == 0 || n == 0 { + return m | n; + } + + // find common factors of 2 + let shift = (m | n).trailing_zeros(); + + // divide n and m by 2 until odd + // m inside loop + n >>= n.trailing_zeros(); + + while m != 0 { + m >>= m.trailing_zeros(); + if n > m { + std::mem::swap(&mut n, &mut m) + } + m -= n; + } + + n << shift + } + } + }; +} + +impl_gcd_old_for_usize!(u8); +impl_gcd_old_for_usize!(u16); +impl_gcd_old_for_usize!(u32); +impl_gcd_old_for_usize!(u64); +impl_gcd_old_for_usize!(usize); +impl_gcd_old_for_usize!(u128); + +/// Return an iterator that yields all Fibonacci numbers fitting into a u128. +fn fibonacci() -> impl Iterator<Item = u128> { + (0..185).scan((0, 1), |&mut (ref mut a, ref mut b), _| { + let tmp = *a; + *a = *b; + *b += tmp; + Some(*b) + }) +} + +fn run_bench<T: Integer + Bounded + Copy + 'static>(b: &mut Bencher, gcd: fn(&T, &T) -> T) +where + T: AsPrimitive<u128>, + u128: AsPrimitive<T>, +{ + let max_value: u128 = T::max_value().as_(); + let pairs: Vec<(T, T)> = fibonacci() + .collect::<Vec<_>>() + .windows(2) + .filter(|&pair| pair[0] <= max_value && pair[1] <= max_value) + .map(|pair| (pair[0].as_(), pair[1].as_())) + .collect(); + b.iter(|| { + for &(ref m, ref n) in &pairs { + black_box(gcd(m, n)); + } + }); +} + +macro_rules! bench_gcd { + ($T:ident) => { + mod $T { + use crate::{run_bench, GcdOld}; + use num_integer::Integer; + use test::Bencher; + + #[bench] + fn bench_gcd(b: &mut Bencher) { + run_bench(b, $T::gcd); + } + + #[bench] + fn bench_gcd_old(b: &mut Bencher) { + run_bench(b, $T::gcd_old); + } + } + }; +} + +bench_gcd!(u8); +bench_gcd!(u16); +bench_gcd!(u32); +bench_gcd!(u64); +bench_gcd!(u128); + +bench_gcd!(i8); +bench_gcd!(i16); +bench_gcd!(i32); +bench_gcd!(i64); +bench_gcd!(i128); diff --git a/third_party/rust/num-integer/benches/roots.rs b/third_party/rust/num-integer/benches/roots.rs new file mode 100644 index 0000000000..7f672786a5 --- /dev/null +++ b/third_party/rust/num-integer/benches/roots.rs @@ -0,0 +1,170 @@ +//! Benchmark sqrt and cbrt + +#![feature(test)] + +extern crate num_integer; +extern crate num_traits; +extern crate test; + +use num_integer::Integer; +use num_traits::checked_pow; +use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul}; +use test::{black_box, Bencher}; + +trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} + +impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} + +fn bench<T, F>(b: &mut Bencher, v: &[T], f: F, n: u32) +where + T: BenchInteger, + F: Fn(&T) -> T, +{ + // Pre-validate the results... + for i in v { + let rt = f(i); + if *i >= T::zero() { + let rt1 = rt + T::one(); + assert!(rt.pow(n) <= *i); + if let Some(x) = checked_pow(rt1, n as usize) { + assert!(*i < x); + } + } else { + let rt1 = rt - T::one(); + assert!(rt < T::zero()); + assert!(*i <= rt.pow(n)); + if let Some(x) = checked_pow(rt1, n as usize) { + assert!(x < *i); + } + }; + } + + // Now just run as fast as we can! + b.iter(|| { + for i in v { + black_box(f(i)); + } + }); +} + +// Simple PRNG so we don't have to worry about rand compatibility +fn lcg<T>(x: T) -> T +where + u32: AsPrimitive<T>, + T: BenchInteger, +{ + // LCG parameters from Numerical Recipes + // (but we're applying it to arbitrary sizes) + const LCG_A: u32 = 1664525; + const LCG_C: u32 = 1013904223; + x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_()) +} + +fn bench_rand<T, F>(b: &mut Bencher, f: F, n: u32) +where + u32: AsPrimitive<T>, + T: BenchInteger, + F: Fn(&T) -> T, +{ + let mut x: T = 3u32.as_(); + let v: Vec<T> = (0..1000) + .map(|_| { + x = lcg(x); + x + }) + .collect(); + bench(b, &v, f, n); +} + +fn bench_rand_pos<T, F>(b: &mut Bencher, f: F, n: u32) +where + u32: AsPrimitive<T>, + T: BenchInteger, + F: Fn(&T) -> T, +{ + let mut x: T = 3u32.as_(); + let v: Vec<T> = (0..1000) + .map(|_| { + x = lcg(x); + while x < T::zero() { + x = lcg(x); + } + x + }) + .collect(); + bench(b, &v, f, n); +} + +fn bench_small<T, F>(b: &mut Bencher, f: F, n: u32) +where + u32: AsPrimitive<T>, + T: BenchInteger, + F: Fn(&T) -> T, +{ + let v: Vec<T> = (0..1000).map(|i| i.as_()).collect(); + bench(b, &v, f, n); +} + +fn bench_small_pos<T, F>(b: &mut Bencher, f: F, n: u32) +where + u32: AsPrimitive<T>, + T: BenchInteger, + F: Fn(&T) -> T, +{ + let v: Vec<T> = (0..1000) + .map(|i| i.as_().mod_floor(&T::max_value())) + .collect(); + bench(b, &v, f, n); +} + +macro_rules! bench_roots { + ($($T:ident),*) => {$( + mod $T { + use test::Bencher; + use num_integer::Roots; + + #[bench] + fn sqrt_rand(b: &mut Bencher) { + ::bench_rand_pos(b, $T::sqrt, 2); + } + + #[bench] + fn sqrt_small(b: &mut Bencher) { + ::bench_small_pos(b, $T::sqrt, 2); + } + + #[bench] + fn cbrt_rand(b: &mut Bencher) { + ::bench_rand(b, $T::cbrt, 3); + } + + #[bench] + fn cbrt_small(b: &mut Bencher) { + ::bench_small(b, $T::cbrt, 3); + } + + #[bench] + fn fourth_root_rand(b: &mut Bencher) { + ::bench_rand_pos(b, |x: &$T| x.nth_root(4), 4); + } + + #[bench] + fn fourth_root_small(b: &mut Bencher) { + ::bench_small_pos(b, |x: &$T| x.nth_root(4), 4); + } + + #[bench] + fn fifth_root_rand(b: &mut Bencher) { + ::bench_rand(b, |x: &$T| x.nth_root(5), 5); + } + + #[bench] + fn fifth_root_small(b: &mut Bencher) { + ::bench_small(b, |x: &$T| x.nth_root(5), 5); + } + } + )*} +} + +bench_roots!(i8, i16, i32, i64, i128); +bench_roots!(u8, u16, u32, u64, u128); diff --git a/third_party/rust/num-integer/build.rs b/third_party/rust/num-integer/build.rs new file mode 100644 index 0000000000..37c985766a --- /dev/null +++ b/third_party/rust/num-integer/build.rs @@ -0,0 +1,13 @@ +extern crate autocfg; + +use std::env; + +fn main() { + // If the "i128" feature is explicity requested, don't bother probing for it. + // It will still cause a build error if that was set improperly. + if env::var_os("CARGO_FEATURE_I128").is_some() || autocfg::new().probe_type("i128") { + autocfg::emit("has_i128"); + } + + autocfg::rerun_path("build.rs"); +} diff --git a/third_party/rust/num-integer/src/average.rs b/third_party/rust/num-integer/src/average.rs new file mode 100644 index 0000000000..29cd11e3fe --- /dev/null +++ b/third_party/rust/num-integer/src/average.rs @@ -0,0 +1,78 @@ +use core::ops::{BitAnd, BitOr, BitXor, Shr}; +use Integer; + +/// Provides methods to compute the average of two integers, without overflows. +pub trait Average: Integer { + /// Returns the ceiling value of the average of `self` and `other`. + /// -- `⌈(self + other)/2⌉` + /// + /// # Examples + /// + /// ``` + /// use num_integer::Average; + /// + /// assert_eq!(( 3).average_ceil(&10), 7); + /// assert_eq!((-2).average_ceil(&-5), -3); + /// assert_eq!(( 4).average_ceil(& 4), 4); + /// + /// assert_eq!(u8::max_value().average_ceil(&2), 129); + /// assert_eq!(i8::min_value().average_ceil(&-1), -64); + /// assert_eq!(i8::min_value().average_ceil(&i8::max_value()), 0); + /// ``` + /// + fn average_ceil(&self, other: &Self) -> Self; + + /// Returns the floor value of the average of `self` and `other`. + /// -- `⌊(self + other)/2⌋` + /// + /// # Examples + /// + /// ``` + /// use num_integer::Average; + /// + /// assert_eq!(( 3).average_floor(&10), 6); + /// assert_eq!((-2).average_floor(&-5), -4); + /// assert_eq!(( 4).average_floor(& 4), 4); + /// + /// assert_eq!(u8::max_value().average_floor(&2), 128); + /// assert_eq!(i8::min_value().average_floor(&-1), -65); + /// assert_eq!(i8::min_value().average_floor(&i8::max_value()), -1); + /// ``` + /// + fn average_floor(&self, other: &Self) -> Self; +} + +impl<I> Average for I +where + I: Integer + Shr<usize, Output = I>, + for<'a, 'b> &'a I: + BitAnd<&'b I, Output = I> + BitOr<&'b I, Output = I> + BitXor<&'b I, Output = I>, +{ + // The Henry Gordon Dietz implementation as shown in the Hacker's Delight, + // see http://aggregate.org/MAGIC/#Average%20of%20Integers + + /// Returns the floor value of the average of `self` and `other`. + #[inline] + fn average_floor(&self, other: &I) -> I { + (self & other) + ((self ^ other) >> 1) + } + + /// Returns the ceil value of the average of `self` and `other`. + #[inline] + fn average_ceil(&self, other: &I) -> I { + (self | other) - ((self ^ other) >> 1) + } +} + +/// Returns the floor value of the average of `x` and `y` -- +/// see [Average::average_floor](trait.Average.html#tymethod.average_floor). +#[inline] +pub fn average_floor<T: Average>(x: T, y: T) -> T { + x.average_floor(&y) +} +/// Returns the ceiling value of the average of `x` and `y` -- +/// see [Average::average_ceil](trait.Average.html#tymethod.average_ceil). +#[inline] +pub fn average_ceil<T: Average>(x: T, y: T) -> T { + x.average_ceil(&y) +} diff --git a/third_party/rust/num-integer/src/lib.rs b/third_party/rust/num-integer/src/lib.rs new file mode 100644 index 0000000000..5005801d5b --- /dev/null +++ b/third_party/rust/num-integer/src/lib.rs @@ -0,0 +1,1386 @@ +// Copyright 2013-2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! Integer trait and functions. +//! +//! ## Compatibility +//! +//! The `num-integer` crate is tested for rustc 1.8 and greater. + +#![doc(html_root_url = "https://docs.rs/num-integer/0.1")] +#![no_std] +#[cfg(feature = "std")] +extern crate std; + +extern crate num_traits as traits; + +use core::mem; +use core::ops::Add; + +use traits::{Num, Signed, Zero}; + +mod roots; +pub use roots::Roots; +pub use roots::{cbrt, nth_root, sqrt}; + +mod average; +pub use average::Average; +pub use average::{average_ceil, average_floor}; + +pub trait Integer: Sized + Num + PartialOrd + Ord + Eq { + /// Floored integer division. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert!(( 8).div_floor(& 3) == 2); + /// assert!(( 8).div_floor(&-3) == -3); + /// assert!((-8).div_floor(& 3) == -3); + /// assert!((-8).div_floor(&-3) == 2); + /// + /// assert!(( 1).div_floor(& 2) == 0); + /// assert!(( 1).div_floor(&-2) == -1); + /// assert!((-1).div_floor(& 2) == -1); + /// assert!((-1).div_floor(&-2) == 0); + /// ~~~ + fn div_floor(&self, other: &Self) -> Self; + + /// Floored integer modulo, satisfying: + /// + /// ~~~ + /// # use num_integer::Integer; + /// # let n = 1; let d = 1; + /// assert!(n.div_floor(&d) * d + n.mod_floor(&d) == n) + /// ~~~ + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert!(( 8).mod_floor(& 3) == 2); + /// assert!(( 8).mod_floor(&-3) == -1); + /// assert!((-8).mod_floor(& 3) == 1); + /// assert!((-8).mod_floor(&-3) == -2); + /// + /// assert!(( 1).mod_floor(& 2) == 1); + /// assert!(( 1).mod_floor(&-2) == -1); + /// assert!((-1).mod_floor(& 2) == 1); + /// assert!((-1).mod_floor(&-2) == -1); + /// ~~~ + fn mod_floor(&self, other: &Self) -> Self; + + /// Ceiled integer division. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(( 8).div_ceil( &3), 3); + /// assert_eq!(( 8).div_ceil(&-3), -2); + /// assert_eq!((-8).div_ceil( &3), -2); + /// assert_eq!((-8).div_ceil(&-3), 3); + /// + /// assert_eq!(( 1).div_ceil( &2), 1); + /// assert_eq!(( 1).div_ceil(&-2), 0); + /// assert_eq!((-1).div_ceil( &2), 0); + /// assert_eq!((-1).div_ceil(&-2), 1); + /// ~~~ + fn div_ceil(&self, other: &Self) -> Self { + let (q, r) = self.div_mod_floor(other); + if r.is_zero() { + q + } else { + q + Self::one() + } + } + + /// Greatest Common Divisor (GCD). + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(6.gcd(&8), 2); + /// assert_eq!(7.gcd(&3), 1); + /// ~~~ + fn gcd(&self, other: &Self) -> Self; + + /// Lowest Common Multiple (LCM). + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(7.lcm(&3), 21); + /// assert_eq!(2.lcm(&4), 4); + /// assert_eq!(0.lcm(&0), 0); + /// ~~~ + fn lcm(&self, other: &Self) -> Self; + + /// Greatest Common Divisor (GCD) and + /// Lowest Common Multiple (LCM) together. + /// + /// Potentially more efficient than calling `gcd` and `lcm` + /// individually for identical inputs. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(10.gcd_lcm(&4), (2, 20)); + /// assert_eq!(8.gcd_lcm(&9), (1, 72)); + /// ~~~ + #[inline] + fn gcd_lcm(&self, other: &Self) -> (Self, Self) { + (self.gcd(other), self.lcm(other)) + } + + /// Greatest common divisor and Bézout coefficients. + /// + /// # Examples + /// + /// ~~~ + /// # extern crate num_integer; + /// # extern crate num_traits; + /// # fn main() { + /// # use num_integer::{ExtendedGcd, Integer}; + /// # use num_traits::NumAssign; + /// fn check<A: Copy + Integer + NumAssign>(a: A, b: A) -> bool { + /// let ExtendedGcd { gcd, x, y, .. } = a.extended_gcd(&b); + /// gcd == x * a + y * b + /// } + /// assert!(check(10isize, 4isize)); + /// assert!(check(8isize, 9isize)); + /// # } + /// ~~~ + #[inline] + fn extended_gcd(&self, other: &Self) -> ExtendedGcd<Self> + where + Self: Clone, + { + let mut s = (Self::zero(), Self::one()); + let mut t = (Self::one(), Self::zero()); + let mut r = (other.clone(), self.clone()); + + while !r.0.is_zero() { + let q = r.1.clone() / r.0.clone(); + let f = |mut r: (Self, Self)| { + mem::swap(&mut r.0, &mut r.1); + r.0 = r.0 - q.clone() * r.1.clone(); + r + }; + r = f(r); + s = f(s); + t = f(t); + } + + if r.1 >= Self::zero() { + ExtendedGcd { + gcd: r.1, + x: s.1, + y: t.1, + } + } else { + ExtendedGcd { + gcd: Self::zero() - r.1, + x: Self::zero() - s.1, + y: Self::zero() - t.1, + } + } + } + + /// Greatest common divisor, least common multiple, and Bézout coefficients. + #[inline] + fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) + where + Self: Clone + Signed, + { + (self.extended_gcd(other), self.lcm(other)) + } + + /// Deprecated, use `is_multiple_of` instead. + fn divides(&self, other: &Self) -> bool; + + /// Returns `true` if `self` is a multiple of `other`. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(9.is_multiple_of(&3), true); + /// assert_eq!(3.is_multiple_of(&9), false); + /// ~~~ + fn is_multiple_of(&self, other: &Self) -> bool; + + /// Returns `true` if the number is even. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(3.is_even(), false); + /// assert_eq!(4.is_even(), true); + /// ~~~ + fn is_even(&self) -> bool; + + /// Returns `true` if the number is odd. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(3.is_odd(), true); + /// assert_eq!(4.is_odd(), false); + /// ~~~ + fn is_odd(&self) -> bool; + + /// Simultaneous truncated integer division and modulus. + /// Returns `(quotient, remainder)`. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(( 8).div_rem( &3), ( 2, 2)); + /// assert_eq!(( 8).div_rem(&-3), (-2, 2)); + /// assert_eq!((-8).div_rem( &3), (-2, -2)); + /// assert_eq!((-8).div_rem(&-3), ( 2, -2)); + /// + /// assert_eq!(( 1).div_rem( &2), ( 0, 1)); + /// assert_eq!(( 1).div_rem(&-2), ( 0, 1)); + /// assert_eq!((-1).div_rem( &2), ( 0, -1)); + /// assert_eq!((-1).div_rem(&-2), ( 0, -1)); + /// ~~~ + fn div_rem(&self, other: &Self) -> (Self, Self); + + /// Simultaneous floored integer division and modulus. + /// Returns `(quotient, remainder)`. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(( 8).div_mod_floor( &3), ( 2, 2)); + /// assert_eq!(( 8).div_mod_floor(&-3), (-3, -1)); + /// assert_eq!((-8).div_mod_floor( &3), (-3, 1)); + /// assert_eq!((-8).div_mod_floor(&-3), ( 2, -2)); + /// + /// assert_eq!(( 1).div_mod_floor( &2), ( 0, 1)); + /// assert_eq!(( 1).div_mod_floor(&-2), (-1, -1)); + /// assert_eq!((-1).div_mod_floor( &2), (-1, 1)); + /// assert_eq!((-1).div_mod_floor(&-2), ( 0, -1)); + /// ~~~ + fn div_mod_floor(&self, other: &Self) -> (Self, Self) { + (self.div_floor(other), self.mod_floor(other)) + } + + /// Rounds up to nearest multiple of argument. + /// + /// # Notes + /// + /// For signed types, `a.next_multiple_of(b) = a.prev_multiple_of(b.neg())`. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(( 16).next_multiple_of(& 8), 16); + /// assert_eq!(( 23).next_multiple_of(& 8), 24); + /// assert_eq!(( 16).next_multiple_of(&-8), 16); + /// assert_eq!(( 23).next_multiple_of(&-8), 16); + /// assert_eq!((-16).next_multiple_of(& 8), -16); + /// assert_eq!((-23).next_multiple_of(& 8), -16); + /// assert_eq!((-16).next_multiple_of(&-8), -16); + /// assert_eq!((-23).next_multiple_of(&-8), -24); + /// ~~~ + #[inline] + fn next_multiple_of(&self, other: &Self) -> Self + where + Self: Clone, + { + let m = self.mod_floor(other); + self.clone() + + if m.is_zero() { + Self::zero() + } else { + other.clone() - m + } + } + + /// Rounds down to nearest multiple of argument. + /// + /// # Notes + /// + /// For signed types, `a.prev_multiple_of(b) = a.next_multiple_of(b.neg())`. + /// + /// # Examples + /// + /// ~~~ + /// # use num_integer::Integer; + /// assert_eq!(( 16).prev_multiple_of(& 8), 16); + /// assert_eq!(( 23).prev_multiple_of(& 8), 16); + /// assert_eq!(( 16).prev_multiple_of(&-8), 16); + /// assert_eq!(( 23).prev_multiple_of(&-8), 24); + /// assert_eq!((-16).prev_multiple_of(& 8), -16); + /// assert_eq!((-23).prev_multiple_of(& 8), -24); + /// assert_eq!((-16).prev_multiple_of(&-8), -16); + /// assert_eq!((-23).prev_multiple_of(&-8), -16); + /// ~~~ + #[inline] + fn prev_multiple_of(&self, other: &Self) -> Self + where + Self: Clone, + { + self.clone() - self.mod_floor(other) + } +} + +/// Greatest common divisor and Bézout coefficients +/// +/// ```no_build +/// let e = isize::extended_gcd(a, b); +/// assert_eq!(e.gcd, e.x*a + e.y*b); +/// ``` +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +pub struct ExtendedGcd<A> { + pub gcd: A, + pub x: A, + pub y: A, +} + +/// Simultaneous integer division and modulus +#[inline] +pub fn div_rem<T: Integer>(x: T, y: T) -> (T, T) { + x.div_rem(&y) +} +/// Floored integer division +#[inline] +pub fn div_floor<T: Integer>(x: T, y: T) -> T { + x.div_floor(&y) +} +/// Floored integer modulus +#[inline] +pub fn mod_floor<T: Integer>(x: T, y: T) -> T { + x.mod_floor(&y) +} +/// Simultaneous floored integer division and modulus +#[inline] +pub fn div_mod_floor<T: Integer>(x: T, y: T) -> (T, T) { + x.div_mod_floor(&y) +} +/// Ceiled integer division +#[inline] +pub fn div_ceil<T: Integer>(x: T, y: T) -> T { + x.div_ceil(&y) +} + +/// Calculates the Greatest Common Divisor (GCD) of the number and `other`. The +/// result is always non-negative. +#[inline(always)] +pub fn gcd<T: Integer>(x: T, y: T) -> T { + x.gcd(&y) +} +/// Calculates the Lowest Common Multiple (LCM) of the number and `other`. +#[inline(always)] +pub fn lcm<T: Integer>(x: T, y: T) -> T { + x.lcm(&y) +} + +/// Calculates the Greatest Common Divisor (GCD) and +/// Lowest Common Multiple (LCM) of the number and `other`. +#[inline(always)] +pub fn gcd_lcm<T: Integer>(x: T, y: T) -> (T, T) { + x.gcd_lcm(&y) +} + +macro_rules! impl_integer_for_isize { + ($T:ty, $test_mod:ident) => { + impl Integer for $T { + /// Floored integer division + #[inline] + fn div_floor(&self, other: &Self) -> Self { + // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_, + // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf) + let (d, r) = self.div_rem(other); + if (r > 0 && *other < 0) || (r < 0 && *other > 0) { + d - 1 + } else { + d + } + } + + /// Floored integer modulo + #[inline] + fn mod_floor(&self, other: &Self) -> Self { + // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_, + // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf) + let r = *self % *other; + if (r > 0 && *other < 0) || (r < 0 && *other > 0) { + r + *other + } else { + r + } + } + + /// Calculates `div_floor` and `mod_floor` simultaneously + #[inline] + fn div_mod_floor(&self, other: &Self) -> (Self, Self) { + // Algorithm from [Daan Leijen. _Division and Modulus for Computer Scientists_, + // December 2001](http://research.microsoft.com/pubs/151917/divmodnote-letter.pdf) + let (d, r) = self.div_rem(other); + if (r > 0 && *other < 0) || (r < 0 && *other > 0) { + (d - 1, r + *other) + } else { + (d, r) + } + } + + #[inline] + fn div_ceil(&self, other: &Self) -> Self { + let (d, r) = self.div_rem(other); + if (r > 0 && *other > 0) || (r < 0 && *other < 0) { + d + 1 + } else { + d + } + } + + /// Calculates the Greatest Common Divisor (GCD) of the number and + /// `other`. The result is always non-negative. + #[inline] + fn gcd(&self, other: &Self) -> Self { + // Use Stein's algorithm + let mut m = *self; + let mut n = *other; + if m == 0 || n == 0 { + return (m | n).abs(); + } + + // find common factors of 2 + let shift = (m | n).trailing_zeros(); + + // The algorithm needs positive numbers, but the minimum value + // can't be represented as a positive one. + // It's also a power of two, so the gcd can be + // calculated by bitshifting in that case + + // Assuming two's complement, the number created by the shift + // is positive for all numbers except gcd = abs(min value) + // The call to .abs() causes a panic in debug mode + if m == Self::min_value() || n == Self::min_value() { + return (1 << shift).abs(); + } + + // guaranteed to be positive now, rest like unsigned algorithm + m = m.abs(); + n = n.abs(); + + // divide n and m by 2 until odd + m >>= m.trailing_zeros(); + n >>= n.trailing_zeros(); + + while m != n { + if m > n { + m -= n; + m >>= m.trailing_zeros(); + } else { + n -= m; + n >>= n.trailing_zeros(); + } + } + m << shift + } + + #[inline] + fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) { + let egcd = self.extended_gcd(other); + // should not have to recalculate abs + let lcm = if egcd.gcd.is_zero() { + Self::zero() + } else { + (*self * (*other / egcd.gcd)).abs() + }; + (egcd, lcm) + } + + /// Calculates the Lowest Common Multiple (LCM) of the number and + /// `other`. + #[inline] + fn lcm(&self, other: &Self) -> Self { + self.gcd_lcm(other).1 + } + + /// Calculates the Greatest Common Divisor (GCD) and + /// Lowest Common Multiple (LCM) of the number and `other`. + #[inline] + fn gcd_lcm(&self, other: &Self) -> (Self, Self) { + if self.is_zero() && other.is_zero() { + return (Self::zero(), Self::zero()); + } + let gcd = self.gcd(other); + // should not have to recalculate abs + let lcm = (*self * (*other / gcd)).abs(); + (gcd, lcm) + } + + /// Deprecated, use `is_multiple_of` instead. + #[inline] + fn divides(&self, other: &Self) -> bool { + self.is_multiple_of(other) + } + + /// Returns `true` if the number is a multiple of `other`. + #[inline] + fn is_multiple_of(&self, other: &Self) -> bool { + if other.is_zero() { + return self.is_zero(); + } + *self % *other == 0 + } + + /// Returns `true` if the number is divisible by `2` + #[inline] + fn is_even(&self) -> bool { + (*self) & 1 == 0 + } + + /// Returns `true` if the number is not divisible by `2` + #[inline] + fn is_odd(&self) -> bool { + !self.is_even() + } + + /// Simultaneous truncated integer division and modulus. + #[inline] + fn div_rem(&self, other: &Self) -> (Self, Self) { + (*self / *other, *self % *other) + } + + /// Rounds up to nearest multiple of argument. + #[inline] + fn next_multiple_of(&self, other: &Self) -> Self { + // Avoid the overflow of `MIN % -1` + if *other == -1 { + return *self; + } + + let m = Integer::mod_floor(self, other); + *self + if m == 0 { 0 } else { other - m } + } + + /// Rounds down to nearest multiple of argument. + #[inline] + fn prev_multiple_of(&self, other: &Self) -> Self { + // Avoid the overflow of `MIN % -1` + if *other == -1 { + return *self; + } + + *self - Integer::mod_floor(self, other) + } + } + + #[cfg(test)] + mod $test_mod { + use core::mem; + use Integer; + + /// Checks that the division rule holds for: + /// + /// - `n`: numerator (dividend) + /// - `d`: denominator (divisor) + /// - `qr`: quotient and remainder + #[cfg(test)] + fn test_division_rule((n, d): ($T, $T), (q, r): ($T, $T)) { + assert_eq!(d * q + r, n); + } + + #[test] + fn test_div_rem() { + fn test_nd_dr(nd: ($T, $T), qr: ($T, $T)) { + let (n, d) = nd; + let separate_div_rem = (n / d, n % d); + let combined_div_rem = n.div_rem(&d); + + assert_eq!(separate_div_rem, qr); + assert_eq!(combined_div_rem, qr); + + test_division_rule(nd, separate_div_rem); + test_division_rule(nd, combined_div_rem); + } + + test_nd_dr((8, 3), (2, 2)); + test_nd_dr((8, -3), (-2, 2)); + test_nd_dr((-8, 3), (-2, -2)); + test_nd_dr((-8, -3), (2, -2)); + + test_nd_dr((1, 2), (0, 1)); + test_nd_dr((1, -2), (0, 1)); + test_nd_dr((-1, 2), (0, -1)); + test_nd_dr((-1, -2), (0, -1)); + } + + #[test] + fn test_div_mod_floor() { + fn test_nd_dm(nd: ($T, $T), dm: ($T, $T)) { + let (n, d) = nd; + let separate_div_mod_floor = + (Integer::div_floor(&n, &d), Integer::mod_floor(&n, &d)); + let combined_div_mod_floor = Integer::div_mod_floor(&n, &d); + + assert_eq!(separate_div_mod_floor, dm); + assert_eq!(combined_div_mod_floor, dm); + + test_division_rule(nd, separate_div_mod_floor); + test_division_rule(nd, combined_div_mod_floor); + } + + test_nd_dm((8, 3), (2, 2)); + test_nd_dm((8, -3), (-3, -1)); + test_nd_dm((-8, 3), (-3, 1)); + test_nd_dm((-8, -3), (2, -2)); + + test_nd_dm((1, 2), (0, 1)); + test_nd_dm((1, -2), (-1, -1)); + test_nd_dm((-1, 2), (-1, 1)); + test_nd_dm((-1, -2), (0, -1)); + } + + #[test] + fn test_gcd() { + assert_eq!((10 as $T).gcd(&2), 2 as $T); + assert_eq!((10 as $T).gcd(&3), 1 as $T); + assert_eq!((0 as $T).gcd(&3), 3 as $T); + assert_eq!((3 as $T).gcd(&3), 3 as $T); + assert_eq!((56 as $T).gcd(&42), 14 as $T); + assert_eq!((3 as $T).gcd(&-3), 3 as $T); + assert_eq!((-6 as $T).gcd(&3), 3 as $T); + assert_eq!((-4 as $T).gcd(&-2), 2 as $T); + } + + #[test] + fn test_gcd_cmp_with_euclidean() { + fn euclidean_gcd(mut m: $T, mut n: $T) -> $T { + while m != 0 { + mem::swap(&mut m, &mut n); + m %= n; + } + + n.abs() + } + + // gcd(-128, b) = 128 is not representable as positive value + // for i8 + for i in -127..127 { + for j in -127..127 { + assert_eq!(euclidean_gcd(i, j), i.gcd(&j)); + } + } + + // last value + // FIXME: Use inclusive ranges for above loop when implemented + let i = 127; + for j in -127..127 { + assert_eq!(euclidean_gcd(i, j), i.gcd(&j)); + } + assert_eq!(127.gcd(&127), 127); + } + + #[test] + fn test_gcd_min_val() { + let min = <$T>::min_value(); + let max = <$T>::max_value(); + let max_pow2 = max / 2 + 1; + assert_eq!(min.gcd(&max), 1 as $T); + assert_eq!(max.gcd(&min), 1 as $T); + assert_eq!(min.gcd(&max_pow2), max_pow2); + assert_eq!(max_pow2.gcd(&min), max_pow2); + assert_eq!(min.gcd(&42), 2 as $T); + assert_eq!((42 as $T).gcd(&min), 2 as $T); + } + + #[test] + #[should_panic] + fn test_gcd_min_val_min_val() { + let min = <$T>::min_value(); + assert!(min.gcd(&min) >= 0); + } + + #[test] + #[should_panic] + fn test_gcd_min_val_0() { + let min = <$T>::min_value(); + assert!(min.gcd(&0) >= 0); + } + + #[test] + #[should_panic] + fn test_gcd_0_min_val() { + let min = <$T>::min_value(); + assert!((0 as $T).gcd(&min) >= 0); + } + + #[test] + fn test_lcm() { + assert_eq!((1 as $T).lcm(&0), 0 as $T); + assert_eq!((0 as $T).lcm(&1), 0 as $T); + assert_eq!((1 as $T).lcm(&1), 1 as $T); + assert_eq!((-1 as $T).lcm(&1), 1 as $T); + assert_eq!((1 as $T).lcm(&-1), 1 as $T); + assert_eq!((-1 as $T).lcm(&-1), 1 as $T); + assert_eq!((8 as $T).lcm(&9), 72 as $T); + assert_eq!((11 as $T).lcm(&5), 55 as $T); + } + + #[test] + fn test_gcd_lcm() { + use core::iter::once; + for i in once(0) + .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a)))) + .chain(once(-128)) + { + for j in once(0) + .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a)))) + .chain(once(-128)) + { + assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j))); + } + } + } + + #[test] + fn test_extended_gcd_lcm() { + use core::fmt::Debug; + use traits::NumAssign; + use ExtendedGcd; + + fn check<A: Copy + Debug + Integer + NumAssign>(a: A, b: A) { + let ExtendedGcd { gcd, x, y, .. } = a.extended_gcd(&b); + assert_eq!(gcd, x * a + y * b); + } + + use core::iter::once; + for i in once(0) + .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a)))) + .chain(once(-128)) + { + for j in once(0) + .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a)))) + .chain(once(-128)) + { + check(i, j); + let (ExtendedGcd { gcd, .. }, lcm) = i.extended_gcd_lcm(&j); + assert_eq!((gcd, lcm), (i.gcd(&j), i.lcm(&j))); + } + } + } + + #[test] + fn test_even() { + assert_eq!((-4 as $T).is_even(), true); + assert_eq!((-3 as $T).is_even(), false); + assert_eq!((-2 as $T).is_even(), true); + assert_eq!((-1 as $T).is_even(), false); + assert_eq!((0 as $T).is_even(), true); + assert_eq!((1 as $T).is_even(), false); + assert_eq!((2 as $T).is_even(), true); + assert_eq!((3 as $T).is_even(), false); + assert_eq!((4 as $T).is_even(), true); + } + + #[test] + fn test_odd() { + assert_eq!((-4 as $T).is_odd(), false); + assert_eq!((-3 as $T).is_odd(), true); + assert_eq!((-2 as $T).is_odd(), false); + assert_eq!((-1 as $T).is_odd(), true); + assert_eq!((0 as $T).is_odd(), false); + assert_eq!((1 as $T).is_odd(), true); + assert_eq!((2 as $T).is_odd(), false); + assert_eq!((3 as $T).is_odd(), true); + assert_eq!((4 as $T).is_odd(), false); + } + + #[test] + fn test_multiple_of_one_limits() { + for x in &[<$T>::min_value(), <$T>::max_value()] { + for one in &[1, -1] { + assert_eq!(Integer::next_multiple_of(x, one), *x); + assert_eq!(Integer::prev_multiple_of(x, one), *x); + } + } + } + } + }; +} + +impl_integer_for_isize!(i8, test_integer_i8); +impl_integer_for_isize!(i16, test_integer_i16); +impl_integer_for_isize!(i32, test_integer_i32); +impl_integer_for_isize!(i64, test_integer_i64); +impl_integer_for_isize!(isize, test_integer_isize); +#[cfg(has_i128)] +impl_integer_for_isize!(i128, test_integer_i128); + +macro_rules! impl_integer_for_usize { + ($T:ty, $test_mod:ident) => { + impl Integer for $T { + /// Unsigned integer division. Returns the same result as `div` (`/`). + #[inline] + fn div_floor(&self, other: &Self) -> Self { + *self / *other + } + + /// Unsigned integer modulo operation. Returns the same result as `rem` (`%`). + #[inline] + fn mod_floor(&self, other: &Self) -> Self { + *self % *other + } + + #[inline] + fn div_ceil(&self, other: &Self) -> Self { + *self / *other + (0 != *self % *other) as Self + } + + /// Calculates the Greatest Common Divisor (GCD) of the number and `other` + #[inline] + fn gcd(&self, other: &Self) -> Self { + // Use Stein's algorithm + let mut m = *self; + let mut n = *other; + if m == 0 || n == 0 { + return m | n; + } + + // find common factors of 2 + let shift = (m | n).trailing_zeros(); + + // divide n and m by 2 until odd + m >>= m.trailing_zeros(); + n >>= n.trailing_zeros(); + + while m != n { + if m > n { + m -= n; + m >>= m.trailing_zeros(); + } else { + n -= m; + n >>= n.trailing_zeros(); + } + } + m << shift + } + + #[inline] + fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) { + let egcd = self.extended_gcd(other); + // should not have to recalculate abs + let lcm = if egcd.gcd.is_zero() { + Self::zero() + } else { + *self * (*other / egcd.gcd) + }; + (egcd, lcm) + } + + /// Calculates the Lowest Common Multiple (LCM) of the number and `other`. + #[inline] + fn lcm(&self, other: &Self) -> Self { + self.gcd_lcm(other).1 + } + + /// Calculates the Greatest Common Divisor (GCD) and + /// Lowest Common Multiple (LCM) of the number and `other`. + #[inline] + fn gcd_lcm(&self, other: &Self) -> (Self, Self) { + if self.is_zero() && other.is_zero() { + return (Self::zero(), Self::zero()); + } + let gcd = self.gcd(other); + let lcm = *self * (*other / gcd); + (gcd, lcm) + } + + /// Deprecated, use `is_multiple_of` instead. + #[inline] + fn divides(&self, other: &Self) -> bool { + self.is_multiple_of(other) + } + + /// Returns `true` if the number is a multiple of `other`. + #[inline] + fn is_multiple_of(&self, other: &Self) -> bool { + if other.is_zero() { + return self.is_zero(); + } + *self % *other == 0 + } + + /// Returns `true` if the number is divisible by `2`. + #[inline] + fn is_even(&self) -> bool { + *self % 2 == 0 + } + + /// Returns `true` if the number is not divisible by `2`. + #[inline] + fn is_odd(&self) -> bool { + !self.is_even() + } + + /// Simultaneous truncated integer division and modulus. + #[inline] + fn div_rem(&self, other: &Self) -> (Self, Self) { + (*self / *other, *self % *other) + } + } + + #[cfg(test)] + mod $test_mod { + use core::mem; + use Integer; + + #[test] + fn test_div_mod_floor() { + assert_eq!(<$T as Integer>::div_floor(&10, &3), 3 as $T); + assert_eq!(<$T as Integer>::mod_floor(&10, &3), 1 as $T); + assert_eq!(<$T as Integer>::div_mod_floor(&10, &3), (3 as $T, 1 as $T)); + assert_eq!(<$T as Integer>::div_floor(&5, &5), 1 as $T); + assert_eq!(<$T as Integer>::mod_floor(&5, &5), 0 as $T); + assert_eq!(<$T as Integer>::div_mod_floor(&5, &5), (1 as $T, 0 as $T)); + assert_eq!(<$T as Integer>::div_floor(&3, &7), 0 as $T); + assert_eq!(<$T as Integer>::div_floor(&3, &7), 0 as $T); + assert_eq!(<$T as Integer>::mod_floor(&3, &7), 3 as $T); + assert_eq!(<$T as Integer>::div_mod_floor(&3, &7), (0 as $T, 3 as $T)); + } + + #[test] + fn test_gcd() { + assert_eq!((10 as $T).gcd(&2), 2 as $T); + assert_eq!((10 as $T).gcd(&3), 1 as $T); + assert_eq!((0 as $T).gcd(&3), 3 as $T); + assert_eq!((3 as $T).gcd(&3), 3 as $T); + assert_eq!((56 as $T).gcd(&42), 14 as $T); + } + + #[test] + fn test_gcd_cmp_with_euclidean() { + fn euclidean_gcd(mut m: $T, mut n: $T) -> $T { + while m != 0 { + mem::swap(&mut m, &mut n); + m %= n; + } + n + } + + for i in 0..255 { + for j in 0..255 { + assert_eq!(euclidean_gcd(i, j), i.gcd(&j)); + } + } + + // last value + // FIXME: Use inclusive ranges for above loop when implemented + let i = 255; + for j in 0..255 { + assert_eq!(euclidean_gcd(i, j), i.gcd(&j)); + } + assert_eq!(255.gcd(&255), 255); + } + + #[test] + fn test_lcm() { + assert_eq!((1 as $T).lcm(&0), 0 as $T); + assert_eq!((0 as $T).lcm(&1), 0 as $T); + assert_eq!((1 as $T).lcm(&1), 1 as $T); + assert_eq!((8 as $T).lcm(&9), 72 as $T); + assert_eq!((11 as $T).lcm(&5), 55 as $T); + assert_eq!((15 as $T).lcm(&17), 255 as $T); + } + + #[test] + fn test_gcd_lcm() { + for i in (0..).take(256) { + for j in (0..).take(256) { + assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j))); + } + } + } + + #[test] + fn test_is_multiple_of() { + assert!((0 as $T).is_multiple_of(&(0 as $T))); + assert!((6 as $T).is_multiple_of(&(6 as $T))); + assert!((6 as $T).is_multiple_of(&(3 as $T))); + assert!((6 as $T).is_multiple_of(&(1 as $T))); + + assert!(!(42 as $T).is_multiple_of(&(5 as $T))); + assert!(!(5 as $T).is_multiple_of(&(3 as $T))); + assert!(!(42 as $T).is_multiple_of(&(0 as $T))); + } + + #[test] + fn test_even() { + assert_eq!((0 as $T).is_even(), true); + assert_eq!((1 as $T).is_even(), false); + assert_eq!((2 as $T).is_even(), true); + assert_eq!((3 as $T).is_even(), false); + assert_eq!((4 as $T).is_even(), true); + } + + #[test] + fn test_odd() { + assert_eq!((0 as $T).is_odd(), false); + assert_eq!((1 as $T).is_odd(), true); + assert_eq!((2 as $T).is_odd(), false); + assert_eq!((3 as $T).is_odd(), true); + assert_eq!((4 as $T).is_odd(), false); + } + } + }; +} + +impl_integer_for_usize!(u8, test_integer_u8); +impl_integer_for_usize!(u16, test_integer_u16); +impl_integer_for_usize!(u32, test_integer_u32); +impl_integer_for_usize!(u64, test_integer_u64); +impl_integer_for_usize!(usize, test_integer_usize); +#[cfg(has_i128)] +impl_integer_for_usize!(u128, test_integer_u128); + +/// An iterator over binomial coefficients. +pub struct IterBinomial<T> { + a: T, + n: T, + k: T, +} + +impl<T> IterBinomial<T> +where + T: Integer, +{ + /// For a given n, iterate over all binomial coefficients binomial(n, k), for k=0...n. + /// + /// Note that this might overflow, depending on `T`. For the primitive + /// integer types, the following n are the largest ones for which there will + /// be no overflow: + /// + /// type | n + /// -----|--- + /// u8 | 10 + /// i8 | 9 + /// u16 | 18 + /// i16 | 17 + /// u32 | 34 + /// i32 | 33 + /// u64 | 67 + /// i64 | 66 + /// + /// For larger n, `T` should be a bigint type. + pub fn new(n: T) -> IterBinomial<T> { + IterBinomial { + k: T::zero(), + a: T::one(), + n: n, + } + } +} + +impl<T> Iterator for IterBinomial<T> +where + T: Integer + Clone, +{ + type Item = T; + + fn next(&mut self) -> Option<T> { + if self.k > self.n { + return None; + } + self.a = if !self.k.is_zero() { + multiply_and_divide( + self.a.clone(), + self.n.clone() - self.k.clone() + T::one(), + self.k.clone(), + ) + } else { + T::one() + }; + self.k = self.k.clone() + T::one(); + Some(self.a.clone()) + } +} + +/// Calculate r * a / b, avoiding overflows and fractions. +/// +/// Assumes that b divides r * a evenly. +fn multiply_and_divide<T: Integer + Clone>(r: T, a: T, b: T) -> T { + // See http://blog.plover.com/math/choose-2.html for the idea. + let g = gcd(r.clone(), b.clone()); + r / g.clone() * (a / (b / g)) +} + +/// Calculate the binomial coefficient. +/// +/// Note that this might overflow, depending on `T`. For the primitive integer +/// types, the following n are the largest ones possible such that there will +/// be no overflow for any k: +/// +/// type | n +/// -----|--- +/// u8 | 10 +/// i8 | 9 +/// u16 | 18 +/// i16 | 17 +/// u32 | 34 +/// i32 | 33 +/// u64 | 67 +/// i64 | 66 +/// +/// For larger n, consider using a bigint type for `T`. +pub fn binomial<T: Integer + Clone>(mut n: T, k: T) -> T { + // See http://blog.plover.com/math/choose.html for the idea. + if k > n { + return T::zero(); + } + if k > n.clone() - k.clone() { + return binomial(n.clone(), n - k); + } + let mut r = T::one(); + let mut d = T::one(); + loop { + if d > k { + break; + } + r = multiply_and_divide(r, n.clone(), d.clone()); + n = n - T::one(); + d = d + T::one(); + } + r +} + +/// Calculate the multinomial coefficient. +pub fn multinomial<T: Integer + Clone>(k: &[T]) -> T +where + for<'a> T: Add<&'a T, Output = T>, +{ + let mut r = T::one(); + let mut p = T::zero(); + for i in k { + p = p + i; + r = r * binomial(p.clone(), i.clone()); + } + r +} + +#[test] +fn test_lcm_overflow() { + macro_rules! check { + ($t:ty, $x:expr, $y:expr, $r:expr) => {{ + let x: $t = $x; + let y: $t = $y; + let o = x.checked_mul(y); + assert!( + o.is_none(), + "sanity checking that {} input {} * {} overflows", + stringify!($t), + x, + y + ); + assert_eq!(x.lcm(&y), $r); + assert_eq!(y.lcm(&x), $r); + }}; + } + + // Original bug (Issue #166) + check!(i64, 46656000000000000, 600, 46656000000000000); + + check!(i8, 0x40, 0x04, 0x40); + check!(u8, 0x80, 0x02, 0x80); + check!(i16, 0x40_00, 0x04, 0x40_00); + check!(u16, 0x80_00, 0x02, 0x80_00); + check!(i32, 0x4000_0000, 0x04, 0x4000_0000); + check!(u32, 0x8000_0000, 0x02, 0x8000_0000); + check!(i64, 0x4000_0000_0000_0000, 0x04, 0x4000_0000_0000_0000); + check!(u64, 0x8000_0000_0000_0000, 0x02, 0x8000_0000_0000_0000); +} + +#[test] +fn test_iter_binomial() { + macro_rules! check_simple { + ($t:ty) => {{ + let n: $t = 3; + let expected = [1, 3, 3, 1]; + for (b, &e) in IterBinomial::new(n).zip(&expected) { + assert_eq!(b, e); + } + }}; + } + + check_simple!(u8); + check_simple!(i8); + check_simple!(u16); + check_simple!(i16); + check_simple!(u32); + check_simple!(i32); + check_simple!(u64); + check_simple!(i64); + + macro_rules! check_binomial { + ($t:ty, $n:expr) => {{ + let n: $t = $n; + let mut k: $t = 0; + for b in IterBinomial::new(n) { + assert_eq!(b, binomial(n, k)); + k += 1; + } + }}; + } + + // Check the largest n for which there is no overflow. + check_binomial!(u8, 10); + check_binomial!(i8, 9); + check_binomial!(u16, 18); + check_binomial!(i16, 17); + check_binomial!(u32, 34); + check_binomial!(i32, 33); + check_binomial!(u64, 67); + check_binomial!(i64, 66); +} + +#[test] +fn test_binomial() { + macro_rules! check { + ($t:ty, $x:expr, $y:expr, $r:expr) => {{ + let x: $t = $x; + let y: $t = $y; + let expected: $t = $r; + assert_eq!(binomial(x, y), expected); + if y <= x { + assert_eq!(binomial(x, x - y), expected); + } + }}; + } + check!(u8, 9, 4, 126); + check!(u8, 0, 0, 1); + check!(u8, 2, 3, 0); + + check!(i8, 9, 4, 126); + check!(i8, 0, 0, 1); + check!(i8, 2, 3, 0); + + check!(u16, 100, 2, 4950); + check!(u16, 14, 4, 1001); + check!(u16, 0, 0, 1); + check!(u16, 2, 3, 0); + + check!(i16, 100, 2, 4950); + check!(i16, 14, 4, 1001); + check!(i16, 0, 0, 1); + check!(i16, 2, 3, 0); + + check!(u32, 100, 2, 4950); + check!(u32, 35, 11, 417225900); + check!(u32, 14, 4, 1001); + check!(u32, 0, 0, 1); + check!(u32, 2, 3, 0); + + check!(i32, 100, 2, 4950); + check!(i32, 35, 11, 417225900); + check!(i32, 14, 4, 1001); + check!(i32, 0, 0, 1); + check!(i32, 2, 3, 0); + + check!(u64, 100, 2, 4950); + check!(u64, 35, 11, 417225900); + check!(u64, 14, 4, 1001); + check!(u64, 0, 0, 1); + check!(u64, 2, 3, 0); + + check!(i64, 100, 2, 4950); + check!(i64, 35, 11, 417225900); + check!(i64, 14, 4, 1001); + check!(i64, 0, 0, 1); + check!(i64, 2, 3, 0); +} + +#[test] +fn test_multinomial() { + macro_rules! check_binomial { + ($t:ty, $k:expr) => {{ + let n: $t = $k.iter().fold(0, |acc, &x| acc + x); + let k: &[$t] = $k; + assert_eq!(k.len(), 2); + assert_eq!(multinomial(k), binomial(n, k[0])); + }}; + } + + check_binomial!(u8, &[4, 5]); + + check_binomial!(i8, &[4, 5]); + + check_binomial!(u16, &[2, 98]); + check_binomial!(u16, &[4, 10]); + + check_binomial!(i16, &[2, 98]); + check_binomial!(i16, &[4, 10]); + + check_binomial!(u32, &[2, 98]); + check_binomial!(u32, &[11, 24]); + check_binomial!(u32, &[4, 10]); + + check_binomial!(i32, &[2, 98]); + check_binomial!(i32, &[11, 24]); + check_binomial!(i32, &[4, 10]); + + check_binomial!(u64, &[2, 98]); + check_binomial!(u64, &[11, 24]); + check_binomial!(u64, &[4, 10]); + + check_binomial!(i64, &[2, 98]); + check_binomial!(i64, &[11, 24]); + check_binomial!(i64, &[4, 10]); + + macro_rules! check_multinomial { + ($t:ty, $k:expr, $r:expr) => {{ + let k: &[$t] = $k; + let expected: $t = $r; + assert_eq!(multinomial(k), expected); + }}; + } + + check_multinomial!(u8, &[2, 1, 2], 30); + check_multinomial!(u8, &[2, 3, 0], 10); + + check_multinomial!(i8, &[2, 1, 2], 30); + check_multinomial!(i8, &[2, 3, 0], 10); + + check_multinomial!(u16, &[2, 1, 2], 30); + check_multinomial!(u16, &[2, 3, 0], 10); + + check_multinomial!(i16, &[2, 1, 2], 30); + check_multinomial!(i16, &[2, 3, 0], 10); + + check_multinomial!(u32, &[2, 1, 2], 30); + check_multinomial!(u32, &[2, 3, 0], 10); + + check_multinomial!(i32, &[2, 1, 2], 30); + check_multinomial!(i32, &[2, 3, 0], 10); + + check_multinomial!(u64, &[2, 1, 2], 30); + check_multinomial!(u64, &[2, 3, 0], 10); + + check_multinomial!(i64, &[2, 1, 2], 30); + check_multinomial!(i64, &[2, 3, 0], 10); + + check_multinomial!(u64, &[], 1); + check_multinomial!(u64, &[0], 1); + check_multinomial!(u64, &[12345], 1); +} diff --git a/third_party/rust/num-integer/src/roots.rs b/third_party/rust/num-integer/src/roots.rs new file mode 100644 index 0000000000..a9eec1a93c --- /dev/null +++ b/third_party/rust/num-integer/src/roots.rs @@ -0,0 +1,391 @@ +use core; +use core::mem; +use traits::checked_pow; +use traits::PrimInt; +use Integer; + +/// Provides methods to compute an integer's square root, cube root, +/// and arbitrary `n`th root. +pub trait Roots: Integer { + /// Returns the truncated principal `n`th root of an integer + /// -- `if x >= 0 { ⌊ⁿ√x⌋ } else { ⌈ⁿ√x⌉ }` + /// + /// This is solving for `r` in `rⁿ = x`, rounding toward zero. + /// If `x` is positive, the result will satisfy `rⁿ ≤ x < (r+1)ⁿ`. + /// If `x` is negative and `n` is odd, then `(r-1)ⁿ < x ≤ rⁿ`. + /// + /// # Panics + /// + /// Panics if `n` is zero: + /// + /// ```should_panic + /// # use num_integer::Roots; + /// println!("can't compute ⁰√x : {}", 123.nth_root(0)); + /// ``` + /// + /// or if `n` is even and `self` is negative: + /// + /// ```should_panic + /// # use num_integer::Roots; + /// println!("no imaginary numbers... {}", (-1).nth_root(10)); + /// ``` + /// + /// # Examples + /// + /// ``` + /// use num_integer::Roots; + /// + /// let x: i32 = 12345; + /// assert_eq!(x.nth_root(1), x); + /// assert_eq!(x.nth_root(2), x.sqrt()); + /// assert_eq!(x.nth_root(3), x.cbrt()); + /// assert_eq!(x.nth_root(4), 10); + /// assert_eq!(x.nth_root(13), 2); + /// assert_eq!(x.nth_root(14), 1); + /// assert_eq!(x.nth_root(std::u32::MAX), 1); + /// + /// assert_eq!(std::i32::MAX.nth_root(30), 2); + /// assert_eq!(std::i32::MAX.nth_root(31), 1); + /// assert_eq!(std::i32::MIN.nth_root(31), -2); + /// assert_eq!((std::i32::MIN + 1).nth_root(31), -1); + /// + /// assert_eq!(std::u32::MAX.nth_root(31), 2); + /// assert_eq!(std::u32::MAX.nth_root(32), 1); + /// ``` + fn nth_root(&self, n: u32) -> Self; + + /// Returns the truncated principal square root of an integer -- `⌊√x⌋` + /// + /// This is solving for `r` in `r² = x`, rounding toward zero. + /// The result will satisfy `r² ≤ x < (r+1)²`. + /// + /// # Panics + /// + /// Panics if `self` is less than zero: + /// + /// ```should_panic + /// # use num_integer::Roots; + /// println!("no imaginary numbers... {}", (-1).sqrt()); + /// ``` + /// + /// # Examples + /// + /// ``` + /// use num_integer::Roots; + /// + /// let x: i32 = 12345; + /// assert_eq!((x * x).sqrt(), x); + /// assert_eq!((x * x + 1).sqrt(), x); + /// assert_eq!((x * x - 1).sqrt(), x - 1); + /// ``` + #[inline] + fn sqrt(&self) -> Self { + self.nth_root(2) + } + + /// Returns the truncated principal cube root of an integer -- + /// `if x >= 0 { ⌊∛x⌋ } else { ⌈∛x⌉ }` + /// + /// This is solving for `r` in `r³ = x`, rounding toward zero. + /// If `x` is positive, the result will satisfy `r³ ≤ x < (r+1)³`. + /// If `x` is negative, then `(r-1)³ < x ≤ r³`. + /// + /// # Examples + /// + /// ``` + /// use num_integer::Roots; + /// + /// let x: i32 = 1234; + /// assert_eq!((x * x * x).cbrt(), x); + /// assert_eq!((x * x * x + 1).cbrt(), x); + /// assert_eq!((x * x * x - 1).cbrt(), x - 1); + /// + /// assert_eq!((-(x * x * x)).cbrt(), -x); + /// assert_eq!((-(x * x * x + 1)).cbrt(), -x); + /// assert_eq!((-(x * x * x - 1)).cbrt(), -(x - 1)); + /// ``` + #[inline] + fn cbrt(&self) -> Self { + self.nth_root(3) + } +} + +/// Returns the truncated principal square root of an integer -- +/// see [Roots::sqrt](trait.Roots.html#method.sqrt). +#[inline] +pub fn sqrt<T: Roots>(x: T) -> T { + x.sqrt() +} + +/// Returns the truncated principal cube root of an integer -- +/// see [Roots::cbrt](trait.Roots.html#method.cbrt). +#[inline] +pub fn cbrt<T: Roots>(x: T) -> T { + x.cbrt() +} + +/// Returns the truncated principal `n`th root of an integer -- +/// see [Roots::nth_root](trait.Roots.html#tymethod.nth_root). +#[inline] +pub fn nth_root<T: Roots>(x: T, n: u32) -> T { + x.nth_root(n) +} + +macro_rules! signed_roots { + ($T:ty, $U:ty) => { + impl Roots for $T { + #[inline] + fn nth_root(&self, n: u32) -> Self { + if *self >= 0 { + (*self as $U).nth_root(n) as Self + } else { + assert!(n.is_odd(), "even roots of a negative are imaginary"); + -((self.wrapping_neg() as $U).nth_root(n) as Self) + } + } + + #[inline] + fn sqrt(&self) -> Self { + assert!(*self >= 0, "the square root of a negative is imaginary"); + (*self as $U).sqrt() as Self + } + + #[inline] + fn cbrt(&self) -> Self { + if *self >= 0 { + (*self as $U).cbrt() as Self + } else { + -((self.wrapping_neg() as $U).cbrt() as Self) + } + } + } + }; +} + +signed_roots!(i8, u8); +signed_roots!(i16, u16); +signed_roots!(i32, u32); +signed_roots!(i64, u64); +#[cfg(has_i128)] +signed_roots!(i128, u128); +signed_roots!(isize, usize); + +#[inline] +fn fixpoint<T, F>(mut x: T, f: F) -> T +where + T: Integer + Copy, + F: Fn(T) -> T, +{ + let mut xn = f(x); + while x < xn { + x = xn; + xn = f(x); + } + while x > xn { + x = xn; + xn = f(x); + } + x +} + +#[inline] +fn bits<T>() -> u32 { + 8 * mem::size_of::<T>() as u32 +} + +#[inline] +fn log2<T: PrimInt>(x: T) -> u32 { + debug_assert!(x > T::zero()); + bits::<T>() - 1 - x.leading_zeros() +} + +macro_rules! unsigned_roots { + ($T:ident) => { + impl Roots for $T { + #[inline] + fn nth_root(&self, n: u32) -> Self { + fn go(a: $T, n: u32) -> $T { + // Specialize small roots + match n { + 0 => panic!("can't find a root of degree 0!"), + 1 => return a, + 2 => return a.sqrt(), + 3 => return a.cbrt(), + _ => (), + } + + // The root of values less than 2ⁿ can only be 0 or 1. + if bits::<$T>() <= n || a < (1 << n) { + return (a > 0) as $T; + } + + if bits::<$T>() > 64 { + // 128-bit division is slow, so do a bitwise `nth_root` until it's small enough. + return if a <= core::u64::MAX as $T { + (a as u64).nth_root(n) as $T + } else { + let lo = (a >> n).nth_root(n) << 1; + let hi = lo + 1; + // 128-bit `checked_mul` also involves division, but we can't always + // compute `hiⁿ` without risking overflow. Try to avoid it though... + if hi.next_power_of_two().trailing_zeros() * n >= bits::<$T>() { + match checked_pow(hi, n as usize) { + Some(x) if x <= a => hi, + _ => lo, + } + } else { + if hi.pow(n) <= a { + hi + } else { + lo + } + } + }; + } + + #[cfg(feature = "std")] + #[inline] + fn guess(x: $T, n: u32) -> $T { + // for smaller inputs, `f64` doesn't justify its cost. + if bits::<$T>() <= 32 || x <= core::u32::MAX as $T { + 1 << ((log2(x) + n - 1) / n) + } else { + ((x as f64).ln() / f64::from(n)).exp() as $T + } + } + + #[cfg(not(feature = "std"))] + #[inline] + fn guess(x: $T, n: u32) -> $T { + 1 << ((log2(x) + n - 1) / n) + } + + // https://en.wikipedia.org/wiki/Nth_root_algorithm + let n1 = n - 1; + let next = |x: $T| { + let y = match checked_pow(x, n1 as usize) { + Some(ax) => a / ax, + None => 0, + }; + (y + x * n1 as $T) / n as $T + }; + fixpoint(guess(a, n), next) + } + go(*self, n) + } + + #[inline] + fn sqrt(&self) -> Self { + fn go(a: $T) -> $T { + if bits::<$T>() > 64 { + // 128-bit division is slow, so do a bitwise `sqrt` until it's small enough. + return if a <= core::u64::MAX as $T { + (a as u64).sqrt() as $T + } else { + let lo = (a >> 2u32).sqrt() << 1; + let hi = lo + 1; + if hi * hi <= a { + hi + } else { + lo + } + }; + } + + if a < 4 { + return (a > 0) as $T; + } + + #[cfg(feature = "std")] + #[inline] + fn guess(x: $T) -> $T { + (x as f64).sqrt() as $T + } + + #[cfg(not(feature = "std"))] + #[inline] + fn guess(x: $T) -> $T { + 1 << ((log2(x) + 1) / 2) + } + + // https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method + let next = |x: $T| (a / x + x) >> 1; + fixpoint(guess(a), next) + } + go(*self) + } + + #[inline] + fn cbrt(&self) -> Self { + fn go(a: $T) -> $T { + if bits::<$T>() > 64 { + // 128-bit division is slow, so do a bitwise `cbrt` until it's small enough. + return if a <= core::u64::MAX as $T { + (a as u64).cbrt() as $T + } else { + let lo = (a >> 3u32).cbrt() << 1; + let hi = lo + 1; + if hi * hi * hi <= a { + hi + } else { + lo + } + }; + } + + if bits::<$T>() <= 32 { + // Implementation based on Hacker's Delight `icbrt2` + let mut x = a; + let mut y2 = 0; + let mut y = 0; + let smax = bits::<$T>() / 3; + for s in (0..smax + 1).rev() { + let s = s * 3; + y2 *= 4; + y *= 2; + let b = 3 * (y2 + y) + 1; + if x >> s >= b { + x -= b << s; + y2 += 2 * y + 1; + y += 1; + } + } + return y; + } + + if a < 8 { + return (a > 0) as $T; + } + if a <= core::u32::MAX as $T { + return (a as u32).cbrt() as $T; + } + + #[cfg(feature = "std")] + #[inline] + fn guess(x: $T) -> $T { + (x as f64).cbrt() as $T + } + + #[cfg(not(feature = "std"))] + #[inline] + fn guess(x: $T) -> $T { + 1 << ((log2(x) + 2) / 3) + } + + // https://en.wikipedia.org/wiki/Cube_root#Numerical_methods + let next = |x: $T| (a / (x * x) + x * 2) / 3; + fixpoint(guess(a), next) + } + go(*self) + } + } + }; +} + +unsigned_roots!(u8); +unsigned_roots!(u16); +unsigned_roots!(u32); +unsigned_roots!(u64); +#[cfg(has_i128)] +unsigned_roots!(u128); +unsigned_roots!(usize); diff --git a/third_party/rust/num-integer/tests/average.rs b/third_party/rust/num-integer/tests/average.rs new file mode 100644 index 0000000000..9fd8cf18f4 --- /dev/null +++ b/third_party/rust/num-integer/tests/average.rs @@ -0,0 +1,100 @@ +extern crate num_integer; +extern crate num_traits; + +macro_rules! test_average { + ($I:ident, $U:ident) => { + mod $I { + mod ceil { + use num_integer::Average; + + #[test] + fn same_sign() { + assert_eq!((14 as $I).average_ceil(&16), 15 as $I); + assert_eq!((14 as $I).average_ceil(&17), 16 as $I); + + let max = $crate::std::$I::MAX; + assert_eq!((max - 3).average_ceil(&(max - 1)), max - 2); + assert_eq!((max - 3).average_ceil(&(max - 2)), max - 2); + } + + #[test] + fn different_sign() { + assert_eq!((14 as $I).average_ceil(&-4), 5 as $I); + assert_eq!((14 as $I).average_ceil(&-5), 5 as $I); + + let min = $crate::std::$I::MIN; + let max = $crate::std::$I::MAX; + assert_eq!(min.average_ceil(&max), 0 as $I); + } + } + + mod floor { + use num_integer::Average; + + #[test] + fn same_sign() { + assert_eq!((14 as $I).average_floor(&16), 15 as $I); + assert_eq!((14 as $I).average_floor(&17), 15 as $I); + + let max = $crate::std::$I::MAX; + assert_eq!((max - 3).average_floor(&(max - 1)), max - 2); + assert_eq!((max - 3).average_floor(&(max - 2)), max - 3); + } + + #[test] + fn different_sign() { + assert_eq!((14 as $I).average_floor(&-4), 5 as $I); + assert_eq!((14 as $I).average_floor(&-5), 4 as $I); + + let min = $crate::std::$I::MIN; + let max = $crate::std::$I::MAX; + assert_eq!(min.average_floor(&max), -1 as $I); + } + } + } + + mod $U { + mod ceil { + use num_integer::Average; + + #[test] + fn bounded() { + assert_eq!((14 as $U).average_ceil(&16), 15 as $U); + assert_eq!((14 as $U).average_ceil(&17), 16 as $U); + } + + #[test] + fn overflow() { + let max = $crate::std::$U::MAX; + assert_eq!((max - 3).average_ceil(&(max - 1)), max - 2); + assert_eq!((max - 3).average_ceil(&(max - 2)), max - 2); + } + } + + mod floor { + use num_integer::Average; + + #[test] + fn bounded() { + assert_eq!((14 as $U).average_floor(&16), 15 as $U); + assert_eq!((14 as $U).average_floor(&17), 15 as $U); + } + + #[test] + fn overflow() { + let max = $crate::std::$U::MAX; + assert_eq!((max - 3).average_floor(&(max - 1)), max - 2); + assert_eq!((max - 3).average_floor(&(max - 2)), max - 3); + } + } + } + }; +} + +test_average!(i8, u8); +test_average!(i16, u16); +test_average!(i32, u32); +test_average!(i64, u64); +#[cfg(has_i128)] +test_average!(i128, u128); +test_average!(isize, usize); diff --git a/third_party/rust/num-integer/tests/roots.rs b/third_party/rust/num-integer/tests/roots.rs new file mode 100644 index 0000000000..f85f9e0211 --- /dev/null +++ b/third_party/rust/num-integer/tests/roots.rs @@ -0,0 +1,272 @@ +extern crate num_integer; +extern crate num_traits; + +use num_integer::Roots; +use num_traits::checked_pow; +use num_traits::{AsPrimitive, PrimInt, Signed}; +use std::f64::MANTISSA_DIGITS; +use std::fmt::Debug; +use std::mem; + +trait TestInteger: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static {} + +impl<T> TestInteger for T where T: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static {} + +/// Check that each root is correct +/// +/// If `x` is positive, check `rⁿ ≤ x < (r+1)ⁿ`. +/// If `x` is negative, check `(r-1)ⁿ < x ≤ rⁿ`. +fn check<T>(v: &[T], n: u32) +where + T: TestInteger, +{ + for i in v { + let rt = i.nth_root(n); + // println!("nth_root({:?}, {}) = {:?}", i, n, rt); + if n == 2 { + assert_eq!(rt, i.sqrt()); + } else if n == 3 { + assert_eq!(rt, i.cbrt()); + } + if *i >= T::zero() { + let rt1 = rt + T::one(); + assert!(rt.pow(n) <= *i); + if let Some(x) = checked_pow(rt1, n as usize) { + assert!(*i < x); + } + } else { + let rt1 = rt - T::one(); + assert!(rt < T::zero()); + assert!(*i <= rt.pow(n)); + if let Some(x) = checked_pow(rt1, n as usize) { + assert!(x < *i); + } + }; + } +} + +/// Get the maximum value that will round down as `f64` (if any), +/// and its successor that will round up. +/// +/// Important because the `std` implementations cast to `f64` to +/// get a close approximation of the roots. +fn mantissa_max<T>() -> Option<(T, T)> +where + T: TestInteger, +{ + let bits = if T::min_value().is_zero() { + 8 * mem::size_of::<T>() + } else { + 8 * mem::size_of::<T>() - 1 + }; + if bits > MANTISSA_DIGITS as usize { + let rounding_bit = T::one() << (bits - MANTISSA_DIGITS as usize - 1); + let x = T::max_value() - rounding_bit; + + let x1 = x + T::one(); + let x2 = x1 + T::one(); + assert!(x.as_() < x1.as_()); + assert_eq!(x1.as_(), x2.as_()); + + Some((x, x1)) + } else { + None + } +} + +fn extend<T>(v: &mut Vec<T>, start: T, end: T) +where + T: TestInteger, +{ + let mut i = start; + while i < end { + v.push(i); + i = i + T::one(); + } + v.push(i); +} + +fn extend_shl<T>(v: &mut Vec<T>, start: T, end: T, mask: T) +where + T: TestInteger, +{ + let mut i = start; + while i != end { + v.push(i); + i = (i << 1) & mask; + } +} + +fn extend_shr<T>(v: &mut Vec<T>, start: T, end: T) +where + T: TestInteger, +{ + let mut i = start; + while i != end { + v.push(i); + i = i >> 1; + } +} + +fn pos<T>() -> Vec<T> +where + T: TestInteger, + i8: AsPrimitive<T>, +{ + let mut v: Vec<T> = vec![]; + if mem::size_of::<T>() == 1 { + extend(&mut v, T::zero(), T::max_value()); + } else { + extend(&mut v, T::zero(), i8::max_value().as_()); + extend( + &mut v, + T::max_value() - i8::max_value().as_(), + T::max_value(), + ); + if let Some((i, j)) = mantissa_max::<T>() { + v.push(i); + v.push(j); + } + extend_shl(&mut v, T::max_value(), T::zero(), !T::min_value()); + extend_shr(&mut v, T::max_value(), T::zero()); + } + v +} + +fn neg<T>() -> Vec<T> +where + T: TestInteger + Signed, + i8: AsPrimitive<T>, +{ + let mut v: Vec<T> = vec![]; + if mem::size_of::<T>() <= 1 { + extend(&mut v, T::min_value(), T::zero()); + } else { + extend(&mut v, i8::min_value().as_(), T::zero()); + extend( + &mut v, + T::min_value(), + T::min_value() - i8::min_value().as_(), + ); + if let Some((i, j)) = mantissa_max::<T>() { + v.push(-i); + v.push(-j); + } + extend_shl(&mut v, -T::one(), T::min_value(), !T::zero()); + extend_shr(&mut v, T::min_value(), -T::one()); + } + v +} + +macro_rules! test_roots { + ($I:ident, $U:ident) => { + mod $I { + use check; + use neg; + use num_integer::Roots; + use pos; + use std::mem; + + #[test] + #[should_panic] + fn zeroth_root() { + (123 as $I).nth_root(0); + } + + #[test] + fn sqrt() { + check(&pos::<$I>(), 2); + } + + #[test] + #[should_panic] + fn sqrt_neg() { + (-123 as $I).sqrt(); + } + + #[test] + fn cbrt() { + check(&pos::<$I>(), 3); + } + + #[test] + fn cbrt_neg() { + check(&neg::<$I>(), 3); + } + + #[test] + fn nth_root() { + let bits = 8 * mem::size_of::<$I>() as u32 - 1; + let pos = pos::<$I>(); + for n in 4..bits { + check(&pos, n); + } + } + + #[test] + fn nth_root_neg() { + let bits = 8 * mem::size_of::<$I>() as u32 - 1; + let neg = neg::<$I>(); + for n in 2..bits / 2 { + check(&neg, 2 * n + 1); + } + } + + #[test] + fn bit_size() { + let bits = 8 * mem::size_of::<$I>() as u32 - 1; + assert_eq!($I::max_value().nth_root(bits - 1), 2); + assert_eq!($I::max_value().nth_root(bits), 1); + assert_eq!($I::min_value().nth_root(bits), -2); + assert_eq!(($I::min_value() + 1).nth_root(bits), -1); + } + } + + mod $U { + use check; + use num_integer::Roots; + use pos; + use std::mem; + + #[test] + #[should_panic] + fn zeroth_root() { + (123 as $U).nth_root(0); + } + + #[test] + fn sqrt() { + check(&pos::<$U>(), 2); + } + + #[test] + fn cbrt() { + check(&pos::<$U>(), 3); + } + + #[test] + fn nth_root() { + let bits = 8 * mem::size_of::<$I>() as u32 - 1; + let pos = pos::<$I>(); + for n in 4..bits { + check(&pos, n); + } + } + + #[test] + fn bit_size() { + let bits = 8 * mem::size_of::<$U>() as u32; + assert_eq!($U::max_value().nth_root(bits - 1), 2); + assert_eq!($U::max_value().nth_root(bits), 1); + } + } + }; +} + +test_roots!(i8, u8); +test_roots!(i16, u16); +test_roots!(i32, u32); +test_roots!(i64, u64); +#[cfg(has_i128)] +test_roots!(i128, u128); +test_roots!(isize, usize); |