Skip to content

Instantly share code, notes, and snippets.

@ziap

ziap/fixed-bigint.cpp

Created October 7, 2024 08:39
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save ziap/cffe7f78b6fdb760ad4d4a538b635378 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save ziap/cffe7f78b6fdb760ad4d4a538b635378 to your computer and use it in GitHub Desktop.
Download ZIP
Fixed-width big integer in C++
Raw
fixed-bigint.cpp
#include <cstdint>
#include <cstring>
#include <charconv>
#include <iostream>
template<const int N>
struct BigInt {
static constexpr size_t digit_count = 9;
static constexpr uint32_t base = 1000000000;
uint32_t limbs[N];
constexpr BigInt operator+(const BigInt &other) const {
BigInt res;
uint32_t carry = 0;
for (int i = 0; i < N; ++i) {
carry += limbs[i] + other.limbs[i];
res.limbs[i] = carry % base;
carry /= base;
}
return res;
}
constexpr BigInt operator-(const BigInt &other) const {
BigInt res;
uint32_t carry = 1;
for (int i = 0; i < N; ++i) {
carry += limbs[i] + (base - 1 - other.limbs[i]);
res.limbs[i] = carry % base;
carry /= base;
}
return res;
}
constexpr BigInt operator*(const BigInt &other) const {
BigInt res = {0};
for (int i = 0; i < N; ++i) {
uint64_t carry = 0;
for (int j = 0; i + j < N; ++j) {
carry += res.limbs[i + j] + (uint64_t)limbs[i] * (uint64_t)other.limbs[j];
res.limbs[i + j] = carry % base;
carry /= base;
}
}
return res;
}
constexpr BigInt operator+(uint32_t other) const {
BigInt res;
uint32_t carry = other;
for (int i = 0; i < N; ++i) {
carry += limbs[i];
res.limbs[i] = carry % base;
carry /= base;
}
return res;
}
constexpr BigInt operator*(uint32_t other) const {
BigInt res;
uint64_t carry = 0;
for (int i = 0; i < N; ++i) {
carry += (uint64_t)limbs[i] * other;
res.limbs[i] = carry % base;
carry /= base;
}
return res;
}
constexpr BigInt operator-(uint32_t other) const {
BigInt res;
uint32_t carry = base - other;
res.limbs[0] = carry % base;
carry /= base;
for (int i = 1; i < N; ++i) {
carry += limbs[i] + base - 1;
res.limbs[i] = carry % base;
carry /= base;
}
return res;
}
constexpr uint32_t operator%(uint32_t m) const {
uint64_t res = 0;
for (int i = N - 1; i >= 0; --i) {
res = (res * base + limbs[i]) % m;
}
return res;
}
int32_t cmp(const BigInt &other) const {
for (int i = N - 1; i >= 0; --i) {
int32_t d = limbs[i] - other.limbs[i];
if (d == 0) continue;
return d;
}
return 0;
}
bool operator==(const BigInt &other) const { return cmp(other) == 0; }
bool operator!=(const BigInt &other) const { return cmp(other) != 0; }
bool operator>(const BigInt &other) const { return cmp(other) > 0; }
bool operator<(const BigInt &other) const { return cmp(other) < 0; }
bool operator>=(const BigInt &other) const { return cmp(other) >= 0; }
bool operator<=(const BigInt &other) const { return cmp(other) <= 0; }
static BigInt from_str(const char* ptr, size_t len) {
BigInt res = {0};
for (int i = 0; len && i < N; ++i) {
size_t next_len = len > digit_count ? len - digit_count : 0;
std::from_chars(ptr + next_len, ptr + len, res.limbs[i]);
len = next_len;
}
return res;
}
char *to_str(char *ptr) const {
bool written = false;
int i = N - 1;
while (i > 0 && limbs[i] == 0) --i;
std::to_chars_result res = std::to_chars(ptr, ptr + digit_count, limbs[i]);
ptr = res.ptr;
for (i = i - 1; i >= 0; --i) {
std::to_chars_result res = std::to_chars(ptr, ptr + digit_count, limbs[i]);
size_t len = res.ptr - ptr;
size_t pad = digit_count - len;
memmove(ptr + pad, ptr, len);
memset(ptr, '0', pad);
ptr += digit_count;
}
return ptr;
}
friend std::ostream &operator<<(std::ostream &out, const BigInt &num) {
char buf[digit_count * N];
char *end = num.to_str(buf);
return out.write(buf, end - buf);
}
friend std::istream &operator>>(std::istream &in, BigInt &num) {
char buf[digit_count * N + 1];
in >> buf;
num = from_str(buf, strlen(buf));
return in;
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment