gistfile1.rs

//big num library in Rust

static MD: int = 1000000000;
enum BigNumber {
   End(int),
   Segment(int, ~BigNumber, int)
}

fn make(val: int) -> ~BigNumber { 
   if(val > MD) { ~Segment(val/MD, ~End(val % MD), 1) }
   else { ~End(val) }
}

fn levup(num: ~BigNumber, levdif: int) -> ~BigNumber {
   match(num) {
      ~End(val) => ~Segment(val, ~End(0), levdif),
      ~Segment(quot, rem, lev) => ~Segment(quot, levup(rem, levdif), lev + levdif)
   }
}

fn multiply(left: ~BigNumber, right: ~BigNumber) -> ~BigNumber {
   match(left) {
      ~End(val) => multi(val, right),
      ~Segment(quot, rem, lev) => add(levup(multi(quot, copy(right)), lev), multiply(right, rem))
   }
}

fn multi(left: int, right: ~BigNumber ) -> ~BigNumber {
   match(right) {
      ~End(val) => make(val * left),
      ~Segment(quot, rem, lev) => add(levup(multi(left, ~End(quot)), lev), multi(left, rem))
   }
}

fn safeseg(quot: int, rem: ~BigNumber, lev: int) -> ~BigNumber {
   match(rem) {
      ~End(val) => 
         if(lev == 0) { make(quot + val) } //should never happen, but it'll work if it does
         else { ~Segment(quot, ~End(val), lev) },
      ~Segment(rquot, rrem, rlev) =>
         if(rlev < lev) { ~Segment(quot, ~Segment(rquot, rrem, rlev), lev) }
         else { ~Segment(rquot + quot, rrem, lev) } //safeseg () assumes rquot will be very small!
   }
}         

fn add(left: ~BigNumber, right: ~BigNumber) -> ~BigNumber {
   match(copy(left)) {
      ~End(lval) => match(right) {
         ~End(rval) => make(lval + rval),
         ~Segment(rquot, rrem, rlev) => safeseg(rquot, add(rrem, left), rlev)
      },
      ~Segment(lquot, lrem, llev) => match(copy(right)) {
         ~End(rval) => safeseg(lquot, add(right, lrem), llev),
         ~Segment(rquot, rrem, rlev) => 
            if(rlev > llev) { safeseg(rquot, add(rrem, left), rlev) }
            else if(llev > rlev) { safeseg(lquot, add(lrem, right), llev) }
            else { add(levup(make(lquot + rquot), rlev), add(lrem, rrem))}
      }
   }
}