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