Comments (8)
Our Decimal implementation relies internally on the Fraction type, so the most efficient way would be to figure out how to convert f64
into a Fraction
and then initialise the Decimal
via its constructor, e.g. GenericDecimal(fraction, fixed_precision)
.
The most flexible (and easy) way I have found initially was to convert f32/64 into a string and then convert it into a fraction. It's implemented here - https://github.com/dnsl48/fraction/blob/master/src/fraction/mod.rs#L453
I considered some ways to optimise that via working with float binary representation, but those Rust APIs weren't stable back then and later I didn't find time to look into it again. Perhaps that could be a way to optimise such conversion.
If you come up with any other ideas, or a more efficient implementation, please let us know. PRs are very welcome too! :)
from fraction.
from fraction.
This algorithm seems to work: https://math.stackexchange.com/a/1049723/17452 .
Here is demo code in Python (I'll try converting that to Rust with the num traits soon, it's a bit tricky because the source f64 needs to be converted to something of type T):
In [6]: def to_frac(f):
...: p = 0
...: while True:
...: if abs(round(f) - f) < 2e-16:
...: break
...: p += 1
...: f *= 10**p
...: # end while
...: g = gcd(int(f), 10**p)
...: print(g)
...: num = f/g
...: den = (10**p)/g
...: print(num, den)
...:
(...)
In [10]: to_frac(pi)
1
3141592653589793.0 100000.0
In [11]: to_frac(0.5)
5
1.0 2.0
In [12]: to_frac(128959848.1457456)
16
8.0599905091091e+16 625.0
In [13]
Here is some (broken) Rust code that I'm working on. I need to figure out how to use p
directly (and bypass the p_i
variable), and convert new_src
to a type T
as well...
pub fn from_decimal_f64(src: f64) -> Result<Self, ParseError>
where
T: CheckedAdd + CheckedMul + FromPrimitive,
{
let sign = if src < 0.0 { Sign::Minus } else { Sign::Plus };
// Using https://math.stackexchange.com/a/1049723/17452
// Find the max precision of this number
let mut p = T::zero();
let mut p_i = 0_u32;
let mut new_src = src;
loop {
// Multiply by the precision
new_src *= 10_f64.powi(p_i as i32);
if (new_src.round() - new_src).abs() < 2e-16 {
// Yay, we've found the precision of this number
break;
}
p = p + T::one();
p_i += 1;
}
// Compute the GCD
let src_u = T::from(new_src);
let denom = 10_u128.pow(p_i);
let g = gcd(src_u, p_i.into());
let num = src_u / g;
let den = p_i.into() / g;
Ok(GenericFraction::Rational(sign, Ratio::new(num.into(), den)))
}
from fraction.
Yes, that looks like the most straightforward way to do it, but it has a flaw.
// Multiply by the precision
new_src *= 10_f64.powi(p_i as i32);
Here might be an overflow for huge numbers, so we can only do that if we're sure there's enough space in f64 for this in-place computation.
from fraction.
Here might be an overflow for huge numbers, so we can only do that if we're sure there's enough space in f64 for this in-place computation.
I guess that's actually an edge case, so we may fallback to the stringify version if that happens. That could allow us to be more efficient in general and still handle big numbers gracefully.
from fraction.
Cool, I've got this implemented, and criterion says it's a pretty significant improvement: 75% speed up.
Running target/release/deps/bench_fraction-2f3e4b9d43259cec
Gnuplot not found, using plotters backend
Decimal u128/u16 init time: [112.55 ns 112.95 ns 113.36 ns]
change: [-77.847% -77.728% -77.609%] (p = 0.00 < 0.05)
Performance has improved.
Found 3 outliers among 100 measurements (3.00%)
3 (3.00%) high mild
Decimal i64/u16 init time: [107.26 ns 107.83 ns 108.49 ns]
change: [-76.184% -75.792% -75.481%] (p = 0.00 < 0.05)
Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
2 (2.00%) high mild
2 (2.00%) high severe
Just gotta clean things up and I'll open a PR. I'll bump it to version 0.7.1 if that's cool, although maybe it's worth using 0.8?
Edit: Found a bug in my implementation which I will fix tomorrow.
from fraction.
That appears very promising!
I'll bump it to version 0.7.1 if that's cool, although maybe it's worth using 0.8?
I would suggest to do it as 0.7.1
. This does not break any backward compatibility. Adding new API should be fine because we're still within the version 0.*
, so semantic versioning shouldn't prevent us from doing that.
from fraction.
Released with 0.8.0
.
Thank you very much for the contribution!
from fraction.
Related Issues (20)
- Add better unicode support (Fraction slash/division slash) HOT 8
- eligible for funding via thanks.dev HOT 2
- Completing implemention of `identities` module from `num_traits` HOT 3
- Add support for ruint? HOT 1
- FromStr trait support + Parse fractions HOT 4
- How to convert to `f32` and `f64` numeric types HOT 1
- .pow() and .root() functions for fraction types HOT 3
- Serde support? HOT 2
- Fraction::from_str can fail with overflow if fractional part ends with too many zeroes HOT 3
- Weird huge values when getting the denominator of a fraction HOT 9
- Serialization support for DynaInt HOT 1
- Error: trait bounds other than `Sized` on const fn parameters are unstable HOT 2
- What does it mean that a value cannot be represented by `Ratio<T>`? HOT 2
- Fraction ceil and floor round negative fraction "the wrong way" HOT 1
- how do you conver a GenericFraction into a float? HOT 5
- Is there a list of methods that floats have that aren't impled for fractions HOT 2
- Do not simplify fractions HOT 1
- How should I handle consts? HOT 1
- Add From for f64 and f32 HOT 6
- Trait bounds were not satisfied with nalgebra HOT 2
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 fraction.