1 //! Big integer type definition.
2 
3 use crate::float::*;
4 use crate::util::*;
5 use super::math::*;
6 
7 // DATA TYPE
8 
9 cfg_if! {
10 if #[cfg(feature = "radix")] {
11     use crate::lib::Vec;
12     type IntStorageType = Vec<Limb>;
13 } else {
14     // Maximum denominator is 767 mantissa digits + 324 exponent,
15     // or 1091 digits, or approximately 3600 bits (round up to 4k).
16     #[cfg(limb_width_32)]
17     type IntStorageType = arrayvec::ArrayVec<[Limb; 128]>;
18 
19     #[cfg(limb_width_64)]
20     type IntStorageType = arrayvec::ArrayVec<[Limb; 64]>;
21 }}  // cfg_if
22 
23 perftools_inline!{
24 /// Calculate the integral ceiling of the binary factor from a basen number.
25 pub(super) fn integral_binary_factor(radix: u32)
26     -> u32
27 {
28     debug_assert_radix!(radix);
29 
30     #[cfg(not(feature = "radix"))] {
31         4
32     }
33 
34     #[cfg(feature = "radix")] {
35         match radix.as_i32() {
36             2  => 1,
37             3  => 2,
38             4  => 2,
39             5  => 3,
40             6  => 3,
41             7  => 3,
42             8  => 3,
43             9  => 4,
44             10 => 4,
45             11 => 4,
46             12 => 4,
47             13 => 4,
48             14 => 4,
49             15 => 4,
50             16 => 4,
51             17 => 5,
52             18 => 5,
53             19 => 5,
54             20 => 5,
55             21 => 5,
56             22 => 5,
57             23 => 5,
58             24 => 5,
59             25 => 5,
60             26 => 5,
61             27 => 5,
62             28 => 5,
63             29 => 5,
64             30 => 5,
65             31 => 5,
66             32 => 5,
67             33 => 6,
68             34 => 6,
69             35 => 6,
70             36 => 6,
71             // Invalid radix
72             _  => unreachable!(),
73         }
74     }
75 }}
76 
77 // BIGINT
78 
79 /// Storage for a big integer type.
80 #[derive(Clone, PartialEq, Eq)]
81 #[cfg_attr(test, derive(Debug))]
82 pub(crate) struct Bigint {
83     /// Internal storage for the Bigint, in little-endian order.
84     pub(crate) data: IntStorageType,
85 }
86 
87 impl Default for Bigint {
default() -> Self88     fn default() -> Self {
89         // We want to avoid lower-order
90         let mut bigint = Bigint { data: IntStorageType::default() };
91         bigint.data.reserve(20);
92         bigint
93     }
94 }
95 
96 impl SharedOps for Bigint {
97     type StorageType = IntStorageType;
98 
99     perftools_inline_always!{
100     fn data<'a>(&'a self) -> &'a Self::StorageType {
101         &self.data
102     }}
103 
104     perftools_inline_always!{
105     fn data_mut<'a>(&'a mut self) -> &'a mut Self::StorageType {
106         &mut self.data
107     }}
108 }
109 
110 impl SmallOps for Bigint {
111 }
112 
113 impl LargeOps for Bigint {
114 }
115 
116 // BIGFLOAT
117 
118 // Adjust the storage capacity for the underlying array.
119 cfg_if! {
120 if #[cfg(limb_width_64)] {
121     type FloatStorageType = arrayvec::ArrayVec<[Limb; 20]>;
122 } else {
123     type FloatStorageType = arrayvec::ArrayVec<[Limb; 36]>;
124 }}   // cfg_if
125 
126 /// Storage for a big floating-point type.
127 #[derive(Clone, PartialEq, Eq)]
128 #[cfg_attr(test, derive(Debug))]
129 pub struct Bigfloat {
130     /// Internal storage for the Bigint, in little-endian order.
131     ///
132     /// Enough storage for up to 10^345, which is 2^1146, or more than
133     /// the max for f64.
134     pub(crate) data: FloatStorageType,
135     /// It also makes sense to store an exponent, since this simplifies
136     /// normalizing and powers of 2.
137     pub(crate) exp: i32,
138 }
139 
140 impl Default for Bigfloat {
141     perftools_inline!{
142     fn default() -> Self {
143         // We want to avoid lower-order
144         let mut bigfloat = Bigfloat { data: FloatStorageType::default(), exp: 0 };
145         bigfloat.data.reserve(10);
146         bigfloat
147     }}
148 }
149 
150 impl SharedOps for Bigfloat {
151     type StorageType = FloatStorageType;
152 
153     perftools_inline_always!{
154     fn data<'a>(&'a self) -> &'a Self::StorageType {
155         &self.data
156     }}
157 
158     perftools_inline_always!{
159     fn data_mut<'a>(&'a mut self) -> &'a mut Self::StorageType {
160         &mut self.data
161     }}
162 }
163 
164 impl SmallOps for Bigfloat {
165     perftools_inline!{
166     fn imul_pow2(&mut self, n: u32) {
167         // Increment exponent to simulate actual multiplication.
168         self.exp += n.as_i32();
169     }}
170 }
171 
172 impl LargeOps for Bigfloat {
173 }
174 
175 // TO BIGFLOAT
176 
177 /// Simple overloads to allow conversions of extended floats to big integers.
178 pub trait ToBigfloat<M: Mantissa> {
to_bigfloat(&self) -> Bigfloat179     fn to_bigfloat(&self) -> Bigfloat;
180 }
181 
182 impl ToBigfloat<u32> for ExtendedFloat<u32> {
183     perftools_inline!{
184     fn to_bigfloat(&self) -> Bigfloat {
185         let mut bigfloat = Bigfloat::from_u32(self.mant);
186         bigfloat.exp = self.exp;
187         bigfloat
188     }}
189 }
190 
191 impl ToBigfloat<u64> for ExtendedFloat<u64> {
192     perftools_inline!{
193     fn to_bigfloat(&self) -> Bigfloat {
194         let mut bigfloat = Bigfloat::from_u64(self.mant);
195         bigfloat.exp = self.exp;
196         bigfloat
197     }}
198 }
199 
200 impl ToBigfloat<u128> for ExtendedFloat<u128> {
201     perftools_inline!{
202     fn to_bigfloat(&self) -> Bigfloat {
203         let mut bigfloat = Bigfloat::from_u128(self.mant);
204         bigfloat.exp = self.exp;
205         bigfloat
206     }}
207 }
208 
209 // TESTS
210 // -----
211 
212 #[cfg(all(test, feature = "correct", feature = "radix"))]
213 mod test {
214     use super::*;
215 
216     #[test]
integral_binary_factor_test()217     fn integral_binary_factor_test() {
218         const TABLE: [u32; 35] = [1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6];
219         for (idx, base) in (2..37).enumerate() {
220             assert_eq!(integral_binary_factor(base), TABLE[idx]);
221         }
222     }
223 }
224