Самая быстрая факториальная реализация с 64-битным результатом в ассемблере

Я ловко построил справочную таблицу на ассемблере. На всякий случай, если вы заржавели в своей сборке, подпрограмма ожидает, что параметр будет в регистре ecx. Я проверяю, что он находится в диапазоне, затем читаю значения таблицы поиска в регистры eax и edx. Если значение выходит за пределы допустимого диапазона, я просто исключаю регистры eax и edx друг с другом (это приводит их к 0). К сожалению, поскольку это процедура сборки, компилятор не сможет встроить код. Но я уверен, что те несколько циклов, которые я сэкономил, написав свою замечательную ассемблерную процедуру, с лихвой компенсируют любой выигрыш от встраивания.

factorial:
    xorl    %eax, %eax
    xorl    %edx, %edx
    cmpl    $20, %ecx
    ja  .TOOBIG
    movl    CSWTCH.1(,%ecx,8), %eax
    movl    CSWTCH.1+4(,%ecx,8), %edx
.TOOBIG:

LOOKUP_TABLE:
    .section    .rodata
    .align 32
    .type   CSWTCH.1, @object
    .size   CSWTCH.1, 168
CSWTCH.1:
    .long   1
    .long   0
    .long   1
    .long   0
    .long   2
    .long   0
    .long   6
    .long   0
    .long   24
    .long   0
    .long   120
    .long   0
    .long   720
    .long   0
    .long   5040
    .long   0
    .long   40320
    .long   0
    .long   362880
    .long   0
    .long   3628800
    .long   0
    .long   39916800
    .long   0
    .long   479001600
    .long   0
    .long   1932053504
    .long   1
    .long   1278945280
    .long   20
    .long   2004310016
    .long   304
    .long   2004189184
    .long   4871
    .long   -288522240
    .long   82814
    .long   -898433024
    .long   1490668
    .long   109641728
    .long   28322707
    .long   -2102132736
    .long   566454140

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

static constexpr uint64_t const_factorial(uint32_t i) {
    return (i==0)? 1: (i * const_factorial(i-1));
}

uint64_t factorial(uint32_t i) {
    switch(i) {
        case 0: return const_factorial(0);
        case 1: return const_factorial(1);
        case 2: return const_factorial(2);
        case 3: return const_factorial(3);
        case 4: return const_factorial(4);
        case 5: return const_factorial(5);
        case 6: return const_factorial(6);
        case 7: return const_factorial(7);
        case 8: return const_factorial(8);
        case 9: return const_factorial(9);
        case 10: return const_factorial(10);
        case 11: return const_factorial(11);
        case 12: return const_factorial(12);
        case 13: return const_factorial(13);
        case 14: return const_factorial(14);
        case 15: return const_factorial(15);
        case 16: return const_factorial(16);
        case 17: return const_factorial(17);
        case 18: return const_factorial(18);
        case 19: return const_factorial(19);
        case 20: return const_factorial(20);
        default: return 0;
    }
}

На случай, если вы пропустили это из-за моей неудачной попытки пошутить. Компилятор C++ более чем способен корректно оптимизировать ваш код. Как видите, мне не нужно было делать ничего особенного с таблицами поиска, бинарными деревьями поиска или хэшами. Всего лишь простой оператор switch, а компилятор сделал все остальное.

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

Поскольку вы заранее точно знаете, сколько и какого размера будут все элементы, просто создайте непрерывный массив значений (жестко закодированных или предварительно рассчитанных). После проверки ввода функции (‹ 0 или > 12/20) вы можете использовать простую адресацию смещения для получения соответствующего значения. Это будет работать за время O(1).

Обновление от 2021 года. Имея под рукой C++17.

Я предполагаю, что нет более быстрого способа, чем ниже. Ассемблер не нужен.

Поскольку количество факториалов, которые будут соответствовать 64-битному значению без знака, очень мало (21), массив constexpr времени компиляции будет использовать в основном только 21 * 8 = 168 байтов.

168 байт

Это число настолько мало, что мы можем легко построить время компиляции constexpr std::array и прекратить все дальнейшие рассмотрения.

На самом деле все можно сделать во время компиляции.

Сначала мы определим подход по умолчанию для вычисления факториала как функцию constexpr:

constexpr unsigned long long factorial(unsigned long long n) noexcept {
    return n == 0ull ? 1 : n * factorial(n - 1ull);
}

При этом факториалы можно легко вычислить во время компиляции. Затем мы заполняем std::array всеми факториалами. Мы также используем constexpr и делаем его шаблоном с вариативным пакетом параметров.

Мы используем std::integer_sequence для создания факториалов для индексов 0,1,2,3,4,5, ....

