124 lines
3.6 KiB
Plaintext
124 lines
3.6 KiB
Plaintext
#[cfg(target_pointer_width = "64")]
|
|
type USingle = u32;
|
|
#[cfg(target_pointer_width = "64")]
|
|
type UDouble = u64;
|
|
#[cfg(target_pointer_width = "64")]
|
|
const WORD_LEN: i32 = 32;
|
|
|
|
#[cfg(not(target_pointer_width = "64"))]
|
|
type USingle = u16;
|
|
#[cfg(not(target_pointer_width = "64"))]
|
|
type UDouble = u32;
|
|
#[cfg(not(target_pointer_width = "64"))]
|
|
const WORD_LEN: i32 = 16;
|
|
|
|
use std::cmp;
|
|
|
|
#[derive(Debug,Clone)]
|
|
struct BigNum {
|
|
// rep_.size() == 0 if and only if the value is zero.
|
|
// Otherwise, the word rep_[0] keeps the least significant bits.
|
|
rep_: Vec<USingle>,
|
|
}
|
|
|
|
impl BigNum {
|
|
pub fn new(n: USingle) -> BigNum {
|
|
let mut result = BigNum { rep_: vec![] };
|
|
if n > 0 { result.rep_.push(n); }
|
|
result
|
|
}
|
|
pub fn equals(&self, n: USingle) -> bool {
|
|
if n == 0 { return self.rep_.is_empty() }
|
|
if self.rep_.len() > 1 { return false }
|
|
self.rep_[0] == n
|
|
}
|
|
pub fn add_big(&self, addend: &BigNum) -> BigNum {
|
|
let mut result = BigNum::new(0);
|
|
let mut sum = 0 as UDouble;
|
|
let sz1 = self.rep_.len();
|
|
let sz2 = addend.rep_.len();
|
|
for i in 0..cmp::max(sz1, sz2) {
|
|
if i < sz1 { sum += self.rep_[i] as UDouble }
|
|
if i < sz2 { sum += addend.rep_[i] as UDouble }
|
|
result.rep_.push(sum as USingle);
|
|
sum >>= WORD_LEN;
|
|
}
|
|
if sum > 0 { result.rep_.push(sum as USingle) }
|
|
result
|
|
}
|
|
pub fn multiply(&self, factor: USingle) -> BigNum {
|
|
let mut result = BigNum::new(0);
|
|
let mut product = 0 as UDouble;
|
|
for i in 0..self.rep_.len() {
|
|
product += self.rep_[i] as UDouble * factor as UDouble;
|
|
result.rep_.push(product as USingle);
|
|
product >>= WORD_LEN;
|
|
}
|
|
if product > 0 {
|
|
result.rep_.push(product as USingle);
|
|
}
|
|
result
|
|
}
|
|
pub fn divide(&self, divisor: USingle, quotient: &mut BigNum,
|
|
remainder: &mut USingle) {
|
|
quotient.rep_.truncate(0);
|
|
let mut dividend: UDouble;
|
|
*remainder = 0;
|
|
for i in 0..self.rep_.len() {
|
|
let j = self.rep_.len() - 1 - i;
|
|
dividend = ((*remainder as UDouble) << WORD_LEN)
|
|
+ self.rep_[j] as UDouble;
|
|
let quo = (dividend / divisor as UDouble) as USingle;
|
|
*remainder = (dividend % divisor as UDouble) as USingle;
|
|
if quo > 0 || j < self.rep_.len() - 1 {
|
|
quotient.rep_.push(quo);
|
|
}
|
|
}
|
|
quotient.rep_.reverse();
|
|
}
|
|
fn to_string(&self) -> String {
|
|
let mut rep = String::new();
|
|
let mut dividend = (*self).clone();
|
|
let mut remainder = 0 as USingle;
|
|
let mut quotient = BigNum::new(0);
|
|
loop {
|
|
dividend.divide(10, &mut quotient, &mut remainder);
|
|
rep.push(('0' as USingle + remainder) as u8 as char);
|
|
if quotient.equals(0) { break; }
|
|
dividend = quotient.clone();
|
|
}
|
|
rep.chars().rev().collect::<String>()
|
|
}
|
|
}
|
|
|
|
use std::fmt;
|
|
impl fmt::Display for BigNum {
|
|
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
|
|
write!(f, "{}", self.to_string())
|
|
}
|
|
}
|
|
|
|
fn lfact(n: USingle) -> BigNum {
|
|
let mut result = BigNum::new(0);
|
|
let mut f = BigNum::new(1);
|
|
for k in 1 as USingle..n + 1 {
|
|
result = result.add_big(&f);
|
|
f = f.multiply(k);
|
|
}
|
|
result
|
|
}
|
|
|
|
fn main() {
|
|
for i in 0..11 {
|
|
println!("!{} = {}", i, lfact(i));
|
|
}
|
|
for i in 2..12 {
|
|
let j = i * 10;
|
|
println!("!{} = {}", j, lfact(j));
|
|
}
|
|
for i in 1..11 {
|
|
let j = i * 1000;
|
|
println!("!{} has {} digits.", j, lfact(j).to_string().len());
|
|
}
|
|
}
|