| 1 |
use std::ops::{AddAssign, MulAssign}; |
| 2 |
|
| 3 |
// For implementing base10_digits() accessor on LitInt. |
| 4 |
pub struct BigInt { |
| 5 |
digits: Vec<u8>, |
| 6 |
} |
| 7 |
|
| 8 |
impl BigInt { |
| 9 |
pub fn new() -> Self { |
| 10 |
BigInt { digits: Vec::new() } |
| 11 |
} |
| 12 |
|
| 13 |
pub fn to_string(&self) -> String { |
| 14 |
let mut repr = String::with_capacity(self.digits.len()); |
| 15 |
|
| 16 |
let mut has_nonzero = false; |
| 17 |
for digit in self.digits.iter().rev() { |
| 18 |
has_nonzero |= *digit != 0; |
| 19 |
if has_nonzero { |
| 20 |
repr.push((*digit + b'0') as char); |
| 21 |
} |
| 22 |
} |
| 23 |
|
| 24 |
if repr.is_empty() { |
| 25 |
repr.push('0'); |
| 26 |
} |
| 27 |
|
| 28 |
repr |
| 29 |
} |
| 30 |
|
| 31 |
fn reserve_two_digits(&mut self) { |
| 32 |
let len = self.digits.len(); |
| 33 |
let desired = |
| 34 |
len + !self.digits.ends_with(&[0, 0]) as usize + !self.digits.ends_with(&[0]) as usize; |
| 35 |
self.digits.resize(desired, 0); |
| 36 |
} |
| 37 |
} |
| 38 |
|
| 39 |
impl AddAssign<u8> for BigInt { |
| 40 |
// Assumes increment <16. |
| 41 |
fn add_assign(&mut self, mut increment: u8) { |
| 42 |
self.reserve_two_digits(); |
| 43 |
|
| 44 |
let mut i = 0; |
| 45 |
while increment > 0 { |
| 46 |
let sum = self.digits[i] + increment; |
| 47 |
self.digits[i] = sum % 10; |
| 48 |
increment = sum / 10; |
| 49 |
i += 1; |
| 50 |
} |
| 51 |
} |
| 52 |
} |
| 53 |
|
| 54 |
impl MulAssign<u8> for BigInt { |
| 55 |
// Assumes base <=16. |
| 56 |
fn mul_assign(&mut self, base: u8) { |
| 57 |
self.reserve_two_digits(); |
| 58 |
|
| 59 |
let mut carry = 0; |
| 60 |
for digit in &mut self.digits { |
| 61 |
let prod = *digit * base + carry; |
| 62 |
*digit = prod % 10; |
| 63 |
carry = prod / 10; |
| 64 |
} |
| 65 |
} |
| 66 |
} |