Это просто и не сложно:

template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { factorial(ManyIndices)... } };
};

Эта функция будет получать целочисленную последовательность 0,1,2,3,4,... и возвращать std::array<unsigned long long, ...> с соответствующими факториалами.

Мы знаем, что можем хранить максимум 21 значение. И поэтому мы создаем следующую функцию, которая будет вызывать вышеуказанную последовательность целых чисел 1,2,3,4,...,20,21, например:

constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}

И вот, наконец,

constexpr auto Factorial = generateArray();

даст нам время компиляции std::array<unsigned long long, 21> с именем Factorial, содержащим все факториалы. А если нам нужен i-й факториал, то можно просто написать Factorial[i]. Расчета во время выполнения не будет.

Я не думаю, что есть более быстрый способ вычислить факториал.

Пожалуйста, ознакомьтесь с полной программой ниже:

#include <iostream>
#include <array>
#include <utility>
// ----------------------------------------------------------------------
// All the below will be calculated at compile time
// constexpr factorial function
constexpr unsigned long long factorial(unsigned long long n) noexcept {
    return n == 0ull ? 1 : n * factorial(n - 1ull);
}
// We will automatically build an array of factorials at compile time
// Generate a std::array with n elements 
template <size_t... ManyIndices>
constexpr auto generateArrayHelper(std::integer_sequence<size_t, ManyIndices...>) noexcept {
    return std::array<unsigned long long, sizeof...(ManyIndices)>{ { factorial(ManyIndices)... } };
};
// Max index for factorials for an 64bit unsigned value 
constexpr size_t MaxIndexFor64BitValue = 21;

// Generate the required number of elements
constexpr auto generateArray()noexcept {
    return generateArrayHelper(std::make_integer_sequence<size_t, MaxIndexFor64BitValue>());
}
// This is an constexpr array of all factorials numbers
constexpr auto Factorial = generateArray();

// All the above was compile time
// ----------------------------------------------------------------------

// Test function
int main() {
    for (size_t i{}; i < MaxIndexFor64BitValue; ++i)
        std::cout << i << '\t' << Factorial[i] << '\n';
    return 0;
}

Разработано, скомпилировано и протестировано с помощью Microsoft Visual Studio Community 2019, версия 16.8.2.

Дополнительно скомпилировано и протестировано с помощью gcc 10.2 и clang 11.0.1.

Язык: С++17

Кто сказал, что ваша версия сборки в любом случае будет быстрее, чем версия C++. В самом деле, кто сказал, что он будет даже соответствовать по скорости? Готов поспорить на 100 долларов, что вам никогда не удастся сделать это так быстро, как это делает компилятор.

По многочисленным просьбам, с точки зрения производительности, это легендарный двоичный поиск, а не хеш-таблица (я полагаю, что в стандартном С++ этого нет).

#include <map>

void main()
{
    std::map<int, BigIntThing> factMap;
    // insert all elements here, probably fancier ways to do this
    factMap.insert( 1 );
    factMap.insert( 1 );
    factMap.insert( 2 );
    // ....
    // to access, say 15!
    BigIntThing factMap[15]; // I think the index is right >_<
}

Вот и все. Заказывается std::map, поэтому, если у вашего BigIntThing есть оператор сравнения, все хорошо. Должен быть способ получить эти const и/или static и/или global, чтобы скомпилировать их так, как вы хотите.

Если вы работаете только с числами от 0 до 19, хеш-таблица или двоичное дерево — это излишество. Просто создайте unsigned int[20], а затем запросите индекс:

const unsigned int FACTORIALS[20] = {1,1,2,6,24,120,etc..};

unsigned int factorial(unsigned int num) {
    if(num >= 0 && num <= 19) {
        return FACTORIALS[num];
    }
    else {
        throw // some sort of exception
    }
}

Вероятно, вы могли бы использовать шаблоны и для построения массива.

ответ gcc

... который, вероятно, лучше вашего, был скомпилирован из:

uint64_t answers[] = {
    1ULL,
    1ULL,
    2ULL,
    6ULL,
    24ULL,
    ...
    2432902008176640000ULL,
};

uint64_t factorial(unsigned int i) {
    if(i >= sizeof(answers) / sizeof(*answers))
        return 0;
    else
        return answers[i];
}

...и сборка...

factorial:
    cmpl    $20, %edi
    movl    $0, %eax
    ja  .L3
    movslq  %edi,%eax
    movq    answers(,%rax,8), %rax
.L3:
    rep
    ret
answers:
    .quad 1
    .quad 1
    ...

... который, кажется, является первым ответом на 64-битный ассемблер...