Skip to content

Instantly share code, notes, and snippets.

@scythe
Last active December 23, 2015 15:39
Show Gist options
  • Save scythe/6656639 to your computer and use it in GitHub Desktop.
Save scythe/6656639 to your computer and use it in GitHub Desktop.
//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))}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment