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>

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;