20
\$\begingroup\$

After a hiatus, I have returned to coding in C++. In an effort to learn some of the newer aspects of the language and for exercise and 'up-skilling', I am writing some simple classes and this HugeInt (huge integer) class is an example.

Looking on the web there are a number of implementations, which appear to use base-10 digits internally. My class uses base-256 digits internally, represented as fixed-length arrays of uint8_t, which gives you about a factor of \$\log_{10}(256) = 2.41\$ increase in decimal digits per unit of storage. Also, masking off the carry byte can be done very easily. Negative values are represented using base-256 complement. More details can be found in the header file and implementation code, both of which are liberally commented.

I would appreciate feedback on coding style, implementation, improvements, etc. I have been using uniform initialisation almost throughout (I cannot bring myself to use it for loop indices) on the advice of a textbook I have been working through. What is current best practice, especially amongst developers in the private sector? Being an arithmetic class, I am relying quite heavily on implicit type conversion from long ints and from C strings. This is a convenience for users of the class, but I welcome comments on this approach.

Perhaps this is not a question for Code Review, but, surprisingly to me, when I used level 2 optimisation in g++ (-O2) the code compiles, but seems to enter an infinite loop on execution. So, if you compile this code, please test first without optimisation. If you can shed some light on why the optimiser causes this behaviour, then I'd be very happy to hear it.

I have checked the results of various calculations by comparing with Wolfram Alpha and all seems to be good, and fairly efficient. I was able to calculate all 2568 digits of \$1000!\$ in about 45 seconds on my old Dell M3800 (you will need to increase numDigits in the code below). I have set the default number of base-256 digits to 200, giving about 480 decimal digits. This seems to be a good choice to balance speed with usefulness, but this can be changed by changing the numDigits member.

The code follows. I have not wrapped the class in a namespace yet, for simplicity, but I do realise that in a production environment this should be done.

Thank you in advance for your time.

Header file:

/*
 * HugeInt.h
 * 
 * Definition of the huge integer class
 * RADIX 256 VERSION
 *
 * Huge integers are represented as N-digit arrays of uint8_t types, where
 * each uint8_t value represents a base 256 digit. By default N = 200, which 
 * corresponds to roughly 480 decimal digits. Each uint8_t contains a single 
 * radix 256, i.e., base 256, digit in the range 0 <= digit < 256. 
 * If `index' represents the index of the array of uint8_t digits[N], 
 * i.e., 0 <= index <= N - 1, and 'value' represents the power of 256 
 * corresponding to the radix 256 digit at 'index', then we have the following 
 * correspondence:
 *
 * index  |...|   7   |   6   |   5   |   4   |   3   |   2   |   1   |   0   |
 * ----------------------------------------------------------------------------
 * value  |...| 256^7 | 256^6 | 256^5 | 256^4 | 256^3 | 256^2 | 256^1 | 256^0 |
 *
 * The physical layout of the uint8_t array in memory is:
 *
 * uint8_t digits[N] = {digits[0], digits[1], digits[2], digits[3], ... }
 *
 * which means that the units appear first in memory, while the power of 
 * 256^(N-1) appears last. This LITTLE ENDIAN storage represents the number in 
 * memory in the REVERSE order of the way we write decimal numbers, but is 
 * convenient.
 *
 * Negative integers are represented by their radix complement. With the 
 * base 256 implementation here, we represent negative integers by their base 
 * 256 complement. With this convention the range of 
 * non-negative integers is:
 *                      0 <= x <= 256^N/2 - 1
 * The range of base 256 integers CORRESPONDING to negative values in the
 * base 256 complement scheme is:
 *                      256^N/2 <= x <= 256^N - 1 
 * So -1 corresponds to 256^N - 1, -2 corresponds to 256^N - 2, and so on.
 */

#ifndef HUGEINT_H
#define HUGEINT_H

#include <string>
#include <iostream>

class HugeInt {
public:
    HugeInt();
    HugeInt(const long int);    // conversion constructor from long int
    HugeInt(const char* const); // conversion constructor from C string
    HugeInt(const HugeInt&);    // copy/conversion constructor

    // assignment operator
    const HugeInt& operator=(const HugeInt&);

    // unary minus operator
    HugeInt operator-() const;
    HugeInt radixComplement() const;

    // conversion to double
    explicit operator long double() const;

    // basic arithmetic
    friend HugeInt operator+(const HugeInt&, const HugeInt&);
    friend HugeInt operator-(const HugeInt&, const HugeInt&);
    friend HugeInt operator*(const HugeInt&, const HugeInt&);
  //  friend HugeInt operator/(const HugeInt&, const HugeInt&); // TODO:

