fraction/
division.rs

1//! Lossless integer division
2//!  - The algorithm uses stack only, no introduced heap allocations for calculation (although underlying integer type implementation may perform those)
3//!  - Linear complexity, O(n)
4//!  - Abstract from a particular integer implementation, may be used on primitive types (as i32 or u32) as well as complex ones (num::BigInt, num::BigUint)
5//! Thus can be efficiently used on any integer type implementing a bunch of required traits (which all primitive ints and num::bigint implement out of the box).
6//! Although in that case the underlying math will be using heap.
7
8use error::DivisionError;
9use generic::GenericInteger;
10
11use std::cmp::{Eq, Ordering, PartialEq};
12use std::fmt::Write;
13
14/// Division state encapsulates remainder and divisor
15#[derive(Clone, Debug)]
16pub struct DivisionState<I> {
17    pub remainder: I,
18    pub divisor: I,
19}
20
21impl<I> DivisionState<I> {
22    pub fn new(remainder: I, divisor: I) -> Self {
23        DivisionState { remainder, divisor }
24    }
25}
26
27impl<I> PartialEq for DivisionState<I>
28where
29    I: PartialEq,
30{
31    fn eq(&self, other: &Self) -> bool {
32        self.remainder.eq(&other.remainder) && self.divisor.eq(&other.divisor)
33    }
34}
35
36impl<I> Eq for DivisionState<I> where I: Eq {}
37
38/// Divide two numbers and produce every single digit of the whole part of the resulting number
39///
40/// WARNING: Negative numbers as arguments are not supported.
41///
42/// Returns remainder of the division
43/// If the consumer returns `Ok(true)` keeps on calculation
44/// If the consumer returns `Ok(false)` stops calculation and returns the remainder
45/// If the consumer returns `Err(_)` the calculation will be stopped and the error will be passed as the result value
46///
47/// # Examples
48///
49/// ```
50/// use fraction::division::divide_integral;
51///
52/// let mut result: [u8; 2] = [0; 2];
53/// let mut ptr: usize = 0;
54///
55/// let state = divide_integral(30, 2, |d| {
56///     result[ptr] = d;
57///     ptr += 1;
58///     Ok(true)
59/// }).unwrap();
60///
61/// assert_eq!([1, 5], result);
62/// assert_eq!(state.remainder, 0);
63/// assert_eq!(state.divisor, 2);
64/// ```
65///
66/// ```
67/// use fraction::division::divide_integral;
68///
69/// let mut result: u8 = 0;
70///
71/// let state = divide_integral(30, 2, |d| {
72///     result = d;
73///     Ok(false)
74/// }).unwrap();
75///
76/// assert_eq!(result, 1);
77/// assert_eq!(state.remainder, 10);
78/// assert_eq!(state.divisor, 2);
79/// ```
80pub fn divide_integral<I, Consumer>(
81    mut dividend: I,
82    divisor: I,
83    mut consumer: Consumer,
84) -> Result<DivisionState<I>, DivisionError>
85where
86    Consumer: FnMut(u8) -> Result<bool, DivisionError>,
87    I: Clone + GenericInteger,
88{
89    if divisor.is_zero() {
90        return Err(DivisionError::DivisionByZero);
91    }
92
93    /* === Figuring out the number size === */
94    let mut ptr: I = match dividend.cmp(&divisor) {
95        Ordering::Equal => {
96            consumer(1u8)?;
97            return Ok(DivisionState::new(I::zero(), divisor));
98        }
99        Ordering::Less => {
100            consumer(0u8)?;
101            return Ok(DivisionState::new(dividend, divisor));
102        }
103        Ordering::Greater => {
104            let mut ptr: I = I::_1();
105
106            loop {
107                if ptr > dividend {
108                    if I::_1r().map_or_else(|| ptr > I::_1(), |_1| ptr > *_1) {
109                        I::_10r().map(|_10| ptr /= _10).or_else(|| {
110                            ptr /= I::_10();
111                            None
112                        });
113                    }
114                    break;
115                }
116
117                ptr = match I::_10r()
118                    .map_or_else(|| ptr.checked_mul(&I::_10()), |_10| ptr.checked_mul(_10))
119                {
120                    Some(n) => n,
121                    None => break,
122                };
123            }
124
125            ptr
126        }
127    };
128
129    let mut passed_leading_zeroes: bool = false;
130    loop {
131        let digit = dividend.div_floor(&ptr).div_floor(&divisor);
132
133        if I::_0r().map_or_else(|| digit > I::_0(), |_0| digit > *_0) {
134            passed_leading_zeroes = true;
135            dividend -= digit.clone() * &divisor * &ptr;
136        }
137
138        if passed_leading_zeroes {
139            let d: Option<u8> = digit.to_u8();
140            match d {
141                Some(n) => {
142                    if !consumer(n)? {
143                        return Ok(DivisionState::new(dividend, divisor));
144                    }
145                }
146                None => unreachable!(),
147            };
148        }
149
150        if I::_1r().map_or_else(|| ptr == I::_1(), |_1| ptr == *_1) {
151            break;
152        }
153
154        I::_10r().map(|_10| ptr /= _10).or_else(|| {
155            ptr /= I::_10();
156            None
157        });
158    }
159
160    Ok(DivisionState::new(dividend, divisor))
161}
162
163/// Produces the fractional part of the decimal from a rest part left after division
164///
165/// WARNING: Negative numbers as arguments are not supported.
166///
167/// Returns remainder of the division
168/// If the consumer returns `Ok(Ok(state))` keeps on calculation
169/// If the consumer returns `Ok(Err(state))` stops calculation and returns the remainder
170/// If the consumer returns `Err(_)` the calculation will be stopped and the error will be passed as the result value
171///
172/// # Examples
173///
174/// ```
175/// use fraction::division::divide_rem;
176///
177/// let mut result: [u8; 2] = [0; 2];
178/// let mut ptr: usize = 0;
179///
180/// let state = divide_rem(3, 4, |state, digit| {
181///     result[ptr] = digit;
182///     ptr += 1;
183///     Ok(Ok(state))
184/// }).unwrap();
185///
186/// assert_eq!(state.remainder, 0);
187/// assert_eq!(state.divisor, 4);
188/// assert_eq!(result, [7, 5]);  // 3/4 == 0.75
189/// ```
190#[inline]
191pub fn divide_rem<I, Consumer>(
192    dividend: I,
193    divisor: I,
194    consumer: Consumer,
195) -> Result<DivisionState<I>, DivisionError>
196where
197    Consumer: FnMut(
198        DivisionState<I>,
199        u8,
200    ) -> Result<Result<DivisionState<I>, DivisionState<I>>, DivisionError>,
201    I: Clone + GenericInteger,
202{
203    divide_rem_resume(DivisionState::new(dividend, divisor), consumer)
204}
205
206/// [divide_rem] co-routine implementation  
207/// Performs the division, changes the state and returns it
208///
209/// # Examples
210///
211/// ```
212/// use fraction::division::{DivisionState, divide_rem_resume};
213///
214/// let mut state = Some(DivisionState::new(1, 3));
215/// let mut precision = 5;
216///
217/// let mut result: Vec<u8> = Vec::new();
218///
219/// loop {
220///     if precision == 0 { break }
221///
222///     state = Some(
223///         divide_rem_resume(state.take().unwrap(), |s, digit| {
224///             precision -= 1;
225///             result.push(digit);
226///
227///             Ok(Err(s))
228///         }).unwrap()
229///     );
230///
231///     // perform some other operations
232/// }
233///
234/// assert_eq!(result, vec![3, 3, 3, 3, 3]);
235/// ```
236pub fn divide_rem_resume<I, Consumer>(
237    mut state: DivisionState<I>,
238    mut consumer: Consumer,
239) -> Result<DivisionState<I>, DivisionError>
240where
241    Consumer: FnMut(
242        DivisionState<I>,
243        u8,
244    ) -> Result<Result<DivisionState<I>, DivisionState<I>>, DivisionError>,
245    I: Clone + GenericInteger,
246{
247    loop {
248        if state.remainder.is_zero() {
249            break;
250        }
251
252        let digit = I::_10r()
253            .map(|_10| {
254                let (rem, digit) = state.remainder.checked_mul(_10).map_or_else(
255                    || {
256                        let (reduced_divisor, reduced_divisor_rem) = state.divisor.div_rem(_10);
257
258                        let mut digit = state.remainder.div_floor(&reduced_divisor);
259                        let mut remainder = state.remainder.clone();
260
261                        remainder -= digit.clone() * &reduced_divisor;
262
263                        let mut red_div_rem_diff =
264                            (reduced_divisor_rem.clone() * &digit).div_rem(_10);
265
266                        loop {
267                            if red_div_rem_diff.0 > remainder {
268                                digit -= I::one();
269                                remainder += &reduced_divisor;
270                                red_div_rem_diff =
271                                    (reduced_divisor_rem.clone() * &digit).div_rem(_10);
272                            } else {
273                                break;
274                            }
275                        }
276
277                        remainder -= red_div_rem_diff.0;
278                        remainder *= _10;
279
280                        if red_div_rem_diff.1 > remainder {
281                            digit -= I::one();
282                            remainder += &state.divisor;
283                        }
284
285                        remainder -= red_div_rem_diff.1;
286
287                        (remainder, digit.to_u8())
288                    },
289                    |mut remainder| {
290                        let digit = remainder.div_floor(&state.divisor);
291                        remainder -= digit.clone() * &state.divisor;
292
293                        (remainder, digit.to_u8())
294                    },
295                );
296
297                state.remainder = rem;
298                digit
299            })
300            .or_else(|| {
301                let ten = I::_10();
302
303                let (rem, digit) = state.remainder.checked_mul(&ten).map_or_else(
304                    || {
305                        let (reduced_divisor, reduced_divisor_rem) = state.divisor.div_rem(&ten);
306
307                        let mut digit = state.remainder.div_floor(&reduced_divisor);
308                        let mut remainder = state.remainder.clone();
309
310                        remainder -= digit.clone() * &reduced_divisor;
311
312                        let mut red_div_rem_diff =
313                            (reduced_divisor_rem.clone() * &digit).div_rem(&ten);
314
315                        loop {
316                            if red_div_rem_diff.0 > remainder {
317                                digit -= I::one();
318                                remainder += &reduced_divisor;
319                                red_div_rem_diff =
320                                    (reduced_divisor_rem.clone() * &digit).div_rem(&ten);
321                            } else {
322                                break;
323                            }
324                        }
325
326                        remainder -= red_div_rem_diff.0;
327                        remainder *= &ten;
328
329                        if red_div_rem_diff.1 > remainder {
330                            digit -= I::one();
331                            remainder += &state.divisor;
332                        }
333
334                        remainder -= red_div_rem_diff.1;
335
336                        (remainder, digit.to_u8())
337                    },
338                    |mut remainder: I| {
339                        let digit = remainder.div_floor(&state.divisor);
340                        remainder -= digit.clone() * &state.divisor;
341
342                        (remainder, digit.to_u8())
343                    },
344                );
345
346                state.remainder = rem;
347                Some(digit)
348            })
349            .unwrap();
350
351        match digit {
352            Some(n) => {
353                state = match consumer(state, n)? {
354                    Ok(state) => state,
355                    Err(s) => return Ok(s),
356                };
357            }
358            None => unreachable!(),
359        };
360    }
361
362    Ok(state)
363}
364
365/// Calculate the max possible length of division in characters (including floating point)
366/// This may be useful for string/vector pre-allocations
367///
368/// WARNING: Negative numbers as arguments are not supported.
369///
370/// # Examples
371/// ```
372/// use fraction::division::division_result_max_char_length;
373///
374/// assert_eq!(division_result_max_char_length(&1, 0), 1);
375/// assert_eq!(division_result_max_char_length(&10, 0), 2);
376/// assert_eq!(division_result_max_char_length(&10, 1), 4);
377/// assert_eq!(division_result_max_char_length(&100, 2), 6);
378/// assert_eq!(division_result_max_char_length(&900, 2), 6);
379/// ```
380pub fn division_result_max_char_length<I>(dividend: &I, precision: usize) -> usize
381where
382    I: Clone + GenericInteger,
383{
384    let mut ptr: I = I::_1();
385    let mut len: usize = 0;
386
387    loop {
388        len += 1;
389
390        ptr = match I::_10r().map_or_else(|| ptr.checked_mul(&I::_10()), |_10| ptr.checked_mul(_10))
391        {
392            Some(n) => n,
393            None => break,
394        };
395
396        if ptr > *dividend {
397            break;
398        }
399    }
400
401    len + precision + usize::from(precision > 0)
402}
403
404/// Divide a fraction into a [`String`]
405///
406/// WARNING: Negative numbers as arguments are not supported.
407///
408///  - Makes only one allocation for the resulting string
409///  - Does not round the last digit
410///
411/// Calculates the resulting string length first, allocates it,
412/// then makes the division and puts the result into the preallocated
413/// string.
414///
415/// # Examples
416///
417/// ```
418/// use fraction::division::divide_to_string;
419///
420/// assert_eq! (divide_to_string(2, 4, 2, false).unwrap(), "0.5");
421/// assert_eq! (divide_to_string(2, 4, 2, true).unwrap(), "0.50");
422/// assert_eq! (divide_to_string(5, 7, 16, false).unwrap(), "0.7142857142857142");
423/// assert_eq! (divide_to_string(1, 3, 3, false).unwrap(), "0.333");
424/// assert_eq! (divide_to_string(1, 3, 3, true).unwrap(), "0.333");
425/// ```
426///
427/// [`String`]: https://doc.rust-lang.org/std/string/struct.String.html
428/// [`divide_integral`]: ./fn.divide_integral.html
429/// [`divide_rem`]: ./fn.divide_rem.html
430#[inline]
431pub fn divide_to_string<I>(
432    dividend: I,
433    divisor: I,
434    precision: usize,
435    trail_zeroes: bool,
436) -> Result<String, DivisionError>
437where
438    I: Clone + GenericInteger,
439{
440    let mut result = String::with_capacity(division_result_max_char_length(&dividend, precision));
441
442    divide_to_writeable(&mut result, dividend, divisor, precision, trail_zeroes)?;
443
444    Ok(result)
445}
446
447/// Divide a fraction into a [`Vec<u8>`] of ASCII(utf8) chars
448///
449/// WARNING: Negative numbers as arguments are not supported.
450///
451///  - Makes only one allocation for the resulting vector
452///  - Does not round the last digit
453///
454/// Calculates the resulting vector length first, allocates it,
455/// then makes the division and puts the result into the preallocated
456/// vector.
457/// Uses [`divide_integral`] and [`divide_rem`] functions internally.
458///
459/// # Examples
460///
461/// ```
462/// use fraction::division::divide_to_ascii_vec;
463///
464/// assert_eq! (divide_to_ascii_vec(2, 4, 2, false).unwrap(), vec![48, 46, 53]);  // "0.5" in ascii
465/// assert_eq! (divide_to_ascii_vec(2, 4, 2, true).unwrap(), vec![48, 46, 53, 48]);  // "0.50" in ascii
466/// assert_eq! (divide_to_ascii_vec(5, 7, 16, false).unwrap(), vec![48, 46, 55, 49, 52, 50, 56, 53, 55, 49, 52, 50, 56, 53, 55, 49, 52, 50]);  // "0.7142857142857142" in ascii
467/// assert_eq! (divide_to_ascii_vec(1, 3, 3, false).unwrap(), vec![48, 46, 51, 51, 51]);  // "0.333" in ascii
468/// ```
469///
470/// [`Vec<u8>`]: https://doc.rust-lang.org/std/vec/struct.Vec.html
471/// [`divide_integral`]: ./fn.divide_integral.html
472/// [`divide_rem`]: ./fn.divide_rem.html
473#[inline]
474pub fn divide_to_ascii_vec<I>(
475    dividend: I,
476    divisor: I,
477    precision: usize,
478    trail_zeroes: bool,
479) -> Result<Vec<u8>, DivisionError>
480where
481    I: Clone + GenericInteger,
482{
483    const ZERO: u8 = 48u8;
484    const DOT: u8 = 46u8;
485
486    let mut result = Vec::with_capacity(division_result_max_char_length(&dividend, precision));
487
488    divide_to_callback(dividend, divisor, precision, trail_zeroes, |digit| {
489        if digit == 10u8 {
490            result.push(DOT);
491        } else {
492            result.push(ZERO + digit);
493        }
494        Ok(true)
495    })?;
496
497    Ok(result)
498}
499
500/// Divide a fraction into a writeable target implementing [`std::fmt::Write`]  
501/// Returns the remainder of the division
502///
503///  - No allocations
504///  - Does not round the last digit
505///
506/// Makes the division and puts the result into the formatter.
507/// Uses [`divide_integral`] and [`divide_rem`] functions internally.
508///
509/// WARNING: Negative numbers as arguments are not supported.
510///
511/// # Examples
512///
513/// ```
514/// use fraction::division::{ divide_to_writeable, division_result_max_char_length };
515///
516/// let num = 7;
517/// let denom = 4;
518///
519/// let mut string = String::with_capacity(division_result_max_char_length(&num, 2));
520///
521/// divide_to_writeable(&mut string, num, denom, 2, false).ok();
522///
523/// assert_eq!(string, "1.75");
524/// ```
525///
526/// ```
527/// use fraction::division::divide_to_writeable;
528///
529/// use std::fmt;
530///
531/// struct Foo(i32, i32);
532///
533/// impl fmt::Display for Foo {
534///     fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
535///         let precision = formatter.precision().unwrap_or(2);
536///         match divide_to_writeable(formatter, self.0, self.1, precision, false) {
537///             Err(_) => Err(fmt::Error),
538///             _ => Ok(())
539///         }
540///     }
541/// }
542///
543/// assert_eq! (format!("{}", Foo(1, 2)), "0.5");
544/// assert_eq! (format!("{:.3}", Foo(1, 3)), "0.333");
545/// assert_eq! (format!("{:.16}", Foo(5, 7)), "0.7142857142857142");
546/// ```
547///
548/// [`std::fmt::Write`]: https://doc.rust-lang.org/std/fmt/trait.Write.html
549/// [`divide_integral`]: ./fn.divide_integral.html
550/// [`divide_rem`]: ./fn.divide_rem.html
551#[inline]
552pub fn divide_to_writeable<I>(
553    writeable: &mut dyn Write,
554    dividend: I,
555    divisor: I,
556    precision: usize,
557    trail_zeroes: bool,
558) -> Result<I, DivisionError>
559where
560    I: Clone + GenericInteger,
561{
562    divide_to_callback(dividend, divisor, precision, trail_zeroes, |digit| {
563        write_digit(writeable, digit)
564    })
565}
566
567/// Calculate the division result and pass every character into the callback  
568/// Returns the remainder of the division
569///
570/// - Makes no allocations
571///
572/// Uses [`divide_integral`] and [`divide_rem`] functions internally.
573///
574/// WARNING: Negative numbers as arguments are not supported.
575///
576/// # Callback
577///
578/// Callback receives every digit of the result as a u8 value.
579/// The floating point character (dot) is passed to the callback as `10u8`.
580/// If the callback returns `Ok(true)`, the function keeps on calculation
581/// If the callback returns `Ok(false)`, the function stops calculation and returns the remainder
582/// If the callback returns `Err(_)` the calculation will be stopped and the error will propagate as the result value
583///
584/// # Examples
585///
586/// ```
587/// use fraction::division::divide_to_callback;
588///
589/// let mut result = Vec::new();
590///
591/// // calculate 7/4, which is 1.75
592/// divide_to_callback(7, 4, 2, false, |d| { result.push(d as i32); Ok(true) }).ok();
593///
594/// assert_eq!(&result, &[1, 10, 7, 5]);
595/// ```
596pub fn divide_to_callback<I, C>(
597    dividend: I,
598    divisor: I,
599    mut precision: usize,
600    trail_zeroes: bool,
601    mut callback: C,
602) -> Result<I, DivisionError>
603where
604    C: FnMut(u8) -> Result<bool, DivisionError>,
605    I: Clone + GenericInteger,
606{
607    let mut keep_going = true;
608
609    let mut div_state = divide_integral(dividend, divisor, |digit: u8| match callback(digit) {
610        result @ Ok(false) => {
611            keep_going = false;
612            result
613        }
614        result => result,
615    })?;
616
617    if !keep_going {
618        return Ok(div_state.remainder);
619    }
620
621    if precision > 0 {
622        let mut dot = false;
623        let mut trailing_zeroes = 0;
624
625        if !div_state.remainder.is_zero() {
626            div_state = divide_rem(
627                div_state.remainder,
628                div_state.divisor,
629                |state, digit: u8| {
630                    precision -= 1;
631
632                    if digit == 0 {
633                        trailing_zeroes += 1;
634                    } else {
635                        if !dot {
636                            dot = true;
637
638                            match callback(10u8) {
639                                result @ Ok(false) => {
640                                    keep_going = false;
641                                    result
642                                }
643                                result => result,
644                            }?;
645
646                            if !keep_going {
647                                return Ok(Err(state));
648                            }
649                        }
650
651                        while trailing_zeroes > 0 {
652                            trailing_zeroes -= 1;
653
654                            match callback(0u8) {
655                                result @ Ok(false) => {
656                                    keep_going = false;
657                                    result
658                                }
659                                result => result,
660                            }?;
661
662                            if !keep_going {
663                                return Ok(Err(state));
664                            }
665                        }
666
667                        match callback(digit) {
668                            result @ Ok(false) => {
669                                keep_going = false;
670                                result
671                            }
672                            result => result,
673                        }?;
674
675                        if !keep_going {
676                            return Ok(Err(state));
677                        }
678                    }
679
680                    if precision > 0 {
681                        Ok(Ok(state))
682                    } else {
683                        Ok(Err(state))
684                    }
685                },
686            )?;
687        }
688
689        if keep_going && trail_zeroes {
690            if !dot {
691                match callback(10u8) {
692                    result @ Ok(false) => {
693                        keep_going = false;
694                        result
695                    }
696                    result => result,
697                }?;
698
699                if !keep_going {
700                    return Ok(div_state.remainder);
701                }
702            }
703
704            while trailing_zeroes > 0 {
705                trailing_zeroes -= 1;
706
707                match callback(0u8) {
708                    result @ Ok(false) => {
709                        keep_going = false;
710                        result
711                    }
712                    result => result,
713                }?;
714
715                if !keep_going {
716                    return Ok(div_state.remainder);
717                }
718            }
719
720            while precision > 0 {
721                precision -= 1;
722
723                match callback(0u8) {
724                    result @ Ok(false) => {
725                        keep_going = false;
726                        result
727                    }
728                    result => result,
729                }?;
730
731                if !keep_going {
732                    return Ok(div_state.remainder);
733                }
734            }
735        }
736    }
737
738    Ok(div_state.remainder)
739}
740
741/// A helper function to use in conjunction with [divide_to_callback]
742///
743/// divide_to_callback passes digits to its callback, this function can
744/// be used to write digits (and dots) into the writeable buffer after
745/// your callback performs its side-effects.
746///
747/// # Examples
748///
749/// ```
750/// use fraction::division::{divide_to_callback, write_digit};
751///
752/// let mut result = String::new();
753/// let mut length = 0;
754///
755/// // calculate 7/4, which is 1.75
756/// divide_to_callback(7, 4, 2, false, |d| { length += 1; write_digit(&mut result, d) }).ok();
757///
758/// assert_eq!(&result, "1.75");
759/// assert_eq!(length, result.len());
760/// ```
761pub fn write_digit(writeable: &mut dyn Write, digit: u8) -> Result<bool, DivisionError> {
762    if digit == 10u8 {
763        match writeable.write_char('.') {
764            Ok(_) => Ok(true),
765            Err(e) => Err(DivisionError::from(e)),
766        }
767    } else {
768        match writeable.write_fmt(format_args!("{}", digit)) {
769            Ok(_) => Ok(true),
770            Err(e) => Err(DivisionError::from(e)),
771        }
772    }
773}
774
775#[cfg(test)]
776mod tests {
777    use super::*;
778    use error::DivisionError;
779    use num::Zero;
780
781    // mod divide_to_string_u8;
782
783    #[cfg(feature = "with-bigint")]
784    use num::{bigint::BigUint, Num};
785
786    #[test]
787    fn test_division() {
788        const PRECISION: usize = 64;
789        let data: Vec<(u8, u8, &'static str, bool)> = vec![
790            (
791                1u8,
792                255u8,
793                "0.0039215686274509803921568627450980392156862745098039215686274509",
794                false,
795            ),
796            (
797                1u8,
798                254u8,
799                "0.0039370078740157480314960629921259842519685039370078740157480314",
800                false,
801            ),
802            (
803                1u8,
804                253u8,
805                "0.003952569169960474308300395256916996047430830039525691699604743",
806                false,
807            ),
808            (
809                1u8,
810                252u8,
811                "0.0039682539682539682539682539682539682539682539682539682539682539",
812                false,
813            ),
814            (
815                1u8,
816                251u8,
817                "0.0039840637450199203187250996015936254980079681274900398406374501",
818                false,
819            ),
820            (1u8, 250u8, "0.004", true),
821            (
822                1u8,
823                112u8,
824                "0.0089285714285714285714285714285714285714285714285714285714285714",
825                false,
826            ),
827            (
828                1u8,
829                111u8,
830                "0.009009009009009009009009009009009009009009009009009009009009009",
831                false,
832            ),
833            (
834                1u8,
835                96u8,
836                "0.0104166666666666666666666666666666666666666666666666666666666666",
837                false,
838            ),
839            (
840                1u8,
841                92u8,
842                "0.0108695652173913043478260869565217391304347826086956521739130434",
843                false,
844            ),
845            (
846                1u8,
847                91u8,
848                "0.0109890109890109890109890109890109890109890109890109890109890109",
849                false,
850            ),
851            (
852                1u8,
853                90u8,
854                "0.0111111111111111111111111111111111111111111111111111111111111111",
855                false,
856            ),
857            (
858                1u8,
859                9u8,
860                "0.1111111111111111111111111111111111111111111111111111111111111111",
861                false,
862            ),
863            (1u8, 8u8, "0.125", true),
864            (
865                1u8,
866                7u8,
867                "0.1428571428571428571428571428571428571428571428571428571428571428",
868                false,
869            ),
870            (
871                1u8,
872                6u8,
873                "0.1666666666666666666666666666666666666666666666666666666666666666",
874                false,
875            ),
876            (1u8, 5u8, "0.2", true),
877            (1u8, 4u8, "0.25", true),
878            (
879                1u8,
880                3u8,
881                "0.3333333333333333333333333333333333333333333333333333333333333333",
882                false,
883            ),
884            (1u8, 2u8, "0.5", true),
885            (1u8, 1u8, "1", true),
886            (
887                49u8,
888                255u8,
889                "0.192156862745098039215686274509803921568627450980392156862745098",
890                false,
891            ),
892            (
893                49u8,
894                254u8,
895                "0.1929133858267716535433070866141732283464566929133858267716535433",
896                false,
897            ),
898            (
899                49u8,
900                253u8,
901                "0.193675889328063241106719367588932806324110671936758893280632411",
902                false,
903            ),
904            (
905                49u8,
906                252u8,
907                "0.1944444444444444444444444444444444444444444444444444444444444444",
908                false,
909            ),
910            (
911                49u8,
912                251u8,
913                "0.1952191235059760956175298804780876494023904382470119521912350597",
914                false,
915            ),
916            (49u8, 250u8, "0.196", true),
917            (
918                49u8,
919                249u8,
920                "0.1967871485943775100401606425702811244979919678714859437751004016",
921                false,
922            ),
923            (
924                49u8,
925                248u8,
926                "0.1975806451612903225806451612903225806451612903225806451612903225",
927                false,
928            ),
929            (
930                49u8,
931                247u8,
932                "0.1983805668016194331983805668016194331983805668016194331983805668",
933                false,
934            ),
935            (
936                49u8,
937                246u8,
938                "0.1991869918699186991869918699186991869918699186991869918699186991",
939                false,
940            ),
941            (49u8, 245u8, "0.2", true),
942            (
943                49u8,
944                69u8,
945                "0.7101449275362318840579710144927536231884057971014492753623188405",
946                false,
947            ),
948            (
949                49u8,
950                68u8,
951                "0.7205882352941176470588235294117647058823529411764705882352941176",
952                false,
953            ),
954            (
955                49u8,
956                67u8,
957                "0.7313432835820895522388059701492537313432835820895522388059701492",
958                false,
959            ),
960            (
961                49u8,
962                66u8,
963                "0.7424242424242424242424242424242424242424242424242424242424242424",
964                false,
965            ),
966            (
967                49u8,
968                65u8,
969                "0.7538461538461538461538461538461538461538461538461538461538461538",
970                false,
971            ),
972            (49u8, 64u8, "0.765625", true),
973            (
974                49u8,
975                63u8,
976                "0.7777777777777777777777777777777777777777777777777777777777777777",
977                false,
978            ),
979            (
980                77u8,
981                255u8,
982                "0.3019607843137254901960784313725490196078431372549019607843137254",
983                false,
984            ),
985            (
986                77u8,
987                254u8,
988                "0.3031496062992125984251968503937007874015748031496062992125984251",
989                false,
990            ),
991            (
992                77u8,
993                253u8,
994                "0.3043478260869565217391304347826086956521739130434782608695652173",
995                false,
996            ),
997            (
998                77u8,
999                252u8,
1000                "0.3055555555555555555555555555555555555555555555555555555555555555",
1001                false,
1002            ),
1003            (
1004                77u8,
1005                251u8,
1006                "0.3067729083665338645418326693227091633466135458167330677290836653",
1007                false,
1008            ),
1009            (77u8, 250u8, "0.308", true),
1010            (
1011                77u8,
1012                249u8,
1013                "0.3092369477911646586345381526104417670682730923694779116465863453",
1014                false,
1015            ),
1016            (
1017                77u8,
1018                248u8,
1019                "0.3104838709677419354838709677419354838709677419354838709677419354",
1020                false,
1021            ),
1022            (
1023                77u8,
1024                231u8,
1025                "0.3333333333333333333333333333333333333333333333333333333333333333",
1026                false,
1027            ),
1028            (
1029                77u8,
1030                230u8,
1031                "0.3347826086956521739130434782608695652173913043478260869565217391",
1032                false,
1033            ),
1034            (
1035                77u8,
1036                229u8,
1037                "0.3362445414847161572052401746724890829694323144104803493449781659",
1038                false,
1039            ),
1040            (
1041                77u8,
1042                228u8,
1043                "0.3377192982456140350877192982456140350877192982456140350877192982",
1044                false,
1045            ),
1046            (
1047                77u8,
1048                227u8,
1049                "0.3392070484581497797356828193832599118942731277533039647577092511",
1050                false,
1051            ),
1052            (
1053                77u8,
1054                226u8,
1055                "0.3407079646017699115044247787610619469026548672566371681415929203",
1056                false,
1057            ),
1058            (
1059                77u8,
1060                225u8,
1061                "0.3422222222222222222222222222222222222222222222222222222222222222",
1062                false,
1063            ),
1064            (77u8, 224u8, "0.34375", true),
1065            (
1066                77u8,
1067                223u8,
1068                "0.3452914798206278026905829596412556053811659192825112107623318385",
1069                false,
1070            ),
1071            (
1072                77u8,
1073                222u8,
1074                "0.3468468468468468468468468468468468468468468468468468468468468468",
1075                false,
1076            ),
1077            (
1078                77u8,
1079                221u8,
1080                "0.3484162895927601809954751131221719457013574660633484162895927601",
1081                false,
1082            ),
1083            (77u8, 220u8, "0.35", true),
1084        ];
1085
1086        for i in data.iter() {
1087            assert_eq!(divide_to_string(i.0, i.1, PRECISION, false).unwrap(), i.2);
1088
1089            {
1090                let mut string: String = String::new();
1091                let remainder =
1092                    divide_to_writeable(&mut string, i.0, i.1, PRECISION, false).unwrap();
1093
1094                assert_eq!(string, i.2);
1095                assert_eq!(remainder.is_zero(), i.3);
1096            }
1097        }
1098
1099        #[cfg(feature = "with-bigint")]
1100        {
1101            for i in data {
1102                assert_eq!(
1103                    divide_to_string(BigUint::from(i.0), BigUint::from(i.1), PRECISION, false)
1104                        .unwrap(),
1105                    i.2
1106                );
1107            }
1108        }
1109    }
1110
1111    #[test]
1112    fn test_divide_to_string() {
1113        assert_eq!(divide_to_string(0, 5, 5, false).unwrap(), "0");
1114        assert_eq!(divide_to_string(0, 5, 5, true).unwrap(), "0.00000");
1115        assert_eq!(divide_to_string(30, 2, 5, false).unwrap(), "15");
1116        assert_eq!(divide_to_string(30, 2, 5, true).unwrap(), "15.00000");
1117        assert_eq!(divide_to_string(2, 4, 2, false).unwrap(), "0.5");
1118        assert_eq!(divide_to_string(2, 4, 2, true).unwrap(), "0.50");
1119        assert_eq!(divide_to_string(255u8, 3u8, 5, false).unwrap(), "85");
1120        assert_eq!(divide_to_string(255u8, 3u8, 5, true).unwrap(), "85.00000");
1121
1122        assert_eq!(divide_to_string(155u8, 253u8, 5, false).unwrap(), "0.61264");
1123        assert_eq!(divide_to_string(1u8, 2u8, 1, false).unwrap(), "0.5");
1124        assert_eq!(divide_to_string(1u8, 2u8, 1, true).unwrap(), "0.5");
1125
1126        assert_eq!(
1127            divide_to_string(1, 3, 28, false).unwrap(),
1128            "0.3333333333333333333333333333"
1129        );
1130        assert_eq!(
1131            divide_to_string(1, 3, 28, true).unwrap(),
1132            "0.3333333333333333333333333333"
1133        );
1134        assert_eq!(divide_to_string(806, 31, 0, false).unwrap(), "26");
1135        assert_eq!(divide_to_string(806, 31, 0, true).unwrap(), "26");
1136        assert_eq!(divide_to_string(807, 31, 4, false).unwrap(), "26.0322");
1137        assert_eq!(divide_to_string(807, 31, 4, true).unwrap(), "26.0322");
1138
1139        if let Err(DivisionError::DivisionByZero) = divide_to_string(1, 0, 1, false) {
1140        } else {
1141            assert!(false);
1142        };
1143
1144        if let Err(DivisionError::DivisionByZero) = divide_to_string(1, 0, 1, true) {
1145        } else {
1146            assert!(false);
1147        };
1148
1149        assert_eq!(divide_to_string(1, 10000, 2, false).unwrap(), "0");
1150        assert_eq!(divide_to_string(1, 10000, 2, true).unwrap(), "0.00");
1151
1152        #[cfg(feature = "with-bigint")]
1153        {
1154            let num = "820123456789012345678901234567890123456789";
1155            let den = "420420420420240240420240420240420420420";
1156            let result = "1950.7222222204153880534352079149419688493160244330759069204925259490806291881834407646199555744655166719234903156227406500953778757619920899563294795746797267246703798051247915744867884912121330007705286911209791422213223230426822190127666529437572025264829201539629594175021000386486667365851813562015885600393107707737453721144405603009059457352854387023006301508907770762997683254372534811586343569328131455924964081595076622200116354403760742833073621862325616259444084808295834752749082040590201012701034118255745516514972270054835928011374231619434684843847682844123336846713100440285930668493675706096464476187809105398269815519780303174023949885603320678109566772031394249633001137109155600514761384776616827086908396960584246277151426685095767130738996420461009015758184659365258827537226581854494195009714400547427050697946126012192691851549545189173091941689299722345297086508711845865506663262915436874050594522308464492248968916100678819937355384703664061966410613989688966690413319849627099468906113991173042101218";
1157
1158            let asrt1 = divide_to_string(
1159                BigUint::from_str_radix(num, 10).ok().unwrap(),
1160                BigUint::from_str_radix(den, 10).ok().unwrap(),
1161                1024,
1162                false,
1163            );
1164
1165            assert_eq!(&asrt1.ok().unwrap(), result);
1166
1167            let asrt1 = divide_to_string(
1168                BigUint::from_str_radix(num, 10).ok().unwrap(),
1169                BigUint::from_str_radix(den, 10).ok().unwrap(),
1170                1024,
1171                true,
1172            );
1173
1174            assert_eq!(&asrt1.ok().unwrap(), result);
1175        }
1176    }
1177
1178    #[test]
1179    fn test_divide_to_ascii_vec() {
1180        assert_eq!(divide_to_ascii_vec(0, 5, 5, false).unwrap(), vec![48]);
1181        assert_eq!(
1182            divide_to_ascii_vec(0, 5, 5, true).unwrap(),
1183            vec![48, 46, 48, 48, 48, 48, 48]
1184        );
1185        assert_eq!(divide_to_ascii_vec(30, 2, 5, false).unwrap(), vec![49, 53]);
1186        assert_eq!(
1187            divide_to_ascii_vec(2, 4, 2, false).unwrap(),
1188            vec![48, 46, 53]
1189        );
1190        assert_eq!(
1191            divide_to_ascii_vec(2, 4, 2, true).unwrap(),
1192            vec![48, 46, 53, 48]
1193        );
1194        assert_eq!(
1195            divide_to_ascii_vec(255u8, 3u8, 5, false).unwrap(),
1196            vec![56, 53]
1197        );
1198        assert_eq!(
1199            divide_to_ascii_vec(1000001u64, 10000u64, 3, false).unwrap(),
1200            vec![49, 48, 48]
1201        );
1202        assert_eq!(
1203            divide_to_ascii_vec(1000001u64, 10000u64, 3, true).unwrap(),
1204            vec![49, 48, 48, 46, 48, 48, 48]
1205        );
1206    }
1207
1208    #[test]
1209    fn test_divide_integral() {
1210        {
1211            let mut r1: [u8; 1] = [0; 1];
1212            let mut p1: usize = 0;
1213
1214            let mut r2: [u8; 2] = [0; 2];
1215            let mut p2: usize = 0;
1216
1217            let mut r3: [u8; 3] = [0; 3];
1218            let mut p3: usize = 0;
1219
1220            let rest1 = divide_integral(2, 4, |d| {
1221                r1[p1] = d;
1222                p1 += 1;
1223                Ok(true)
1224            });
1225
1226            assert_eq!(r1, [0]);
1227            assert_eq!(p1, 1);
1228            assert_eq!(rest1.unwrap(), DivisionState::new(2, 4));
1229
1230            let rest2 = divide_integral(82, 3, |d| {
1231                r2[p2] = d;
1232                p2 += 1;
1233                Ok(true)
1234            });
1235
1236            assert_eq!(r2, [2, 7]);
1237            assert_eq!(p2, 2);
1238            assert_eq!(rest2.unwrap(), DivisionState::new(1, 3));
1239
1240            let rest3 = divide_integral(2020, 4, |d| {
1241                r3[p3] = d;
1242                p3 += 1;
1243                Ok(true)
1244            });
1245
1246            assert_eq!(r3, [5, 0, 5]);
1247            assert_eq!(p3, 3);
1248            assert_eq!(rest3.unwrap(), DivisionState::new(0, 4));
1249        }
1250
1251        {
1252            let mut result = Vec::new();
1253            let rem = divide_integral(255u8, 3u8, |d| {
1254                result.push(d);
1255                Ok(true)
1256            });
1257
1258            assert_eq!(rem.ok(), Some(DivisionState::new(0, 3)));
1259            assert_eq!(result, vec![8, 5]);
1260        }
1261
1262        {
1263            let mut result = Vec::new();
1264            let rem = divide_integral(255u8, 3u8, |d| {
1265                result.push(d);
1266                Ok(false)
1267            });
1268
1269            assert_eq!(rem.ok(), Some(DivisionState::new(15, 3)));
1270            assert_eq!(result, vec![8]);
1271        }
1272    }
1273
1274    #[test]
1275    fn test_divide_rem() {
1276        let mut r1: [u8; 1] = [0; 1];
1277        let mut p1: usize = 0;
1278
1279        let mut r2: [u8; 2] = [0; 2];
1280        let mut p2: usize = 0;
1281
1282        let mut r3: [u8; 3] = [0; 3];
1283        let mut p3: usize = 0;
1284
1285        let mut rest1 = None;
1286        divide_rem(1, 3, |s, d| {
1287            r1[p1] = d;
1288            p1 += 1;
1289            rest1 = Some(s.remainder);
1290            Ok(Err(s))
1291        })
1292        .ok();
1293
1294        assert_eq!(r1, [3]);
1295        assert_eq!(p1, 1);
1296        assert_eq!(rest1, Some(1));
1297
1298        p1 = 0;
1299        let rest1 = divide_rem(1, 2, |s, d| {
1300            r1[p1] = d;
1301            p1 += 1;
1302            Ok(Ok(s))
1303        });
1304
1305        assert_eq!(r1, [5]);
1306        assert_eq!(p1, 1);
1307        assert_eq!(rest1.unwrap(), DivisionState::new(0, 2));
1308
1309        let rest2 = divide_rem(500, 2000, |s, d| {
1310            r2[p2] = d;
1311            p2 += 1;
1312            Ok(Ok(s))
1313        });
1314
1315        assert_eq!(r2, [2, 5]);
1316        assert_eq!(p2, 2);
1317        assert_eq!(rest2.unwrap(), DivisionState::new(0, 2000));
1318
1319        let rest3 = divide_rem(2, 1000, |s, d| {
1320            r3[p3] = d;
1321            p3 += 1;
1322            Ok(Ok(s))
1323        });
1324
1325        assert_eq!(r3, [0, 0, 2]);
1326        assert_eq!(p3, 3);
1327        assert_eq!(rest3.unwrap(), DivisionState::new(0, 1000));
1328
1329        p3 = 0;
1330        let rest3 = divide_rem(502, 1000, |s, d| {
1331            r3[p3] = d;
1332            p3 += 1;
1333            Ok(Ok(s))
1334        });
1335
1336        assert_eq!(r3, [5, 0, 2]);
1337        assert_eq!(p3, 3);
1338        assert_eq!(rest3.unwrap(), DivisionState::new(0, 1000));
1339    }
1340}
fraction/division.rs

fraction/
division.rs
