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