    // increment and decrement operators
    HugeInt& operator+=(const HugeInt&);
    HugeInt& operator-=(const HugeInt&);
    HugeInt& operator*=(const HugeInt&);
  //  HugeInt& operator/=(const HugeInt&); TODO:
    HugeInt& operator++();     // prefix
    HugeInt  operator++(int);  // postfix
    HugeInt& operator--();     // prefix
    HugeInt  operator--(int);  // postfix

    // relational operators
    friend bool operator==(const HugeInt&, const HugeInt&);
    friend bool operator!=(const HugeInt&, const HugeInt&);
    friend bool operator<(const HugeInt&, const HugeInt&);
    friend bool operator>(const HugeInt&, const HugeInt&);
    friend bool operator<=(const HugeInt&, const HugeInt&);
    friend bool operator>=(const HugeInt&, const HugeInt&);

    bool isZero() const;
    bool isNegative() const;

    // output 
    std::string toStringRaw() const;
    std::string toDecimalString() const;
    friend std::ostream& operator<<(std::ostream& output, const HugeInt&);

private:
    static const int numDigits{200}; // max. number of radix 256 digits
    uint8_t          digits[numDigits]{0}; // radix 256 digits; zero by default

    // private utility functions
    HugeInt& radixComplementSelf();
    HugeInt  shortDivide(int) const;
    int      shortModulo(int) const;
    HugeInt  shortMultiply(int) const;
    HugeInt& shiftLeftDigits(int);
};

#endif /* HUGEINT_H */

The implementation is here:

/*
 * HugeInt.cpp
 *
 * Implementation of the HugeInt class. See comments in HugeInt.h for
 * details of representation, etc.
 *
 * RADIX 256 VERSION
 * 
 */

#include <cstdlib>   // for abs(), labs(), etc.
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <stdexcept>
#include "HugeInt.h"

/*
 * Non-member utility functions
 */

/**
 * get_carry
 *
 * Return the high byte of the lower two-byte word stored as an int.
 * Return this byte value as an integer.
 * 
 * @param value
 * @return 
 */

inline int get_carry(int value) {
    return static_cast<int>(value >> 8 & 0xff);
}

/**
 * get_digit
 * 
 *Return the low byte of the two-byte word stored as an int.
 * Return this byte value as an integer.
 * 
 * @param value
 * @return 
 */

inline int get_digit(int value) {
    return static_cast<int>(value & 0xff);
}

/**
 * Constructor (default)
 *
 */

HugeInt::HugeInt() {
    // empty body
}

/**
 * Constructor (conversion constructor)
 *
 * Construct a HugeInt from a long integer (the base 10 representation of
 * the number).
 *
 */ 

HugeInt::HugeInt(const long int x) {
    if (x == 0) {
        return;
    }

    long int xp{labs(x)};
    int i{0};

    // Successively determine units, 256's, 256^2's, 256^3's, etc.
    // storing them in digits[0], digits[1], digits[2], ...,
    // respectively. That is units = digits[0], 256's = digits[1], etc.
    while (xp > 0) {
        digits[i++] = xp % 256;
        xp /= 256;
    }

    if (x < 0) {
        radixComplementSelf();
    }
}

/**
 * Constructor (conversion constructor)
 *
 * Construct a HugeInt from a null-terminated C string representing the
 * base 10 representation of the number. The string is assumed to have 
 * the form "[+/-]31415926", including an optional '+' or '-' sign. 
 *
 * WARNING: No spaces are allowed in the decimal string.
 * 
 * @param str
 */

HugeInt::HugeInt(const char *const str) {
    bool    flagNegative{false};
    HugeInt theNumber{0L};
    HugeInt powerOfTen{1L}; // initially 10^0 = 1
    int     numDecimalDigits{0};
    int     digitValue{0};
    int     len{static_cast<int>(strlen(str))};

    if (len == 0) {
        throw std::invalid_argument{"empty decimal string in constructor"};
    }

    // Check for explicit positive and negative signs and adjust accordingly.
    // If negative, we flag the case and perform a ten's complement at the end.
    if (str[0] == '+') {
        numDecimalDigits = len - 1;
    } else if (str[0] == '-') {
        flagNegative = true;
        numDecimalDigits = len - 1;
    } else {
        numDecimalDigits = len;
    }

    // Loop (backwards) through each decimal digit, digit[i], in the string, 
    // adding its numerical contribution, digit[i]*10^i, to theNumber. Here i 
    // runs upwards from zero, starting at the right-most digit of the string 
    // of decimal digits.

    for (int i = 0; i < numDecimalDigits; ++i) {
        digitValue = static_cast<int>(str[len - 1 - i]) - '0';
        theNumber += powerOfTen.shortMultiply(digitValue);
        powerOfTen = powerOfTen.shortMultiply(10);
    }

    if (flagNegative) {
        theNumber.radixComplementSelf();
    }

    for (int i = 0; i < numDigits; ++i) {
        digits[i] = theNumber.digits[i];
    }
}

