summaryrefslogtreecommitdiff
path: root/number.cpp
diff options
context:
space:
mode:
authorOlivier Gayot <og@satcom1.com>2017-11-19 13:12:51 +0100
committerOlivier Gayot <og@satcom1.com>2017-11-19 16:21:05 +0100
commitd7d33b9779232972a1281bfddc1cf2626ec36050 (patch)
treeb4076f3897da1c7efc6c53b8af1b892775b0a40a /number.cpp
parent471186ab6e721fed603871f385d9590a69878de3 (diff)
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 <og@satcom1.com>
Diffstat (limited to 'number.cpp')
-rw-r--r--number.cpp32
1 files 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;