[BEGIN COPILOT TEXT]
## Introduction
This small C++ console program implements two classical multiplication algorithms:
**long multiplication** (the grade‑school method) and **Karatsuba multiplication**, the first sub‑quadratic multiplication algorithm discovered (Anatoly Karatsuba, 1960).
My goal here is not to optimize or modernize the algorithms, but to preserve their structure in a clear, readable form. The implementations follow the versions presented in the Wikipedia “Multiplication” article as faithfully as possible.
The code is intentionally simple and procedural. It uses 1‑based indexing for digit arrays because that mirrors the mathematical notation more closely than 0‑based indexing.
## Long Multiplication
This function implements the classical long multiplication algorithm in an arbitrary base.
Digits are stored in reverse order (least significant digit first), which simplifies carry propagation.
The implementation below is intentionally direct and mirrors the textbook algorithm step‑by‑step
## Karatsuba Multiplication (Base 10)
This is a minimal, non‑recursive implementation of the Karatsuba method.
The inputs are split into high and low parts:
x = x_1 * B ^ m + x_0
y = y_1 * B ^ m + y_0
Karatsuba reduces the number of multiplications from 4 to 3 by computing:
z = x * y = z_2 *B ^ 2m + z_1 * B ^ m + z_0
This implementation follows the Wikipedia pseudocode closely.
[END COPILOT TEXT]
#pragma once
class MyAlgorithms
{
public:
static void LongMultiplication(
int base, int p, int q, int& pSize,
std::vector<int> a,
std::vector<int> b,
std::vector<int>& product
);
static void KaratsubaBase10(
int x0, int x1, int y0, int y1,
int B, int m, long long& z);
};
#include "pch.h"
#include "MyAlgorithms.h"
void MyAlgorithms::LongMultiplication(
int base, int p, int q, int& pSize,
std::vector<int> a, std::vector<int> b,
std::vector<int>& product)
{
pSize = p + q;
product.resize(pSize + 1LL);
for (int b_i = 1; b_i <= q; b_i++)
{
int carry = 0;
for (int a_i = 1; a_i <= p; a_i++)
{
product[static_cast<long long>(a_i) + b_i - 1LL] +=
carry + a[a_i] * b[b_i];
carry = product[static_cast<long long>(a_i) + b_i - 1] / base;
product[static_cast<long long>(a_i) + b_i - 1] =
product[static_cast<long long>(a_i) + b_i - 1] % base;
}
product[static_cast<long long>(b_i) + p] = carry;
}
}
void MyAlgorithms::KaratsubaBase10(
int B, int m, int x0, int x1,
int y0, int y1, long long& z)
{
int pb = static_cast<int>(pow(B, m));
int x = x1 * pb + x0;
int y = y1 * pb + y0;
int z2 = x1 * y1;
int z1 = x1 * y0 + x0 * y1;
int z0 = x0 * y0;
z = z2 * static_cast<int>(pow(B, 2 * m)) + z1 * pb + z0;
}
#include "MyAlgorithms.h"
static void DoLongMultiplication()
{
int base = 0, p = 0, q = 0, pSize = 0;
char line[128] = "";
char inputaStr[128] = "";
char inputbStr[128] = "";
char* aReverseStr = nullptr;
char* bReverseStr = nullptr;
std::cout << "Enter base = ";
std::cin.getline(line, 128);
base = atoi(line);
std::cout << "a = ";
std::cin.getline(inputaStr, 128);
std::cout << "b = ";
std::cin.getline(inputbStr, 128);
aReverseStr = _strrev(inputaStr);
bReverseStr = _strrev(inputbStr);
p = static_cast<int>(strlen(aReverseStr));
q = static_cast<int>(strlen(bReverseStr));
pSize = p + q;
std::vector<int> a(p + 1);
std::vector<int> b(q + 1);
std::vector<int> ab(p + q + 1);
std::vector<int> product;
for (int i = 1; i <= p; i++)
a[i] = aReverseStr[i - 1] - '0';
for (int i = 1; i <= q; i++)
b[i] = bReverseStr[i - 1] - '0';
MyAlgorithms::LongMultiplication(
base, p, q, pSize, a, b, ab);
size_t i = ab.size() - 1, j = 1;
while (i >= 0)
{
if (ab[i] == 0)
i--;
else
break;
}
product.push_back(0);
for (j = i; j >= 1; j--)
product.push_back(ab[j]);
std::cout << "product = ";
for (int i = 1; i < product.size(); i++)
std::cout << product[i];
std::cout << std::endl;
}
static void DoKaratsuba()
{
char line[128] = "";
std::cout << "Enter base = ";
std::cin.getline(line, 128);
int B = atoi(line);
std::cout << "Enter m = ";
std::cin.getline(line, 128);
int m = atoi(line);
std::cout << "x1 = ";
std::cin.getline(line, 128);
int x1 = atoi(line);
std::cout << "x0 = ";
std::cin.getline(line, 128);
int x0 = atoi(line);
std::cout << "y1 = ";
std::cin.getline(line, 128);
int y1 = atoi(line);
std::cout << "y0 = ";
std::cin.getline(line, 128);
int y0 = atoi(line);
long long z = 0;
MyAlgorithms::KaratsubaBase10(
B, m, x0, x1, y0, y1, z);
std::cout << "z = " << z << std::endl;
}
int main()
{
while (true)
{
char line[128] = "";
std::cout << "== Menu ==" << std::endl;
std::cout << "1 Long Multiplication" << std::endl;
std::cout << "2 Karatsuba Multiplication" << std::endl;
std::cout << "3 Exit" << std::endl;
std::cout << "Option (1 or 2 or 3) = ";
std::cin.getline(line, 128);
char option = line[0];
if (option == '1')
{
DoLongMultiplication();
}
else if (option == '2')
{
DoKaratsuba();
}
else
break;
}
return 0;
}
== Menu ==
1 Long Multiplication
2 Karatsuba Multiplication
3 Exit
Option (1 or 2 or 3) = 1
Enter base = 10
a = 506
b = 208
product = 105248
== Menu ==
1 Long Multiplication
2 Karatsuba Multiplication
3 Exit
Option (1 or 2 or 3) = 2
Enter base = 10
Enter m = 2
x1 = 5
x0 = 6
y1 = 2
y0 = 8
z = 105248
== Menu ==
1 Long Multiplication
2 Karatsuba Multiplication
3 Exit
Option (1 or 2 or 3) = 3
D:\Multiplication\x64\Debug\Multiplication.exe (process 30912) exited with code 0 (0x0).
Press any key to close this window . . .
Numerical Explorations 