/**
 * Copy constructor
 * 
 * @param rhs
 */

HugeInt::HugeInt(const HugeInt& rhs) {
    // TODO: perhaps call copy assignment?
    for (int i = 0; i < numDigits; ++i)
        digits[i] = rhs.digits[i];
}

/**
 * Assignment operator
 * 
 * @param rhs
 * @return 
 */

const HugeInt& HugeInt::operator=(const HugeInt& rhs) {
    if (&rhs != this) {
        for (int i = 0; i < numDigits; ++i) {
            digits[i] = rhs.digits[i]; 
        }
    }

    return *this;
}

/**
 * Unary minus operator
 * 
 * @return 
 */

HugeInt HugeInt::operator-() const {
    return radixComplement();
}

/**
 * radixComplement()
 * 
 * Return the radix-256 complement of HugeInt.
 * 
 * @return 
 */

HugeInt HugeInt::radixComplement() const {
    HugeInt result{*this};

    return result.radixComplementSelf();
}


/**
 * operator long double() 
 *
 * Use with static_cast<long double>(hugeint) to convert hugeint to its
 * approximate (long double) floating point value.
 * 
 */
HugeInt::operator long double() const {
    long double retval{0.0L};
    long double pwrOf256{1.0L};
    long double sign{1.0L};
    HugeInt copy{*this};

    if (copy.isNegative()) {
        copy.radixComplementSelf();
        sign = -1.0L;
    }

    for (int i = 0; i < numDigits; ++i) {
        retval += copy.digits[i] * pwrOf256;
        pwrOf256 *= 256.0L;
    }

    return retval*sign;
}

/**
 * Operator +=
 *
 * NOTE: With the conversion constructors provided, also
 *       provides operator+=(long int) and
 *                operator+=(const char *const)
 * 
 * @param increment
 * @return 
 */

HugeInt& HugeInt::operator+=(const HugeInt& increment) {
    *this = *this + increment;
    return *this;
}

/**
 * Operator -=
 * 
 * NOTE: With the conversion constructors provided, also
 *       provides operator-=(long int) and
 *                operator-=(const char *const)
 * 
 * 
 * @param decrement
 * @return 
 */

HugeInt& HugeInt::operator-=(const HugeInt& decrement) {
    *this = *this - decrement;
    return *this;
}

/**
 * Operator *=
 * 
 * NOTE: With the conversion constructors provided, also
 *       provides operator*=(long int) and
 *                operator*=(const char *const)
 * 
 * @param multiplier
 * @return 
 */

HugeInt& HugeInt::operator*=(const HugeInt& multiplier) {
    *this = *this * multiplier;
    return *this;
}

/**
 * Operator ++ (prefix)
 * 
 * @return 
 */

HugeInt& HugeInt::operator++() {
    *this = *this + 1;
    return *this;
}

/**
 * Operator ++ (postfix)
 * 
 * @param 
 * @return 
 */

HugeInt HugeInt::operator++(int) {
   HugeInt retval{*this};
   ++(*this);

   return retval;
}

/**
 * Operator -- (prefix)
 * 
 * @return 
 */

HugeInt& HugeInt::operator--() {
   *this = *this - 1;
   return *this;
}

/**
 * Operator -- (postfix)
 * 
 * @param 
 * @return 
 */

HugeInt HugeInt::operator--(int) {
   HugeInt retval{*this};
   --(*this);

   return retval;
}

/**
 * isZero()
 * 
 * Return true if the HugeInt is zero, otherwise false.
 * 
 * @return 
 */

bool HugeInt::isZero() const {
    int i{numDigits - 1};

    while (digits[i] == 0) {
        i--;
    }

    return i < 0;
}

/**
 * isNegative()
 * 
 * Return true if a number x is negative (x < 0). If x >=0, then
 * return false.
 * 
 * NOTE: In radix-256 complement notation, negative numbers, x, are 
 *       represented by the range of values: 256^N/2 <= x <=256^N - 1.
 *       Since 256^N/2 = (256/2)*256^(N-1) = 128*256^(N-1), we only need to
 *       check whether the (N - 1)'th base 256 digit is at least 128. 
 * 
 * @return 
 */

bool HugeInt::isNegative() const {
    return digits[numDigits - 1] >= 128;
}


