Эффективное вычисление битов высокого порядка умножения

Многие ЦП имеют окоды с одной сборкой для возврата бит порядка высокий для 32-битного целочисленного умножения. Обычно умножение двух 32-битных целых чисел приводит к 64-битовому результату, но это сокращается до младших 32 бит, если вы храните его в 32-битном целое.

Например, в PowerPC код операции mulhw возвращает 32 бита 64-битного результата умножения 32x32 бит в одном Часы. Это именно то, что я ищу, но более переносимо. Там аналогичный код операции, umulhi(), в NVidia CUDA.

В C/С++ существует ли эффективный способ вернуть бит высокого порядка 32x32 умножения? В настоящее время я вычисляю его, отбрасывая до 64 бит, что-то вроде:

unsigned int umulhi32(unsigned int x, unsigned int y)
{
  unsigned long long xx=x;
  xx*=y;
  return (unsigned int)(xx>>32);
}

но это более чем в 11 раз медленнее обычного 32 на 32 умножить, потому что я использую overkill 64-битную математику даже для умножения.

Есть ли более быстрый способ вычисления бит высокого порядка?

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

У SSE есть PMULHUW, 16x16 → верхняя 16-разрядная версия этого, но не 32x32 → топ-32 версия, как я Я ищу.

Ответ 1

gcc 4.3.2 с оптимизацией -O1 или выше, перевел вашу функцию точно так же, как вы показали ее на сборке IA32 следующим образом:

umulhi32:
        pushl   %ebp
        movl    %esp, %ebp
        movl    12(%ebp), %eax
        mull    8(%ebp)
        movl    %edx, %eax
        popl    %ebp
        ret

Который делает только один 32-битный mull и помещает высокие 32 бита результата (от %edx) в возвращаемое значение.

Что ты хотел, правда? Похоже, вам просто нужно включить оптимизацию на вашем компиляторе;) Возможно, вы можете нажать компилятор в правильном направлении, исключив промежуточную переменную:

unsigned int umulhi32(unsigned int x, unsigned int y)
{
  return (unsigned int)(((unsigned long long)x * y)>>32);
}

Ответ 2

Я не думаю, что есть способ сделать это в стандартном C/С++ лучше, чем то, что у вас уже есть. То, что я сделал бы, это написать простой сборщик, который возвращает нужный результат.

Не то, чтобы вы спрашивали о Windows, но в качестве примера, даже если Windows имеет API, который звучит так, как будто он делает то, что вы хотите (32-битный 32-разрядный размножается при получении полного результата в 64 бит), он реализует умножение как макрос, который делает то, что вы делаете:

#define UInt32x32To64( a, b ) (ULONGLONG)((ULONGLONG)(DWORD)(a) * (DWORD)(b))

Ответ 3

В 32-разрядной версии intel умножение влияет на два регистра для вывода. То есть, 64 бита полностью доступны, хотите вы этого или нет. Его просто функция того, является ли компилятор достаточно умным, чтобы использовать его.

Современные компиляторы делают потрясающие вещи, поэтому мое предложение - экспериментировать с флагами оптимизации еще немного, по крайней мере, на Intel. Вы могли бы подумать, что оптимизатор может знать, что процессор производит 64-битное значение от 32 до 32 бит.

Тем не менее, в какой-то момент я попытался заставить компилятор использовать modulo, а также дивиденд по результату деления, но старый компилятор Microsoft с 1998 года был недостаточно умен, чтобы реализовать ту же инструкцию, что и оба результата.