Boom quickly due to infinite precision

[7sDream]

I try this crate because f64's 15 precision is not enough when I wanna use Rust to render some fractal picture.

But because of the infinite precision of BigDecimal, it will become very slow after some iteration, there is a test:

extern crate bigdecimal;

use bigdecimal::BigDecimal;
use std::time::Instant;

fn main() {
    let mut x = BigDecimal::from(1.1);
    for iter in 0..1_000_000 {
        let start = Instant::now();
        x = x.clone() * x;
        let end = Instant::now();
        let usage = end - start;
        println!("iter {} takes {} secs", iter, usage.as_secs() as f32 + usage.subsec_nanos() as f32 / 1.0e9);
    }
}

which shows(use default release profile):

iter 0 takes 0.000001439 secs
iter 1 takes 0.000000622 secs
iter 2 takes 0.000000354 secs
iter 3 takes 0.000002063 secs
iter 4 takes 0.000002645 secs
iter 5 takes 0.000006876 secs
iter 6 takes 0.000012924 secs
iter 7 takes 0.000039836 secs
iter 8 takes 0.000143239 secs
iter 9 takes 0.000382201 secs
iter 10 takes 0.000865692 secs
iter 11 takes 0.001903312 secs
iter 12 takes 0.006370908 secs
iter 13 takes 0.015460448 secs
iter 14 takes 0.04334534 secs
iter 15 takes 0.11174759 secs
iter 16 takes 0.3095196 secs
iter 17 takes 0.8349745 secs
iter 18 takes 2.3625574 secs
iter 19 takes 6.400373 secs
iter 20 takes 17.913374 secs
iter 21 takes 49.185394 secs
iter 22 takes 140.00293 secs

:boom:

Maybe we need a round method or a BigDecimal of fixed precision?

[akubera]

Yikes!

Yeah I was working on a context object that would have user-set precision and rounding methods, standard features of BigDecimal implementations. This is partially implemented in the feature/simple-context branch, but I have not been able to continue working on it (and will not be able to until after I finish my thesis!). If I remember right, precision was only used in the div method essentially limiting repeating numbers. I don't know how much work it would be to check precision in the other operations and clip the underlying int.

It looks like if you got to 22 iterations, it was dealing with the number 1.1^(2²²) ~= 3.2×10¹⁷³⁶¹³... I'm glad it's computable, but I think we'll keep that out of the untitests for now.

[7sDream]

I have no idea for the 1.1 case because the integer part become bigger in iteration.

but I now use a stupid (also inefficient) way to trunc at given precision, this make 0.999… case runable(?).

/// trunc BigDecimal `x` at a given precision `p`
fn trunc(x: BigDecimal, p: u32) -> BigDecimal {
    // get the raw bigint and scale e
    let (b, e) = x.as_bigint_and_exponent();
    // extra digit count we will erase
    let extra = e - p as i64;
    return if extra > 0 {
        // convert big int to str(base 10)
        let s = b.to_str_radix(10);
        // str length small then extra means the value is too small to trunc, it becomes zero
        if s.len() - if x.is_negative() {1} else {0} <= extra as usize {
            BigDecimal::zero()
        } else {
            // erase extra digits and now the precision is p now
            let b = BigInt::parse_bytes(&s.as_bytes()[..s.len() - extra as usize], 10).unwrap();
            // built a new BigDecimal from b and p
            BigDecimal::new(b, p as i64)
        }
    } else {
        // if now precision small then or equal with given p, just return it
        x
    }
}

---

0.999… case without trunc

Code

fn main() {
    let mut x: BigDecimal = "0.9999999".parse().unwrap();;
    for iter in 0..30 {
        let start = Instant::now();
        x = &x * &x;
        let end = Instant::now();
        let usage = end - start;
        // we can't pirnt value because it will be a very very long string...
        println!(
            "iter {} takes {} secs",
            iter, usage.as_secs() as f32 + usage.subsec_nanos() as f32 / 1.0e9
        );
    }
}

Output

