smart_big_rational/
util.rs

1// Copyright 2026 The SmartBigRational Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     https://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::ops::{Div, Rem, Shr};
16
17#[derive(Debug, Default, Clone, Copy)]
18pub struct OddDivider<T> {
19    /// Original divisor.
20    pub divisor: T,
21    /// Magic multiplier to compute divisions by this divisor.
22    pub multiplier: T,
23    /// Shift to compute divisions by this divisor.
24    pub shift: u32,
25}
26
27impl<T> OddDivider<T>
28where
29    T: Copy + Shr<u32, Output = T> + Div<Output = T> + Rem<Output = T> + Arithmetic,
30{
31    // Not suitable for powers of 2 (as the shift is adjusted differently).
32    #[inline(always)]
33    fn div_non_power_of_two(&self, x: T) -> T {
34        // See https://rubenvannieuwpoort.nl/posts/division-by-constant-unsigned-integers:
35        //  multiplier = m - 2^N
36        //  hi = (x*m - x*2^N) >> N = x*m / 2^N - x
37        //  y = (2x - x*m / 2^N) / 2 + x*m / 2^N - x
38        //    = x*m / 2^(N+1)
39        //  y >> shift = x*m / 2^(N+shift+1)
40        let (_, hi) = x.widening_mul(self.multiplier);
41        let y = ((x.wrapping_sub(hi)) >> 1).wrapping_add(hi);
42        y >> self.shift
43    }
44
45    #[inline(always)]
46    pub fn div_rem(&self, x: T) -> (T, T) {
47        let q = self.div_non_power_of_two(x);
48        let r = x.wrapping_sub(q.wrapping_mul(self.divisor));
49        (q, r)
50    }
51}
52
53pub trait Arithmetic: Sized {
54    fn wrapping_add(self, other: Self) -> Self;
55
56    fn wrapping_sub(self, other: Self) -> Self;
57
58    fn wrapping_mul(self, other: Self) -> Self;
59
60    /// Returns (low, high) of multiplying `self` by `other`.
61    fn widening_mul(self, other: Self) -> (Self, Self);
62}
63
64impl Arithmetic for u16 {
65    #[inline(always)]
66    fn wrapping_add(self, other: Self) -> Self {
67        self.wrapping_add(other)
68    }
69
70    #[inline(always)]
71    fn wrapping_sub(self, other: Self) -> Self {
72        self.wrapping_sub(other)
73    }
74
75    #[inline(always)]
76    fn wrapping_mul(self, other: Self) -> Self {
77        self.wrapping_mul(other)
78    }
79
80    #[inline(always)]
81    fn widening_mul(self, other: Self) -> (Self, Self) {
82        self.carrying_mul(other, 0)
83    }
84}
85
86impl Arithmetic for u32 {
87    #[inline(always)]
88    fn wrapping_add(self, other: Self) -> Self {
89        self.wrapping_add(other)
90    }
91
92    #[inline(always)]
93    fn wrapping_sub(self, other: Self) -> Self {
94        self.wrapping_sub(other)
95    }
96
97    #[inline(always)]
98    fn wrapping_mul(self, other: Self) -> Self {
99        self.wrapping_mul(other)
100    }
101
102    #[inline(always)]
103    fn widening_mul(self, other: Self) -> (Self, Self) {
104        self.carrying_mul(other, 0)
105    }
106}
107
108impl Arithmetic for u64 {
109    #[inline(always)]
110    fn wrapping_add(self, other: Self) -> Self {
111        self.wrapping_add(other)
112    }
113
114    #[inline(always)]
115    fn wrapping_sub(self, other: Self) -> Self {
116        self.wrapping_sub(other)
117    }
118
119    #[inline(always)]
120    fn wrapping_mul(self, other: Self) -> Self {
121        self.wrapping_mul(other)
122    }
123
124    #[inline(always)]
125    fn widening_mul(self, other: Self) -> (Self, Self) {
126        self.carrying_mul(other, 0)
127    }
128}
smart_big_rational/util.rs

smart_big_rational/
util.rs