/**
 * toStringRaw()
 * 
 * Format a HugeInt as string in raw internal format, i.e., as a sequence 
 * of base-256 digits (each in decimal form, 0 <= digit < 256).
 *  
 * @return 
 */

std::string HugeInt::toStringRaw() const {
    std::ostringstream oss;
    int istart{numDigits - 1};

    while (digits[istart] == 0) {
        istart--;
    }

    if (istart < 0) // the number is zero
    {
        oss << static_cast<int> (digits[0]);
    } else {
        for (int i = istart; i >= 0; --i) {
            oss << std::setw(3) << std::setfill('0')
                    << static_cast<int>(digits[i]) << " ";
        }
    }

    return oss.str();
}

/**
 * toDecimalString()
 * 
 * Format HugeInt as a string of decimal digits. The length of the decimal 
 * string is estimated (roughly) by solving for x:
 *
 *     256^N = 10^x    ==>    x = N log_10(256) = N * 2.40825 (approx)
 *
 * where N is the number of base 256 digits. A safety margin of 5 is added
 * for good measure.
 * 
 * @return 
 */

std::string HugeInt::toDecimalString() const {
    const int numDecimal{static_cast<int>(numDigits * 2.40825) + 5};
    int decimalDigits[numDecimal]{0}; // int avoids <char> casts
    std::ostringstream oss;
    HugeInt tmp;

    // Special case HugeInt == 0 is easy
    if (isZero()) {
        oss << "0";
        return oss.str();
    }

    // set copy to the absolute value of *this
    // for use in shortDivide and shortModulo
    if (isNegative()) {
        oss << "-";
        tmp = this->radixComplement();
    } else {
        tmp = *this;
    }

    // determine the decimal digits of the absolute value 
    int i = 0;

    while (!tmp.isZero()) {
        decimalDigits[i++] = tmp.shortModulo(10);
        tmp = tmp.shortDivide(10);
    }

    // output the decimal digits
    for (int j = i - 1; j >= 0; --j) {
        if (j < i - 1) {
            if ((j + 1) % 3 == 0) // show thousands separator
            {
                oss << ','; // thousands separator
            }
        }

        oss << decimalDigits[j];
    }

    return oss.str();
}

////////////////////////////////////////////////////////////////////////////
// friend functions                                                       //
////////////////////////////////////////////////////////////////////////////

/**
 * friend binary operator +
 *
 * Add two HugeInts a and b and return c = a + b.
 *
 * Note: since we provide conversion constructors for long int's and
 *       null-terminated C strings, this function, in effect, also provides
 *       the following functionality by implicit conversion of strings and
 *       long int's to HugeInt
 *
 *       c = a + <some long int>    e.g.  c = a + 2412356L
 *       c = <some long int> + a    e.g.  c = 2412356L + a
 *
 *       c = a + <some C string>    e.g.  c = a + "12345876987"
 *       c = <some C string> + a    e.g.  c = "12345876987" + a
 * 
 * @param a
 * @param b
 * @return 
 */

HugeInt operator+(const HugeInt& a, const HugeInt& b) {
    HugeInt sum;
    int carry{0};
    int partial{0};

    for (int i = 0; i < HugeInt::numDigits; ++i) {
        // add digits with carry
        partial = a.digits[i] + b.digits[i] + carry;
        carry = get_carry(partial);
        sum.digits[i] = static_cast<uint8_t> (get_digit(partial));
    }

    return sum;
}

/**
 * friend binary operator-
 *
 * Subtract HugeInt a from HugeInt a and return the value c = a - b.
 *
 * Note: since we provide conversion constructors for long int's and
 *       null-terminated C strings, this function, in effect, also provides
 *       the following functionality by implicit conversion of strings and
 *       long int's to HugeInt
 *
 *       c = a - <some long int>    e.g.  c = a - 2412356L
 *       c = <some long int> - a    e.g.  c = 2412356L - a
 *
 *       c = a - <some C string>    e.g.  c = a - "12345876987"
 *       c = <some C string> - a    e.g.  c = "12345876987" - a
 * 
 * @param a
 * @param b
 * @return 
 */

HugeInt operator-(const HugeInt& a, const HugeInt& b) {
    return a + (-b);
}

/**
 * friend binary operator *
 *
 * Multiply two HugeInt numbers. Uses standard long multipication algorithm
 * adapted to base 256.
 * 
 * @param a
 * @param b
 * @return 
 */

HugeInt operator*(const HugeInt& a, const HugeInt& b) {
    HugeInt product{0L};
    HugeInt partial;

    for (int i = 0; i < HugeInt::numDigits; ++i) {
        partial = a.shortMultiply(b.digits[i]);
        product += partial.shiftLeftDigits(i);
    }

    return product;
}

