Class template for basic operations on large integers?

sjtwenzhou

Regarding the basic operations of this large integer (such as long long) and other related issues, I have also read many posts, the storage methods are different, and the implementation ideas are also different. I would like to be able to compile these basic operations into a class template. I hope you can provide some golden algorithms or good implementation ideas!
    The basic operations include, addition, subtraction, multiplication, division, modulo, power, output, etc .; storage methods such as arrays, linked lists, etc. can be used.

superandy

Division is not easy to achieve.

珈蓝易拉罐

Large integers, is it better to make a class?
What does the template normalize?

zfy010317

How to output as a string? It's not easy to do

sjtwenzhou

Upstairs is right, it should be made into a class. What I wrote above may be a bit misleading. In fact, I want to encapsulate these functions into a class. Oh, thank you for your correction!

sjtwenzhou

How to output as a string? It's not easy to do
------------------------------------------------
The output is implemented in this way, the following can be a class member function, of course, we can also write a << overloaded function, hoping to throw a brick
void print_bigint(long long n)
{
if (n>=10)
print_bigint(n/10);
printf("%d",int(n%10));
}

superandy

Give you one that only supports *=(int)
class BigInt
{
    typedef unsigned long FUNDUS_T;
    typedef unsigned long long int ACCUMULATE_T;
    typedef vector<FUNDUS_T> CONTAINER_T;
    enum {FUNDUS = 1000000000};
    enum {FUNDUS_LEN = numeric_limits<FUNDUS_T>::digits10};

public:
    BigInt(FUNDUS_T x = 0)
    {
        c.reserve(65535);
        do
        {
            c.push_back(x% FUNDUS);
            x /= FUNDUS;
        } while (x != 0);
    }

public:
    BigInt&operator*=(FUNDUS_T x)
    {
        ACCUMULATE_T carry = 0;
        for (CONTAINER_T::iterator i = c.begin(); i != c.end(); ++i)
        {
            carry = ACCUMULATE_T(*i) * x + carry;
            *i = carry% FUNDUS;
            carry /= FUNDUS;
        }

        if (carry != 0)
        {
            c.push_back(carry);
        }
        
        return *this;
    }

public:
    template <typename OSTREAM_T>
        friend OSTREAM_T&operator<<(OSTREAM_T&, const BigInt&);

private:
    CONTAINER_T c;
};

    template<typename OSTREAM_T>
        OSTREAM_T&operator<<(OSTREAM_T&os, const BigInt&x)
    {
        BigInt::CONTAINER_T::const_reverse_iterator iter = x.c.rbegin();
        os << *iter;
        ++iter;
        while (iter != x.c.rend())
        {
            os << setw(BigInt::FUNDUS_LEN) << setfill('0') << *iter;
            ++iter;
        }

        return os;
    }

zfy010317

The output is implemented in this way, the following can be a class member function, of course, we can also write a << overloaded function, hoping to throw a brick
void print_bigint(long long n)
{
if (n>=10)
print_bigint(n/10);
printf("%d",int(n%10));
}
-------------------------------------------------- -
Large numbers are not a set of numbers, and the decimal grouping and the binary grouping are not the same.

sjtwenzhou

Large numbers are not a set of numbers, and the decimal grouping and the binary grouping are not the same.
-----------------------------------
I don't quite understand the meaning of this sentence?

Thank you, jixingzhong(Drowthworm·Xingchen) The link you provided does exist. I have browsed it before, but did not notice it.

zfy010317

For example, 0xff00 in hexadecimal, separate 0xff, 0x00. Grouping is natural, and merging is intuitive.
But in decimal, all numbers must be merged to know the situation of each digit (but it is not possible to combine all numbers.
Separate, is this not a contradiction?)
such as:
255, 0 and 65280 have nothing in common.