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