Loading...
Searching...
No Matches
bignum.hh
#pragma once
/*
Copyright (c) 2003-2021 Tommi Junttila
Released under the GNU Lesser General Public License version 3.
This file is part of bliss.
bliss is free software: you can redistribute it and/or modify
it under the terms of the GNU Lesser General Public License as published by
the Free Software Foundation, version 3 of the License.
bliss is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License
along with bliss. If not, see <http://www.gnu.org/licenses/>.
*/
#if defined(BLISS_USE_GMP)
#include <gmp.h>
#else
#include <vector>
#include <string>
#endif
#include <cstdlib>
#include <cstdio>
#include <bliss/defs.hh>
namespace bliss {
#if defined(BLISS_USE_GMP)
class BigNum
{
mpz_t v;
public:
BigNum() {mpz_init(v); }
~BigNum() {mpz_clear(v); }
void assign(unsigned int n) {mpz_set_ui(v, n); }
void multiply(unsigned int n) {mpz_mul_ui(v, v, n); }
size_t print(FILE* const fp) const {return mpz_out_str(fp, 10, v); }
void get(mpz_t& result) const {mpz_set(result, v); }
};
#elif defined(BLISS_BIGNUM_APPROX)
class BigNum
{
long double v;
public:
BigNum(): v(0.0) {}
void assign(unsigned int n) {v = (long double)n; }
void multiply(unsigned int n) {v *= (long double)n; }
size_t print(FILE* const fp) const {return fprintf(fp, "%Lg", v); }
};
#else
class BigNum
{
/* This is a version that does not actually compute the number
* but rather only stores the factor integers.
*/
std::vector<unsigned int> factors;
public:
BigNum() {
factors.push_back(0);
}
~BigNum() {}
void assign(unsigned int n) {
factors.clear();
factors.push_back(n);
}
void multiply(unsigned int n) {
factors.push_back(n);
}
size_t print(FILE* const fp) const {
assert(not factors.empty());
size_t r = 0;
/*
const char* sep = "";
for(int v: factors) {
r += fprintf(fp, "%s%d", sep, v);
sep = "*";
}
*/
for(char d: to_string())
r += fprintf(fp, "%c", d);
return r;
}
const std::vector<unsigned int>& get_factors() const {
return factors;
}
std::string to_string() const {
// Base 100 result, in reverse order
std::vector<unsigned int> result;
result.push_back(1);
for(unsigned int factor: factors) {
std::vector<unsigned int> summand;
unsigned int offset = 0;
while(factor != 0) {
const unsigned int multiplier = factor % 100;
// Multiplication by a "digit"
std::vector<unsigned int> product;
for(unsigned int i = 0; i < offset; i++)
product.push_back(0);
unsigned int carry = 0;
for(unsigned int digit: result) {
unsigned int v = digit * multiplier + carry;
product.push_back(v % 100);
carry = v / 100;
}
if(carry > 0)
product.push_back(carry);
// Addition
add(summand, product);
// Next "digit" in factor
factor = factor / 100;
offset++;
}
result = summand;
}
return _string(result);
}
protected:
static void add(std::vector<unsigned int>& num, const std::vector<unsigned int>& summand) {
unsigned int carry = 0;
unsigned int i = 0;
while(i < num.size() and i < summand.size()) {
const unsigned int v = carry + num[i] + summand[i];
num[i] = v % 100;
carry = v / 100;
i++;
}
while(i < summand.size()) {
const unsigned int v = carry + summand[i];
num.push_back(v % 100);
carry = v / 100;
i++;
}
while(i < num.size()) {
const unsigned int v = carry + num[i];
num[i] = v % 100;
carry = v / 100;
i++;
}
if(carry != 0)
num.push_back(carry);
}
static std::string _string(const std::vector<unsigned int> n) {
const char digits[] = {'0','1','2','3','4','5','6','7','8','9'};
std::string r;
bool first = true;
for(auto it = n.crbegin(); it != n.crend(); it++) {
unsigned int digit = *it;
unsigned int high = digit / 10;
if(not first or high > 0)
r.push_back(digits[high]);
first = false;
r.push_back(digits[digit % 10]);
}
return r;
}
};
#endif
} //namespace bliss
bliss::BigNum
A simple wrapper class for non-negative big integers (or approximation of them).
Definition bignum.hh:118
bliss::BigNum::to_string
std::string to_string() const
Definition bignum.hh:182
bliss::BigNum::~BigNum
~BigNum()
Definition bignum.hh:134
bliss::BigNum::BigNum
BigNum()
Definition bignum.hh:127
bliss::BigNum::get_factors
const std::vector< unsigned int > & get_factors() const
Definition bignum.hh:174
bliss::BigNum::assign
void assign(unsigned int n)
Definition bignum.hh:139
bliss::BigNum::multiply
void multiply(unsigned int n)
Definition bignum.hh:147
bliss::BigNum::print
size_t print(FILE *const fp) const
Definition bignum.hh:156
bliss
Definition abstractgraph.cc:35