////////////////////////////////////////////////////////////////////////////
// Relational operators (friends)                                         //
////////////////////////////////////////////////////////////////////////////

/**
 * Operator ==
 * 
 * @param lhs
 * @param rhs
 * @return 
 */

bool operator==(const HugeInt& lhs, const HugeInt& rhs) {
   HugeInt diff{rhs - lhs};

   return diff.isZero();
}

/**
 * Operator !=
 * 
 * @param lhs
 * @param rhs
 * @return 
 */

bool operator!=(const HugeInt& lhs, const HugeInt& rhs) {
   return !(rhs == lhs);
}

/**
 * Operator <
 * 
 * @param lhs
 * @param rhs
 * @return 
 */

bool operator<(const HugeInt& lhs, const HugeInt& rhs) {
   HugeInt diff{lhs - rhs};

   return diff.isNegative();
}

/**
 * Operator >
 * 
 * @param lhs
 * @param rhs
 * @return 
 */

bool operator>(const HugeInt& lhs, const HugeInt& rhs) {
    return rhs < lhs;
}

/**
 * Operator <=
 * 
 * @param lhs
 * @param rhs
 * @return 
 */

bool operator<=(const HugeInt& lhs, const HugeInt& rhs) {
    return !(lhs > rhs);
}

/**
 * Operator >=
 * 
 * @param lhs
 * @param rhs
 * @return 
 */

bool operator>=(const HugeInt& lhs, const HugeInt& rhs) {
    return !(lhs < rhs);
}

////////////////////////////////////////////////////////////////////////////
// Private utility functions                                              //
////////////////////////////////////////////////////////////////////////////

/**
 * shortDivide:
 * 
 * Return the result of a base 256 short division by 0 < divisor < 256, using 
 * the usual primary school algorithm adapted to radix 256.
 *
 * WARNING: assumes both HugeInt and the divisor are POSITIVE.
 * 
 * @param divisor
 * @return 
 */

HugeInt HugeInt::shortDivide(int divisor) const {
    int j;
    int remainder{0};
    HugeInt quotient;

    for (int i = numDigits - 1; i >= 0; --i) {
        j = 256 * remainder + digits[i];
        quotient.digits[i] = static_cast<uint8_t>(j / divisor);
        remainder = j % divisor;
    }

    return quotient;
}

/**
 * shortModulo
 * 
 * Return the remainder of a base 256 short division by divisor, where 
 * 0 < divisor < 256.
 *
 * WARNING: assumes both HugeInt and the divisor are POSITIVE.
 * 
 * @param divisor
 * @return 
 */

int HugeInt::shortModulo(int divisor) const {
    int j;
    int remainder{0};

    for (int i = numDigits - 1; i >= 0; --i) {
        j = 256 * remainder + digits[i];
        remainder = j % divisor;
    }

    return remainder;
}

/**
 * shortMultiply
 * 
 * Return the result of a base 256 short multiplication by multiplier, where
 * 0 <= multiplier < 256.
 *
 * WARNING: assumes both HugeInt and multiplier are POSITIVE.
 * 
 * @param multiplier
 * @return 
 */

HugeInt HugeInt::shortMultiply(int multiplier) const {
    HugeInt product;
    int carry{0};
    int tmp;

    for (int i = 0; i < numDigits; ++i) {
        tmp = digits[i] * multiplier + carry;
        carry = get_carry(tmp);
        product.digits[i] = static_cast<uint8_t>(get_digit(tmp));
    }

    return product;
}

/**
 * shiftLeftDigits
 *
 * Shift this HugeInt's radix-256 digits left by num places, filling
 * with zeroes from the right.
 * 
 * @param num
 * @return 
 */

HugeInt& HugeInt::shiftLeftDigits(int num) {
    if (num == 0) {
        return *this;
    }

    for (int i = numDigits - num - 1; i >= 0; --i) {
        digits[i + num] = digits[i];
    }

    for (int i = 0; i < num; ++i) {
        digits[i] = 0;
    }

    return *this;
}

/**
 * radixComplementSelf()
 *
 * Perform a radix complement on the object in place (changes object).
 * 
 * @return 
 */

HugeInt& HugeInt::radixComplementSelf() {
    if (!isZero()) {
        int sum{0};
        int carry{1};

        for (int i = 0; i < numDigits; ++i) {
            sum = 255 - digits[i] + carry;
            carry = get_carry(sum);
            digits[i] = static_cast<uint8_t>(get_digit(sum));
        }
    }

    return *this;
}

/**
 * operator<<
 * 
 * Overloaded stream insertion for HugeInt.
 * 
 * @param output
 * @param x
 * @return 
 */

