aboutsummaryrefslogtreecommitdiff
path: root/vendor/num-integer
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/num-integer')
-rw-r--r--vendor/num-integer/.cargo-checksum.json1
-rw-r--r--vendor/num-integer/Cargo.toml51
-rw-r--r--vendor/num-integer/LICENSE-APACHE201
-rw-r--r--vendor/num-integer/LICENSE-MIT25
-rw-r--r--vendor/num-integer/README.md64
-rw-r--r--vendor/num-integer/RELEASES.md112
-rw-r--r--vendor/num-integer/benches/average.rs414
-rw-r--r--vendor/num-integer/benches/gcd.rs176
-rw-r--r--vendor/num-integer/benches/roots.rs170
-rw-r--r--vendor/num-integer/build.rs13
-rw-r--r--vendor/num-integer/src/average.rs78
-rw-r--r--vendor/num-integer/src/lib.rs1386
-rw-r--r--vendor/num-integer/src/roots.rs391
-rw-r--r--vendor/num-integer/tests/average.rs100
-rw-r--r--vendor/num-integer/tests/roots.rs272
15 files changed, 0 insertions, 3454 deletions
diff --git a/vendor/num-integer/.cargo-checksum.json b/vendor/num-integer/.cargo-checksum.json
deleted file mode 100644
index 52b0e24..0000000
--- a/vendor/num-integer/.cargo-checksum.json
+++ /dev/null
@@ -1 +0,0 @@
-{"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/vendor/num-integer/Cargo.toml b/vendor/num-integer/Cargo.toml
deleted file mode 100644
index 51a1a3e..0000000
--- a/vendor/num-integer/Cargo.toml
+++ /dev/null
@@ -1,51 +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 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/vendor/num-integer/LICENSE-APACHE b/vendor/num-integer/LICENSE-APACHE
deleted file mode 100644
index 16fe87b..0000000
--- 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 39d4bdb..0000000
--- 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 5f638cd..0000000
--- a/vendor/num-integer/README.md
+++ /dev/null
@@ -1,64 +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.
-
-## 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/vendor/num-integer/RELEASES.md b/vendor/num-integer/RELEASES.md
deleted file mode 100644
index 05c649b..0000000
--- a/vendor/num-integer/RELEASES.md
+++ /dev/null
@@ -1,112 +0,0 @@
-# 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/vendor/num-integer/benches/average.rs b/vendor/num-integer/benches/average.rs
deleted file mode 100644
index 649078c..0000000
--- 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<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/vendor/num-integer/benches/gcd.rs b/vendor/num-integer/benches/gcd.rs
deleted file mode 100644
index 082d5ee..0000000
--- 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<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/vendor/num-integer/benches/roots.rs b/vendor/num-integer/benches/roots.rs
deleted file mode 100644
index 7f67278..0000000
--- 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<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/vendor/num-integer/build.rs b/vendor/num-integer/build.rs
deleted file mode 100644
index 37c9857..0000000
--- a/vendor/num-integer/build.rs
+++ /dev/null
@@ -1,13 +0,0 @@
-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/vendor/num-integer/src/average.rs b/vendor/num-integer/src/average.rs
deleted file mode 100644
index 29cd11e..0000000
--- 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<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/vendor/num-integer/src/lib.rs b/vendor/num-integer/src/lib.rs
deleted file mode 100644
index 5005801..0000000
--- a/vendor/num-integer/src/lib.rs
+++ /dev/null
@@ -1,1386 +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 <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/vendor/num-integer/src/roots.rs b/vendor/num-integer/src/roots.rs
deleted file mode 100644
index a9eec1a..0000000
--- 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<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/vendor/num-integer/tests/average.rs b/vendor/num-integer/tests/average.rs
deleted file mode 100644
index 9fd8cf1..0000000
--- 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 f85f9e0..0000000
--- 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<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);
Copyright © 2024 Valentin A. Popov. All Rights Reverse Engineered.