Определение наиболее эффективного размера слова для реализации bignums в C ++ 11?
Обычно bignums реализуются с использованием нескольких слов, но я бы хотел выбрать размер слова как можно более переносимым. Это сложнее, чем может показаться — std::uint64_t доступно во многих 32-битных компиляторах, но std::uint32_t вероятно, будет лучшим выбором на 32-битной машине. Таким образом, соблазн будет использовать std :: size_t, но нет гарантии для данной архитектуры, что std::size_t является наиболее эффективным типом для арифметики, например, на новый x32 Linux ABI std::size_t будет 32-битным, но std::uint64_t все равно будет лучшим выбором.
В C ++ 11 определены быстрые / наименьшие типы различных размеров, но он не дает возможности запрашивать их относительную производительность. Я понимаю, что не может быть лучшего портативного ответа, мое лучшее предположение сейчас по умолчанию std::size_t и обнаруживать исключительные архитектуры во время настройки. Но может быть, есть лучший способ?
Решение
Реальный ключ, эффективно реализующий bignums, заключается в том, что вам нужно иметь умножающееся расширение, которое дает вам в 2 раза больше бит, чем ваш основной размер слова. Таким образом, вы можете использовать uint64_t в качестве базового размера слова, только если ваша платформа поддерживает 128-битный результат умножения. Размер указателей на вашей машине в значительной степени не имеет значения.
Если вы действительно хотите максимально эффективную реализацию, которая была бы максимально переносимой, вы должны сделать размер слова выбираемым во время компиляции. Затем создайте сценарий автоконфигурации, который (попытается) создать код с различными размерами слов и протестирует результаты этих сборок на правильность и скорость.
#define WORD_(SIZE) std::uint ## SIZE ## _t
#define WORD(SIZE) WORD_(SIZE)
#define X2_(SIZE) X2_ ## SIZE
#define X2(SIZE) X2_(SIZE)
#define X2_8 16
#define X2_16 32
#define X2_32 64
#define X2_64 128
использование WORD(WORD_SIZE) а также WORD(X2(WORD_SIZE)) в вашем коде и скомпилировать с
-DWORD_SIZE=8 или же 16 или же 32 или же 64
Другие решения
Других решений пока нет …