diff --git a/.cargo_vcs_info.json b/.cargo_vcs_info.json
new file mode 100644
index 0000000..14ea4d6
--- /dev/null
+++ b/.cargo_vcs_info.json
@@ -0,0 +1,5 @@
+{
+  "git": {
+    "sha1": "4d166cbb754244760e28ea4ce826d54fafd3e629"
+  }
+}
diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..fa8d85a
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,2 @@
+Cargo.lock
+target
diff --git a/Cargo.toml b/Cargo.toml
new file mode 100644
index 0000000..8f72e39
--- /dev/null
+++ b/Cargo.toml
@@ -0,0 +1,38 @@
+# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO
+#
+# When uploading crates to the registry Cargo will automatically
+# "normalize" Cargo.toml files for maximal compatibility
+# with all versions of Cargo and also rewrite `path` dependencies
+# to registry (e.g., crates.io) dependencies
+#
+# If you believe there's an error in this file please file an
+# issue against the rust-lang/cargo repository. If you're
+# editing this file be aware that the upstream Cargo.toml
+# will likely look very different (and much more reasonable)
+
+[package]
+name = "num-integer"
+version = "0.1.44"
+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/Cargo.toml.orig b/Cargo.toml.orig
new file mode 100644
index 0000000..4ff8291
--- /dev/null
+++ b/Cargo.toml.orig
@@ -0,0 +1,29 @@
+[package]
+authors = ["The Rust Project Developers"]
+description = "Integer traits and functions"
+documentation = "https://docs.rs/num-integer"
+homepage = "https://github.com/rust-num/num-integer"
+keywords = ["mathematics", "numerics"]
+categories = ["algorithms", "science", "no-std"]
+license = "MIT OR Apache-2.0"
+repository = "https://github.com/rust-num/num-integer"
+name = "num-integer"
+version = "0.1.44"
+readme = "README.md"
+build = "build.rs"
+exclude = ["/bors.toml", "/ci/*", "/.github/*"]
+
+[package.metadata.docs.rs]
+features = ["std"]
+
+[dependencies.num-traits]
+version = "0.2.11"
+default-features = false
+
+[features]
+default = ["std"]
+i128 = ["num-traits/i128"]
+std = ["num-traits/std"]
+
+[build-dependencies]
+autocfg = "1"
diff --git a/LICENSE b/LICENSE
new file mode 120000
index 0000000..6b579aa
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1 @@
+LICENSE-APACHE
\ No newline at end of file
diff --git a/LICENSE-APACHE b/LICENSE-APACHE
new file mode 100644
index 0000000..16fe87b
--- /dev/null
+++ b/LICENSE-APACHE
@@ -0,0 +1,201 @@
+                              Apache License
+                        Version 2.0, January 2004
+                     http://www.apache.org/licenses/
+
+TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
+
+1. Definitions.
+
+   "License" shall mean the terms and conditions for use, reproduction,
+   and distribution as defined by Sections 1 through 9 of this document.
+
+   "Licensor" shall mean the copyright owner or entity authorized by
+   the copyright owner that is granting the License.
+
+   "Legal Entity" shall mean the union of the acting entity and all
+   other entities that control, are controlled by, or are under common
+   control with that entity. For the purposes of this definition,
+   "control" means (i) the power, direct or indirect, to cause the
+   direction or management of such entity, whether by contract or
+   otherwise, or (ii) ownership of fifty percent (50%) or more of the
+   outstanding shares, or (iii) beneficial ownership of such entity.
+
+   "You" (or "Your") shall mean an individual or Legal Entity
+   exercising permissions granted by this License.
+
+   "Source" form shall mean the preferred form for making modifications,
+   including but not limited to software source code, documentation
+   source, and configuration files.
+
+   "Object" form shall mean any form resulting from mechanical
+   transformation or translation of a Source form, including but
+   not limited to compiled object code, generated documentation,
+   and conversions to other media types.
+
+   "Work" shall mean the work of authorship, whether in Source or
+   Object form, made available under the License, as indicated by a
+   copyright notice that is included in or attached to the work
+   (an example is provided in the Appendix below).
+
+   "Derivative Works" shall mean any work, whether in Source or Object
+   form, that is based on (or derived from) the Work and for which the
+   editorial revisions, annotations, elaborations, or other modifications
+   represent, as a whole, an original work of authorship. For the purposes
+   of this License, Derivative Works shall not include works that remain
+   separable from, or merely link (or bind by name) to the interfaces of,
+   the Work and Derivative Works thereof.
+
+   "Contribution" shall mean any work of authorship, including
+   the original version of the Work and any modifications or additions
+   to that Work or Derivative Works thereof, that is intentionally
+   submitted to Licensor for inclusion in the Work by the copyright owner
+   or by an individual or Legal Entity authorized to submit on behalf of
+   the copyright owner. For the purposes of this definition, "submitted"
+   means any form of electronic, verbal, or written communication sent
+   to the Licensor or its representatives, including but not limited to
+   communication on electronic mailing lists, source code control systems,
+   and issue tracking systems that are managed by, or on behalf of, the
+   Licensor for the purpose of discussing and improving the Work, but
+   excluding communication that is conspicuously marked or otherwise
+   designated in writing by the copyright owner as "Not a Contribution."
+
+   "Contributor" shall mean Licensor and any individual or Legal Entity
+   on behalf of whom a Contribution has been received by Licensor and
+   subsequently incorporated within the Work.
+
+2. Grant of Copyright License. Subject to the terms and conditions of
+   this License, each Contributor hereby grants to You a perpetual,
+   worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+   copyright license to reproduce, prepare Derivative Works of,
+   publicly display, publicly perform, sublicense, and distribute the
+   Work and such Derivative Works in Source or Object form.
+
+3. Grant of Patent License. Subject to the terms and conditions of
+   this License, each Contributor hereby grants to You a perpetual,
+   worldwide, non-exclusive, no-charge, royalty-free, irrevocable
+   (except as stated in this section) patent license to make, have made,
+   use, offer to sell, sell, import, and otherwise transfer the Work,
+   where such license applies only to those patent claims licensable
+   by such Contributor that are necessarily infringed by their
+   Contribution(s) alone or by combination of their Contribution(s)
+   with the Work to which such Contribution(s) was submitted. If You
+   institute patent litigation against any entity (including a
+   cross-claim or counterclaim in a lawsuit) alleging that the Work
+   or a Contribution incorporated within the Work constitutes direct
+   or contributory patent infringement, then any patent licenses
+   granted to You under this License for that Work shall terminate
+   as of the date such litigation is filed.
+
+4. Redistribution. You may reproduce and distribute copies of the
+   Work or Derivative Works thereof in any medium, with or without
+   modifications, and in Source or Object form, provided that You
+   meet the following conditions:
+
+   (a) You must give any other recipients of the Work or
+       Derivative Works a copy of this License; and
+
+   (b) You must cause any modified files to carry prominent notices
+       stating that You changed the files; and
+
+   (c) You must retain, in the Source form of any Derivative Works
+       that You distribute, all copyright, patent, trademark, and
+       attribution notices from the Source form of the Work,
+       excluding those notices that do not pertain to any part of
+       the Derivative Works; and
+
+   (d) If the Work includes a "NOTICE" text file as part of its
+       distribution, then any Derivative Works that You distribute must
+       include a readable copy of the attribution notices contained
+       within such NOTICE file, excluding those notices that do not
+       pertain to any part of the Derivative Works, in at least one
+       of the following places: within a NOTICE text file distributed
+       as part of the Derivative Works; within the Source form or
+       documentation, if provided along with the Derivative Works; or,
+       within a display generated by the Derivative Works, if and
+       wherever such third-party notices normally appear. The contents
+       of the NOTICE file are for informational purposes only and
+       do not modify the License. You may add Your own attribution
+       notices within Derivative Works that You distribute, alongside
+       or as an addendum to the NOTICE text from the Work, provided
+       that such additional attribution notices cannot be construed
+       as modifying the License.
+
+   You may add Your own copyright statement to Your modifications and
+   may provide additional or different license terms and conditions
+   for use, reproduction, or distribution of Your modifications, or
+   for any such Derivative Works as a whole, provided Your use,
+   reproduction, and distribution of the Work otherwise complies with
+   the conditions stated in this License.
+
+5. Submission of Contributions. Unless You explicitly state otherwise,
+   any Contribution intentionally submitted for inclusion in the Work
+   by You to the Licensor shall be under the terms and conditions of
+   this License, without any additional terms or conditions.
+   Notwithstanding the above, nothing herein shall supersede or modify
+   the terms of any separate license agreement you may have executed
+   with Licensor regarding such Contributions.
+
+6. Trademarks. This License does not grant permission to use the trade
+   names, trademarks, service marks, or product names of the Licensor,
+   except as required for reasonable and customary use in describing the
+   origin of the Work and reproducing the content of the NOTICE file.
+
+7. Disclaimer of Warranty. Unless required by applicable law or
+   agreed to in writing, Licensor provides the Work (and each
+   Contributor provides its Contributions) on an "AS IS" BASIS,
+   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
+   implied, including, without limitation, any warranties or conditions
+   of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
+   PARTICULAR PURPOSE. You are solely responsible for determining the
+   appropriateness of using or redistributing the Work and assume any
+   risks associated with Your exercise of permissions under this License.
+
+8. Limitation of Liability. In no event and under no legal theory,
+   whether in tort (including negligence), contract, or otherwise,
+   unless required by applicable law (such as deliberate and grossly
+   negligent acts) or agreed to in writing, shall any Contributor be
+   liable to You for damages, including any direct, indirect, special,
+   incidental, or consequential damages of any character arising as a
+   result of this License or out of the use or inability to use the
+   Work (including but not limited to damages for loss of goodwill,
+   work stoppage, computer failure or malfunction, or any and all
+   other commercial damages or losses), even if such Contributor
+   has been advised of the possibility of such damages.
+
+9. Accepting Warranty or Additional Liability. While redistributing
+   the Work or Derivative Works thereof, You may choose to offer,
+   and charge a fee for, acceptance of support, warranty, indemnity,
+   or other liability obligations and/or rights consistent with this
+   License. However, in accepting such obligations, You may act only
+   on Your own behalf and on Your sole responsibility, not on behalf
+   of any other Contributor, and only if You agree to indemnify,
+   defend, and hold each Contributor harmless for any liability
+   incurred by, or claims asserted against, such Contributor by reason
+   of your accepting any such warranty or additional liability.
+
+END OF TERMS AND CONDITIONS
+
+APPENDIX: How to apply the Apache License to your work.
+
+   To apply the Apache License to your work, attach the following
+   boilerplate notice, with the fields enclosed by brackets "[]"
+   replaced with your own identifying information. (Don't include
+   the brackets!)  The text should be enclosed in the appropriate
+   comment syntax for the file format. We also recommend that a
+   file or class name and description of purpose be included on the
+   same "printed page" as the copyright notice for easier
+   identification within third-party archives.
+
+Copyright [yyyy] [name of copyright owner]
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+	http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
diff --git a/LICENSE-MIT b/LICENSE-MIT
new file mode 100644
index 0000000..39d4bdb
--- /dev/null
+++ b/LICENSE-MIT
@@ -0,0 +1,25 @@
+Copyright (c) 2014 The Rust Project Developers
+
+Permission is hereby granted, free of charge, to any
+person obtaining a copy of this software and associated
+documentation files (the "Software"), to deal in the
+Software without restriction, including without
+limitation the rights to use, copy, modify, merge,
+publish, distribute, sublicense, and/or sell copies of
+the Software, and to permit persons to whom the Software
+is furnished to do so, subject to the following
+conditions:
+
+The above copyright notice and this permission notice
+shall be included in all copies or substantial portions
+of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
+ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
+TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
+PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
+SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
+IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+DEALINGS IN THE SOFTWARE.
diff --git a/METADATA b/METADATA
new file mode 100644
index 0000000..16e112f
--- /dev/null
+++ b/METADATA
@@ -0,0 +1,19 @@
+name: "num-integer"
+description: "Integer traits and functions"
+third_party {
+  url {
+    type: HOMEPAGE
+    value: "https://crates.io/crates/num-integer"
+  }
+  url {
+    type: ARCHIVE
+    value: "https://static.crates.io/crates/num-integer/num-integer-0.1.44.crate"
+  }
+  version: "0.1.44"
+  license_type: NOTICE
+  last_upgrade_date {
+    year: 2021
+    month: 1
+    day: 28
+  }
+}
diff --git a/MODULE_LICENSE_APACHE2 b/MODULE_LICENSE_APACHE2
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/MODULE_LICENSE_APACHE2
diff --git a/OWNERS b/OWNERS
new file mode 100644
index 0000000..46fc303
--- /dev/null
+++ b/OWNERS
@@ -0,0 +1 @@
+include platform/prebuilts/rust:/OWNERS
diff --git a/README.md b/README.md
new file mode 100644
index 0000000..5f638cd
--- /dev/null
+++ b/README.md
@@ -0,0 +1,64 @@
+# 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/RELEASES.md b/RELEASES.md
new file mode 100644
index 0000000..05be073
--- /dev/null
+++ b/RELEASES.md
@@ -0,0 +1,98 @@
+# 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/benches/average.rs b/benches/average.rs
new file mode 100644
index 0000000..05d824c
--- /dev/null
+++ b/benches/average.rs
@@ -0,0 +1,414 @@
+//! Benchmark sqrt and cbrt
+
+#![feature(test)]
+
+extern crate num_integer;
+extern crate num_traits;
+extern crate test;
+
+use num_integer::Integer;
+use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul};
+use std::cmp::{max, min};
+use std::fmt::Debug;
+use test::{black_box, Bencher};
+
+// --- Utilities for RNG ----------------------------------------------------
+
+trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+// Simple PRNG so we don't have to worry about rand compatibility
+fn lcg<T>(x: T) -> T
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+{
+    // LCG parameters from Numerical Recipes
+    // (but we're applying it to arbitrary sizes)
+    const LCG_A: u32 = 1664525;
+    const LCG_C: u32 = 1013904223;
+    x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_())
+}
+
+// --- Alt. Implementations -------------------------------------------------
+
+trait NaiveAverage {
+    fn naive_average_ceil(&self, other: &Self) -> Self;
+    fn naive_average_floor(&self, other: &Self) -> Self;
+}
+
+trait UncheckedAverage {
+    fn unchecked_average_ceil(&self, other: &Self) -> Self;
+    fn unchecked_average_floor(&self, other: &Self) -> Self;
+}
+
+trait ModuloAverage {
+    fn modulo_average_ceil(&self, other: &Self) -> Self;
+    fn modulo_average_floor(&self, other: &Self) -> Self;
+}
+
+macro_rules! naive_average {
+    ($T:ident) => {
+        impl super::NaiveAverage for $T {
+            fn naive_average_floor(&self, other: &$T) -> $T {
+                match self.checked_add(*other) {
+                    Some(z) => z.div_floor(&2),
+                    None => {
+                        if self > other {
+                            let diff = self - other;
+                            other + diff.div_floor(&2)
+                        } else {
+                            let diff = other - self;
+                            self + diff.div_floor(&2)
+                        }
+                    }
+                }
+            }
+            fn naive_average_ceil(&self, other: &$T) -> $T {
+                match self.checked_add(*other) {
+                    Some(z) => z.div_ceil(&2),
+                    None => {
+                        if self > other {
+                            let diff = self - other;
+                            self - diff.div_floor(&2)
+                        } else {
+                            let diff = other - self;
+                            other - diff.div_floor(&2)
+                        }
+                    }
+                }
+            }
+        }
+    };
+}
+
+macro_rules! unchecked_average {
+    ($T:ident) => {
+        impl super::UncheckedAverage for $T {
+            fn unchecked_average_floor(&self, other: &$T) -> $T {
+                self.wrapping_add(*other) / 2
+            }
+            fn unchecked_average_ceil(&self, other: &$T) -> $T {
+                (self.wrapping_add(*other) / 2).wrapping_add(1)
+            }
+        }
+    };
+}
+
+macro_rules! modulo_average {
+    ($T:ident) => {
+        impl super::ModuloAverage for $T {
+            fn modulo_average_ceil(&self, other: &$T) -> $T {
+                let (q1, r1) = self.div_mod_floor(&2);
+                let (q2, r2) = other.div_mod_floor(&2);
+                q1 + q2 + (r1 | r2)
+            }
+            fn modulo_average_floor(&self, other: &$T) -> $T {
+                let (q1, r1) = self.div_mod_floor(&2);
+                let (q2, r2) = other.div_mod_floor(&2);
+                q1 + q2 + (r1 * r2)
+            }
+        }
+    };
+}
+
+// --- Bench functions ------------------------------------------------------
+
+fn bench_unchecked<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/benches/gcd.rs b/benches/gcd.rs
new file mode 100644
index 0000000..082d5ee
--- /dev/null
+++ b/benches/gcd.rs
@@ -0,0 +1,176 @@
+//! Benchmark comparing the current GCD implemtation against an older one.
+
+#![feature(test)]
+
+extern crate num_integer;
+extern crate num_traits;
+extern crate test;
+
+use num_integer::Integer;
+use num_traits::{AsPrimitive, Bounded, Signed};
+use test::{black_box, Bencher};
+
+trait GcdOld: Integer {
+    fn gcd_old(&self, other: &Self) -> Self;
+}
+
+macro_rules! impl_gcd_old_for_isize {
+    ($T:ty) => {
+        impl GcdOld for $T {
+            /// Calculates the Greatest Common Divisor (GCD) of the number and
+            /// `other`. The result is always positive.
+            #[inline]
+            fn gcd_old(&self, other: &Self) -> Self {
+                // Use Stein's algorithm
+                let mut m = *self;
+                let mut n = *other;
+                if m == 0 || n == 0 {
+                    return (m | n).abs();
+                }
+
+                // find common factors of 2
+                let shift = (m | n).trailing_zeros();
+
+                // The algorithm needs positive numbers, but the minimum value
+                // can't be represented as a positive one.
+                // It's also a power of two, so the gcd can be
+                // calculated by bitshifting in that case
+
+                // Assuming two's complement, the number created by the shift
+                // is positive for all numbers except gcd = abs(min value)
+                // The call to .abs() causes a panic in debug mode
+                if m == Self::min_value() || n == Self::min_value() {
+                    return (1 << shift).abs();
+                }
+
+                // guaranteed to be positive now, rest like unsigned algorithm
+                m = m.abs();
+                n = n.abs();
+
+                // divide n and m by 2 until odd
+                // m inside loop
+                n >>= n.trailing_zeros();
+
+                while m != 0 {
+                    m >>= m.trailing_zeros();
+                    if n > m {
+                        std::mem::swap(&mut n, &mut m)
+                    }
+                    m -= n;
+                }
+
+                n << shift
+            }
+        }
+    };
+}
+
+impl_gcd_old_for_isize!(i8);
+impl_gcd_old_for_isize!(i16);
+impl_gcd_old_for_isize!(i32);
+impl_gcd_old_for_isize!(i64);
+impl_gcd_old_for_isize!(isize);
+impl_gcd_old_for_isize!(i128);
+
+macro_rules! impl_gcd_old_for_usize {
+    ($T:ty) => {
+        impl GcdOld for $T {
+            /// Calculates the Greatest Common Divisor (GCD) of the number and
+            /// `other`. The result is always positive.
+            #[inline]
+            fn gcd_old(&self, other: &Self) -> Self {
+                // Use Stein's algorithm
+                let mut m = *self;
+                let mut n = *other;
+                if m == 0 || n == 0 {
+                    return m | n;
+                }
+
+                // find common factors of 2
+                let shift = (m | n).trailing_zeros();
+
+                // divide n and m by 2 until odd
+                // m inside loop
+                n >>= n.trailing_zeros();
+
+                while m != 0 {
+                    m >>= m.trailing_zeros();
+                    if n > m {
+                        std::mem::swap(&mut n, &mut m)
+                    }
+                    m -= n;
+                }
+
+                n << shift
+            }
+        }
+    };
+}
+
+impl_gcd_old_for_usize!(u8);
+impl_gcd_old_for_usize!(u16);
+impl_gcd_old_for_usize!(u32);
+impl_gcd_old_for_usize!(u64);
+impl_gcd_old_for_usize!(usize);
+impl_gcd_old_for_usize!(u128);
+
+/// Return an iterator that yields all Fibonacci numbers fitting into a u128.
+fn fibonacci() -> impl Iterator<Item = u128> {
+    (0..185).scan((0, 1), |&mut (ref mut a, ref mut b), _| {
+        let tmp = *a;
+        *a = *b;
+        *b += tmp;
+        Some(*b)
+    })
+}
+
+fn run_bench<T: Integer + Bounded + Copy + 'static>(b: &mut Bencher, gcd: fn(&T, &T) -> T)
+where
+    T: AsPrimitive<u128>,
+    u128: AsPrimitive<T>,
+{
+    let max_value: u128 = T::max_value().as_();
+    let pairs: Vec<(T, T)> = fibonacci()
+        .collect::<Vec<_>>()
+        .windows(2)
+        .filter(|&pair| pair[0] <= max_value && pair[1] <= max_value)
+        .map(|pair| (pair[0].as_(), pair[1].as_()))
+        .collect();
+    b.iter(|| {
+        for &(ref m, ref n) in &pairs {
+            black_box(gcd(m, n));
+        }
+    });
+}
+
+macro_rules! bench_gcd {
+    ($T:ident) => {
+        mod $T {
+            use crate::{run_bench, GcdOld};
+            use num_integer::Integer;
+            use test::Bencher;
+
+            #[bench]
+            fn bench_gcd(b: &mut Bencher) {
+                run_bench(b, $T::gcd);
+            }
+
+            #[bench]
+            fn bench_gcd_old(b: &mut Bencher) {
+                run_bench(b, $T::gcd_old);
+            }
+        }
+    };
+}
+
+bench_gcd!(u8);
+bench_gcd!(u16);
+bench_gcd!(u32);
+bench_gcd!(u64);
+bench_gcd!(u128);
+
+bench_gcd!(i8);
+bench_gcd!(i16);
+bench_gcd!(i32);
+bench_gcd!(i64);
+bench_gcd!(i128);
diff --git a/benches/roots.rs b/benches/roots.rs
new file mode 100644
index 0000000..7f67278
--- /dev/null
+++ b/benches/roots.rs
@@ -0,0 +1,170 @@
+//! Benchmark sqrt and cbrt
+
+#![feature(test)]
+
+extern crate num_integer;
+extern crate num_traits;
+extern crate test;
+
+use num_integer::Integer;
+use num_traits::checked_pow;
+use num_traits::{AsPrimitive, PrimInt, WrappingAdd, WrappingMul};
+use test::{black_box, Bencher};
+
+trait BenchInteger: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+impl<T> BenchInteger for T where T: Integer + PrimInt + WrappingAdd + WrappingMul + 'static {}
+
+fn bench<T, F>(b: &mut Bencher, v: &[T], f: F, n: u32)
+where
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    // Pre-validate the results...
+    for i in v {
+        let rt = f(i);
+        if *i >= T::zero() {
+            let rt1 = rt + T::one();
+            assert!(rt.pow(n) <= *i);
+            if let Some(x) = checked_pow(rt1, n as usize) {
+                assert!(*i < x);
+            }
+        } else {
+            let rt1 = rt - T::one();
+            assert!(rt < T::zero());
+            assert!(*i <= rt.pow(n));
+            if let Some(x) = checked_pow(rt1, n as usize) {
+                assert!(x < *i);
+            }
+        };
+    }
+
+    // Now just run as fast as we can!
+    b.iter(|| {
+        for i in v {
+            black_box(f(i));
+        }
+    });
+}
+
+// Simple PRNG so we don't have to worry about rand compatibility
+fn lcg<T>(x: T) -> T
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+{
+    // LCG parameters from Numerical Recipes
+    // (but we're applying it to arbitrary sizes)
+    const LCG_A: u32 = 1664525;
+    const LCG_C: u32 = 1013904223;
+    x.wrapping_mul(&LCG_A.as_()).wrapping_add(&LCG_C.as_())
+}
+
+fn bench_rand<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let mut x: T = 3u32.as_();
+    let v: Vec<T> = (0..1000)
+        .map(|_| {
+            x = lcg(x);
+            x
+        })
+        .collect();
+    bench(b, &v, f, n);
+}
+
+fn bench_rand_pos<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let mut x: T = 3u32.as_();
+    let v: Vec<T> = (0..1000)
+        .map(|_| {
+            x = lcg(x);
+            while x < T::zero() {
+                x = lcg(x);
+            }
+            x
+        })
+        .collect();
+    bench(b, &v, f, n);
+}
+
+fn bench_small<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let v: Vec<T> = (0..1000).map(|i| i.as_()).collect();
+    bench(b, &v, f, n);
+}
+
+fn bench_small_pos<T, F>(b: &mut Bencher, f: F, n: u32)
+where
+    u32: AsPrimitive<T>,
+    T: BenchInteger,
+    F: Fn(&T) -> T,
+{
+    let v: Vec<T> = (0..1000)
+        .map(|i| i.as_().mod_floor(&T::max_value()))
+        .collect();
+    bench(b, &v, f, n);
+}
+
+macro_rules! bench_roots {
+    ($($T:ident),*) => {$(
+        mod $T {
+            use test::Bencher;
+            use num_integer::Roots;
+
+            #[bench]
+            fn sqrt_rand(b: &mut Bencher) {
+                ::bench_rand_pos(b, $T::sqrt, 2);
+            }
+
+            #[bench]
+            fn sqrt_small(b: &mut Bencher) {
+                ::bench_small_pos(b, $T::sqrt, 2);
+            }
+
+            #[bench]
+            fn cbrt_rand(b: &mut Bencher) {
+                ::bench_rand(b, $T::cbrt, 3);
+            }
+
+            #[bench]
+            fn cbrt_small(b: &mut Bencher) {
+                ::bench_small(b, $T::cbrt, 3);
+            }
+
+            #[bench]
+            fn fourth_root_rand(b: &mut Bencher) {
+                ::bench_rand_pos(b, |x: &$T| x.nth_root(4), 4);
+            }
+
+            #[bench]
+            fn fourth_root_small(b: &mut Bencher) {
+                ::bench_small_pos(b, |x: &$T| x.nth_root(4), 4);
+            }
+
+            #[bench]
+            fn fifth_root_rand(b: &mut Bencher) {
+                ::bench_rand(b, |x: &$T| x.nth_root(5), 5);
+            }
+
+            #[bench]
+            fn fifth_root_small(b: &mut Bencher) {
+                ::bench_small(b, |x: &$T| x.nth_root(5), 5);
+            }
+        }
+    )*}
+}
+
+bench_roots!(i8, i16, i32, i64, i128);
+bench_roots!(u8, u16, u32, u64, u128);
diff --git a/build.rs b/build.rs
new file mode 100644
index 0000000..37c9857
--- /dev/null
+++ b/build.rs
@@ -0,0 +1,13 @@
+extern crate autocfg;
+
+use std::env;
+
+fn main() {
+    // If the "i128" feature is explicity requested, don't bother probing for it.
+    // It will still cause a build error if that was set improperly.
+    if env::var_os("CARGO_FEATURE_I128").is_some() || autocfg::new().probe_type("i128") {
+        autocfg::emit("has_i128");
+    }
+
+    autocfg::rerun_path("build.rs");
+}
diff --git a/src/average.rs b/src/average.rs
new file mode 100644
index 0000000..29cd11e
--- /dev/null
+++ b/src/average.rs
@@ -0,0 +1,78 @@
+use core::ops::{BitAnd, BitOr, BitXor, Shr};
+use Integer;
+
+/// Provides methods to compute the average of two integers, without overflows.
+pub trait Average: Integer {
+    /// Returns the ceiling value of the average of `self` and `other`.
+    /// -- `⌈(self + other)/2⌉`
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use num_integer::Average;
+    ///
+    /// assert_eq!(( 3).average_ceil(&10),  7);
+    /// assert_eq!((-2).average_ceil(&-5), -3);
+    /// assert_eq!(( 4).average_ceil(& 4),  4);
+    ///
+    /// assert_eq!(u8::max_value().average_ceil(&2), 129);
+    /// assert_eq!(i8::min_value().average_ceil(&-1), -64);
+    /// assert_eq!(i8::min_value().average_ceil(&i8::max_value()), 0);
+    /// ```
+    ///
+    fn average_ceil(&self, other: &Self) -> Self;
+
+    /// Returns the floor value of the average of `self` and `other`.
+    /// -- `⌊(self + other)/2⌋`
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use num_integer::Average;
+    ///
+    /// assert_eq!(( 3).average_floor(&10),  6);
+    /// assert_eq!((-2).average_floor(&-5), -4);
+    /// assert_eq!(( 4).average_floor(& 4),  4);
+    ///
+    /// assert_eq!(u8::max_value().average_floor(&2), 128);
+    /// assert_eq!(i8::min_value().average_floor(&-1), -65);
+    /// assert_eq!(i8::min_value().average_floor(&i8::max_value()), -1);
+    /// ```
+    ///
+    fn average_floor(&self, other: &Self) -> Self;
+}
+
+impl<I> Average for I
+where
+    I: Integer + Shr<usize, Output = I>,
+    for<'a, 'b> &'a I:
+        BitAnd<&'b I, Output = I> + BitOr<&'b I, Output = I> + BitXor<&'b I, Output = I>,
+{
+    // The Henry Gordon Dietz implementation as shown in the Hacker's Delight,
+    // see http://aggregate.org/MAGIC/#Average%20of%20Integers
+
+    /// Returns the floor value of the average of `self` and `other`.
+    #[inline]
+    fn average_floor(&self, other: &I) -> I {
+        (self & other) + ((self ^ other) >> 1)
+    }
+
+    /// Returns the ceil value of the average of `self` and `other`.
+    #[inline]
+    fn average_ceil(&self, other: &I) -> I {
+        (self | other) - ((self ^ other) >> 1)
+    }
+}
+
+/// Returns the floor value of the average of `x` and `y` --
+/// see [Average::average_floor](trait.Average.html#tymethod.average_floor).
+#[inline]
+pub fn average_floor<T: Average>(x: T, y: T) -> T {
+    x.average_floor(&y)
+}
+/// Returns the ceiling value of the average of `x` and `y` --
+/// see [Average::average_ceil](trait.Average.html#tymethod.average_ceil).
+#[inline]
+pub fn average_ceil<T: Average>(x: T, y: T) -> T {
+    x.average_ceil(&y)
+}
diff --git a/src/lib.rs b/src/lib.rs
new file mode 100644
index 0000000..0281954
--- /dev/null
+++ b/src/lib.rs
@@ -0,0 +1,1343 @@
+// 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,
+                _hidden: (),
+            }
+        } else {
+            ExtendedGcd {
+                gcd: Self::zero() - r.1,
+                x: Self::zero() - s.1,
+                y: Self::zero() - t.1,
+                _hidden: (),
+            }
+        }
+    }
+
+    /// Greatest common divisor, least common multiple, and Bézout coefficients.
+    #[inline]
+    fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, 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,
+    _hidden: (),
+}
+
+/// 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 positive.
+#[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 positive.
+            #[inline]
+            fn gcd(&self, other: &Self) -> Self {
+                // Use Stein's algorithm
+                let mut m = *self;
+                let mut n = *other;
+                if m == 0 || n == 0 {
+                    return (m | n).abs();
+                }
+
+                // find common factors of 2
+                let shift = (m | n).trailing_zeros();
+
+                // The algorithm needs positive numbers, but the minimum value
+                // can't be represented as a positive one.
+                // It's also a power of two, so the gcd can be
+                // calculated by bitshifting in that case
+
+                // Assuming two's complement, the number created by the shift
+                // is positive for all numbers except gcd = abs(min value)
+                // The call to .abs() causes a panic in debug mode
+                if m == Self::min_value() || n == Self::min_value() {
+                    return (1 << shift).abs();
+                }
+
+                // guaranteed to be positive now, rest like unsigned algorithm
+                m = m.abs();
+                n = n.abs();
+
+                // divide n and m by 2 until odd
+                m >>= m.trailing_zeros();
+                n >>= n.trailing_zeros();
+
+                while m != n {
+                    if m > n {
+                        m -= n;
+                        m >>= m.trailing_zeros();
+                    } else {
+                        n -= m;
+                        n >>= n.trailing_zeros();
+                    }
+                }
+                m << shift
+            }
+
+            #[inline]
+            fn extended_gcd_lcm(&self, other: &Self) -> (ExtendedGcd<Self>, Self) {
+                let egcd = self.extended_gcd(other);
+                // should not have to recalculate abs
+                let lcm = if egcd.gcd.is_zero() {
+                    Self::zero()
+                } else {
+                    (*self * (*other / egcd.gcd)).abs()
+                };
+                (egcd, lcm)
+            }
+
+            /// Calculates the Lowest Common Multiple (LCM) of the number and
+            /// `other`.
+            #[inline]
+            fn lcm(&self, other: &Self) -> Self {
+                self.gcd_lcm(other).1
+            }
+
+            /// Calculates the Greatest Common Divisor (GCD) and
+            /// Lowest Common Multiple (LCM) of the number and `other`.
+            #[inline]
+            fn gcd_lcm(&self, other: &Self) -> (Self, Self) {
+                if self.is_zero() && other.is_zero() {
+                    return (Self::zero(), Self::zero());
+                }
+                let gcd = self.gcd(other);
+                // should not have to recalculate abs
+                let lcm = (*self * (*other / gcd)).abs();
+                (gcd, lcm)
+            }
+
+            /// Deprecated, use `is_multiple_of` instead.
+            #[inline]
+            fn divides(&self, other: &Self) -> bool {
+                self.is_multiple_of(other)
+            }
+
+            /// Returns `true` if the number is a multiple of `other`.
+            #[inline]
+            fn is_multiple_of(&self, other: &Self) -> bool {
+                *self % *other == 0
+            }
+
+            /// Returns `true` if the number is divisible by `2`
+            #[inline]
+            fn is_even(&self) -> bool {
+                (*self) & 1 == 0
+            }
+
+            /// Returns `true` if the number is not divisible by `2`
+            #[inline]
+            fn is_odd(&self) -> bool {
+                !self.is_even()
+            }
+
+            /// Simultaneous truncated integer division and modulus.
+            #[inline]
+            fn div_rem(&self, other: &Self) -> (Self, Self) {
+                (*self / *other, *self % *other)
+            }
+        }
+
+        #[cfg(test)]
+        mod $test_mod {
+            use core::mem;
+            use Integer;
+
+            /// Checks that the division rule holds for:
+            ///
+            /// - `n`: numerator (dividend)
+            /// - `d`: denominator (divisor)
+            /// - `qr`: quotient and remainder
+            #[cfg(test)]
+            fn test_division_rule((n, d): ($T, $T), (q, r): ($T, $T)) {
+                assert_eq!(d * q + r, n);
+            }
+
+            #[test]
+            fn test_div_rem() {
+                fn test_nd_dr(nd: ($T, $T), qr: ($T, $T)) {
+                    let (n, d) = nd;
+                    let separate_div_rem = (n / d, n % d);
+                    let combined_div_rem = n.div_rem(&d);
+
+                    assert_eq!(separate_div_rem, qr);
+                    assert_eq!(combined_div_rem, qr);
+
+                    test_division_rule(nd, separate_div_rem);
+                    test_division_rule(nd, combined_div_rem);
+                }
+
+                test_nd_dr((8, 3), (2, 2));
+                test_nd_dr((8, -3), (-2, 2));
+                test_nd_dr((-8, 3), (-2, -2));
+                test_nd_dr((-8, -3), (2, -2));
+
+                test_nd_dr((1, 2), (0, 1));
+                test_nd_dr((1, -2), (0, 1));
+                test_nd_dr((-1, 2), (0, -1));
+                test_nd_dr((-1, -2), (0, -1));
+            }
+
+            #[test]
+            fn test_div_mod_floor() {
+                fn test_nd_dm(nd: ($T, $T), dm: ($T, $T)) {
+                    let (n, d) = nd;
+                    let separate_div_mod_floor = (n.div_floor(&d), n.mod_floor(&d));
+                    let combined_div_mod_floor = n.div_mod_floor(&d);
+
+                    assert_eq!(separate_div_mod_floor, dm);
+                    assert_eq!(combined_div_mod_floor, dm);
+
+                    test_division_rule(nd, separate_div_mod_floor);
+                    test_division_rule(nd, combined_div_mod_floor);
+                }
+
+                test_nd_dm((8, 3), (2, 2));
+                test_nd_dm((8, -3), (-3, -1));
+                test_nd_dm((-8, 3), (-3, 1));
+                test_nd_dm((-8, -3), (2, -2));
+
+                test_nd_dm((1, 2), (0, 1));
+                test_nd_dm((1, -2), (-1, -1));
+                test_nd_dm((-1, 2), (-1, 1));
+                test_nd_dm((-1, -2), (0, -1));
+            }
+
+            #[test]
+            fn test_gcd() {
+                assert_eq!((10 as $T).gcd(&2), 2 as $T);
+                assert_eq!((10 as $T).gcd(&3), 1 as $T);
+                assert_eq!((0 as $T).gcd(&3), 3 as $T);
+                assert_eq!((3 as $T).gcd(&3), 3 as $T);
+                assert_eq!((56 as $T).gcd(&42), 14 as $T);
+                assert_eq!((3 as $T).gcd(&-3), 3 as $T);
+                assert_eq!((-6 as $T).gcd(&3), 3 as $T);
+                assert_eq!((-4 as $T).gcd(&-2), 2 as $T);
+            }
+
+            #[test]
+            fn test_gcd_cmp_with_euclidean() {
+                fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
+                    while m != 0 {
+                        mem::swap(&mut m, &mut n);
+                        m %= n;
+                    }
+
+                    n.abs()
+                }
+
+                // gcd(-128, b) = 128 is not representable as positive value
+                // for i8
+                for i in -127..127 {
+                    for j in -127..127 {
+                        assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
+                    }
+                }
+
+                // last value
+                // FIXME: Use inclusive ranges for above loop when implemented
+                let i = 127;
+                for j in -127..127 {
+                    assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
+                }
+                assert_eq!(127.gcd(&127), 127);
+            }
+
+            #[test]
+            fn test_gcd_min_val() {
+                let min = <$T>::min_value();
+                let max = <$T>::max_value();
+                let max_pow2 = max / 2 + 1;
+                assert_eq!(min.gcd(&max), 1 as $T);
+                assert_eq!(max.gcd(&min), 1 as $T);
+                assert_eq!(min.gcd(&max_pow2), max_pow2);
+                assert_eq!(max_pow2.gcd(&min), max_pow2);
+                assert_eq!(min.gcd(&42), 2 as $T);
+                assert_eq!((42 as $T).gcd(&min), 2 as $T);
+            }
+
+            #[test]
+            #[should_panic]
+            fn test_gcd_min_val_min_val() {
+                let min = <$T>::min_value();
+                assert!(min.gcd(&min) >= 0);
+            }
+
+            #[test]
+            #[should_panic]
+            fn test_gcd_min_val_0() {
+                let min = <$T>::min_value();
+                assert!(min.gcd(&0) >= 0);
+            }
+
+            #[test]
+            #[should_panic]
+            fn test_gcd_0_min_val() {
+                let min = <$T>::min_value();
+                assert!((0 as $T).gcd(&min) >= 0);
+            }
+
+            #[test]
+            fn test_lcm() {
+                assert_eq!((1 as $T).lcm(&0), 0 as $T);
+                assert_eq!((0 as $T).lcm(&1), 0 as $T);
+                assert_eq!((1 as $T).lcm(&1), 1 as $T);
+                assert_eq!((-1 as $T).lcm(&1), 1 as $T);
+                assert_eq!((1 as $T).lcm(&-1), 1 as $T);
+                assert_eq!((-1 as $T).lcm(&-1), 1 as $T);
+                assert_eq!((8 as $T).lcm(&9), 72 as $T);
+                assert_eq!((11 as $T).lcm(&5), 55 as $T);
+            }
+
+            #[test]
+            fn test_gcd_lcm() {
+                use core::iter::once;
+                for i in once(0)
+                    .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
+                    .chain(once(-128))
+                {
+                    for j in once(0)
+                        .chain((1..).take(127).flat_map(|a| once(a).chain(once(-a))))
+                        .chain(once(-128))
+                    {
+                        assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j)));
+                    }
+                }
+            }
+
+            #[test]
+            fn test_extended_gcd_lcm() {
+                use core::fmt::Debug;
+                use traits::NumAssign;
+                use ExtendedGcd;
+
+                fn check<A: 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);
+            }
+        }
+    };
+}
+
+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 {
+                *self % *other == 0
+            }
+
+            /// Returns `true` if the number is divisible by `2`.
+            #[inline]
+            fn is_even(&self) -> bool {
+                *self % 2 == 0
+            }
+
+            /// Returns `true` if the number is not divisible by `2`.
+            #[inline]
+            fn is_odd(&self) -> bool {
+                !self.is_even()
+            }
+
+            /// Simultaneous truncated integer division and modulus.
+            #[inline]
+            fn div_rem(&self, other: &Self) -> (Self, Self) {
+                (*self / *other, *self % *other)
+            }
+        }
+
+        #[cfg(test)]
+        mod $test_mod {
+            use core::mem;
+            use Integer;
+
+            #[test]
+            fn test_div_mod_floor() {
+                assert_eq!((10 as $T).div_floor(&(3 as $T)), 3 as $T);
+                assert_eq!((10 as $T).mod_floor(&(3 as $T)), 1 as $T);
+                assert_eq!((10 as $T).div_mod_floor(&(3 as $T)), (3 as $T, 1 as $T));
+                assert_eq!((5 as $T).div_floor(&(5 as $T)), 1 as $T);
+                assert_eq!((5 as $T).mod_floor(&(5 as $T)), 0 as $T);
+                assert_eq!((5 as $T).div_mod_floor(&(5 as $T)), (1 as $T, 0 as $T));
+                assert_eq!((3 as $T).div_floor(&(7 as $T)), 0 as $T);
+                assert_eq!((3 as $T).mod_floor(&(7 as $T)), 3 as $T);
+                assert_eq!((3 as $T).div_mod_floor(&(7 as $T)), (0 as $T, 3 as $T));
+            }
+
+            #[test]
+            fn test_gcd() {
+                assert_eq!((10 as $T).gcd(&2), 2 as $T);
+                assert_eq!((10 as $T).gcd(&3), 1 as $T);
+                assert_eq!((0 as $T).gcd(&3), 3 as $T);
+                assert_eq!((3 as $T).gcd(&3), 3 as $T);
+                assert_eq!((56 as $T).gcd(&42), 14 as $T);
+            }
+
+            #[test]
+            fn test_gcd_cmp_with_euclidean() {
+                fn euclidean_gcd(mut m: $T, mut n: $T) -> $T {
+                    while m != 0 {
+                        mem::swap(&mut m, &mut n);
+                        m %= n;
+                    }
+                    n
+                }
+
+                for i in 0..255 {
+                    for j in 0..255 {
+                        assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
+                    }
+                }
+
+                // last value
+                // FIXME: Use inclusive ranges for above loop when implemented
+                let i = 255;
+                for j in 0..255 {
+                    assert_eq!(euclidean_gcd(i, j), i.gcd(&j));
+                }
+                assert_eq!(255.gcd(&255), 255);
+            }
+
+            #[test]
+            fn test_lcm() {
+                assert_eq!((1 as $T).lcm(&0), 0 as $T);
+                assert_eq!((0 as $T).lcm(&1), 0 as $T);
+                assert_eq!((1 as $T).lcm(&1), 1 as $T);
+                assert_eq!((8 as $T).lcm(&9), 72 as $T);
+                assert_eq!((11 as $T).lcm(&5), 55 as $T);
+                assert_eq!((15 as $T).lcm(&17), 255 as $T);
+            }
+
+            #[test]
+            fn test_gcd_lcm() {
+                for i in (0..).take(256) {
+                    for j in (0..).take(256) {
+                        assert_eq!(i.gcd_lcm(&j), (i.gcd(&j), i.lcm(&j)));
+                    }
+                }
+            }
+
+            #[test]
+            fn test_is_multiple_of() {
+                assert!((6 as $T).is_multiple_of(&(6 as $T)));
+                assert!((6 as $T).is_multiple_of(&(3 as $T)));
+                assert!((6 as $T).is_multiple_of(&(1 as $T)));
+            }
+
+            #[test]
+            fn test_even() {
+                assert_eq!((0 as $T).is_even(), true);
+                assert_eq!((1 as $T).is_even(), false);
+                assert_eq!((2 as $T).is_even(), true);
+                assert_eq!((3 as $T).is_even(), false);
+                assert_eq!((4 as $T).is_even(), true);
+            }
+
+            #[test]
+            fn test_odd() {
+                assert_eq!((0 as $T).is_odd(), false);
+                assert_eq!((1 as $T).is_odd(), true);
+                assert_eq!((2 as $T).is_odd(), false);
+                assert_eq!((3 as $T).is_odd(), true);
+                assert_eq!((4 as $T).is_odd(), false);
+            }
+        }
+    };
+}
+
+impl_integer_for_usize!(u8, test_integer_u8);
+impl_integer_for_usize!(u16, test_integer_u16);
+impl_integer_for_usize!(u32, test_integer_u32);
+impl_integer_for_usize!(u64, test_integer_u64);
+impl_integer_for_usize!(usize, test_integer_usize);
+#[cfg(has_i128)]
+impl_integer_for_usize!(u128, test_integer_u128);
+
+/// An iterator over binomial coefficients.
+pub struct IterBinomial<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/src/roots.rs b/src/roots.rs
new file mode 100644
index 0000000..a9eec1a
--- /dev/null
+++ b/src/roots.rs
@@ -0,0 +1,391 @@
+use core;
+use core::mem;
+use traits::checked_pow;
+use traits::PrimInt;
+use Integer;
+
+/// Provides methods to compute an integer's square root, cube root,
+/// and arbitrary `n`th root.
+pub trait Roots: Integer {
+    /// Returns the truncated principal `n`th root of an integer
+    /// -- `if x >= 0 { ⌊ⁿ√x⌋ } else { ⌈ⁿ√x⌉ }`
+    ///
+    /// This is solving for `r` in `rⁿ = x`, rounding toward zero.
+    /// If `x` is positive, the result will satisfy `rⁿ ≤ x < (r+1)ⁿ`.
+    /// If `x` is negative and `n` is odd, then `(r-1)ⁿ < x ≤ rⁿ`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `n` is zero:
+    ///
+    /// ```should_panic
+    /// # use num_integer::Roots;
+    /// println!("can't compute ⁰√x : {}", 123.nth_root(0));
+    /// ```
+    ///
+    /// or if `n` is even and `self` is negative:
+    ///
+    /// ```should_panic
+    /// # use num_integer::Roots;
+    /// println!("no imaginary numbers... {}", (-1).nth_root(10));
+    /// ```
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use num_integer::Roots;
+    ///
+    /// let x: i32 = 12345;
+    /// assert_eq!(x.nth_root(1), x);
+    /// assert_eq!(x.nth_root(2), x.sqrt());
+    /// assert_eq!(x.nth_root(3), x.cbrt());
+    /// assert_eq!(x.nth_root(4), 10);
+    /// assert_eq!(x.nth_root(13), 2);
+    /// assert_eq!(x.nth_root(14), 1);
+    /// assert_eq!(x.nth_root(std::u32::MAX), 1);
+    ///
+    /// assert_eq!(std::i32::MAX.nth_root(30), 2);
+    /// assert_eq!(std::i32::MAX.nth_root(31), 1);
+    /// assert_eq!(std::i32::MIN.nth_root(31), -2);
+    /// assert_eq!((std::i32::MIN + 1).nth_root(31), -1);
+    ///
+    /// assert_eq!(std::u32::MAX.nth_root(31), 2);
+    /// assert_eq!(std::u32::MAX.nth_root(32), 1);
+    /// ```
+    fn nth_root(&self, n: u32) -> Self;
+
+    /// Returns the truncated principal square root of an integer -- `⌊√x⌋`
+    ///
+    /// This is solving for `r` in `r² = x`, rounding toward zero.
+    /// The result will satisfy `r² ≤ x < (r+1)²`.
+    ///
+    /// # Panics
+    ///
+    /// Panics if `self` is less than zero:
+    ///
+    /// ```should_panic
+    /// # use num_integer::Roots;
+    /// println!("no imaginary numbers... {}", (-1).sqrt());
+    /// ```
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use num_integer::Roots;
+    ///
+    /// let x: i32 = 12345;
+    /// assert_eq!((x * x).sqrt(), x);
+    /// assert_eq!((x * x + 1).sqrt(), x);
+    /// assert_eq!((x * x - 1).sqrt(), x - 1);
+    /// ```
+    #[inline]
+    fn sqrt(&self) -> Self {
+        self.nth_root(2)
+    }
+
+    /// Returns the truncated principal cube root of an integer --
+    /// `if x >= 0 { ⌊∛x⌋ } else { ⌈∛x⌉ }`
+    ///
+    /// This is solving for `r` in `r³ = x`, rounding toward zero.
+    /// If `x` is positive, the result will satisfy `r³ ≤ x < (r+1)³`.
+    /// If `x` is negative, then `(r-1)³ < x ≤ r³`.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use num_integer::Roots;
+    ///
+    /// let x: i32 = 1234;
+    /// assert_eq!((x * x * x).cbrt(), x);
+    /// assert_eq!((x * x * x + 1).cbrt(), x);
+    /// assert_eq!((x * x * x - 1).cbrt(), x - 1);
+    ///
+    /// assert_eq!((-(x * x * x)).cbrt(), -x);
+    /// assert_eq!((-(x * x * x + 1)).cbrt(), -x);
+    /// assert_eq!((-(x * x * x - 1)).cbrt(), -(x - 1));
+    /// ```
+    #[inline]
+    fn cbrt(&self) -> Self {
+        self.nth_root(3)
+    }
+}
+
+/// Returns the truncated principal square root of an integer --
+/// see [Roots::sqrt](trait.Roots.html#method.sqrt).
+#[inline]
+pub fn sqrt<T: Roots>(x: T) -> T {
+    x.sqrt()
+}
+
+/// Returns the truncated principal cube root of an integer --
+/// see [Roots::cbrt](trait.Roots.html#method.cbrt).
+#[inline]
+pub fn cbrt<T: Roots>(x: T) -> T {
+    x.cbrt()
+}
+
+/// Returns the truncated principal `n`th root of an integer --
+/// see [Roots::nth_root](trait.Roots.html#tymethod.nth_root).
+#[inline]
+pub fn nth_root<T: Roots>(x: T, n: u32) -> T {
+    x.nth_root(n)
+}
+
+macro_rules! signed_roots {
+    ($T:ty, $U:ty) => {
+        impl Roots for $T {
+            #[inline]
+            fn nth_root(&self, n: u32) -> Self {
+                if *self >= 0 {
+                    (*self as $U).nth_root(n) as Self
+                } else {
+                    assert!(n.is_odd(), "even roots of a negative are imaginary");
+                    -((self.wrapping_neg() as $U).nth_root(n) as Self)
+                }
+            }
+
+            #[inline]
+            fn sqrt(&self) -> Self {
+                assert!(*self >= 0, "the square root of a negative is imaginary");
+                (*self as $U).sqrt() as Self
+            }
+
+            #[inline]
+            fn cbrt(&self) -> Self {
+                if *self >= 0 {
+                    (*self as $U).cbrt() as Self
+                } else {
+                    -((self.wrapping_neg() as $U).cbrt() as Self)
+                }
+            }
+        }
+    };
+}
+
+signed_roots!(i8, u8);
+signed_roots!(i16, u16);
+signed_roots!(i32, u32);
+signed_roots!(i64, u64);
+#[cfg(has_i128)]
+signed_roots!(i128, u128);
+signed_roots!(isize, usize);
+
+#[inline]
+fn fixpoint<T, F>(mut x: T, f: F) -> T
+where
+    T: Integer + Copy,
+    F: Fn(T) -> T,
+{
+    let mut xn = f(x);
+    while x < xn {
+        x = xn;
+        xn = f(x);
+    }
+    while x > xn {
+        x = xn;
+        xn = f(x);
+    }
+    x
+}
+
+#[inline]
+fn bits<T>() -> u32 {
+    8 * mem::size_of::<T>() as u32
+}
+
+#[inline]
+fn log2<T: PrimInt>(x: T) -> u32 {
+    debug_assert!(x > T::zero());
+    bits::<T>() - 1 - x.leading_zeros()
+}
+
+macro_rules! unsigned_roots {
+    ($T:ident) => {
+        impl Roots for $T {
+            #[inline]
+            fn nth_root(&self, n: u32) -> Self {
+                fn go(a: $T, n: u32) -> $T {
+                    // Specialize small roots
+                    match n {
+                        0 => panic!("can't find a root of degree 0!"),
+                        1 => return a,
+                        2 => return a.sqrt(),
+                        3 => return a.cbrt(),
+                        _ => (),
+                    }
+
+                    // The root of values less than 2ⁿ can only be 0 or 1.
+                    if bits::<$T>() <= n || a < (1 << n) {
+                        return (a > 0) as $T;
+                    }
+
+                    if bits::<$T>() > 64 {
+                        // 128-bit division is slow, so do a bitwise `nth_root` until it's small enough.
+                        return if a <= core::u64::MAX as $T {
+                            (a as u64).nth_root(n) as $T
+                        } else {
+                            let lo = (a >> n).nth_root(n) << 1;
+                            let hi = lo + 1;
+                            // 128-bit `checked_mul` also involves division, but we can't always
+                            // compute `hiⁿ` without risking overflow.  Try to avoid it though...
+                            if hi.next_power_of_two().trailing_zeros() * n >= bits::<$T>() {
+                                match checked_pow(hi, n as usize) {
+                                    Some(x) if x <= a => hi,
+                                    _ => lo,
+                                }
+                            } else {
+                                if hi.pow(n) <= a {
+                                    hi
+                                } else {
+                                    lo
+                                }
+                            }
+                        };
+                    }
+
+                    #[cfg(feature = "std")]
+                    #[inline]
+                    fn guess(x: $T, n: u32) -> $T {
+                        // for smaller inputs, `f64` doesn't justify its cost.
+                        if bits::<$T>() <= 32 || x <= core::u32::MAX as $T {
+                            1 << ((log2(x) + n - 1) / n)
+                        } else {
+                            ((x as f64).ln() / f64::from(n)).exp() as $T
+                        }
+                    }
+
+                    #[cfg(not(feature = "std"))]
+                    #[inline]
+                    fn guess(x: $T, n: u32) -> $T {
+                        1 << ((log2(x) + n - 1) / n)
+                    }
+
+                    // https://en.wikipedia.org/wiki/Nth_root_algorithm
+                    let n1 = n - 1;
+                    let next = |x: $T| {
+                        let y = match checked_pow(x, n1 as usize) {
+                            Some(ax) => a / ax,
+                            None => 0,
+                        };
+                        (y + x * n1 as $T) / n as $T
+                    };
+                    fixpoint(guess(a, n), next)
+                }
+                go(*self, n)
+            }
+
+            #[inline]
+            fn sqrt(&self) -> Self {
+                fn go(a: $T) -> $T {
+                    if bits::<$T>() > 64 {
+                        // 128-bit division is slow, so do a bitwise `sqrt` until it's small enough.
+                        return if a <= core::u64::MAX as $T {
+                            (a as u64).sqrt() as $T
+                        } else {
+                            let lo = (a >> 2u32).sqrt() << 1;
+                            let hi = lo + 1;
+                            if hi * hi <= a {
+                                hi
+                            } else {
+                                lo
+                            }
+                        };
+                    }
+
+                    if a < 4 {
+                        return (a > 0) as $T;
+                    }
+
+                    #[cfg(feature = "std")]
+                    #[inline]
+                    fn guess(x: $T) -> $T {
+                        (x as f64).sqrt() as $T
+                    }
+
+                    #[cfg(not(feature = "std"))]
+                    #[inline]
+                    fn guess(x: $T) -> $T {
+                        1 << ((log2(x) + 1) / 2)
+                    }
+
+                    // https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method
+                    let next = |x: $T| (a / x + x) >> 1;
+                    fixpoint(guess(a), next)
+                }
+                go(*self)
+            }
+
+            #[inline]
+            fn cbrt(&self) -> Self {
+                fn go(a: $T) -> $T {
+                    if bits::<$T>() > 64 {
+                        // 128-bit division is slow, so do a bitwise `cbrt` until it's small enough.
+                        return if a <= core::u64::MAX as $T {
+                            (a as u64).cbrt() as $T
+                        } else {
+                            let lo = (a >> 3u32).cbrt() << 1;
+                            let hi = lo + 1;
+                            if hi * hi * hi <= a {
+                                hi
+                            } else {
+                                lo
+                            }
+                        };
+                    }
+
+                    if bits::<$T>() <= 32 {
+                        // Implementation based on Hacker's Delight `icbrt2`
+                        let mut x = a;
+                        let mut y2 = 0;
+                        let mut y = 0;
+                        let smax = bits::<$T>() / 3;
+                        for s in (0..smax + 1).rev() {
+                            let s = s * 3;
+                            y2 *= 4;
+                            y *= 2;
+                            let b = 3 * (y2 + y) + 1;
+                            if x >> s >= b {
+                                x -= b << s;
+                                y2 += 2 * y + 1;
+                                y += 1;
+                            }
+                        }
+                        return y;
+                    }
+
+                    if a < 8 {
+                        return (a > 0) as $T;
+                    }
+                    if a <= core::u32::MAX as $T {
+                        return (a as u32).cbrt() as $T;
+                    }
+
+                    #[cfg(feature = "std")]
+                    #[inline]
+                    fn guess(x: $T) -> $T {
+                        (x as f64).cbrt() as $T
+                    }
+
+                    #[cfg(not(feature = "std"))]
+                    #[inline]
+                    fn guess(x: $T) -> $T {
+                        1 << ((log2(x) + 2) / 3)
+                    }
+
+                    // https://en.wikipedia.org/wiki/Cube_root#Numerical_methods
+                    let next = |x: $T| (a / (x * x) + x * 2) / 3;
+                    fixpoint(guess(a), next)
+                }
+                go(*self)
+            }
+        }
+    };
+}
+
+unsigned_roots!(u8);
+unsigned_roots!(u16);
+unsigned_roots!(u32);
+unsigned_roots!(u64);
+#[cfg(has_i128)]
+unsigned_roots!(u128);
+unsigned_roots!(usize);
diff --git a/tests/average.rs b/tests/average.rs
new file mode 100644
index 0000000..9fd8cf1
--- /dev/null
+++ b/tests/average.rs
@@ -0,0 +1,100 @@
+extern crate num_integer;
+extern crate num_traits;
+
+macro_rules! test_average {
+    ($I:ident, $U:ident) => {
+        mod $I {
+            mod ceil {
+                use num_integer::Average;
+
+                #[test]
+                fn same_sign() {
+                    assert_eq!((14 as $I).average_ceil(&16), 15 as $I);
+                    assert_eq!((14 as $I).average_ceil(&17), 16 as $I);
+
+                    let max = $crate::std::$I::MAX;
+                    assert_eq!((max - 3).average_ceil(&(max - 1)), max - 2);
+                    assert_eq!((max - 3).average_ceil(&(max - 2)), max - 2);
+                }
+
+                #[test]
+                fn different_sign() {
+                    assert_eq!((14 as $I).average_ceil(&-4), 5 as $I);
+                    assert_eq!((14 as $I).average_ceil(&-5), 5 as $I);
+
+                    let min = $crate::std::$I::MIN;
+                    let max = $crate::std::$I::MAX;
+                    assert_eq!(min.average_ceil(&max), 0 as $I);
+                }
+            }
+
+            mod floor {
+                use num_integer::Average;
+
+                #[test]
+                fn same_sign() {
+                    assert_eq!((14 as $I).average_floor(&16), 15 as $I);
+                    assert_eq!((14 as $I).average_floor(&17), 15 as $I);
+
+                    let max = $crate::std::$I::MAX;
+                    assert_eq!((max - 3).average_floor(&(max - 1)), max - 2);
+                    assert_eq!((max - 3).average_floor(&(max - 2)), max - 3);
+                }
+
+                #[test]
+                fn different_sign() {
+                    assert_eq!((14 as $I).average_floor(&-4), 5 as $I);
+                    assert_eq!((14 as $I).average_floor(&-5), 4 as $I);
+
+                    let min = $crate::std::$I::MIN;
+                    let max = $crate::std::$I::MAX;
+                    assert_eq!(min.average_floor(&max), -1 as $I);
+                }
+            }
+        }
+
+        mod $U {
+            mod ceil {
+                use num_integer::Average;
+
+                #[test]
+                fn bounded() {
+                    assert_eq!((14 as $U).average_ceil(&16), 15 as $U);
+                    assert_eq!((14 as $U).average_ceil(&17), 16 as $U);
+                }
+
+                #[test]
+                fn overflow() {
+                    let max = $crate::std::$U::MAX;
+                    assert_eq!((max - 3).average_ceil(&(max - 1)), max - 2);
+                    assert_eq!((max - 3).average_ceil(&(max - 2)), max - 2);
+                }
+            }
+
+            mod floor {
+                use num_integer::Average;
+
+                #[test]
+                fn bounded() {
+                    assert_eq!((14 as $U).average_floor(&16), 15 as $U);
+                    assert_eq!((14 as $U).average_floor(&17), 15 as $U);
+                }
+
+                #[test]
+                fn overflow() {
+                    let max = $crate::std::$U::MAX;
+                    assert_eq!((max - 3).average_floor(&(max - 1)), max - 2);
+                    assert_eq!((max - 3).average_floor(&(max - 2)), max - 3);
+                }
+            }
+        }
+    };
+}
+
+test_average!(i8, u8);
+test_average!(i16, u16);
+test_average!(i32, u32);
+test_average!(i64, u64);
+#[cfg(has_i128)]
+test_average!(i128, u128);
+test_average!(isize, usize);
diff --git a/tests/roots.rs b/tests/roots.rs
new file mode 100644
index 0000000..f85f9e0
--- /dev/null
+++ b/tests/roots.rs
@@ -0,0 +1,272 @@
+extern crate num_integer;
+extern crate num_traits;
+
+use num_integer::Roots;
+use num_traits::checked_pow;
+use num_traits::{AsPrimitive, PrimInt, Signed};
+use std::f64::MANTISSA_DIGITS;
+use std::fmt::Debug;
+use std::mem;
+
+trait TestInteger: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static {}
+
+impl<T> TestInteger for T where T: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static {}
+
+/// Check that each root is correct
+///
+/// If `x` is positive, check `rⁿ ≤ x < (r+1)ⁿ`.
+/// If `x` is negative, check `(r-1)ⁿ < x ≤ rⁿ`.
+fn check<T>(v: &[T], n: u32)
+where
+    T: TestInteger,
+{
+    for i in v {
+        let rt = i.nth_root(n);
+        // println!("nth_root({:?}, {}) = {:?}", i, n, rt);
+        if n == 2 {
+            assert_eq!(rt, i.sqrt());
+        } else if n == 3 {
+            assert_eq!(rt, i.cbrt());
+        }
+        if *i >= T::zero() {
+            let rt1 = rt + T::one();
+            assert!(rt.pow(n) <= *i);
+            if let Some(x) = checked_pow(rt1, n as usize) {
+                assert!(*i < x);
+            }
+        } else {
+            let rt1 = rt - T::one();
+            assert!(rt < T::zero());
+            assert!(*i <= rt.pow(n));
+            if let Some(x) = checked_pow(rt1, n as usize) {
+                assert!(x < *i);
+            }
+        };
+    }
+}
+
+/// Get the maximum value that will round down as `f64` (if any),
+/// and its successor that will round up.
+///
+/// Important because the `std` implementations cast to `f64` to
+/// get a close approximation of the roots.
+fn mantissa_max<T>() -> Option<(T, T)>
+where
+    T: TestInteger,
+{
+    let bits = if T::min_value().is_zero() {
+        8 * mem::size_of::<T>()
+    } else {
+        8 * mem::size_of::<T>() - 1
+    };
+    if bits > MANTISSA_DIGITS as usize {
+        let rounding_bit = T::one() << (bits - MANTISSA_DIGITS as usize - 1);
+        let x = T::max_value() - rounding_bit;
+
+        let x1 = x + T::one();
+        let x2 = x1 + T::one();
+        assert!(x.as_() < x1.as_());
+        assert_eq!(x1.as_(), x2.as_());
+
+        Some((x, x1))
+    } else {
+        None
+    }
+}
+
+fn extend<T>(v: &mut Vec<T>, start: T, end: T)
+where
+    T: TestInteger,
+{
+    let mut i = start;
+    while i < end {
+        v.push(i);
+        i = i + T::one();
+    }
+    v.push(i);
+}
+
+fn extend_shl<T>(v: &mut Vec<T>, start: T, end: T, mask: T)
+where
+    T: TestInteger,
+{
+    let mut i = start;
+    while i != end {
+        v.push(i);
+        i = (i << 1) & mask;
+    }
+}
+
+fn extend_shr<T>(v: &mut Vec<T>, start: T, end: T)
+where
+    T: TestInteger,
+{
+    let mut i = start;
+    while i != end {
+        v.push(i);
+        i = i >> 1;
+    }
+}
+
+fn pos<T>() -> Vec<T>
+where
+    T: TestInteger,
+    i8: AsPrimitive<T>,
+{
+    let mut v: Vec<T> = vec![];
+    if mem::size_of::<T>() == 1 {
+        extend(&mut v, T::zero(), T::max_value());
+    } else {
+        extend(&mut v, T::zero(), i8::max_value().as_());
+        extend(
+            &mut v,
+            T::max_value() - i8::max_value().as_(),
+            T::max_value(),
+        );
+        if let Some((i, j)) = mantissa_max::<T>() {
+            v.push(i);
+            v.push(j);
+        }
+        extend_shl(&mut v, T::max_value(), T::zero(), !T::min_value());
+        extend_shr(&mut v, T::max_value(), T::zero());
+    }
+    v
+}
+
+fn neg<T>() -> Vec<T>
+where
+    T: TestInteger + Signed,
+    i8: AsPrimitive<T>,
+{
+    let mut v: Vec<T> = vec![];
+    if mem::size_of::<T>() <= 1 {
+        extend(&mut v, T::min_value(), T::zero());
+    } else {
+        extend(&mut v, i8::min_value().as_(), T::zero());
+        extend(
+            &mut v,
+            T::min_value(),
+            T::min_value() - i8::min_value().as_(),
+        );
+        if let Some((i, j)) = mantissa_max::<T>() {
+            v.push(-i);
+            v.push(-j);
+        }
+        extend_shl(&mut v, -T::one(), T::min_value(), !T::zero());
+        extend_shr(&mut v, T::min_value(), -T::one());
+    }
+    v
+}
+
+macro_rules! test_roots {
+    ($I:ident, $U:ident) => {
+        mod $I {
+            use check;
+            use neg;
+            use num_integer::Roots;
+            use pos;
+            use std::mem;
+
+            #[test]
+            #[should_panic]
+            fn zeroth_root() {
+                (123 as $I).nth_root(0);
+            }
+
+            #[test]
+            fn sqrt() {
+                check(&pos::<$I>(), 2);
+            }
+
+            #[test]
+            #[should_panic]
+            fn sqrt_neg() {
+                (-123 as $I).sqrt();
+            }
+
+            #[test]
+            fn cbrt() {
+                check(&pos::<$I>(), 3);
+            }
+
+            #[test]
+            fn cbrt_neg() {
+                check(&neg::<$I>(), 3);
+            }
+
+            #[test]
+            fn nth_root() {
+                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
+                let pos = pos::<$I>();
+                for n in 4..bits {
+                    check(&pos, n);
+                }
+            }
+
+            #[test]
+            fn nth_root_neg() {
+                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
+                let neg = neg::<$I>();
+                for n in 2..bits / 2 {
+                    check(&neg, 2 * n + 1);
+                }
+            }
+
+            #[test]
+            fn bit_size() {
+                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
+                assert_eq!($I::max_value().nth_root(bits - 1), 2);
+                assert_eq!($I::max_value().nth_root(bits), 1);
+                assert_eq!($I::min_value().nth_root(bits), -2);
+                assert_eq!(($I::min_value() + 1).nth_root(bits), -1);
+            }
+        }
+
+        mod $U {
+            use check;
+            use num_integer::Roots;
+            use pos;
+            use std::mem;
+
+            #[test]
+            #[should_panic]
+            fn zeroth_root() {
+                (123 as $U).nth_root(0);
+            }
+
+            #[test]
+            fn sqrt() {
+                check(&pos::<$U>(), 2);
+            }
+
+            #[test]
+            fn cbrt() {
+                check(&pos::<$U>(), 3);
+            }
+
+            #[test]
+            fn nth_root() {
+                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
+                let pos = pos::<$I>();
+                for n in 4..bits {
+                    check(&pos, n);
+                }
+            }
+
+            #[test]
+            fn bit_size() {
+                let bits = 8 * mem::size_of::<$U>() as u32;
+                assert_eq!($U::max_value().nth_root(bits - 1), 2);
+                assert_eq!($U::max_value().nth_root(bits), 1);
+            }
+        }
+    };
+}
+
+test_roots!(i8, u8);
+test_roots!(i16, u16);
+test_roots!(i32, u32);
+test_roots!(i64, u64);
+#[cfg(has_i128)]
+test_roots!(i128, u128);
+test_roots!(isize, usize);