std::ostream& operator<<(std::ostream& output, const HugeInt& x) {
    output << x.toDecimalString();

    return output;
}

Simple driver:

/*
 * Simple driver to test a few features of th HugeInt class.
 */

#include <iostream>
#include <iomanip>
#include <limits>
#include "HugeInt.h"

HugeInt factorial_recursive(const HugeInt& n);
HugeInt factorial_iterative(const HugeInt& n);
HugeInt fibonacci_recursive(const HugeInt& n);
HugeInt fibonacci_iterative(const HugeInt& n);


int main() {
    long int inum{};

    do {
        std::cout << "Enter a non-negative integer (0-200): ";
        std::cin >> inum;
    } while (inum < 0 || inum > 200);

    HugeInt nfac{inum};
    HugeInt factorial = factorial_iterative(nfac);
    long double factorial_dec = static_cast<long double>(factorial);

    std::cout << "\nThe value of " << nfac << "! is:\n";
    std::cout << factorial << '\n';
    std::cout.precision(std::numeric_limits<long double>::digits10);
    std::cout << "\nIts decimal approximation is: " << factorial_dec << '\n';

    do {
        std::cout << "\n\nEnter a non-negative integer (0-1800): ";
        std::cin >> inum;
    } while (inum < 0 || inum > 1800);

    HugeInt nfib{inum};
    HugeInt fibonacci = fibonacci_iterative(nfib);
    long double fibonacci_dec = static_cast<long double>(fibonacci);

    std::cout << "\nThe " << nfib << "th Fibonacci number is:\n";
    std::cout << fibonacci << '\n';
    std::cout << "\nIts decimal approximation is: " << fibonacci_dec << '\n';

    std::cout << "\nComparing these two values we observe that ";
    if (factorial == fibonacci) {
        std::cout << nfac << "! == Fibonacci_{" << nfib << "}\n";
    }

    if (factorial < fibonacci) {
        std::cout << nfac << "! < Fibonacci_{" << nfib << "}\n";
    }

    if (factorial > fibonacci) {
        std::cout << nfac << "! > Fibonacci_{" << nfib << "}\n";
    }

    HugeInt sum = factorial + fibonacci;
    HugeInt diff = factorial - fibonacci;

    std::cout << "\nTheir sum (factorial + fibonacci) is:\n";
    std::cout << sum << '\n';
    std::cout << "\n\twhich is approximately " << static_cast<long double>(sum);
    std::cout << '\n';

    std::cout << "\nTheir difference (factorial - fibonacci) is:\n";
    std::cout << diff << '\n';
    std::cout << "\n\twhich is approximately " << static_cast<long double>(diff);
    std::cout << '\n';

    HugeInt x{"-80538738812075974"};
    HugeInt y{"80435758145817515"};
    HugeInt z{"12602123297335631"};

    HugeInt k = x*x*x + y*y*y + z*z*z;

    std::cout << "\nDid you know that, with:\n";
    std::cout << "\tx = " << x << '\n';
    std::cout << "\ty = " << y << '\n';
    std::cout << "\tz = " << z << '\n';
    std::cout << "\nx^3 + y^3 + z^3 = " << k << '\n';
}

/**
 * factorial_recursive:
 * 
 * Recursive factorial function using HugeInt. Not too slow.
 * 
 * @param n
 * @return 
 */

HugeInt factorial_recursive(const HugeInt& n) {
    const HugeInt one{1L};

    if (n <= one) {
        return one;
    } else {
        return n * factorial_recursive(n - one);
    }
}

HugeInt factorial_iterative(const HugeInt& n) {
    HugeInt result{1L};

    if (n == 0L) {
        return result;
    }

    for (HugeInt i = n; i >= 1; --i) {
        result *= i;
    }

    return result;
}

/**
 * fibonacci_recursive:
 * 
 * Recursively calculate the n'th Fibonacci number, where n>=0.
 * 
 * WARNING: S l o w . . .
 * 
 * @param n
 * @return 
 */
HugeInt fibonacci_recursive(const HugeInt& n) {
    const HugeInt zero;
    const HugeInt one{1L};

    if ((n == zero) || (n == one)) {
        return n;
    } 
    else {
        return fibonacci_recursive(n - 1L) + fibonacci_recursive(n - 2L);
    }  
}

