Initialization of Decimal without str?

[dnsl48]

Initialization of Decimal without str?

[dnsl48]

Hi @ChristopherRabotin,

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! :)

[ChristopherRabotin]

Awesome, thanks for the link to the specific part of the code. I'll see if I can find another approach (absolutely no guarantees, you obviously have thought about the problem much more than I have!) Christopher Rabotin.

…

On Tue, Dec 8, 2020, 14:14 Serge Latyntsev ***@***.***> wrote: Hi @ChristopherRabotin <https://github.com/ChristopherRabotin>, 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! :) — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#36 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABEZV2GHVVEP7KGE5CMRC2TST2JKDANCNFSM4URK4N3Q> .

[ChristopherRabotin]

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)))
}

[dnsl48]

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.

[dnsl48]

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.

[ChristopherRabotin]

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.

[dnsl48]

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.

[dnsl48]

Released with 0.8.0.
Thank you very much for the contribution!