Получение старшей и младшей половин полного целочисленного умножения

Для этого вам не нужны векторы, если у вас нет нескольких входов для параллельной обработки. clang и gcc уже хорошо справляются с оптимизацией «нормального» способа написания кода: приведение к двойному размеру, умножение, затем сдвиг, чтобы получить высокую половину. Компиляторы распознают этот шаблон.

Они замечают, что операнды начинались как 32-битные, поэтому все верхние половины равны нулю после преобразования в 64b. Таким образом, они могут использовать mul insn x86 для умножения 32b * 32b-> 64b вместо выполнения полного умножения на 64b с расширенной точностью. В 64-битном режиме они делают то же самое с __uint128_t версией вашего кода.

Обе эти функции компилируются в довольно хороший код (по одному mul или imul на умножение).. gcc -m32 не поддерживает типы 128b, но я не буду вдаваться в подробности, потому что 1. вы спрашивали только о полных умножениях 32-битных значений и 2. вы всегда должны использовать 64-битный код, когда хотите, чтобы что-то работало быстро. Если вы выполняете полное умножение, когда результат не помещается в регистр, clang позволит избежать множества дополнительных инструкций mov, потому что gcc глупо об этом. Эта небольшая тестовая функция послужила хорошим тестовым примером для отчета об ошибке gcc.

Эта ссылка на Godbolt включает функцию, которая вызывает это в цикле, сохраняя результат в массиве. Он автоматически векторизуется с кучей перетасовки, но по-прежнему выглядит как ускорение, если у вас есть несколько входов для параллельной обработки. Другой формат вывода может потребовать меньше перетасовки после умножения, например, сохранение отдельных массивов для D и E.

Я включаю версию 128b, чтобы показать, что компиляторы могут справиться с этим, даже если это нетривиально (например, просто выполните 64-битную инструкцию imul, чтобы выполнить умножение 64 * 64-> 64b на 32-битных входах, после обнуления любых старших битов, которые могут быть сидит во входных регистрах при вводе функции.)

При нацеливании на процессоры Haswell и новее, gcc и clang могут использовать инструкцию mulx BMI2. (Я использовал -mno-bmi2 -mno-avx2 в ссылке godbolt, чтобы упростить asm. Если у вас есть процессор Haswell, просто используйте -O3 -march=haswell.) mulx dest1, dest2, src1 выполняет dest1:dest2 = rdx * src1, а mul src1 rdx:rax = rax * src1. Итак, mulx имеет два входа только для чтения (один неявный: _17 _ / _ 18_) и два выхода только для записи. Это позволяет компиляторам выполнять полное умножение с меньшим количеством mov инструкций для ввода и вывода данных в неявные регистры для mul. Это лишь небольшое ускорение, особенно. поскольку 64-битный mulx имеет задержку 4 цикла вместо 3 на Haswell. (Как ни странно, 64-битные mul и mulx немного дешевле 32-битных mul и mulx.)

// compiles to good code: you can and should do this sort of thing:
#include <stdint.h>

struct DE { uint32_t D,E; };

struct DE f_structret(uint32_t A, uint32_t B, uint32_t C) {
  uint64_t AC = A * (uint64_t)C;
  uint64_t BC = B * (uint64_t)C;
  uint32_t D = AC >> 32;         // high half
  uint32_t E = AC + (BC >> 32);  // We could cast to uint32_t before adding, but don't need to
  struct DE retval = { D, E };
  return retval;
}



#ifdef __SIZEOF_INT128__  // IDK the "correct" way to detect __int128_t support
struct DE64 { uint64_t D,E; };

struct DE64 f64_structret(uint64_t A, uint64_t B, uint64_t C) {
  __uint128_t AC = A * (__uint128_t)C;
  __uint128_t BC = B * (__uint128_t)C;
  uint64_t D = AC >> 64;         // high half
  uint64_t E = AC + (BC >> 64);
  struct DE64 retval = { D, E };
  return retval;
}
#endif

Если я правильно понимаю, вы хотите вычислить количество потенциальных переполнений в A * B. Если да, то у вас есть 2 хороших варианта - «использовать вдвое большую переменную» (написать 128-битную математическую функцию для uint64 - это не так уж сложно (или подождите, пока я опубликую ее завтра)) и «использовать тип с плавающей запятой»: (float (A) * float (B)) / float (C), поскольку потеря точности минимальна (при условии, что float составляет 4 байта, двойной 8 байтов и длинный двойной 16 байтов), а для float и uint32 требуется 4 байта памяти (используйте double для uint64_t, так как он должен быть длиной 8 байт):

#include <iostream>
#include <conio.h>
#include <stdint.h>

using namespace std;

int main()
{
    uint32_t a(-1), b(-1);
    uint64_t result1;
    float result2;
    result1 = uint64_t(a)*uint64_t(b)/4294967296ull;    // >>32 would be faster and less memory consuming
    result2 = float(a)*float(b)/4294967296.0f;
    cout.precision(20);
    cout<<result1<<'\n'<<result2;
    getch();
    return 0;
}

Производит:

4294967294
4294967296

Но если вам нужен действительно точный и правильный ответ, я бы предложил использовать для вычислений вдвое больший шрифт.

Теперь, когда я думаю об этом - вы можете использовать long double для uint64 и double для uint32 вместо написания функции для uint64, но я не думаю, что это гарантирует, что long double будет 128 бит, и вам придется это проверить. Я бы выбрал более универсальный вариант.

РЕДАКТИРОВАТЬ:

You can write function to calculate that without using anything more
than A, B and result variable which would be of the same type as A.
Just add rightmost bit of (where Z equals B*(A>>pass_number&1)) Z<<0,
Z<<1, Z<<2 (...) Z<<X in first pass, Z<<-1, Z<<0, Z<<1 (...) Z<<(X-1)
for second (there should be X passes), while right shifting the result
by 1 (the just computed bit becomes irrelevant to us after it's
computed as it won't participate in calculation anymore, and it would
be erased anyway after dividing by 2^X (doing >>X)

(пришлось поместить в «код», так как я здесь новичок и не могу найти другого способа, чтобы скрипт форматирования не съел половину его)

Это всего лишь быстрая идея. Вам нужно будет проверить его правильность (извините, но я действительно устал прямо сейчас - но результат не должен выходить за рамки любой точки расчета, так как максимальный перенос будет иметь значение 2X, если я прав, а сам алгоритм вроде хороший).

Я напишу код для этого завтра, если вам все еще понадобится помощь.