From d7d33b9779232972a1281bfddc1cf2626ec36050 Mon Sep 17 00:00:00 2001 From: Olivier Gayot Date: Sun, 19 Nov 2017 13:12:51 +0100 Subject: Replaced dumb multiplication algorithm by long multiplication Long multiplication is the multiplication algorithm that is being taught to children in grade school. Although it is very slow compared to Karatsuba algorithm, it is still much faster than the dumb algorithm previously used. Signed-off-by: Olivier Gayot --- number.cpp | 32 ++++++++++++++++++++++++++++++-- 1 file changed, 30 insertions(+), 2 deletions(-) diff --git a/number.cpp b/number.cpp index fa62b00..12448de 100644 --- a/number.cpp +++ b/number.cpp @@ -108,8 +108,36 @@ number::operator*(const number &n) const { number result; - for (number i; i < n; ++i) { - result += *this; + if (n < UINT32_MAX && *this < UINT32_MAX) { + return number(1ull * to_uint32() * n.to_uint32()); + } + + int level = 0; + + for (auto it_low: _operands) { + number intermediate; + + std::uint32_t carry = 0; + + for (auto it_high: n._operands) { + std::uint64_t tmp = 1ull * it_low * it_high + carry; + + intermediate._operands.push_back(tmp & UINT32_MAX); + + carry = tmp >> 32; + } + + if (carry) { + intermediate._operands.push_back(carry); + } + + for (auto j = 0; j < level; ++j) { + intermediate <<= 32; + } + + result += intermediate; + + ++level; } return result; -- cgit v1.2.3