HugeInt fibonacci_iterative(const HugeInt& n) {
    const HugeInt zero;
    const HugeInt one{1L};

    if ((n == zero) || (n == one)) {
        return n;
    }

    HugeInt retval;
    HugeInt fib_nm1 = one;
    HugeInt fib_nm2 = zero;

    for (HugeInt i = 2; i <= n; ++i) {
        retval = fib_nm1 + fib_nm2;
        fib_nm2 = fib_nm1;
        fib_nm1 = retval;
    }

    return retval;
}
\$\endgroup\$
  • 13
    \$\begingroup\$ why base 256, and not base 2**32? \$\endgroup\$ – Eevee Feb 3 at 23:01
  • 3
    \$\begingroup\$ @Eevee: Note that for bases of int or wider you'll have to manually cast to a wider type to get carry-out in the high half. This code looks like it relies on narrow integer types implicitly promoting up to int when used as operands to +. But yes, it's about 4x more efficient to work in 32-bit chunks than 8-bit chunks, especially on a 64-bit CPU where the "carry emulation" using uint64_t could compile efficiently. (C++ doesn't expose hardware carry-in / out in a way that makes it possible to write really efficient portable code; that's why CPython uses base 2^30 in 32-bit integer chunks.) \$\endgroup\$ – Peter Cordes Feb 4 at 13:16
  • 2
    \$\begingroup\$ Taking advantage of hardware carry-flags, add-with-carry, widening multiply, etc. is one of several reasons why GMP (gmplib.org) has its lowest-level building block routines written in assembly. (And thus needs different versions tuned for different CPU microarchitectures in the same ISA.) \$\endgroup\$ – Peter Cordes Feb 4 at 13:21
  • 2
    \$\begingroup\$ @RichardMace you don't need 64-bit registers to implement uint64_t. Compilers targeting 32-bit ISAs will do that for you using HW carry (or if necessary, software carry check, on MIPS and RISC-V which don't have flags.) re: division: it's hard. Have a look at what GMP does: gmplib.org/repo/gmp/file/tip/mpn/generic/div_q.c (not easy to understand, and uses GMP helper functions). You can probably find something if you google on extended-precision division. I don't know how an algorithm off the top of my head, but I do know there aren't any very efficient ones. \$\endgroup\$ – Peter Cordes Feb 4 at 14:12
  • 1
    \$\begingroup\$ Knuth's "Algorithm D" for multiword division takes some getting to know, but it works just fine and I'm not aware of anything that's hugely faster. There's a sample implementation and a possibly more understandable description in Hacker's Delight (code available on the web iirc). For an efficient implementation with native-sized words you'll need the not-widely-available _udiv64/_udiv128 intrinsics. \$\endgroup\$ – Sneftel Feb 4 at 17:44
21
\$\begingroup\$

General

I like the presentation. It's easy to read, with good use of whitespace and useful comments.


Width

It's inconvenient to have to recompile to use a larger width HugeInt, and impossible to mix sizes. Consider making numDigits a template parameter (and use an unsigned type for it - perhaps std::size_t).

If we template the width, then we'll have a bit of work to do to support promotions between different width values, but you'll find that good exercise.

Conversions

If this were my code, I think I'd make the char* constructor explicit. The one taking long int seems reasonable to accept as implicit.

Consider adding an explicit operator bool() to allow idiomatic tests such as if (!num).

Comparisons

