hmath/ratio/
convert.rs

1use crate::{Ratio, BigInt, UBigInt};
2use crate::err::ConversionError;
3use crate::utils::gcd_i32;
4use crate::ubigint::convert::_to_scientific_notation;
5use std::str::FromStr;
6
7mod from;
8mod ieee754;
9mod into;
10
11pub use ieee754::{inspect_ieee754_f32, inspect_ieee754_f64};
12
13impl Ratio {
14
15    pub fn from_denom_and_numer(denom: BigInt, numer: BigInt) -> Self {
16        let mut result = Ratio::from_denom_and_numer_raw(denom, numer);
17        result.fit();
18
19        result
20    }
21
22    pub fn from_denom_and_numer_i32(mut denom: i32, mut numer: i32) -> Self {
23        let r = gcd_i32(denom, numer);
24
25        if r != 1 {
26            denom /= r;
27            numer /= r;
28        }
29
30        if denom < 0 {
31            denom *= -1;
32            numer *= -1;
33        }
34
35        Ratio::from_denom_and_numer_raw(BigInt::from_i32(denom), BigInt::from_i32(numer))
36    }
37
38    /// This function does not do any safety checks. Use this function only when you're sure that the properties below are satisfied.
39    ///
40    /// - `denom` and `numer` are coprime
41    /// - `denom` is positive
42    /// - `denom` is 1 when `numer` is 0
43    pub fn from_denom_and_numer_raw(denom: BigInt, numer: BigInt) -> Self {
44        Ratio { denom, numer }
45    }
46
47    pub fn from_bi(n: BigInt) -> Self {
48        #[cfg(test)] assert!(n.is_valid());
49
50        // Safety: 1 and another integer are always coprime. 1 is positive. denom is 1 when n is 0.
51        Ratio::from_denom_and_numer_raw(BigInt::one(), n)
52    }
53
54    pub fn from_ubi(n: UBigInt) -> Self {
55        #[cfg(test)] assert!(n.is_valid());
56
57        // Safety: 1 and another integer are always coprime. 1 is positive. denom is 1 when n is 0.
58        Ratio::from_denom_and_numer_raw(BigInt::one(), BigInt::from_ubi(n, false))
59    }
60
61    pub fn from_i32(n: i32) -> Self {
62        // Safety: 1 and another integer are always coprime. 1 is positive. denom is 1 when n is 0.
63        Ratio::from_denom_and_numer_raw(BigInt::one(), BigInt::from_i32(n))
64    }
65
66    pub fn from_i64(n: i64) -> Self {
67        // Safety: 1 and another integer are always coprime. 1 is positive. denom is 1 when n is 0.
68        Ratio::from_denom_and_numer_raw(BigInt::one(), BigInt::from_i64(n))
69    }
70
71    pub fn from_i128(n: i128) -> Self {
72        // Safety: 1 and another integer are always coprime. 1 is positive. denom is 1 when n is 0.
73        Ratio::from_denom_and_numer_raw(BigInt::one(), BigInt::from_i128(n))
74    }
75
76    pub fn from_string(s: &str) -> Result<Self, ConversionError> {
77
78        if s.len() == 0 {
79            return Err(ConversionError::NoData);
80        }
81
82        let dot_index = s.find('.');
83
84        let e_index = if let Some(c) = get_non_decimal_char(s) {
85
86            if c.to_ascii_lowercase() != 'x' {
87                s.find(|c: char| c.to_ascii_lowercase() == 'e')
88            }
89
90            else {
91                None
92            }
93
94        } else {
95            s.find(|c: char| c.to_ascii_lowercase() == 'e')
96        };
97
98        if dot_index.is_none() && e_index.is_none() {
99            return match BigInt::from_string(s) {
100                Ok(n) => Ok(Ratio::from_bi(n)),
101                Err(e) => Err(e)
102            };
103        }
104
105        if let Some(c) = get_non_decimal_char(s) {
106
107            if c.to_ascii_lowercase() != 'e' {
108                return Err(ConversionError::InvalidChar(c));
109            }
110
111        }
112
113        let is_neg = s.starts_with('-');
114
115        // `111e22.33` is invalid
116        let integer_end_index = if let Some(i) = dot_index {
117            i
118        } else {
119            e_index.unwrap()
120        };
121
122        let integer_part = {
123            let integer_string = s.get(0..integer_end_index).unwrap();
124
125            match BigInt::from_string(integer_string) {
126                Ok(n) => n,
127                Err(e) => { return Err(e); }
128            }
129
130        };
131        let mut fractional_part = match dot_index {
132            None => Ratio::zero(),
133            Some(i) => {
134                let fractional_part_end_index = if let Some(ii) = e_index {
135                    ii
136                } else {
137                    s.len()
138                };
139
140                // if i + 1 == fractional_part_end_index, fractional_part is 0
141                // eg: '3.'
142                let fraction_string = match s.get((i + 1)..fractional_part_end_index) {
143                    Some(i) => i,
144                    _ => { return Err(ConversionError::UnexpectedEnd); }
145                };
146
147                let mut denom = BigInt::one();
148                let mut numer = BigInt::zero();
149
150                for c in fraction_string.chars() {
151
152                    match c {
153                        '_' => { continue; }
154                        x if x.is_digit(10) => {
155                            denom.mul_i32_mut(10);
156                            numer.mul_i32_mut(10);
157                            numer.add_i32_mut(x.to_digit(10).unwrap() as i32);
158                        }
159                        _ => {
160                            return Err(ConversionError::InvalidChar(c));
161                        }
162                    }
163
164                }
165
166                Ratio::from_denom_and_numer(denom, numer)
167            }
168        };
169        let exponential_part = match e_index {
170            None => 0,
171            Some(i) => {
172                let exp_string = match s.get((i + 1)..) {
173                    Some(i) => i,
174                    _ => { return Err(ConversionError::UnexpectedEnd); }
175                };
176
177                match BigInt::from_string(&exp_string) {
178                    Err(e) => {
179                        return Err(e);
180                    }
181                    Ok(n) => match n.to_i32() {
182                        Ok(n) => n,
183                        Err(e) => { return Err(e); }
184                    }
185                }
186
187            }
188        };
189
190        if is_neg {
191            fractional_part.neg_mut();
192        }
193
194        let mut result = Ratio::from_bi(integer_part);
195        result.add_rat_mut(&fractional_part);
196
197        // exponential_part is a multiple of 2 and 5. So, it uses `rem_i32(2)` and `rem_i32(5)` instead of `rem_bi` for gcd
198        // -> that's much faster
199        if exponential_part != 0 {
200            let mut exponential_part_bi = BigInt::from_i32(10).pow_u32(exponential_part.abs() as u32);
201
202            if exponential_part > 0 {
203
204                while result.denom.rem_pow2(2).is_zero() && exponential_part_bi.rem_pow2(2).is_zero() {
205                    result.denom.div_i32_mut(2);
206                    exponential_part_bi.div_i32_mut(2);
207                }
208
209                while result.denom.rem_i32(5).is_zero() && exponential_part_bi.rem_i32(5).is_zero() {
210                    result.denom.div_i32_mut(5);
211                    exponential_part_bi.div_i32_mut(5);
212                }
213
214                result.numer.mul_bi_mut(&exponential_part_bi);
215            }
216
217            else if exponential_part < 0 {
218
219                while result.numer.rem_pow2(2).is_zero() && exponential_part_bi.rem_pow2(2).is_zero() {
220                    result.numer.div_i32_mut(2);
221                    exponential_part_bi.div_i32_mut(2);
222                }
223
224                while result.numer.rem_i32(5).is_zero() && exponential_part_bi.rem_i32(5).is_zero() {
225                    result.numer.div_i32_mut(5);
226                    exponential_part_bi.div_i32_mut(5);
227                }
228
229                result.denom.mul_bi_mut(&exponential_part_bi);
230            }
231
232            #[cfg(test)] assert!(result.is_valid());
233        }
234
235        Ok(result)
236    }
237
238    /// Ratio { 4, 7 } -> "4/7".
239    pub fn to_ratio_string(&self) -> String {
240        if self.denom.is_one() {
241            self.numer.to_string_dec()
242        } else {
243            format!("{}/{}", self.numer.to_string_dec(), self.denom.to_string_dec())
244        }
245    }
246
247    /// Ratio { 4, 7 } -> "1.75".
248    /// The length of the returned string is less or equal to `digits`.
249    /// If `digits` is less than 6, it'll count that as 6.
250    pub fn to_approx_string(&self, max_len: usize) -> String {
251        let mut max_len = max_len.max(6);
252
253        let log2 = self.numer.log2_accurate().sub_bi(&self.denom.log2_accurate());
254
255        // 2^70777 = 10^21306 + small
256        let log10i64 = log2.mul_i32(21306).div_i32(70777).shift_right(1).to_i64().unwrap();
257        let is_neg = self.is_neg();
258
259        let sign_part = if is_neg { "-" } else { "" };
260
261        if log10i64.abs() > 9990 {
262            let log10 = Ratio::from_denom_and_numer(
263                BigInt::from_i64(70777 << 32),
264                log2.mul_i32(21306)
265            );
266
267            // `truncate` and `frac` does the same operation twice
268            let (mut exp, mut frac) = log10.truncate_and_frac();
269
270            if exp.is_neg() && !frac.is_zero() {
271                exp.sub_i32_mut(1);
272                frac.abs_mut();
273                frac = Ratio::one().sub_rat(&frac);
274            }
275
276            // it takes only 4 digits
277            let mut digits = Ratio::from_denom_and_numer(
278                BigInt::from_i64(1 << 32),
279                BigInt::from_i64(exp10(&frac))
280            ).mul_i32(1_000_000).truncate_bi().to_i32().unwrap();
281
282            if digits % 1000 > 992 {
283                digits += 1000 - digits % 1000;
284            }
285
286            digits /= 1000;
287
288            let digits = if digits % 1000 == 0 {
289                format!("{}", digits / 1000)
290            } else if digits % 100 == 0 {
291                format!("{}.{}", digits / 1000, digits / 100 % 10)
292            } else if digits % 10 == 0 {
293                format!("{}.{:02}", digits / 1000, digits % 1000 / 10)
294            } else {
295                format!("{}.{:03}", digits / 1000, digits % 1000)
296            };
297
298            return format!("{sign_part}{digits}e{exp}");
299        }
300
301        let result = if log10i64 > max_len as i64 - 3 {
302            // we don't need the fractional part
303
304            let mut bi = self.truncate_bi();
305            bi.abs_mut();
306            let mut exp = 0;
307
308            if log10i64 > 15 {
309                bi.div_bi_mut(&BigInt::from_i32(10).pow_u32(log10i64 as u32 - 10));
310                exp += log10i64 - 10;
311            }
312
313            while bi.len() > 1 || bi.gt_i32(1_000_000_000) {
314                bi.div_i32_mut(10);
315                exp += 1;
316            }
317
318            let mut bi = bi.to_i32().unwrap();
319            let mut digits = Vec::with_capacity(20);
320
321            while bi > 0 {
322                digits.push(bi % 10);
323                bi /= 10;
324                exp += 1;
325            }
326
327            digits.reverse();
328            exp -= 1;
329
330            while digits.len() > 1 && digits[digits.len() - 1] == 0 {
331                digits.pop().unwrap();
332            }
333
334            let mut digits = if digits.len() == 1 {
335                digits[0].to_string()
336            } else {
337                format!(
338                    "{}.{}",
339                    digits[0].to_string(),
340                    digits[1..].iter().map(|n| n.to_string()).collect::<Vec<String>>().concat()
341                )
342            };
343
344            let exp = format!("e{exp}");
345
346            // At least 2 digits
347            max_len = max_len.max(exp.len() + 3);
348
349            if digits.len() + exp.len() + sign_part.len() > max_len {
350                digits = digits.get(0..(max_len - exp.len() - sign_part.len())).unwrap().to_string();
351
352                // '3.e720' doesn't make sense; it should be `3e720`
353                if digits.ends_with('.') {
354                    digits = digits.get(0..(digits.len() - 1)).unwrap().to_string();
355                }
356
357            }
358
359            format!("{sign_part}{digits}{exp}")
360        }
361
362        else if log10i64 < -(max_len as i64 - 3) {
363            let mut self_clone = self.abs();
364            let mut exp = -1;
365
366            if log10i64 < -6 {
367                let pow10 = -log10i64;
368                let mut pow2 = pow10;
369                let mut pow5 = pow10;
370
371                while pow2 > 0 && self_clone.denom.rem_pow2(2).is_zero() {
372                    self_clone.denom.div_i32_mut(2);
373                    pow2 -= 1;
374                }
375
376                while pow5 > 0 && self_clone.denom.rem_i32(5).is_zero() {
377                    self_clone.denom.div_i32_mut(5);
378                    pow5 -= 1;
379                }
380
381                self_clone.numer.mul_bi_mut(&BigInt::exp2(pow2 as u64).mul_bi(&BigInt::from_i32(5).pow_u32(pow5 as u32)));
382                exp -= pow10;
383            }
384
385            let mut self_int = self_clone.mul_i32(1_000_000_000).truncate_bi();
386            exp -= 9;
387
388            let mut digits = Vec::with_capacity(20);
389
390            while self_int.gt_i32(0) {
391                digits.push(self_int.rem_i32(10).to_i32().unwrap());
392                self_int.div_i32_mut(10);
393                exp += 1;
394            }
395
396            digits.reverse();
397            let exp = format!("e{exp}");
398
399            // At least 2 digits
400            max_len = max_len.max(exp.len() + 3);
401
402            let mut curr_len = digits.len() + sign_part.len() + exp.len() + 1;
403
404            while curr_len > max_len && digits.len() > 0 {
405                digits.pop().unwrap();
406                curr_len -= 1;
407            }
408
409            while digits.len() > 0 && digits[digits.len() - 1] == 0 {
410                digits.pop().unwrap();
411            }
412
413            let digits = if digits.len() > 1 {
414                format!("{}.{}", digits[0], digits[1..].iter().map(|c| c.to_string()).collect::<Vec<String>>().join(""))
415            } else {
416                format!("{}", digits[0])
417            };
418
419            format!("{sign_part}{digits}{exp}")
420        }
421
422        else {
423            let int_part = self.truncate_bi().abs().to_string();
424            let mut frac_part = self.abs().frac();
425            let sign_part = if is_neg {"-"} else {""};
426
427            let mut digits = Vec::with_capacity(20);
428            let mut curr_len = int_part.len() + 1 + sign_part.len();
429
430            while curr_len < max_len {
431                frac_part.mul_i32_mut(10);
432                digits.push(frac_part.truncate_bi().to_i32().unwrap());
433                frac_part.frac_mut();
434                curr_len += 1;
435            }
436
437            while digits.len() > 0 && digits[digits.len() - 1] == 0 {
438                digits.pop().unwrap();
439            }
440
441            if digits.len() > 0 {
442                format!("{sign_part}{int_part}.{}", digits.iter().map(|c| c.to_string()).collect::<Vec<String>>().join(""))
443            } else {
444                format!("{sign_part}{int_part}")
445            }
446
447        };
448
449        #[cfg(test)] assert!(result.len() <= max_len);
450
451        result
452    }
453
454    /// '9.8e5'
455    pub fn to_scientific_notation(&self, digits_max_len: usize) -> String {
456        let len_min = self.numer.len().min(self.denom.len());
457        let mut self_clone = if len_min > 4 {
458            Ratio::from_denom_and_numer(
459                self.denom.shift_right(len_min - 4),
460                self.numer.shift_right(len_min - 4)
461            )
462        }
463
464        else {
465            self.clone()
466        };
467
468        self_clone.abs_mut();
469
470        // truncate(log10(abs(self)))
471        let approx_digits = self_clone.numer.log2_accurate().sub_bi(&self_clone.denom.log2_accurate()).mul_i32(21306).div_i32(70777).shift_right(1).to_i64().unwrap();
472
473        let mut exp = 0;
474
475        let self_bi = if approx_digits < 17 {
476            exp -= 17 - approx_digits;
477            self_clone.numer.mul_bi(&BigInt::from_i32(10).pow_u32((17 - approx_digits) as u32)).div_bi(&self_clone.denom).to_i64().unwrap()
478        } else {
479            exp += approx_digits - 17;
480            self_clone.numer.div_bi(&self_clone.denom.mul_bi(&BigInt::from_i32(10).pow_u32(approx_digits as u32 - 17))).to_i64().unwrap()
481        };
482
483        let (digits, new_exp) = _to_scientific_notation(self_bi as u64, digits_max_len);
484
485        format!(
486            "{}{digits}e{}",
487            if self.is_neg() { "-" } else { "" },
488            exp + new_exp as i64
489        )
490    }
491
492    /// `self.to_approx_string(12)`
493    pub fn to_string(&self) -> String {
494        self.to_approx_string(12)
495    }
496
497}
498
499// it returns the first non-decimal character, if exists
500// it assumes that `s` is a valid numeric literal
501fn get_non_decimal_char(s: &str) -> Option<char> {
502
503    for c in s.chars() {
504
505        match c.to_ascii_lowercase() {
506            '-' | '0' | '.' => { continue; }
507            x if x.is_digit(10) => { return None; }
508            _ => { return Some(c); }
509        }
510
511    }
512
513    None
514}
515
516// truncate(10^n * 4294967296), n is between 0 and 1
517// internal function
518// It's very inaccurate and very inefficient
519fn exp10(n: &Ratio) -> i64 {
520    // binary search
521    // sqrt(10^a * 10^b) = 10^((a+b)/2)
522    let mut small = BigInt::from_raw(vec![0, 1], false);  // 10^0 * 4294967296
523    let mut small_exp = Ratio::zero();
524
525    let mut big = BigInt::from_i32(10).shift_left(1);  // 10^1 * 4294967296
526    let mut big_exp = Ratio::one();
527
528    for _ in 0..32 {
529        let mid = small.mul_bi(&big).sqrt();
530        let mid_exp = small_exp.add_rat(&big_exp).div_i32(2);
531
532        if mid_exp.lt_rat(n) {
533            small = mid;
534            small_exp = mid_exp;
535        }
536
537        else {
538            big = mid;
539            big_exp = mid_exp;
540        }
541
542    }
543
544    small.to_i64().unwrap()
545}
546
547impl std::fmt::Display for Ratio {
548
549    fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
550        write!(fmt, "{}", self.to_string())
551    }
552
553}
554
555impl FromStr for Ratio {
556    type Err = ConversionError;
557
558    fn from_str(s: &str) -> Result<Self, Self::Err> {
559        Ratio::from_string(s)
560    }
561
562}
563
564#[cfg(test)]
565mod tests {
566    use crate::{Ratio, BigInt};
567
568    #[test]
569    fn string_test() {
570        assert_eq!(
571            Ratio::from_string("3.141592e720").unwrap().to_approx_string(12),
572            "3.141592e720"
573        );
574        assert_eq!(
575            Ratio::from_string("-3.141592e720").unwrap().to_approx_string(16),
576            "-3.141592e720"
577        );
578        assert_eq!(
579            Ratio::from_string("3.141592e720").unwrap().to_approx_string(9),
580            "3.141e720"
581        );
582        assert_eq!(
583            Ratio::from_string("-3.141592e720").unwrap().to_approx_string(10),
584            "-3.141e720"
585        );
586        assert_eq!(
587            Ratio::from_string("3.141592e720").unwrap().to_approx_string(6),
588            "3.1e720"
589        );
590        assert_eq!(
591            Ratio::from_string("-3.141592e720").unwrap().to_approx_string(6),
592            "-3e720"
593        );
594        assert_eq!(
595            Ratio::from_string("3e20").unwrap().to_approx_string(0),
596            "3e20"
597        );
598        assert_eq!(
599            Ratio::from_string("-3e20").unwrap().to_approx_string(0),
600            "-3e20"
601        );
602        assert_eq!(
603            // not 16 * 10^5
604            Ratio::from_string("0x16e5").unwrap(),
605            Ratio::from_bi(BigInt::from_i32(0x16e5))
606        );
607        assert_eq!(
608            // not -16 * 10^5
609            Ratio::from_string("-0x16e5").unwrap(),
610            Ratio::from_bi(BigInt::from_i32(-0x16e5))
611        );
612        assert_eq!(
613            Ratio::from_string("16e5").unwrap(),
614            Ratio::from_bi(BigInt::from_i32(1600000))
615        );
616        assert_eq!(
617            Ratio::from_string("1600e-1").unwrap(),
618            Ratio::from_bi(BigInt::from_i32(160))
619        );
620        assert_eq!(
621            Ratio::from_string("3.012").unwrap(),
622            Ratio::from_denom_and_numer_i32(1000, 3012)
623        );
624        assert!(Ratio::from_string("0x123.4").is_err());
625        assert!(Ratio::from_string("0x123.4e4").is_err());
626        assert!(Ratio::from_string("0x123.e44").is_err());
627        assert!(Ratio::from_string("0x.3").is_err());
628        assert!(Ratio::from_string("-0x123.4").is_err());
629        assert!(Ratio::from_string("-0x123.4e4").is_err());
630        assert!(Ratio::from_string("-0x123.e44").is_err());
631        assert!(Ratio::from_string("-0x.3").is_err());
632
633        // TODO: aren't the below valid in Rust?
634        assert!(Ratio::from_string(".3").is_err());
635        assert!(Ratio::from_string("-.3").is_err());
636    }
637
638    #[test]
639    fn exp_number_test() {
640        let samples = vec![
641            "1.234e-80",
642            "1.004e-65",
643            "1.23e-120",
644            "1.2345e-9",
645            "3e-1200",
646            "3.141e7"
647        ];
648
649        for sample in samples.into_iter() {
650            let n = Ratio::from_string(sample).unwrap();
651
652            assert_eq!(sample, n.to_approx_string(sample.len()));
653            assert_eq!(sample, n.to_approx_string(sample.len() + 1));
654        }
655
656        assert_eq!("1.099e20000", Ratio::from_string("1.09999999999e20000").unwrap().to_approx_string(8));
657        assert_eq!("9.099e20000", Ratio::from_string("9.09999999999e20000").unwrap().to_approx_string(8));
658        assert_eq!("3.141e120000", Ratio::from_string("3.14159e120000").unwrap().to_approx_string(8));
659        assert_eq!("3.141e-120000", Ratio::from_string("3.14159e-120000").unwrap().to_approx_string(8));
660        assert_eq!("1e10000", Ratio::from_string("1.0001e10000").unwrap().to_approx_string(8));
661        assert_eq!("1e-10000", Ratio::from_string("1.0001e-10000").unwrap().to_approx_string(8));
662        assert_eq!("1.1e10000", Ratio::from_string("1.1001e10000").unwrap().to_approx_string(8));
663        assert_eq!("1.1e-10000", Ratio::from_string("1.1001e-10000").unwrap().to_approx_string(8));
664        assert_eq!("1.01e10000", Ratio::from_string("1.01e10000").unwrap().to_approx_string(8));
665        assert_eq!("1.01e-10000", Ratio::from_string("1.01e-10000").unwrap().to_approx_string(8));
666    }
667
668    #[test]
669    fn ratio_scientific_notation_test() {
670        let exp = -1024;
671
672        for i in 0..64 {
673            let s = Ratio::from_string(&format!("3.1415926535e{}", exp + i * 32)).unwrap();
674            let s2 = s.neg();
675
676            let ans = format!("3.14159e{}", exp + i * 32);
677            let ans2 = format!("-{ans}");
678
679            assert_eq!(ans, s.to_scientific_notation(6));
680            assert_eq!(ans2, s2.to_scientific_notation(6));
681        }
682
683    }
684
685}
hmath/ratio/convert.rs

hmath/ratio/
convert.rs
