mercredi 4 août 2021

BigInt multiplication and to_string implementation outputs too many zeros

I created the following for multiplying two big integers stored with base 1,000,000,000 as a vector<int32_t>:

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

template<typename T>
constexpr T power_of_10(T n)
{
    return n < 0 ? 0 : n == 0 ? 1 : (n == 1 ? 10 : 10 * power_of_10(n - 1));
}

template<typename T>
constexpr T base_value = power_of_10<T>(std::numeric_limits<T>::digits10);

template<typename T>
class BigInt {
private:
    static constexpr const T base = base_value<T>;
    std::vector<T> digits;
    
public:
    BigInt(const char* value) : BigInt(std::string(value))
    {
    }
    
    BigInt(const std::string& value)
    {
        constexpr const int stride = std::numeric_limits<T>::digits10;
        const std::size_t size = value.size() / stride;

        for (std::size_t i = 0; i < size; ++i)
        {
            auto it = value.begin();
            auto jt = value.begin();
            std::advance(it, i * stride);
            std::advance(jt, (i * stride) + stride);
            digits.push_back(std::stoi(std::string(it, jt)));
        }
        
        if (value.size() % stride)
        {
            auto remainder = std::string(value.begin() + size * stride, value.end());
            digits.push_back(std::stoi(remainder));
        }
        
        std::reverse(digits.begin(), digits.end());
    }
    
    BigInt& multiply(const BigInt<T>& other)
    {
        std::vector<T> product = std::vector<T>(digits.size() + other.digits.size(), 0);
        
        for (std::size_t j = 0; j < other.digits.size(); ++j)
        {
            std::uint64_t carry = 0, total = 0;
            for (std::size_t i = 0; i < digits.size(); ++i)
            {
                total = product[i + j] + (static_cast<std::uint64_t>(digits[i]) * static_cast<std::uint64_t>(other.digits[j])) + carry;
                carry = total / base;
                total %= base;

                if (i + j >= product.size())
                {
                    product.resize(product.size() + 1);
                }

                product[i + j] = static_cast<T>(total);
            }

            if (carry)
            {
                product[product.size() - 1] = static_cast<T>(carry);
            }
        }
        
        digits = product;
        return *this;
    }
    
    std::string to_string() {
        std::string result;
        for (std::int64_t i = digits.size() - 1; i >= 0; --i)
        {
            T value = digits[i];
            T divisor = base;

            while(divisor)
            {
                if (divisor != base)
                {
                    result += (value / divisor) + '0';
                }
                value %= divisor;
                divisor /= 10;
            }
        }
        return result;
    }
};

int main(int argc, const char * argv[])
{
    BigInt<std::int32_t> a = "5000000000";
    BigInt<std::int32_t> b = "5000000000";
    
    std::cout<<a.multiply(b).to_string()<<"\n";
    
    return 0;
}

When I print the result of the multiplication, I am getting 5,000,000,000 * 5,000,000,000 = 250,000,000,000,000,000,000,000,000,000,000,000 which has way too many zeroes!

It should have 18 zeroes, but mine has 34.

I believe my multiplication algorithm is correct and my to_string is incorrect because 500 * 500 prints correctly as 25,000.

Any ideas what is wrong?

Aucun commentaire:

Enregistrer un commentaire