1 use crate::error::{FendError, Interrupt};
2 use crate::format::Format;
3 use crate::interrupt::test_int;
4 use crate::num::{out_of_range, Base, Exact, Range, RangeBound};
5 use crate::result::FResult;
6 use crate::serialize::{Deserialize, Serialize};
7 use std::cmp::{max, Ordering};
8 use std::{fmt, hash, io};
9
10 #[derive(Clone)]
11 pub(crate) enum BigUint {
12 Small(u64),
13 // little-endian, len >= 1
14 Large(Vec<u64>),
15 }
16
17 impl hash::Hash for BigUint {
hash<H: hash::Hasher>(&self, state: &mut H)18 fn hash<H: hash::Hasher>(&self, state: &mut H) {
19 match self {
20 Small(u) => u.hash(state),
21 Large(v) => {
22 for u in v {
23 u.hash(state);
24 }
25 }
26 }
27 }
28 }
29
30 use BigUint::{Large, Small};
31
32 #[allow(clippy::cast_possible_truncation)]
truncate(n: u128) -> u6433 const fn truncate(n: u128) -> u64 {
34 n as u64
35 }
36
37 impl BigUint {
is_zero(&self) -> bool38 fn is_zero(&self) -> bool {
39 match self {
40 Small(n) => *n == 0,
41 Large(value) => {
42 for v in value {
43 if *v != 0 {
44 return false;
45 }
46 }
47 true
48 }
49 }
50 }
51
get(&self, idx: usize) -> u6452 fn get(&self, idx: usize) -> u64 {
53 match self {
54 Small(n) => {
55 if idx == 0 {
56 *n
57 } else {
58 0
59 }
60 }
61 Large(value) => {
62 if idx < value.len() {
63 value[idx]
64 } else {
65 0
66 }
67 }
68 }
69 }
70
try_as_usize<I: Interrupt>(&self, int: &I) -> FResult<usize>71 pub(crate) fn try_as_usize<I: Interrupt>(&self, int: &I) -> FResult<usize> {
72 let error = || -> FResult<_> {
73 Ok(out_of_range(
74 self.fm(int)?,
75 Range {
76 start: RangeBound::Closed(0),
77 end: RangeBound::Closed(usize::MAX),
78 },
79 ))
80 };
81
82 Ok(match self {
83 Small(n) => {
84 if let Ok(res) = usize::try_from(*n) {
85 res
86 } else {
87 return Err(error()?);
88 }
89 }
90 Large(v) => {
91 // todo use correct method to get actual length excluding leading zeroes
92 if v.len() == 1 {
93 if let Ok(res) = usize::try_from(v[0]) {
94 res
95 } else {
96 return Err(error()?);
97 }
98 } else {
99 return Err(error()?);
100 }
101 }
102 })
103 }
104
105 #[allow(clippy::cast_precision_loss)]
as_f64(&self) -> f64106 pub(crate) fn as_f64(&self) -> f64 {
107 match self {
108 Small(n) => *n as f64,
109 Large(v) => {
110 let mut res = 0.0;
111 for &n in v.iter().rev() {
112 res *= u64::MAX as f64;
113 res += n as f64;
114 }
115 res
116 }
117 }
118 }
119
make_large(&mut self)120 fn make_large(&mut self) {
121 match self {
122 Small(n) => {
123 *self = Large(vec![*n]);
124 }
125 Large(_) => (),
126 }
127 }
128
set(&mut self, idx: usize, new_value: u64)129 fn set(&mut self, idx: usize, new_value: u64) {
130 match self {
131 Small(n) => {
132 if idx == 0 {
133 *n = new_value;
134 } else if new_value == 0 {
135 // no need to do anything
136 } else {
137 self.make_large();
138 self.set(idx, new_value);
139 }
140 }
141 Large(value) => {
142 while idx >= value.len() {
143 value.push(0);
144 }
145 value[idx] = new_value;
146 }
147 }
148 }
149
value_len(&self) -> usize150 fn value_len(&self) -> usize {
151 match self {
152 Small(_) => 1,
153 Large(value) => value.len(),
154 }
155 }
156
value_push(&mut self, new: u64)157 fn value_push(&mut self, new: u64) {
158 if new == 0 {
159 return;
160 }
161 self.make_large();
162 match self {
163 Small(_) => unreachable!(),
164 Large(v) => v.push(new),
165 }
166 }
167
gcd<I: Interrupt>(mut a: Self, mut b: Self, int: &I) -> FResult<Self>168 pub(crate) fn gcd<I: Interrupt>(mut a: Self, mut b: Self, int: &I) -> FResult<Self> {
169 while b >= 1.into() {
170 let r = a.rem(&b, int)?;
171 a = b;
172 b = r;
173 }
174
175 Ok(a)
176 }
177
pow<I: Interrupt>(a: &Self, b: &Self, int: &I) -> FResult<Self>178 pub(crate) fn pow<I: Interrupt>(a: &Self, b: &Self, int: &I) -> FResult<Self> {
179 if a.is_zero() && b.is_zero() {
180 return Err(FendError::ZeroToThePowerOfZero);
181 }
182 if b.is_zero() {
183 return Ok(Self::from(1));
184 }
185 if b.value_len() > 1 {
186 return Err(FendError::ExponentTooLarge);
187 }
188 a.pow_internal(b.get(0), int)
189 }
190
191 // computes the exact `n`-th root if possible, otherwise the next lower integer
192 #[allow(clippy::redundant_clone)]
root_n<I: Interrupt>(self, n: &Self, int: &I) -> FResult<Exact<Self>>193 pub(crate) fn root_n<I: Interrupt>(self, n: &Self, int: &I) -> FResult<Exact<Self>> {
194 if self == 0.into() || self == 1.into() || n == &Self::from(1) {
195 return Ok(Exact::new(self, true));
196 }
197 let mut low_guess = Self::from(1);
198 let mut high_guess = self.clone();
199 while high_guess.clone().sub(&low_guess) > 1.into() {
200 test_int(int)?;
201 let mut guess = low_guess.clone().add(&high_guess);
202 guess.rshift(int)?;
203
204 let res = Self::pow(&guess, n, int)?;
205 match res.cmp(&self) {
206 Ordering::Equal => return Ok(Exact::new(guess, true)),
207 Ordering::Greater => high_guess = guess,
208 Ordering::Less => low_guess = guess,
209 }
210 }
211 Ok(Exact::new(low_guess, false))
212 }
213
pow_internal<I: Interrupt>(&self, mut exponent: u64, int: &I) -> FResult<Self>214 fn pow_internal<I: Interrupt>(&self, mut exponent: u64, int: &I) -> FResult<Self> {
215 let mut result = Self::from(1);
216 let mut base = self.clone();
217 while exponent > 0 {
218 test_int(int)?;
219 if exponent % 2 == 1 {
220 result = result.mul(&base, int)?;
221 }
222 exponent >>= 1;
223 base = base.clone().mul(&base, int)?;
224 }
225 Ok(result)
226 }
227
lshift<I: Interrupt>(&mut self, int: &I) -> FResult<()>228 fn lshift<I: Interrupt>(&mut self, int: &I) -> FResult<()> {
229 match self {
230 Small(n) => {
231 if *n & 0xc000_0000_0000_0000 == 0 {
232 *n <<= 1;
233 } else {
234 *self = Large(vec![*n << 1, *n >> 63]);
235 }
236 }
237 Large(value) => {
238 if value[value.len() - 1] & (1_u64 << 63) != 0 {
239 value.push(0);
240 }
241 for i in (0..value.len()).rev() {
242 test_int(int)?;
243 value[i] <<= 1;
244 if i != 0 {
245 value[i] |= value[i - 1] >> 63;
246 }
247 }
248 }
249 }
250 Ok(())
251 }
252
rshift<I: Interrupt>(&mut self, int: &I) -> FResult<()>253 fn rshift<I: Interrupt>(&mut self, int: &I) -> FResult<()> {
254 match self {
255 Small(n) => *n >>= 1,
256 Large(value) => {
257 for i in 0..value.len() {
258 test_int(int)?;
259 value[i] >>= 1;
260 let next = if i + 1 >= value.len() {
261 0
262 } else {
263 value[i + 1]
264 };
265 value[i] |= next << 63;
266 }
267 }
268 }
269 Ok(())
270 }
271
divmod<I: Interrupt>(&self, other: &Self, int: &I) -> FResult<(Self, Self)>272 pub(crate) fn divmod<I: Interrupt>(&self, other: &Self, int: &I) -> FResult<(Self, Self)> {
273 if let (Small(a), Small(b)) = (self, other) {
274 if let (Some(div_res), Some(mod_res)) = (a.checked_div(*b), a.checked_rem(*b)) {
275 return Ok((Small(div_res), Small(mod_res)));
276 }
277 return Err(FendError::DivideByZero);
278 }
279 if other.is_zero() {
280 return Err(FendError::DivideByZero);
281 }
282 if other == &Self::from(1) {
283 return Ok((self.clone(), Self::from(0)));
284 }
285 if self.is_zero() {
286 return Ok((Self::from(0), Self::from(0)));
287 }
288 if self < other {
289 return Ok((Self::from(0), self.clone()));
290 }
291 if self == other {
292 return Ok((Self::from(1), Self::from(0)));
293 }
294 if other == &Self::from(2) {
295 let mut div_result = self.clone();
296 div_result.rshift(int)?;
297 let modulo = self.get(0) & 1;
298 return Ok((div_result, Self::from(modulo)));
299 }
300 // binary long division
301 let mut q = Self::from(0);
302 let mut r = Self::from(0);
303 for i in (0..self.value_len()).rev() {
304 test_int(int)?;
305 for j in (0..64).rev() {
306 r.lshift(int)?;
307 let bit_of_self = u64::from((self.get(i) & (1 << j)) != 0);
308 r.set(0, r.get(0) | bit_of_self);
309 if &r >= other {
310 r = r.sub(other);
311 q.set(i, q.get(i) | (1 << j));
312 }
313 }
314 }
315 Ok((q, r))
316 }
317
318 /// computes self *= other
mul_internal<I: Interrupt>(&mut self, other: &Self, int: &I) -> FResult<()>319 fn mul_internal<I: Interrupt>(&mut self, other: &Self, int: &I) -> FResult<()> {
320 if self.is_zero() || other.is_zero() {
321 *self = Self::from(0);
322 return Ok(());
323 }
324 let self_clone = self.clone();
325 self.make_large();
326 match self {
327 Small(_) => unreachable!(),
328 Large(v) => {
329 v.clear();
330 v.push(0);
331 }
332 }
333 for i in 0..other.value_len() {
334 test_int(int)?;
335 self.add_assign_internal(&self_clone, other.get(i), i);
336 }
337 Ok(())
338 }
339
340 /// computes `self += (other * mul_digit) << (64 * shift)`
add_assign_internal(&mut self, other: &Self, mul_digit: u64, shift: usize)341 fn add_assign_internal(&mut self, other: &Self, mul_digit: u64, shift: usize) {
342 let mut carry = 0;
343 for i in 0..max(self.value_len(), other.value_len() + shift) {
344 let a = self.get(i);
345 let b = if i >= shift { other.get(i - shift) } else { 0 };
346 let sum = u128::from(a) + (u128::from(b) * u128::from(mul_digit)) + u128::from(carry);
347 self.set(i, truncate(sum));
348 carry = truncate(sum >> 64);
349 }
350 if carry != 0 {
351 self.value_push(carry);
352 }
353 }
354
355 // Note: 0! = 1, 1! = 1
factorial<I: Interrupt>(mut self, int: &I) -> FResult<Self>356 pub(crate) fn factorial<I: Interrupt>(mut self, int: &I) -> FResult<Self> {
357 let mut res = Self::from(1);
358 while self > 1.into() {
359 test_int(int)?;
360 res = res.mul(&self, int)?;
361 self = self.sub(&1.into());
362 }
363 Ok(res)
364 }
365
mul<I: Interrupt>(mut self, other: &Self, int: &I) -> FResult<Self>366 pub(crate) fn mul<I: Interrupt>(mut self, other: &Self, int: &I) -> FResult<Self> {
367 if let (Small(a), Small(b)) = (&self, &other) {
368 if let Some(res) = a.checked_mul(*b) {
369 return Ok(Self::from(res));
370 }
371 }
372 self.mul_internal(other, int)?;
373 Ok(self)
374 }
375
rem<I: Interrupt>(&self, other: &Self, int: &I) -> FResult<Self>376 fn rem<I: Interrupt>(&self, other: &Self, int: &I) -> FResult<Self> {
377 Ok(self.divmod(other, int)?.1)
378 }
379
is_even<I: Interrupt>(&self, int: &I) -> FResult<bool>380 pub(crate) fn is_even<I: Interrupt>(&self, int: &I) -> FResult<bool> {
381 Ok(self.divmod(&Self::from(2), int)?.1 == 0.into())
382 }
383
div<I: Interrupt>(self, other: &Self, int: &I) -> FResult<Self>384 pub(crate) fn div<I: Interrupt>(self, other: &Self, int: &I) -> FResult<Self> {
385 Ok(self.divmod(other, int)?.0)
386 }
387
add(mut self, other: &Self) -> Self388 pub(crate) fn add(mut self, other: &Self) -> Self {
389 self.add_assign_internal(other, 1, 0);
390 self
391 }
392
sub(self, other: &Self) -> Self393 pub(crate) fn sub(self, other: &Self) -> Self {
394 if let (Small(a), Small(b)) = (&self, &other) {
395 return Self::from(a - b);
396 }
397 match self.cmp(other) {
398 Ordering::Equal => return Self::from(0),
399 Ordering::Less => unreachable!("number would be less than 0"),
400 Ordering::Greater => (),
401 };
402 if other.is_zero() {
403 return self;
404 }
405 let mut carry = 0; // 0 or 1
406 let mut res = match self {
407 Large(x) => x,
408 Small(v) => vec![v],
409 };
410 if res.len() < other.value_len() {
411 res.resize(other.value_len(), 0);
412 }
413 for (i, a) in res.iter_mut().enumerate() {
414 let b = other.get(i);
415 if !(b == std::u64::MAX && carry == 1) && *a >= b + carry {
416 *a = *a - b - carry;
417 carry = 0;
418 } else {
419 let next_digit =
420 u128::from(*a) + ((1_u128) << 64) - u128::from(b) - u128::from(carry);
421 *a = truncate(next_digit);
422 carry = 1;
423 }
424 }
425 assert_eq!(carry, 0);
426 Large(res)
427 }
428
is_definitely_zero(&self) -> bool429 pub(crate) const fn is_definitely_zero(&self) -> bool {
430 match self {
431 Small(x) => *x == 0,
432 Large(_) => false,
433 }
434 }
435
is_definitely_one(&self) -> bool436 pub(crate) const fn is_definitely_one(&self) -> bool {
437 match self {
438 Small(x) => *x == 1,
439 Large(_) => false,
440 }
441 }
442
serialize(&self, write: &mut impl io::Write) -> FResult<()>443 pub(crate) fn serialize(&self, write: &mut impl io::Write) -> FResult<()> {
444 match self {
445 Small(x) => {
446 1u8.serialize(write)?;
447 x.serialize(write)?;
448 }
449 Large(v) => {
450 2u8.serialize(write)?;
451 v.len().serialize(write)?;
452 for b in v {
453 b.serialize(write)?;
454 }
455 }
456 }
457 Ok(())
458 }
459
deserialize(read: &mut impl io::Read) -> FResult<Self>460 pub(crate) fn deserialize(read: &mut impl io::Read) -> FResult<Self> {
461 let kind = u8::deserialize(read)?;
462 Ok(match kind {
463 1 => Self::Small(u64::deserialize(read)?),
464 2 => {
465 let len = usize::deserialize(read)?;
466 let mut v = Vec::with_capacity(len);
467 for _ in 0..len {
468 v.push(u64::deserialize(read)?);
469 }
470 Self::Large(v)
471 }
472 _ => return Err(FendError::DeserializationError),
473 })
474 }
475
bitwise_and(self, rhs: &Self) -> Self476 pub(crate) fn bitwise_and(self, rhs: &Self) -> Self {
477 match (self, rhs) {
478 (Small(a), Small(b)) => Small(a & *b),
479 (Large(a), Small(b)) => Small(a[0] & *b),
480 (Small(a), Large(b)) => Small(a & b[0]),
481 (Large(a), Large(b)) => {
482 let mut result = b.clone();
483 for (i, res_i) in result.iter_mut().enumerate() {
484 *res_i &= a.get(i).unwrap_or(&0);
485 }
486 Large(result)
487 }
488 }
489 }
490
bitwise_or(self, rhs: &Self) -> Self491 pub(crate) fn bitwise_or(self, rhs: &Self) -> Self {
492 match (self, rhs) {
493 (Small(a), Small(b)) => Small(a | *b),
494 (Large(mut a), Small(b)) => {
495 a[0] |= b;
496 Large(a)
497 }
498 (Small(a), Large(b)) => {
499 let mut result = b.clone();
500 result[0] |= a;
501 Large(result)
502 }
503 (Large(mut a), Large(b)) => {
504 while a.len() < b.len() {
505 a.push(0);
506 }
507 for i in 0..b.len() {
508 a[i] |= b[i];
509 }
510 Large(a)
511 }
512 }
513 }
514
bitwise_xor(self, rhs: &Self) -> Self515 pub(crate) fn bitwise_xor(self, rhs: &Self) -> Self {
516 match (self, rhs) {
517 (Small(a), Small(b)) => Small(a ^ *b),
518 (Large(mut a), Small(b)) => {
519 a[0] ^= b;
520 Large(a)
521 }
522 (Small(a), Large(b)) => {
523 let mut result = b.clone();
524 result[0] ^= a;
525 Large(result)
526 }
527 (Large(mut a), Large(b)) => {
528 while a.len() < b.len() {
529 a.push(0);
530 }
531 for i in 0..b.len() {
532 a[i] ^= b[i];
533 }
534 Large(a)
535 }
536 }
537 }
538
lshift_n<I: Interrupt>(mut self, rhs: &Self, int: &I) -> FResult<Self>539 pub(crate) fn lshift_n<I: Interrupt>(mut self, rhs: &Self, int: &I) -> FResult<Self> {
540 let mut rhs = rhs.try_as_usize(int)?;
541 if rhs > 64 {
542 self.make_large();
543 match &mut self {
544 Large(v) => {
545 while rhs >= 64 {
546 v.insert(0, 0);
547 rhs -= 64;
548 }
549 }
550 Small(_) => unreachable!(),
551 }
552 }
553 for _ in 0..rhs {
554 self.lshift(int)?;
555 }
556 Ok(self)
557 }
558
rshift_n<I: Interrupt>(mut self, rhs: &Self, int: &I) -> FResult<Self>559 pub(crate) fn rshift_n<I: Interrupt>(mut self, rhs: &Self, int: &I) -> FResult<Self> {
560 let rhs = rhs.try_as_usize(int)?;
561 for _ in 0..rhs {
562 if self.is_zero() {
563 break;
564 }
565 self.rshift(int)?;
566 }
567 Ok(self)
568 }
569 }
570
571 impl Ord for BigUint {
cmp(&self, other: &Self) -> Ordering572 fn cmp(&self, other: &Self) -> Ordering {
573 if let (Small(a), Small(b)) = (self, other) {
574 return a.cmp(b);
575 }
576 let mut i = std::cmp::max(self.value_len(), other.value_len());
577 while i != 0 {
578 let v1 = self.get(i - 1);
579 let v2 = other.get(i - 1);
580 match v1.cmp(&v2) {
581 Ordering::Less => return Ordering::Less,
582 Ordering::Greater => return Ordering::Greater,
583 Ordering::Equal => (),
584 }
585 i -= 1;
586 }
587
588 Ordering::Equal
589 }
590 }
591
592 impl PartialOrd for BigUint {
partial_cmp(&self, other: &Self) -> Option<Ordering>593 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
594 Some(self.cmp(other))
595 }
596 }
597
598 impl PartialEq for BigUint {
eq(&self, other: &Self) -> bool599 fn eq(&self, other: &Self) -> bool {
600 self.cmp(other) == Ordering::Equal
601 }
602 }
603
604 impl Eq for BigUint {}
605
606 impl From<u64> for BigUint {
from(val: u64) -> Self607 fn from(val: u64) -> Self {
608 Small(val)
609 }
610 }
611
612 impl fmt::Debug for BigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result613 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
614 match self {
615 Small(n) => write!(f, "{n}")?,
616 Large(value) => {
617 write!(f, "[")?;
618 let mut first = true;
619 for v in value.iter().rev() {
620 if !first {
621 write!(f, ", ")?;
622 }
623 write!(f, "{v}")?;
624 first = false;
625 }
626 write!(f, "]")?;
627 }
628 }
629 Ok(())
630 }
631 }
632
633 #[derive(Default)]
634 pub(crate) struct FormatOptions {
635 pub(crate) base: Base,
636 pub(crate) write_base_prefix: bool,
637 pub(crate) sf_limit: Option<usize>,
638 }
639
640 impl Format for BigUint {
641 type Params = FormatOptions;
642 type Out = FormattedBigUint;
643
format<I: Interrupt>(&self, params: &Self::Params, int: &I) -> FResult<Exact<Self::Out>>644 fn format<I: Interrupt>(&self, params: &Self::Params, int: &I) -> FResult<Exact<Self::Out>> {
645 let base_prefix = if params.write_base_prefix {
646 Some(params.base)
647 } else {
648 None
649 };
650
651 if self.is_zero() {
652 return Ok(Exact::new(
653 FormattedBigUint {
654 base: base_prefix,
655 ty: FormattedBigUintType::Zero,
656 },
657 true,
658 ));
659 }
660
661 let mut num = self.clone();
662 Ok(
663 if num.value_len() == 1 && params.base.base_as_u8() == 10 && params.sf_limit.is_none() {
664 Exact::new(
665 FormattedBigUint {
666 base: base_prefix,
667 ty: FormattedBigUintType::Simple(num.get(0)),
668 },
669 true,
670 )
671 } else {
672 let base_as_u128: u128 = params.base.base_as_u8().into();
673 let mut divisor = base_as_u128;
674 let mut rounds = 1;
675 // note that the string is reversed: this is the number of trailing zeroes while
676 // printing, but actually the number of leading zeroes in the final number
677 let mut num_trailing_zeroes = 0;
678 let mut num_leading_zeroes = 0;
679 let mut finished_counting_leading_zeroes = false;
680 while divisor
681 < u128::MAX
682 .checked_div(base_as_u128)
683 .expect("base appears to be 0")
684 {
685 divisor *= base_as_u128;
686 rounds += 1;
687 }
688 let divisor = Self::Large(vec![truncate(divisor), truncate(divisor >> 64)]);
689 let mut output = String::with_capacity(rounds);
690 while !num.is_zero() {
691 test_int(int)?;
692 let divmod_res = num.divmod(&divisor, int)?;
693 let mut digit_group_value =
694 u128::from(divmod_res.1.get(1)) << 64 | u128::from(divmod_res.1.get(0));
695 for _ in 0..rounds {
696 let digit_value = digit_group_value % base_as_u128;
697 digit_group_value /= base_as_u128;
698 let ch = Base::digit_as_char(truncate(digit_value)).unwrap();
699 if ch == '0' {
700 num_trailing_zeroes += 1;
701 } else {
702 for _ in 0..num_trailing_zeroes {
703 output.push('0');
704 if !finished_counting_leading_zeroes {
705 num_leading_zeroes += 1;
706 }
707 }
708 finished_counting_leading_zeroes = true;
709 num_trailing_zeroes = 0;
710 output.push(ch);
711 }
712 }
713 num = divmod_res.0;
714 }
715 let exact = params
716 .sf_limit
717 .map_or(true, |sf| sf >= output.len() - num_leading_zeroes);
718 Exact::new(
719 FormattedBigUint {
720 base: base_prefix,
721 ty: FormattedBigUintType::Complex(output, params.sf_limit),
722 },
723 exact,
724 )
725 },
726 )
727 }
728 }
729
730 #[derive(Debug)]
731 enum FormattedBigUintType {
732 Zero,
733 Simple(u64),
734 Complex(String, Option<usize>),
735 }
736
737 #[must_use]
738 #[derive(Debug)]
739 pub(crate) struct FormattedBigUint {
740 base: Option<Base>,
741 ty: FormattedBigUintType,
742 }
743
744 impl fmt::Display for FormattedBigUint {
fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error>745 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> Result<(), fmt::Error> {
746 if let Some(base) = self.base {
747 base.write_prefix(f)?;
748 }
749 match &self.ty {
750 FormattedBigUintType::Zero => write!(f, "0")?,
751 FormattedBigUintType::Simple(i) => write!(f, "{i}")?,
752 FormattedBigUintType::Complex(s, sf_limit) => {
753 for (i, ch) in s.chars().rev().enumerate() {
754 if sf_limit.is_some() && &Some(i) >= sf_limit {
755 write!(f, "0")?;
756 } else {
757 write!(f, "{ch}")?;
758 }
759 }
760 }
761 }
762 Ok(())
763 }
764 }
765
766 impl FormattedBigUint {
num_digits(&self) -> usize767 pub(crate) fn num_digits(&self) -> usize {
768 match &self.ty {
769 FormattedBigUintType::Zero => 1,
770 FormattedBigUintType::Simple(i) => {
771 if *i <= 9 {
772 1
773 } else {
774 i.to_string().len()
775 }
776 }
777 FormattedBigUintType::Complex(s, _) => s.len(),
778 }
779 }
780 }
781
782 #[cfg(test)]
783 mod tests {
784 use super::BigUint;
785 type Res = Result<(), crate::error::FendError>;
786
787 #[test]
test_sqrt() -> Res788 fn test_sqrt() -> Res {
789 let two = &BigUint::from(2);
790 let int = crate::interrupt::Never;
791 let test_sqrt_inner = |n, expected_root, exact| -> Res {
792 let actual = BigUint::from(n).root_n(two, &int)?;
793 assert_eq!(actual.value, BigUint::from(expected_root));
794 assert_eq!(actual.exact, exact);
795 Ok(())
796 };
797 test_sqrt_inner(0, 0, true)?;
798 test_sqrt_inner(1, 1, true)?;
799 test_sqrt_inner(2, 1, false)?;
800 test_sqrt_inner(3, 1, false)?;
801 test_sqrt_inner(4, 2, true)?;
802 test_sqrt_inner(5, 2, false)?;
803 test_sqrt_inner(6, 2, false)?;
804 test_sqrt_inner(7, 2, false)?;
805 test_sqrt_inner(8, 2, false)?;
806 test_sqrt_inner(9, 3, true)?;
807 test_sqrt_inner(10, 3, false)?;
808 test_sqrt_inner(11, 3, false)?;
809 test_sqrt_inner(12, 3, false)?;
810 test_sqrt_inner(13, 3, false)?;
811 test_sqrt_inner(14, 3, false)?;
812 test_sqrt_inner(15, 3, false)?;
813 test_sqrt_inner(16, 4, true)?;
814 test_sqrt_inner(17, 4, false)?;
815 test_sqrt_inner(18, 4, false)?;
816 test_sqrt_inner(19, 4, false)?;
817 test_sqrt_inner(20, 4, false)?;
818 test_sqrt_inner(200_000, 447, false)?;
819 test_sqrt_inner(1_740_123_984_719_364_372, 1_319_137_591, false)?;
820 let val = BigUint::Large(vec![0, 3_260_954_456_333_195_555]).root_n(two, &int)?;
821 assert_eq!(val.value, BigUint::from(7_755_900_482_342_532_476));
822 assert!(!val.exact);
823 Ok(())
824 }
825
826 #[test]
test_cmp()827 fn test_cmp() {
828 assert_eq!(BigUint::from(0), BigUint::from(0));
829 assert!(BigUint::from(0) < BigUint::from(1));
830 assert!(BigUint::from(100) > BigUint::from(1));
831 assert!(BigUint::from(10_000_000) > BigUint::from(1));
832 assert!(BigUint::from(10_000_000) > BigUint::from(9_999_999));
833 }
834
835 #[test]
test_addition()836 fn test_addition() {
837 assert_eq!(BigUint::from(2).add(&BigUint::from(2)), BigUint::from(4));
838 assert_eq!(BigUint::from(5).add(&BigUint::from(3)), BigUint::from(8));
839 assert_eq!(
840 BigUint::from(0).add(&BigUint::Large(vec![0, 9_223_372_036_854_775_808, 0])),
841 BigUint::Large(vec![0, 9_223_372_036_854_775_808, 0])
842 );
843 }
844
845 #[test]
test_sub()846 fn test_sub() {
847 assert_eq!(BigUint::from(5).sub(&BigUint::from(3)), BigUint::from(2));
848 assert_eq!(BigUint::from(0).sub(&BigUint::from(0)), BigUint::from(0));
849 }
850
851 #[test]
test_multiplication() -> Res852 fn test_multiplication() -> Res {
853 let int = &crate::interrupt::Never;
854 assert_eq!(
855 BigUint::from(20).mul(&BigUint::from(3), int)?,
856 BigUint::from(60)
857 );
858 Ok(())
859 }
860
861 #[test]
test_small_division_by_two() -> Res862 fn test_small_division_by_two() -> Res {
863 let int = &crate::interrupt::Never;
864 let two = BigUint::from(2);
865 assert_eq!(BigUint::from(0).div(&two, int)?, BigUint::from(0));
866 assert_eq!(BigUint::from(1).div(&two, int)?, BigUint::from(0));
867 assert_eq!(BigUint::from(2).div(&two, int)?, BigUint::from(1));
868 assert_eq!(BigUint::from(3).div(&two, int)?, BigUint::from(1));
869 assert_eq!(BigUint::from(4).div(&two, int)?, BigUint::from(2));
870 assert_eq!(BigUint::from(5).div(&two, int)?, BigUint::from(2));
871 assert_eq!(BigUint::from(6).div(&two, int)?, BigUint::from(3));
872 assert_eq!(BigUint::from(7).div(&two, int)?, BigUint::from(3));
873 assert_eq!(BigUint::from(8).div(&two, int)?, BigUint::from(4));
874 Ok(())
875 }
876
877 #[test]
test_rem() -> Res878 fn test_rem() -> Res {
879 let int = &crate::interrupt::Never;
880 let three = BigUint::from(3);
881 assert_eq!(BigUint::from(20).rem(&three, int)?, BigUint::from(2));
882 assert_eq!(BigUint::from(21).rem(&three, int)?, BigUint::from(0));
883 assert_eq!(BigUint::from(22).rem(&three, int)?, BigUint::from(1));
884 assert_eq!(BigUint::from(23).rem(&three, int)?, BigUint::from(2));
885 assert_eq!(BigUint::from(24).rem(&three, int)?, BigUint::from(0));
886 Ok(())
887 }
888
889 #[test]
test_lshift() -> Res890 fn test_lshift() -> Res {
891 let int = &crate::interrupt::Never;
892 let mut n = BigUint::from(1);
893 for _ in 0..100 {
894 n.lshift(int)?;
895 assert_eq!(n.get(0) & 1, 0);
896 }
897 Ok(())
898 }
899
900 #[test]
test_gcd() -> Res901 fn test_gcd() -> Res {
902 let int = &crate::interrupt::Never;
903 assert_eq!(BigUint::gcd(2.into(), 4.into(), int)?, 2.into());
904 assert_eq!(BigUint::gcd(4.into(), 2.into(), int)?, 2.into());
905 assert_eq!(BigUint::gcd(37.into(), 43.into(), int)?, 1.into());
906 assert_eq!(BigUint::gcd(43.into(), 37.into(), int)?, 1.into());
907 assert_eq!(BigUint::gcd(215.into(), 86.into(), int)?, 43.into());
908 assert_eq!(BigUint::gcd(86.into(), 215.into(), int)?, 43.into());
909 Ok(())
910 }
911
912 #[test]
test_add_assign_internal()913 fn test_add_assign_internal() {
914 // 0 += (1 * 1) << (64 * 1)
915 let mut x = BigUint::from(0);
916 x.add_assign_internal(&BigUint::from(1), 1, 1);
917 assert_eq!(x, BigUint::Large(vec![0, 1]));
918 }
919
920 #[test]
test_large_lshift() -> Res921 fn test_large_lshift() -> Res {
922 let int = &crate::interrupt::Never;
923 let mut a = BigUint::from(9_223_372_036_854_775_808);
924 a.lshift(int)?;
925 assert!(!a.is_zero());
926 Ok(())
927 }
928
929 #[test]
test_big_multiplication() -> Res930 fn test_big_multiplication() -> Res {
931 let int = &crate::interrupt::Never;
932 assert_eq!(
933 BigUint::from(1).mul(&BigUint::Large(vec![0, 1]), int)?,
934 BigUint::Large(vec![0, 1])
935 );
936 Ok(())
937 }
938 }
939