rust-num / num-integer Goto Github PK

View Code? Open in Web Editor NEW

178.0 4.0 45.0 1.35 MB

Integer trait and functions for Rust

License: Apache License 2.0

Shell 2.05% Rust 97.95%

rust num-integer

num-integer's Introduction

num-integer

Integer trait and functions for Rust.

Usage

Add this to your Cargo.toml:

[dependencies]
num-integer = "0.1"

Features

This crate can be used without the standard library (#![no_std]) by disabling the default std feature. Use this in Cargo.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.

Releases

Release notes are available in RELEASES.md.

Compatibility

The num-integer crate is tested for rustc 1.31 and greater.

License

Licensed under either of

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.

num-integer's People

Contributors

Stargazers

Watchers

num-integer's Issues

Make std a feature, using `#![no_std]` otherwise

Depends on rust-num/num-traits#16, cc rust-num/num#216.

`binomial(n, k)` for `n < 0`

This would be a breaking change either way, but binomial(n, k) with n < 0 should either produce (-1).pow(k) * binomial(k - n - 1, k) = n(n-1)...(n-k +1)/k! or n and k should be unsigned. See eg https://en.wikipedia.org/wiki/Binomial_coefficient#Generalization_and_connection_to_the_binomial_series.

Integer::divides is not marked deprecated.

The doc comment of Integer::divides is Deprecated, use is_multiple_of instead. but it does not have deprecated attribute.

Contribute is_power_of_ten?

I'd like to contribute a high performance implementation of is_power_of_ten. Is that an appropriate function for this crate?

`Integer::gcd()` returns negative value

The docs for Integer::gcd() state "The result is always non-negative", but this is not the case when calculating the gcd of zero and the minimum value of a signed integer type (i8, i16, ...).

use num::Integer;

fn main() {
    assert!(i8::MIN.gcd(&0).is_negative()); // returns i8::MIN
}

The reason for this are the following lines in the impl_integer_for_isize macro, which in the above example result in .abs() being called on i8::MIN, resulting in a panic in debug mode, and the value i8::MIN being returned in release mode.

Don't know if this issue can be elegantly fixed, since the actual result does not fit in the signed type, but maybe it should at least be mentioned in the documentation for the gcd method.

Integer::extended_gcd should not permit unsigned value.

This code fails to get the y value, with the error 'attempt to subtract with overflow'.

#[test]
fn extended_gcd_test(){
  use num_integer::Integer;
  let _x = 10.extended_gcd(&4);
  let _y = 10_u32.extended_gcd(&4);
}

Increment and decrement methods for Integer trait?

From @L117 on June 22, 2017 9:55

When dealing with primitive integers it's fast and easy to increment/decrement with x += 1;/x -= 1;, but with BigInt/BigUint it wastes an allocation and/or becomes tedious (Imagine calling One::one, From::from and defining static ONE). So such methods could come in handy.

Copied from original issue: rust-num/num#307

is_multiple behaviour with 0

Currently, running BigUint::zero().is_multiple_of(&BigUint::zero()) panics, since the implementation attemps to perform a modular division

num-integer/src/lib.rs

Line 888 in d5267dc

*self % *other == 0

However, 0 is indeed a multiple of 0 and as such true should be returned.
Since this is the only edge case, this can be fixed very easily, and I have opened a pull request (#47) accordingly.

test_lcm_overflow fails on sparc64

The build of the Debian package of num-integer 0.1.41 failed test_lcm_overflow on sparc64, it succeeded on the other Debian architectures.
Test log can be found at https://buildd.debian.org/status/fetch.php?pkg=rust-num-integer&arch=sparc64&ver=0.1.41-1&stamp=1562827854&raw=0
The relevant output with the backtrace is:

---- test_lcm_overflow stdout ----
thread 'test_lcm_overflow' panicked at 'attempt to multiply with overflow', src/lib.rs:871:27
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
   1: std::sys_common::backtrace::print
   2: std::panicking::default_hook::{{closure}}
   3: std::panicking::default_hook
   4: std::panicking::rust_panic_with_hook
   5: std::panicking::continue_panic_fmt
   6: rust_begin_unwind
   7: core::panicking::panic_fmt
   8: core::panicking::panic
   9: <u64 as num_integer::Integer>::gcd_lcm
             at src/lib.rs:871
  10: <u64 as num_integer::Integer>::lcm
             at src/lib.rs:860
  11: num_integer::test_lcm_overflow
             at src/lib.rs:1166
  12: num_integer::test_lcm_overflow::{{closure}}
             at src/lib.rs:1138
  13: core::ops::function::FnOnce::call_once
             at /usr/src/rustc-1.34.2/src/libcore/ops/function.rs:231

I took a quick look at the affected code locations, but I'm not too much into the internals and bit widths of the affected integer types.

Add checked_* for div and mod functions

It's very easy to implement the check wrong, most people only check if denominator is 0, but not i32::MIN / -1.

`NonZero*`?

This isn't a follow-up to #63, but it's related. I understand that despite NonZero being stable, its trait-bound isn't, so nothing should be done WRT that.

However, if does get stabilized with that trait-bound, it would be convenient if there was a non-prim counterpart provided by this crate, such as:

use std::hint::unreachable_unchecked;
use num_integer::Integer; // 0.1

pub struct NonZeroInt<T: Integer>(T);
impl<T: Integer> NonZeroInt<T> {
    #[must_use]
    fn new(n: T) -> Option<Self> {
        if n.is_zero() {
            None
        } else {
            Some(Self(n))
        }
    }
    #[must_use]
    unsafe fn new_unchecked(n: T) -> Self {
        match Self::new(n) {
            Some(n) => n,
            _ => unsafe { unreachable_unchecked() },
        }
    }
    #[must_use]
    fn get(self) -> T {
        self.0
    }
}

// (optional)
use core::ops::Deref;
impl<T: Integer> Deref for NonZeroInt<T> {
    type Target = T;
    fn deref(&self) -> &Self::Target {
        &self.0
    }
}

Implement more number theory functions

From @ejmahler on June 30, 2016 22:59

In num_integer, I see an implementation of gcd.

I would like to implement some related number theory functions: modular exponentiation, extended euclid's algorithm, modular multiplicative inverse.

I'm also interested in prime factorization, euler's totient function, primitive roots, etc, but these might be too much.

Is there an interest for these functions in this library, to go alongside gcd? I'd be happy to implement the functions, tests, documentation, etc, I just want to make sure there's interest from the maintainers before I begin.

Copied from original issue: rust-num/num#202

Wrapper types?

Taking inspiration from NonZero<T> and Type-driven parsing, what if this crate (or a separate one, for organizing) provided wrappers for specific numeric properties?

Strawman examples (not tested as compilable):

#[derive(Deref)]
struct Even<T: Integer>(T);

impl<T: Integer> even for Even{
    fn new(x: T) -> Option<Self> {
        if x.is_even() {Some(Self(x))} else {None}
    }
}
// assume `Odd` is defined similarly...

impl<T> Add for Even<T> {
    // even + even = even
    fn add(self, &Self) -> Self
    // even + odd = odd
    fn add(self, &Odd) -> Odd
}
// etc... assume Odd also has similar methods which follow the theorems of math

New fns could be defined that take advantage of such types. If a fn requires a Prime to work properly and safely, it'll no longer have to check primality by itself!

The compiler could optimize code using Even or Odd to have the same size and alignment as Option<Even | Odd> (because LSB is unused).

Existing fns could use these types to guarantee stuff such as

fn sqrt(n: Square<u64>) -> u32

// this equality will be satisfied for all `Square`s!
assert_eq!(sqrt(Square::new(4).unwrap()).pow(2), 4)

If num provided such types, there would be less crates implementing their own wrappers, or worse, doing redundant expensive checks:

use crate1::Prime1;
use crate2::Prime2;
use crate3::CheckedPrime;

crate1::some_fn(Prime1::new(5).unwrap())
crate2::another_fn(Prime2::new(5).unwrap())
crate3::some_fn(CheckedPrime::build(5).unwrap())

If there was 1:

use num_integer::Prime;

let p = Prime::new(5).unwrap();

// assuming all crates have chosen `num` as standard
crate1::new_fn(p)
crate2::yet_another_fn(p)
crate3::foobar_fn(p)

ERROR: python3-cryptography-37.0.4-r0 do_unpack: Bitbake Fetcher Error: UnpackError

Hi Josh Stone @cuviper

Greetings!!

In yocto builds num-integer are being used in python3-cryptography-37.0.4.bb recipe of Yocto langdale branch.
Issue is num-integer-0.1.44.crate is NOT a gzip compressed file.

error log :

For a candidate test sample : ( command sequence can be found in the above error log)

@cuviper can you please guide/provide hint on how to build locally / solve this issue.
Others ( lazy_static-1.4.0.crate) in the recipe are being done without problem.

Regards,
Phanirajkiran

Build error building in docker ekidd/rust-musl-builder --target x86_64-unknown-linux-musl

Hi, one of my dependencies has a dependency on num-integer.

This code compiles fine on mac, ubuntu, and windows when I run cargo build --release but I have been trying to build inside docker image ekidd/rust-musl-builder with cargo build --release --target x86_64-unknown-linux-musl and I get the following error:

Any ideas on how to fix this?

rust@ae0894d6a5f2:~/src$ cargo build --release --target x86_64-unknown-linux-musl
   Compiling num-integer v0.1.44
   Compiling num-traits v0.1.43
   Compiling serde_derive v1.0.136
   Compiling tokio-macros v1.7.0
   Compiling futures-macro v0.3.21
   Compiling proc-macro2-diagnostics v0.9.1
   Compiling time-macros-impl v0.1.2
   Compiling tracing-attributes v0.1.19
error[E0277]: the trait bound `i128: traits::Num` is not satisfied
   --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/roots.rs:136:14
    |
136 |         impl Roots for $T {
    |              ^^^^^ the trait `traits::Num` is not implemented for `i128`
...
170 | signed_roots!(i128, u128);
    | ------------------------- in this macro invocation
    |
note: required by a bound in `Roots`
   --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/roots.rs:9:18
    |
9   | pub trait Roots: Integer {
    |                  ^^^^^^^ required by this bound in `Roots`
    = note: this error originates in the macro `signed_roots` (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0277]: the trait bound `u128: traits::Num` is not satisfied
   --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/roots.rs:204:14
    |
204 |         impl Roots for $T {
    |              ^^^^^ the trait `traits::Num` is not implemented for `u128`
...
390 | unsigned_roots!(u128);
    | --------------------- in this macro invocation
    |
note: required by a bound in `Roots`
   --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/roots.rs:9:18
    |
9   | pub trait Roots: Integer {
    |                  ^^^^^^^ required by this bound in `Roots`
    = note: this error originates in the macro `unsigned_roots` (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0277]: the trait bound `i128: traits::Num` is not satisfied
   --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/lib.rs:409:14
    |
409 |         impl Integer for $T {
    |              ^^^^^^^ the trait `traits::Num` is not implemented for `i128`
...
797 | impl_integer_for_isize!(i128, test_integer_i128);
    | ------------------------------------------------ in this macro invocation
    |
note: required by a bound in `Integer`
   --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/lib.rs:37:28
    |
37  | pub trait Integer: Sized + Num + PartialOrd + Ord + Eq {
    |                            ^^^ required by this bound in `Integer`
    = note: this error originates in the macro `impl_integer_for_isize` (in Nightly builds, run with -Z macro-backtrace for more info)

error[E0277]: the trait bound `u128: traits::Num` is not satisfied
    --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/lib.rs:801:14
     |
801  |         impl Integer for $T {
     |              ^^^^^^^ the trait `traits::Num` is not implemented for `u128`
...
1014 | impl_integer_for_usize!(u128, test_integer_u128);
     | ------------------------------------------------ in this macro invocation
     |
note: required by a bound in `Integer`
    --> /home/rust/.cargo/registry/src/github.com-1ecc6299db9ec823/num-integer-0.1.44/src/lib.rs:37:28
     |
37   | pub trait Integer: Sized + Num + PartialOrd + Ord + Eq {
     |                            ^^^ required by this bound in `Integer`
     = note: this error originates in the macro `impl_integer_for_usize` (in Nightly builds, run with -Z macro-backtrace for more info)

For more information about this error, try `rustc --explain E0277`.
error: could not compile `num-integer` due to 4 previous errors

Why hiding field of ExtendedGcd?

Noticed that there's no way to construct ExtendedGcd from user code (because of hidden field), and I can't implement Integer::extended_gcd (as I can't construct being returned structure) and I have to use your generic implementation of egcd. Perhaps there should be ExtendedGcd::new() constructor?

`Integer::next_multiple_of` unexpectedly fails on `MIN` and `-1`

i8::MIN.next_multiple_of(-1) should return -128 (i8::MIN), but instead panics. The fix for this is to add if self == -1 { return self; } at the top of the method.

I have not checked, but it is certainly worth checking whether a similar situation applies with prev_multiple_of.

This is the only issue with the current implementation of next_multiple_of. It otherwise works as expected.

Target asmjs-unknown-emscripten fails to compile

   Compiling num-integer v0.1.41 (num-integer)
warning: `#[inline]` is ignored on function prototypes
   --> src/lib.rs:260:5
    |
260 |     #[inline]
    |     ^^^^^^^^^
    |
    = note: `#[warn(unused_attributes)]` on by default

Referencing function in another module!
  call void <badref>(i8* %40), !dbg !51
; ModuleID = 'r5a5ydnla8md0lz'
void (i8*)* <badref>
; ModuleID = '
error: could not compile `num-integer`.

Caused by:
  process didn't exit successfully: `rustc --crate-name num_integer src/lib.rs --error-format=json --json=diagnostic-rendered-ansi --crate-type lib --emit=dep-info,metadata,link -C debuginfo=2 --cfg 'feature="default"' --cfg 'feature="std"' -C metadata=f504e2cc341ea776 -C extra-filename=-f504e2cc341ea776 --out-dir num-integer/target/asmjs-unknown-emscripten/debug/deps --target asmjs-unknown-emscripten -C incremental=num-integer/target/asmjs-unknown-emscripten/debug/incremental -L dependency=num-integer/target/asmjs-unknown-emscripten/debug/deps -L dependency=num-integer/target/debug/deps --extern num_traits=num-integer/target/asmjs-unknown-emscripten/debug/deps/libnum_traits-f59bfd1ff0bed9bd.rmeta --cfg has_i128` (signal: 11, SIGSEGV: invalid memory reference)

Poorly I don't know what causes this.