Самый быстрый алгоритм MOD в C++ для чрезвычайно больших чисел uint_64_t, хранящихся в массиве. ⇐ C++

[Anonymous]

Я работаю с очень большими числами и хотел бы проверить результат умножения Карацубы ((2^136279841)-1)^2, для которого требуется (532 344 * _m256i_epi64)^2, т. е. 4 258 752 uint64_t для хранения результата. p>
Все необходимые массивы данных я сохранил в заранее выделенной памяти:

Код: Выделить всё

size_t num_bits = 136279841;
size_t num_uint64 = (num_bits + 255) / 256 * 4;
size_t n = num_uint64;

// Correct calculation for First_256_offset
size_t First_256_offset = (GB * 0x40000000ULL) - ((2ULL + 1ULL) * num_uint64 * sizeof(uint64_t));

constexpr size_t GB = 3;
static const SIZE_T giga = 1024 * 1024 * 1024;
static const SIZE_T size = GB * giga;
uint64_t* ARRAY = static_cast(VirtualAlloc(NULL, size, MEM_COMMIT, PAGE_READWRITE));

uint64_t* number = ARRAY + First_256_offset / sizeof(uint64_t);

// Store the number (2^136279841)-1) using _mm256_maskstore_epi64 in a loop
__m256i ones = _mm256_set1_epi64x(-1);
size_t i = 0;
for (; i < (num_uint64 - 4); i += 4) {
_mm256_store_si256((__m256i*) & number[i], ones);
}

_mm256_maskstore_epi64((long long int*) & number[i], _mm256_setr_epi64x(-1, -1, -1, -1), _mm256_setr_epi64x(0x1111111111111111, 0x0000000000000001LL, 0x0, 0x0));

Мне нужно вычислить MOD (A, B), где A, результат умножения, который занимает около 3 минут на моем ноутбуке, сохраняется из МАССИВА, а B — число в коде. Пространство памяти выше A и ниже First_256_offset используется как временное пространство для умножения Карацубы. В результате MOD (A, B) я могу использовать пробел под First_256_offset.
Мне нужно избегать использования каких-либо внешних библиотек, векторных, строковых функций или функций memalloc.P.S. Обратите внимание, что я использую операцию uint64_t в своей программе C++ Karatsuba, поскольку _m256i может обрабатывать только int64_t, а мне нужно работать с данными uint64_t.

Подробнее здесь: https://stackoverflow.com/questions/791 ... -stored-in