std/bigint.zc
Rama main · réplica de lectura del repositorio original.
import "./vec.zc"
import "./mem.zc"
import "./result.zc"
struct BigInt {
digits: Vec<u8>;
}
impl BigInt {
fn new() -> Self {
return BigInt { digits: Vec<u8>::new() };
}
fn from_int(val_in: u64) -> Self {
let b = BigInt::new();
let val = val_in;
if val == 0 {
b.digits.push(0);
return b;
}
while val > 0 {
b.digits.push((u8)(val % 10));
val /= 10;
}
return b;
}
fn clone(self) -> Self {
return BigInt { digits: self.digits.clone() };
}
fn free(self) {
self.digits.free();
}
// Deprecated alias; use `free`.
fn free_mem(self) {
self.free();
}
fn add_in_place(self, other: BigInt*) {
let carry: u8 = 0;
let i: usize = 0;
let max_len = self.digits.len;
if other.digits.len > max_len {
max_len = other.digits.len;
}
while i < max_len || carry > 0 {
let sum: u8 = carry;
if i < self.digits.len {
sum += self.digits.get(i);
}
if i < other.digits.len {
sum += other.digits.get(i);
}
carry = sum / 10;
let digit = sum % 10;
if i < self.digits.len {
self.digits.data[i] = digit;
} else {
self.digits.push(digit);
}
i += 1;
}
}
fn add(self, other: BigInt*) -> Self {
let res = self.clone();
(&res).add_in_place(other);
return res;
}
fn to_string(self) -> char* {
let len = self.digits.len;
if len == 0 {
let s: char* = alloc_n<char>(2);
if (s != NULL) {
s[0] = '0';
s[1] = 0;
}
return s;
}
let buf: char* = alloc_n<char>(len + 1);
let idx: usize = 0;
let i = len;
while i > 0 {
i -= 1;
buf[idx] = (char)(self.digits.get(i) + '0');
idx += 1;
}
buf[idx] = 0;
return buf;
}
// internal: remove leading zeros (always keep at least one digit)
fn _trim(self) {
while (self.digits.len > 1) {
if (self.digits.get(self.digits.len - 1) != 0) {
break;
}
self.digits.pop();
}
}
// internal: multiply by a small digit m (0..9) in place
fn _mul_small_in_place(self, m: int) {
if (m == 0) {
self.digits.len = 1;
self.digits.data[0] = 0;
return;
}
let carry: int = 0;
for (let i: usize = 0; i < self.digits.len; i = i + 1) {
let cur = (int)self.digits.get(i) * m + carry;
self.digits.data[i] = (u8)(cur % 10);
carry = cur / 10;
}
while (carry > 0) {
self.digits.push((u8)(carry % 10));
carry = carry / 10;
}
}
// internal: add a small digit in place
fn _add_small_in_place(self, d: int) {
let carry = d;
let i: usize = 0;
while (carry > 0) {
if (i >= self.digits.len) {
self.digits.push((u8)(carry % 10));
carry = carry / 10;
} else {
let cur = (int)self.digits.get(i) + carry;
self.digits.data[i] = (u8)(cur % 10);
carry = cur / 10;
}
i = i + 1;
}
}
// internal: returns self * m for a small digit m
fn _mul_small(self, m: int) -> BigInt {
let res = self.clone();
res._mul_small_in_place(m);
return res;
}
// internal: multiply by 10^n in place
fn _mul_pow10_in_place(self, n: int) {
if (n <= 0) { return; }
for (let i: int = 0; i < n; i = i + 1) {
self.digits.insert(0, 0);
}
}
// Returns 0 if this == other, -1 if this < other, +1 if this > other.
fn compare(self, other: BigInt*) -> int {
if (self.digits.len < other.digits.len) return -1;
if (self.digits.len > other.digits.len) return 1;
let i = self.digits.len;
while (i > 0) {
i = i - 1;
let a = self.digits.get(i);
let b = other.digits.get(i);
if (a < b) return -1;
if (a > b) return 1;
}
return 0;
}
fn is_zero(self) -> bool {
for (let i: usize = 0; i < self.digits.len; i = i + 1) {
if (self.digits.get(i) != 0) return false;
}
return true;
}
// Parses a decimal string (digits only) into a BigInt.
fn from_string(s: char*) -> Result<BigInt> {
let len = strlen(s);
if (len == 0) {
return Result<BigInt>::Err("BigInt::from_string: empty string");
}
if (s[0] == '-') {
return Result<BigInt>::Err("BigInt::from_string: negative numbers not supported");
}
let b = BigInt::new();
b.digits.push(0);
for (let i: usize = 0; i < len; i = i + 1) {
let c = s[i];
if (c < '0' || c > '9') {
b.free();
return Result<BigInt>::Err("BigInt::from_string: invalid digit");
}
b._mul_small_in_place(10);
b._add_small_in_place((int)(c - '0'));
}
return Result<BigInt>::Ok(b);
}
// Subtracts other from this (this must be >= other).
fn sub(self, other: BigInt*) -> BigInt {
if (self.compare(other) < 0) {
panic("BigInt::sub: negative result not supported");
}
let res = self.clone();
let borrow: int = 0;
for (let i: usize = 0; i < res.digits.len; i = i + 1) {
let sub = borrow;
if (i < other.digits.len) {
sub += (int)other.digits.get(i);
}
let cur = (int)res.digits.get(i);
if (cur >= sub) {
res.digits.data[i] = (u8)(cur - sub);
borrow = 0;
} else {
res.digits.data[i] = (u8)(cur + 10 - sub);
borrow = 1;
}
}
res._trim();
return res;
}
// Multiplies this by other (schoolbook).
fn mul(self, other: BigInt*) -> BigInt {
let a_len = self.digits.len;
let b_len = other.digits.len;
let res = BigInt::new();
for (let i: usize = 0; i < a_len + b_len; i = i + 1) {
res.digits.push(0);
}
for (let i: usize = 0; i < a_len; i = i + 1) {
let carry: int = 0;
for (let j: usize = 0; j < b_len; j = j + 1) {
let cur = (int)res.digits.get(i + j) +
(int)self.digits.get(i) * (int)other.digits.get(j) + carry;
res.digits.data[i + j] = (u8)(cur % 10);
carry = cur / 10;
}
let k = i + b_len;
while (carry > 0) {
let cur = (int)res.digits.get(k) + carry;
res.digits.data[k] = (u8)(cur % 10);
carry = cur / 10;
k = k + 1;
}
}
res._trim();
return res;
}
// Returns the quotient of this / divisor (integer division).
fn div(self, divisor: BigInt*) -> BigInt {
if (divisor.is_zero()) {
panic("BigInt::div: division by zero");
}
let zero = BigInt::new();
zero.digits.push(0);
if (self.compare(divisor) < 0) {
return zero;
}
let quotient = BigInt::new();
quotient.digits.push(0);
let rem = BigInt::new();
rem.digits.push(0);
let i = self.digits.len;
while (i > 0) {
i = i - 1;
rem._mul_small_in_place(10);
rem._add_small_in_place((int)self.digits.get(i));
let d = 0;
while (d < 9) {
let trial = divisor._mul_small(d + 1);
if (trial.compare(&rem) > 0) {
break;
}
d = d + 1;
}
quotient._mul_small_in_place(10);
quotient._add_small_in_place(d);
if (d > 0) {
let m = divisor._mul_small(d);
let r = rem.sub(&m);
rem = r;
}
}
quotient._trim();
return quotient;
}
// Returns the remainder of this / divisor.
fn rem(self, divisor: BigInt*) -> BigInt {
let q = self.div(divisor);
let p = q.mul(divisor);
let r = self.sub(&p);
return r;
}
}
impl Drop for BigInt {
fn drop(self) {
self.free();
}
}