Comments (9)
From @hauleth on July 1, 2016 12:0
It would be great!
from num-integer.
From @koverstreet on July 5, 2016 21:49
I'd like to see these implemented as generics over ring/field traits. Especially with specialization coming soon (or has it landed?), this is really the right way to go.
from num-integer.
From @ejmahler on July 6, 2016 5:3
Could you give a really quick example, to illustrate what you're picturing?
from num-integer.
From @koverstreet on July 6, 2016 5:11
Along the lines of a numeric tower (read up on Haskell's if you're curious) - except, I have no intention of trying to do a full numeric tower because no one seems to be able to get that right.
All I'm thinking for now is - define traits for Group, Ring, Field, etc. so we have a place to stick generic algorithms. I tend to think we shouldn't even have the various traits inherit from each other, at least for now - BigUint can always inherit from each of Group/Ring/whatever.
Basically keep it as simple as possible for now - nothing more than a place to stick things that should work on anything that's a group/ring/field.
gcd(), lcm()... perhaps a few others should then become generic functions on whatever the appropriate trait is, with specializations where it matters for performance.
from num-integer.
From @hauleth on July 7, 2016 22:44
I think that having additional structures defined using typenum would feel more "natural".
from num-integer.
From @ejmahler on July 17, 2016 12:50
I understand the high-level picture of what you're looking for, @koverstreet . A set of composable traits that can be included and maybe specialized for each type.
So starting small for now with jsut a "ring" trait that implements all sorts of modular arithmetic functions on this -- what's the correct way to implement this? I wouldn't call myself a rust expert yet so I need some guidance.
The following is what my mind jumps to, but this obviously doesn't compile because you can't implement a trait in terms of another trait -- you need a concrete type. But if we implement this trait for all the primitive types explicitly, that defeats the point of composition of these traits, doesn't it?
pub trait Ring {
fn pow_mod(&self, exponent: &Self, modulo: &Self) -> Self;
}
impl Ring for Integer {
fn pow_mod(&self, exponent: &Self, modulo: &Self) -> Self {
//...
}
}
We could implement these as standalone template functions:
pub fn pow_mod<T: Integer + Copy>(.......
But again that kind of defeats the point. So how should this be done?
from num-integer.
From @vks on March 17, 2017 17:16
I would like to implement some related number theory functions: modular exponentiation, extended euclid's algorithm, modular multiplicative inverse.
I implemented all of these some time ago here.
from num-integer.
Personally, I think it would be fine to do these without the more ambitious trait categories, but I'm also open to that if someone wants to try it.
from num-integer.
FWIW, I created num-modular
and num-prime
crates for the same purpose. They accept generic parameters and they're decently optimized.
Note that the implementation for num_bigint::BigUint
is very naive, because advanced implementations need num_bigint
to expose some of the inner APIs.
from num-integer.
Related Issues (17)
- Contribute is_power_of_ten? HOT 5
- Increment and decrement methods for Integer trait? HOT 5
- test_lcm_overflow fails on sparc64 HOT 2
- Target asmjs-unknown-emscripten fails to compile HOT 1
- Why hiding field of ExtendedGcd? HOT 3
- Make std a feature, using `#![no_std]` otherwise
- Integer::extended_gcd should not permit unsigned value. HOT 5
- Integer::divides is not marked deprecated.
- `Integer::next_multiple_of` unexpectedly fails on `MIN` and `-1`
- is_multiple behaviour with 0 HOT 1
- Build error building in docker ekidd/rust-musl-builder --target x86_64-unknown-linux-musl HOT 6
- `Integer::gcd()` returns negative value HOT 1
- `binomial(n, k)` for `n < 0`
- Add checked_* for div and mod functions HOT 2
- Wrapper types? HOT 5
- ERROR: python3-cryptography-37.0.4-r0 do_unpack: Bitbake Fetcher Error: UnpackError HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from num-integer.