Есть ли математическая «оптимальная» база, которая бы ускорила факторный расчет?

Question

Существует ли какая-то математическая "оптимальная" база, которая бы ускорила факторные вычисления?

Справочная информация: Ради интереса я внедряю собственную библиотеку bignum.(-: Это моя первая ошибка? :-).Я экспериментирую с различными базами, используемыми во внутреннем представлении и регрессионном тестировании, распечатывая точные значения (в десятичном виде) для n факториала (n!).

То, как моя библиотека bignum представляет целые числа и выполняет умножение,время пропорционально общему количеству битов «1» во внутреннем представлении n !.Использование оснований 2, 4, 8, 16, 2 ^ 8, 2 ^ 30 и т. Д. В моем внутреннем представлении дает мне одинаковое общее количество бит «1» для любого конкретного числа.

Если я не допустил какой-либо ошибки, любой данный факториал (n!), Представленный в базе 18, имеет меньше битов «1», чем то же значение, представленное в базе 10 или в базе 16 или в базе 19. И так (в принципе), используя базу18 заставит мою библиотеку bignum работать быстрее, чем использование базы 10 или некоторой двоичной базы 2 ^ w или базы 19. Я думаю, это как-то связано с тем фактом, что n!он либо короче, либо имеет больше «конечных нулей», либо и того и другого, если он распечатан в базе 18, а не в базе 10 или в базе 16 или в базе 19. Есть ли какая-то другая база, которая будет работать даже лучше, чем база 18?Другими словами, есть ли база, которая представляет n!с еще меньшим количеством битов «1», чем у основания 18?

Это не дублирует вопрос «Что представляет собой удобная база для алгоритма тестирования bignum и алгоритма проверки простоты?»потому что я подозреваю, что «оптимальная база для работы с целыми числами, которые, как известно, являются большими факториалами, с большим количеством факторов 2 и 3», отличается от «оптимальной базы для работы с целыми числами, которые не имеют каких-либо небольших факторов и, возможно,премьер».(-: ускорение факторных вычислений - возможно, за счет других видов вычислений - моя вторая ошибка?: -)

edit: Например:

(decimal) 16! ==
(decimal    ) == 20,922,789,888,000 // uses decimal 14 "1" bits
(dozenal    ) ==  2,41A,B88,000,000 // uses decimal 10 "1" bits
(hexadecimal) ==    130,777,758,000 // uses decimal 18 "1" bits
(octadecimal) ==     5F,8B5,024,000 // uses decimal 14 "1" bits

(IЯ более-менее сохраняю цифры справа, без запятых, плюс некоторые издержки метаданных).(Хотя можно подумать, что «при увеличении базы вы будете использовать меньше« 1 »битов для представления данного числа», или «При увеличении базы вы будете использовать меньше ненулевых цифр для представления данного числа», вышепример показывает, что это не всегда так.)

Я храню каждую цифру в виде небольшого целого числа ("int" или "long int" или "byte"). Есть ли другой разумный способ хранения цифр?Я почти уверен, что мой компьютер хранит эти целые числа в двоичном виде - каждая цифра «1», «2», «4», «8» и «G» использует один бит «1»; каждый «3», «5Цифры "," 6 "," 9 "и" A "используют два бита" 1 "; каждая цифра" 7 "и" B "использует три бита" 1 "; каждая цифра" F "использует четыре бита" 1 ",и т. д.

И десятичное, и восьмеричное представление этого значения (16!) требуют 14 "1" битов. Поэтому я допустил ошибку в своих предыдущих вычислениях: для каждого n, представляющего n! в восьмизначном не всегда имеет меньше "1" битов, чем представление того же значения в десятичном виде. Но вопрос все еще остается: есть ли какой-то другой "оптимум"«База, которая требует наименьшего числа 1 бит для хранения больших факториалов?

Кто-то спрашивает:« Как вы храните эти числа? »Ну, это точно мой вопрос - каков наилучший способ хранения чиселформа n!?Я мог бы внутренне использовать цифры в базе 10, или некоторую базу со степенью двойки, или базу 18, или какую-то другую базу.Какой из них лучше?Я мог бы хранить эти целые числа внутри себя как одномерный массив цифр с длиной, необходимой для хранения всех цифр.Есть ли разумный способ распечатать 100!в десятичном формате без такого массива?

Answer 1

Если вы просто пытаетесь оптимизировать время выполнения для расчета факториала, а изменение базы - единственный изменяемый параметр, то оптимальная база, скорее всего, будет содержать небольшие факторы.60 может быть разумным выбором.Если вы хотите поэкспериментировать, я бы попробовал различные основы вида (2 ^ a) (3 ^ b) (5 ^ c)

Повышение скорости умножения, вероятно, является лучшим способом повышения производительности.Какой алгоритм вы используете для умножения?(учебник, Карацуба, Toom-Cook, FFT, ...)

Есть и другие факторы, которые следует учитывать.Если вы будете часто преобразовывать числа в десятичные, то основание со степенью 10 сделает преобразование максимально быстрым.

Много (*) лет назад я написал число с плавающей запятой 6библиотека, специально предназначенная для решения проблемы с повторным умножением / делением на 2 и / или 3. Но если вы не пытаетесь решить конкретную проблему, я думаю, что вам лучше справится с оптимизацией ваших алгоритмов в целом, чем с простой попыткой оптимизации факториала

casevh

(*) Первоначально я говорил «Несколько лет назад», пока не вспомнил, что программа работала в течение многих дней на частоте 1228 Гц 80286.

Answer 2

Хотя с чисто математической точки зрения оптимальное основание составляет e (и после округления до ближайшего целого числа - 3), с практической точки зрения для библиотеки bignum на компьютере, выберите размер машинного слова в качестве основы для вашей числовой системы (2 ^ 32 или 2 ^ 64). Да, он огромен, но более высокий уровень абстракции в вашей системе bignum - это дроссельная точка, базовые вычисления для машинных слов - быстрая часть, поэтому делегируйте столько же вычислений низкоуровневым инструкциям ЦП, сохраняя при этом свою работу минимальной.

И нет, это не ошибка. Это очень хорошее учебное упражнение.

Answer 3

Если под «1» битами вы подразумеваете цифры, то я предлагаю использовать 256 или 65536 оснований. Другими словами, сделайте каждый байт / слово «цифрой» для вашей математики. Компьютер обрабатывает эти цифры регулярно и оптимизирован для этого. Ваши факториалы будут быстрыми, как и другие операции.

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

Answer 4

Я не буду притворяться, что знаю какую-либо математику, поэтому не принимайте мой ответ как священный «оптимум», который вы, вероятно, ищете. Если бы мне нужно было сделать факториал как можно быстрее, я бы либо попробовал какое-то приближение (что-то вроде приближения Стирлинга), либо уменьшил бы число умножений, потому что умножение - дорогостоящая операция. Если вы представляете число в k-base, вы можете смоделировать умножение на k с помощью сдвига. Если вы выберете 2-основание, половина всех умножений будет сдвигаться. Другие умножения - сдвиги и одноразрядное переключение. Если вы стремитесь минимизировать число «1» в своем представлении числа, это зависит от того, какие числа вы представляете. По мере увеличения базы вы будете использовать меньше «1» для представления заданного числа, но вам нужно будет иметь больше битов для каждого порядка, что означает больше потенциальных «1». Надеюсь, это поможет хоть немного, если нет, просто спросите, я постараюсь ответить.