From dc0db358abe19481e475e10c32149b53370f1a1c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Thu, 30 May 2024 05:57:31 +0200 Subject: Merging upstream version 1.72.1+dfsg1. Signed-off-by: Daniel Baumann --- vendor/num-integer/.cargo-checksum.json | 1 - vendor/num-integer/Cargo.toml | 38 - vendor/num-integer/LICENSE-APACHE | 201 ----- vendor/num-integer/LICENSE-MIT | 25 - vendor/num-integer/README.md | 50 -- vendor/num-integer/RELEASES.md | 88 -- vendor/num-integer/benches/average.rs | 414 ---------- vendor/num-integer/benches/gcd.rs | 176 ---- vendor/num-integer/benches/roots.rs | 170 ---- vendor/num-integer/build.rs | 14 - vendor/num-integer/src/average.rs | 78 -- vendor/num-integer/src/lib.rs | 1343 ------------------------------- vendor/num-integer/src/roots.rs | 391 --------- vendor/num-integer/tests/average.rs | 100 --- vendor/num-integer/tests/roots.rs | 272 ------- 15 files changed, 3361 deletions(-) delete mode 100644 vendor/num-integer/.cargo-checksum.json delete mode 100644 vendor/num-integer/Cargo.toml delete mode 100644 vendor/num-integer/LICENSE-APACHE delete mode 100644 vendor/num-integer/LICENSE-MIT delete mode 100644 vendor/num-integer/README.md delete mode 100644 vendor/num-integer/RELEASES.md delete mode 100644 vendor/num-integer/benches/average.rs delete mode 100644 vendor/num-integer/benches/gcd.rs delete mode 100644 vendor/num-integer/benches/roots.rs delete mode 100644 vendor/num-integer/build.rs delete mode 100644 vendor/num-integer/src/average.rs delete mode 100644 vendor/num-integer/src/lib.rs delete mode 100644 vendor/num-integer/src/roots.rs delete mode 100644 vendor/num-integer/tests/average.rs delete mode 100644 vendor/num-integer/tests/roots.rs (limited to 'vendor/num-integer') diff --git a/vendor/num-integer/.cargo-checksum.json b/vendor/num-integer/.cargo-checksum.json deleted file mode 100644 index 135a6295d..000000000 --- a/vendor/num-integer/.cargo-checksum.json +++ /dev/null @@ -1 +0,0 @@ -{"files":{"Cargo.toml":"df725a7c5780368b03dbe14ac170989ddd987e2e3c8a69bfb47d34025e0e06ec","LICENSE-APACHE":"a60eea817514531668d7e00765731449fe14d059d3249e0bc93b36de45f759f2","LICENSE-MIT":"6485b8ed310d3f0340bf1ad1f47645069ce4069dcc6bb46c7d5c6faf41de1fdb","README.md":"c49fdda3780903fa8c17bb5811ea3029e271e9e79a8f6c59aa3b2468eb9b203f","RELEASES.md":"756843fa25e29f642367b6b3fc161ce34a72d01ae0fb67d5531a280245d287c8","benches/average.rs":"2a30b4ccd8ece8663d17583ae2e3623e654b5f401babef90f1634722824e6c2b","benches/gcd.rs":"9b5c0ae8ccd6c7fc8f8384fb351d10cfdd0be5fbea9365f9ea925d8915b015bf","benches/roots.rs":"79b4ab2d8fe7bbf43fe65314d2e1bc206165bc4cb34b3ceaa899f9ea7af31c09","build.rs":"b4b2d0df90ca7570a339ca4d84a72e4ef00d9dced8927350424e666790c752d7","src/average.rs":"a66cf6a49f893e60697c17b2540258e69daa15ab97d8d444c6f2e8cac2f01ae9","src/lib.rs":"bf0ce9a09f92f606ca038288cde7a29670ccca480d42ec97e88f3c56b117e33c","src/roots.rs":"2a9b908bd3666b5cffc58c1b37d329e46ed02f71ad6d5deea1e8440c10660e1a","tests/average.rs":"5f26a31be042626e9af66f7b751798621561fa090da48b1ec5ab63e388288a91","tests/roots.rs":"a0caa4142899ec8cb806a7a0d3410c39d50de97cceadc4c2ceca707be91b1ddd"},"package":"8d59457e662d541ba17869cf51cf177c0b5f0cbf476c66bdc90bf1edac4f875b"} \ No newline at end of file diff --git a/vendor/num-integer/Cargo.toml b/vendor/num-integer/Cargo.toml deleted file mode 100644 index 39d70f789..000000000 --- a/vendor/num-integer/Cargo.toml +++ /dev/null @@ -1,38 +0,0 @@ -# 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 believe there's an error in this file please file an -# issue against the rust-lang/cargo repository. If you're -# editing this file be aware that the upstream Cargo.toml -# will likely look very different (and much more reasonable) - -[package] -name = "num-integer" -version = "0.1.43" -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/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/vendor/num-integer/LICENSE-APACHE b/vendor/num-integer/LICENSE-APACHE deleted file mode 100644 index 16fe87b06..000000000 --- a/vendor/num-integer/LICENSE-APACHE +++ /dev/null @@ -1,201 +0,0 @@ - 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/vendor/num-integer/LICENSE-MIT b/vendor/num-integer/LICENSE-MIT deleted file mode 100644 index 39d4bdb5a..000000000 --- a/vendor/num-integer/LICENSE-MIT +++ /dev/null @@ -1,25 +0,0 @@ -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/vendor/num-integer/README.md b/vendor/num-integer/README.md deleted file mode 100644 index 249d5f046..000000000 --- a/vendor/num-integer/README.md +++ /dev/null @@ -1,50 +0,0 @@ -# num-integer - -[![crate](https://img.shields.io/crates/v/num-integer.svg)](https://crates.io/crates/num-integer) -[![documentation](https://docs.rs/num-integer/badge.svg)](https://docs.rs/num-integer) -[![minimum rustc 1.8](https://img.shields.io/badge/rustc-1.8+-red.svg)](https://rust-lang.github.io/rfcs/2495-min-rust-version.html) -[![build status](https://github.com/rust-num/num-integer/workflows/master/badge.svg)](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. diff --git a/vendor/num-integer/RELEASES.md b/vendor/num-integer/RELEASES.md deleted file mode 100644 index 727369661..000000000 --- a/vendor/num-integer/RELEASES.md +++ /dev/null @@ -1,88 +0,0 @@ -# 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/vendor/num-integer/benches/average.rs b/vendor/num-integer/benches/average.rs deleted file mode 100644 index 05d824c84..000000000 --- a/vendor/num-integer/benches/average.rs +++ /dev/null @@ -1,414 +0,0 @@ -//! 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 BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} - -// Simple PRNG so we don't have to worry about rand compatibility -fn lcg(x: T) -> T -where - u32: AsPrimitive, - 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) => z.div_floor(&2), - None => { - if self > other { - let diff = self - other; - other + diff.div_floor(&2) - } else { - let diff = other - self; - self + diff.div_floor(&2) - } - } - } - } - fn naive_average_ceil(&self, other: &$T) -> $T { - match self.checked_add(*other) { - Some(z) => z.div_ceil(&2), - None => { - if self > other { - let diff = self - other; - self - diff.div_floor(&2) - } else { - let diff = other - self; - other - diff.div_floor(&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(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(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(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/vendor/num-integer/benches/gcd.rs b/vendor/num-integer/benches/gcd.rs deleted file mode 100644 index 082d5ee09..000000000 --- a/vendor/num-integer/benches/gcd.rs +++ /dev/null @@ -1,176 +0,0 @@ -//! 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 { - (0..185).scan((0, 1), |&mut (ref mut a, ref mut b), _| { - let tmp = *a; - *a = *b; - *b += tmp; - Some(*b) - }) -} - -fn run_bench(b: &mut Bencher, gcd: fn(&T, &T) -> T) -where - T: AsPrimitive, - u128: AsPrimitive, -{ - let max_value: u128 = T::max_value().as_(); - let pairs: Vec<(T, T)> = fibonacci() - .collect::>() - .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/vendor/num-integer/benches/roots.rs b/vendor/num-integer/benches/roots.rs deleted file mode 100644 index 7f672786a..000000000 --- a/vendor/num-integer/benches/roots.rs +++ /dev/null @@ -1,170 +0,0 @@ -//! 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 BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {} - -fn bench(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(x: T) -> T -where - u32: AsPrimitive, - 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(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let mut x: T = 3u32.as_(); - let v: Vec = (0..1000) - .map(|_| { - x = lcg(x); - x - }) - .collect(); - bench(b, &v, f, n); -} - -fn bench_rand_pos(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let mut x: T = 3u32.as_(); - let v: Vec = (0..1000) - .map(|_| { - x = lcg(x); - while x < T::zero() { - x = lcg(x); - } - x - }) - .collect(); - bench(b, &v, f, n); -} - -fn bench_small(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let v: Vec = (0..1000).map(|i| i.as_()).collect(); - bench(b, &v, f, n); -} - -fn bench_small_pos(b: &mut Bencher, f: F, n: u32) -where - u32: AsPrimitive, - T: BenchInteger, - F: Fn(&T) -> T, -{ - let v: Vec = (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/vendor/num-integer/build.rs b/vendor/num-integer/build.rs deleted file mode 100644 index e483c15fd..000000000 --- a/vendor/num-integer/build.rs +++ /dev/null @@ -1,14 +0,0 @@ -extern crate autocfg; - -use std::env; - -fn main() { - let ac = autocfg::new(); - if ac.probe_type("i128") { - println!("cargo:rustc-cfg=has_i128"); - } else if env::var_os("CARGO_FEATURE_I128").is_some() { - panic!("i128 support was not detected!"); - } - - autocfg::rerun_path("build.rs"); -} diff --git a/vendor/num-integer/src/average.rs b/vendor/num-integer/src/average.rs deleted file mode 100644 index 29cd11e3f..000000000 --- a/vendor/num-integer/src/average.rs +++ /dev/null @@ -1,78 +0,0 @@ -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 Average for I -where - I: Integer + Shr, - 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(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(x: T, y: T) -> T { - x.average_ceil(&y) -} diff --git a/vendor/num-integer/src/lib.rs b/vendor/num-integer/src/lib.rs deleted file mode 100644 index 02819541b..000000000 --- a/vendor/num-integer/src/lib.rs +++ /dev/null @@ -1,1343 +0,0 @@ -// 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 or the MIT license -// , 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: 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 - 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, - _hidden: (), - } - } else { - ExtendedGcd { - gcd: Self::zero() - r.1, - x: Self::zero() - s.1, - y: Self::zero() - t.1, - _hidden: (), - } - } - } - - /// Greatest common divisor, least common multiple, and Bézout coefficients. - #[inline] - fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd, 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 { - pub gcd: A, - pub x: A, - pub y: A, - _hidden: (), -} - -/// Simultaneous integer division and modulus -#[inline] -pub fn div_rem(x: T, y: T) -> (T, T) { - x.div_rem(&y) -} -/// Floored integer division -#[inline] -pub fn div_floor(x: T, y: T) -> T { - x.div_floor(&y) -} -/// Floored integer modulus -#[inline] -pub fn mod_floor(x: T, y: T) -> T { - x.mod_floor(&y) -} -/// Simultaneous floored integer division and modulus -#[inline] -pub fn div_mod_floor(x: T, y: T) -> (T, T) { - x.div_mod_floor(&y) -} -/// Ceiled integer division -#[inline] -pub fn div_ceil(x: T, y: T) -> T { - x.div_ceil(&y) -} - -/// Calculates the Greatest Common Divisor (GCD) of the number and `other`. The -/// result is always positive. -#[inline(always)] -pub fn gcd(x: T, y: T) -> T { - x.gcd(&y) -} -/// Calculates the Lowest Common Multiple (LCM) of the number and `other`. -#[inline(always)] -pub fn lcm(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(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 positive. - #[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) { - 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 { - *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) - } - } - - #[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 = (n.div_floor(&d), n.mod_floor(&d)); - let combined_div_mod_floor = n.div_mod_floor(&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: 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); - } - } - }; -} - -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) { - 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 { - *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!((10 as $T).div_floor(&(3 as $T)), 3 as $T); - assert_eq!((10 as $T).mod_floor(&(3 as $T)), 1 as $T); - assert_eq!((10 as $T).div_mod_floor(&(3 as $T)), (3 as $T, 1 as $T)); - assert_eq!((5 as $T).div_floor(&(5 as $T)), 1 as $T); - assert_eq!((5 as $T).mod_floor(&(5 as $T)), 0 as $T); - assert_eq!((5 as $T).div_mod_floor(&(5 as $T)), (1 as $T, 0 as $T)); - assert_eq!((3 as $T).div_floor(&(7 as $T)), 0 as $T); - assert_eq!((3 as $T).mod_floor(&(7 as $T)), 3 as $T); - assert_eq!((3 as $T).div_mod_floor(&(7 as $T)), (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!((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))); - } - - #[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 { - a: T, - n: T, - k: T, -} - -impl IterBinomial -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 { - IterBinomial { - k: T::zero(), - a: T::one(), - n: n, - } - } -} - -impl Iterator for IterBinomial -where - T: Integer + Clone, -{ - type Item = T; - - fn next(&mut self) -> Option { - 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(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(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(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/vendor/num-integer/src/roots.rs b/vendor/num-integer/src/roots.rs deleted file mode 100644 index a9eec1a93..000000000 --- a/vendor/num-integer/src/roots.rs +++ /dev/null @@ -1,391 +0,0 @@ -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(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(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(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(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() -> u32 { - 8 * mem::size_of::() as u32 -} - -#[inline] -fn log2(x: T) -> u32 { - debug_assert!(x > T::zero()); - bits::() - 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/vendor/num-integer/tests/average.rs b/vendor/num-integer/tests/average.rs deleted file mode 100644 index 9fd8cf18f..000000000 --- a/vendor/num-integer/tests/average.rs +++ /dev/null @@ -1,100 +0,0 @@ -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/vendor/num-integer/tests/roots.rs b/vendor/num-integer/tests/roots.rs deleted file mode 100644 index f85f9e021..000000000 --- a/vendor/num-integer/tests/roots.rs +++ /dev/null @@ -1,272 +0,0 @@ -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 + 'static {} - -impl TestInteger for T where T: Roots + PrimInt + Debug + AsPrimitive + '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(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() -> Option<(T, T)> -where - T: TestInteger, -{ - let bits = if T::min_value().is_zero() { - 8 * mem::size_of::() - } else { - 8 * mem::size_of::() - 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(v: &mut Vec, 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(v: &mut Vec, 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(v: &mut Vec, start: T, end: T) -where - T: TestInteger, -{ - let mut i = start; - while i != end { - v.push(i); - i = i >> 1; - } -} - -fn pos() -> Vec -where - T: TestInteger, - i8: AsPrimitive, -{ - let mut v: Vec = vec![]; - if mem::size_of::() == 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::() { - 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() -> Vec -where - T: TestInteger + Signed, - i8: AsPrimitive, -{ - let mut v: Vec = vec![]; - if mem::size_of::() <= 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::() { - 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); -- cgit v1.2.3