iter 0 takes 0.000001312 secs
iter 1 takes 0.000000303 secs
iter 2 takes 0.000000271 secs
iter 3 takes 0.000000254 secs
iter 4 takes 0.000001981 secs
iter 5 takes 0.00000267 secs
iter 6 takes 0.00002066 secs
iter 7 takes 0.000012487 secs
iter 8 takes 0.000034567 secs
iter 9 takes 0.00010299 secs
iter 10 takes 0.000313883 secs
iter 11 takes 0.000628928 secs
iter 12 takes 0.001770737 secs
iter 13 takes 0.00656106 secs
iter 14 takes 0.01890613 secs
iter 15 takes 0.045263167 secs
iter 16 takes 0.10588724 secs
iter 17 takes 0.29619893 secs
iter 18 takes 0.79520166 secs
iter 19 takes 2.2273023 secs
iter 20 takes 6.072619 secs
iter 21 takes 16.929794 secs
iter 22 takes 48.151283 secs
iter 23 takes 126.38544 secs
...

0.999… case with the trunc:

Code

fn main() {
    let mut x: BigDecimal = "0.9999999".parse().unwrap();
    for iter in 0..30 {
        let start = Instant::now();
        // x = &x * &x;
        x = trunc(&x * &x, 32);
        let end = Instant::now();
        let usage = end - start;
        println!(
            "iter {} takes {} secs, value = {}",
            iter, usage.as_secs() as f32 + usage.subsec_nanos() as f32 / 1.0e9, x
        );
    }
}

Output

iter 0 takes 0.000001637 secs, value = 0.99999980000001
iter 1 takes 0.000000422 secs, value = 0.9999996000000599999960000001
iter 2 takes 0.000002447 secs, value = 0.99999920000027999994400000699999
iter 3 takes 0.000001701 secs, value = 0.99999840000119999944000018199993
iter 4 takes 0.000001517 secs, value = 0.99999680000495999504000359599793
iter 5 takes 0.000001312 secs, value = 0.99999360002015995833606353752364
// middle part omitted
iter 25 takes 0.00000165 secs, value = 0.00121758397078202264962550325666
iter 26 takes 0.000001691 secs, value = 0.00000148251072590531738533343796
iter 27 takes 0.000001546 secs, value = 0.00000000000219783805242431109239
iter 28 takes 0.000001363 secs, value = 0.00000000000000000000000483049210
iter 29 takes 0.000000828 secs, value = 0

---

If anyone want to look, there are some tests for trunc function

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn works_for_normal_usage() {
        let x = "1.12345678999".parse().unwrap();
        assert_eq!(
            trunc(x, 3),
            "1.123".parse().unwrap(),
        )
    }

    #[test]
    fn works_for_neg_num() {
        let x = "-1.12345678999".parse().unwrap();
        assert_eq!(
            trunc(x, 3),
            "-1.123".parse().unwrap(),
        )
    }

    #[test]
    fn return_self_when_precision_small_then_given() {
        let x: BigDecimal = "-1.12345678999".parse().unwrap();
        assert_eq!(
            trunc(x.clone(), 32),
            x,
        )
    }

    #[test]
    fn works_for_big_number() {
        let x: BigDecimal = "100000000000000.213213".parse().unwrap();
        assert_eq!(
            trunc(x, 2),
            "100000000000000.21".parse().unwrap(),
        )
    }

    #[test]
    fn works_for_big_neg_number() {
        let x: BigDecimal = "-100000000000000.213213".parse().unwrap();
        assert_eq!(
            trunc(x, 2),
            "-100000000000000.21".parse().unwrap(),
        )
    }

    #[test]
    fn works_for_small_number_trunc_to_zero() {
        let x: BigDecimal = "0.0000001".parse().unwrap();
        for i in 0..7 {
            assert_eq!(
                trunc(x.clone(), i),
                BigDecimal::zero()
            );
        }
        assert_eq!(
            trunc(x.clone(), 8),
            x
        );
    }

    #[test]
    fn works_for_neg_small_number_trunc_to_zero() {
        let x: BigDecimal = "-0.0000001".parse().unwrap();
        for i in 0..7 {
            assert_eq!(
                trunc(x.clone(), i),
                BigDecimal::zero()
            );
        }
        assert_eq!(
            trunc(x.clone(), 8),
            x
        );
    }
}

[akubera]

more efficient method would just be diving the integer by the required power-of-ten; something along the lines of:

    ...
    let extra = e - p as i64;
    if extra > 0 {
        b /= ten_to_the(extra);  // defined somewhere in the crate
        return BigDecimal::new(b, p);
    }

[7sDream]

@akubera I will try this, thank you.