Необходимо проверить код C++ и получить результат умножения Карацубы. ⇐ C++

[Anonymous]

Похоже, программа умножения двух чисел (2^136279841)-1 у меня работает. Но я не уверен в правильности результата. Программа должна печатать первые *5 значений: 1, 0, 0, 0 и 0. Но она печатает:
Time = 68148010 (us DEC)
POLE[0]: 0x1
POLE[1]: 0
POLE[2]: 0
Pole[3]: 0xffffffffffffffff
Pole[4]: 0xfffffffffffffffd

*Примечание: я проверяю с помощью функции BitAnd[BitShiftRight[(2^136279841 - 1)^2, 0], 264 - 1] на wolframalpha.com Для POLE [x] вместо 0 в формуле введите x * 64, т.е. для POLE[3] вместо 0 введите 192.
Я в своей программе выделяю 3 ГБ ОЗУ. Число (2^136279841) - 1 сохраняется ближе к концу памяти от позиции First256_offset, в окне отладки введите POLE + First256_offset/ 8, затем конец числа находится под адресом POLE + First256_offset/ 8 + n ( введите в окно памяти). Результат сохраняется с начала выделенной памяти, т.е. ПОЛЮСА (введите в окно памяти). Пространство памяти над результатом и под числом используется программой для вспомогательных массивов вычислений.
Пользовательская функциональная программа:
// AVX2_openai-01-preview_Karatsuba_test.cpp

#include

#include
#include
#include

#include // I added
#include "windows.h" // I added for BYTE* ptr

using namespace std;
using namespace std::chrono;

constexpr size_t GB = 3;

// Function prototypes
void big_add(uint64_t* result, const uint64_t* a, const uint64_t* b, size_t n);
void big_sub(uint64_t* result, const uint64_t* a, const uint64_t* b, size_t n);
void karatsuba_mul(uint64_t* result, const uint64_t* x, const uint64_t* y, size_t n, uint64_t* temp);

// The main function performing Karatsuba multiplication
void karatsuba_multiplication(uint64_t* POLE, size_t First_256_offset, size_t n_words) {
// The two numbers are the same and start at POLE + First_256_offset
uint64_t* x = POLE + First_256_offset / sizeof(uint64_t);
uint64_t* y = x; // Since we are multiplying the number by itself

// The result will be stored in POLE[0...2*n_words - 1]
uint64_t* result = POLE; // Use the beginning of POLE for the result

// Allocate temporary space from POLE[2*n_words...First_256_offset - 1]
uint64_t* temp = POLE + 2ULL * n_words;
//size_t temp_size = First_256_offset - 2ULL * n_words;
size_t temp_size = (size_t)(GB * 0x40000000ULL) - 3ULL * n_words;

// Ensure we have enough temporary space
if (temp_size < 6 * n_words) {
// Not enough temporary space
// Handle error appropriately (e.g., return, print error)
return;
}

karatsuba_mul(result, x, y, n_words, temp);
}

// Function to add two big numbers: result = a + b
void big_add(uint64_t* result, const uint64_t* a, const uint64_t* b, size_t n) {
unsigned char carry = 0;
for (size_t i = 0; i < n; ++i) {
carry = _addcarry_u64(carry, a, b, &result);
}
}

// Function to subtract two big numbers: result = a - b
void big_sub(uint64_t* result, const uint64_t* a, const uint64_t* b, size_t n) {
unsigned char borrow = 0;
for (size_t i = 0; i < n; ++i) {
borrow = _subborrow_u64(borrow, a, b, &result);
}
}

// Karatsuba multiplication function
void karatsuba_mul(uint64_t* result, const uint64_t* x, const uint64_t* y, size_t n, uint64_t* temp) {
// Base case: if the size is small, use traditional multiplication
if (n

Подробнее здесь: https://stackoverflow.com/questions/792 ... iplication