Implementing the relational operators in terms of subtraction misses an opportunity: if we find a difference in the high-order digits, there's no need to examine the rest of the number. I'd consider writing a simple <=> function, and using that to implement the public comparisons. (In C++20, you'll be able to implement operator<=>() and the compiler will then produce all the rest for you).

Streaming

We're missing an operator >> to accept input from a standard stream.

When streaming out, we might be able to produce two digits at a time if we carefully manage leading zeros - that will reduce the number of divisions by around 50%.


Missing std:: qualifier

A lot of the C Standard Library identifiers are missing their namespace prefix (e.g. std::abs, std::strlen, etc). These should be specified, as these names are not guaranteed to also be in the global namespace.

Overflow bug

long int xp{std::abs(x)};

On twos-complement systems, LONG_MIN is greater in magnitude than LONG_MAX, so we fail to convert LONG_MIN correctly.

Internationalisation

This loop embodies a specific locale convention:

for (int j = i - 1; j >= 0; --j) {
    if (j < i - 1) {
        if ((j + 1) % 3 == 0) // show thousands separator
        {
            oss << ','; // thousands separator
        }
    }

That's fine for European English, but isn't a good match for Indian English, for example. I believe we can get information from the locale's std::numpunct facet, but I don't know the details.

I worry that writing separators by default (and with no option to disable) may be a poor choice unless we update our string-to-number conversion to be able to ignore separators - I'm much more comfortable when a round-trip will work.

Input handling

I know it's only meant to be illustrative, but here we need to check the status of std::cin before repeating the loop:

do {
    std::cout << "Enter a non-negative integer (0-200): ";
    std::cin >> inum;
} while (inum < 0 || inum > 200);

If I give -1 as input (and nothing else), the program enters an infinite loop, because the closed stream never changes inum to an acceptable value. For a simple program like this, perhaps it's simplest to arrange the stream to throw on EOF, and possibly on other errors.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thank you for the encouraging review and very useful suggestions. I shall implement them in version 2.0. \$\endgroup\$ – Richard Mace Feb 3 at 17:43
  • \$\begingroup\$ Following up on your very nice review yesterday, would you mind elaborating on the overflow bug you mention above. I realise I have not checked for over/underflow for performance reasons, but it would be helpful to me if you could elaborate on your point. Thanks. \$\endgroup\$ – Richard Mace Feb 4 at 8:24
  • 1
    \$\begingroup\$ To make the numbers simpler, pretend that long is 8 bits and 2s-complement, so it has a range of -128 to +127. What's std::labs(-128) in that case? Mathematically, it should be +128, but that can't be represented. Since it can't be represented, the behaviour is undefined. It might be possible to avoid converting the number to its absolute value, but I tend to confuse myself when working with negative numbers... A simpler technique, given that we're using 2s-complement for our representation, would be to convert the long to unsigned long (which is well-defined)... \$\endgroup\$ – Toby Speight Feb 4 at 9:28
  • \$\begingroup\$ ... and then copy it into the low-order bytes of the HugeInt. Then sign-extend its left-most bit to the high-order bytes. That should avoid all UB. \$\endgroup\$ – Toby Speight Feb 4 at 9:29
  • \$\begingroup\$ Thanks for the clarification. I understand now. I noticed the same problem in base 256. The magnitude of the smallest representable negative number is larger than the largest positive number, so you cannot take its absolute value. A possible approach is just to ignore this negative limit and use <minimum>+1 as your minimum for useful work (and alert users of the class). \$\endgroup\$ – Richard Mace Feb 4 at 9:37
9
\$\begingroup\$

In addition to the good suggestions from @TobySpeight, I noted the following (in source order):

HugeInt.h:

  • #include <ostream> instead of <iostream> (pet peeve of mine)
  • Use long long instead of long (some platforms - notably Windows - has sizeof(long)==sizeof(int) even of 64-bit platforms)
  • default and copy constructors should just be defaulted (= default) rather than be explicitly defined since you're not doing anything non-default.
  • maybe construct from std::string_view rather than const char*, and maybe make that constructor explicit
  • why is HugeInt radixComplement() const public?

HugeInt.cpp:

  • internal functions should be in an unnamed namespace (or be static)
  • HugeInt::HugeInt(const char *const str)
    • use const for constant values (e.g. len)
    • keep the scope of variables as short as possible
    • probably want to check for illegal characters
  • The conversion to long double overflows, when pwrOf256 gets too large (and turns into +inf) you end up with NaN after multiply by zero ruining the result
  • You'd probably want to implement operator+/- in terms of +=/-= if you're going for speed rather than the other way round (but there are many other performance optimizations possible, so no big deal)
  • Starting out I wouldn't have bothered with operator++/-- they're not really common for bigint classes IME
  • isZero relies on undefined behavior, if the number is zero you're reading past the start of digits
  • toRawString has the same issue
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ All valid and constructive suggestions. Thank you very much for your time. I shall implement your suggestions in version 2.0. \$\endgroup\$ – Richard Mace Feb 3 at 20:05
  • \$\begingroup\$ Thanks again for your very helpful review. I am aware of the overflow issue when converting to long double, but have not included checks in the code for performance reasons. Thank you for pointing out the problem with isZero and toRawString. Walking out of the array bounds is something I overlooked. Thanks for spotting this. \$\endgroup\$ – Richard Mace Feb 4 at 8:28
  • 1
    \$\begingroup\$ You're welcome. A thing I neglected to mention in my post is that I'd recommend using the sanitizers (in particular address sanitizer and ubsan) built into GCC and clang to check your program. They would have almost certainly highlighted some of these issues. Good luck. \$\endgroup\$ – user786653 Feb 4 at 17:19
  • \$\begingroup\$ @RichardMace, let me point out that you had noticed the problem in isZero ("please test first without optimisation"), you had just not tracked it down. godbolt.org/z/CnVYsq \$\endgroup\$ – Carsten S Feb 4 at 18:58
  • \$\begingroup\$ I'd suggest using <cinttypes> and int_fast64_t instead of long long, since that's guaranteed to be the fastest 64-bit int no matter the system. Though I haven't tested it on various C++ systems, it is standard. \$\endgroup\$ – prosfilaes Feb 5 at 1:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.