Целочисленный расчет биномиального коэффициента с использованием boost :: math :: binomial_coefficient, возвращающий значение в виде boost :: multiprecision :: cpp_int? Как?

Question

Целочисленный расчет биномиального коэффициента с использованием boost :: math :: binomial_coefficient, возвращающий значение в виде boost :: multiprecision :: cpp_int? Как?

Я хотел бы рассчитать биномиальный коэффициент как целое число до примерно numberLeaves=100, K=10, Я считаю, что это должно быть возможно хранить в 128-битном целом числе.

Поэтому я хотел бы использовать boost::multiprecision::cpp_int сохранить результат и использовать boost::math::binomial_coefficient<boost::multiprecision::cpp_int> рассчитать это:

// Invalid because the template argument must be a floating-point type!
boost::multiprecision::cpp_int number_branch_combinations =
boost::math::binomial_coefficient<boost::multiprecision::cpp_int>(numberLeaves, K);

К сожалению, хотя биномиальный коэффициент является целым числом, приведенный выше код недействителен, поскольку boost::math::binomial_coefficient требует, чтобы возвращаемое значение должен быть типом с плавающей запятой, утверждая, что:

…аргумент шаблона должен быть вещественным типом, таким как float или
double, а не целочисленный тип — это слишком легко переполнится!

Как уже отмечалось, в моем случае я ожидаю, что результат вычисления биномиального коэффициента будет соответствовать примерно 128 битам — и я хотел бы, чтобы он был целым числом.

Поэтому я рассмотрел прохождение boost::multiprecision::cpp_dec_float в качестве аргумента шаблона для boost::math::binomial_coefficient, а затем делать преобразование от возвращаемого значения с плавающей точкой (посредством округления) до ближайшего целого числа.

К сожалению, я не могу найти способ конвертировать из boost::multiprecision::cpp_dec_float к boost::multiprecision::cpp_int, Похоже, что преобразование с потерями строго запрещено посредством boost::multiprecision библиотека:

cpp_int             cppi(2);
cpp_dec_float_50    df(cppi);    // OK, int to float
df                  = static_cast<cpp_dec_float_50>(cppr);  // OK, explicit rational to float conversion
// However narrowing and/or implicit conversions always fail:
cppi                =   df;    // Compiler error, conversion not allowed

Сейчас я просто пишу свою собственную функцию для вычисления биномиального коэффициента и возврата значения в виде целого числа.

Мне трудно поверить, что буквально нет никакого способа использовать boost::math::binomial_coefficient рассчитать биномиальный коэффициент и вернуть его в виде boost::multiprecision::cpp_int,

Можно ли использовать boost::math::binomial_coefficient рассчитать биномиальный коэффициент и вернуть его в виде boost::multiprecision::cpp_int?

3

binomial-coefficients boost c++math

Решение

Другие решения

Вот что я использую, чтобы получить общее число n, выбрав k:

boost::multiprecision::cpp_int BinomialCoefficient(unsigned int n, unsigned int k) {
if (k == 0) { return 1; }
else { return (n * BinomialCoefficient(n - 1, k - 1)) / k; }
}

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

1

Источник

Accepted Answer

Мне трудно поверить, что буквально нет никакого способа использовать boost::math::binomial_coefficient рассчитать биномиальный коэффициент и вернуть его как a boost::multiprecision::cpp_int,

Как вы думаете, почему в это так трудно поверить?

Это был четкий выбор дизайна, который был задокументирован как таковой, и в то время это имело большой смысл.

Повышение Multiprecision было введено только в 1_53. я думаю binomial_coefficient легко на несколько лет старше этого (хотя я не проверял).

Таким образом, вместо того, чтобы выразить свое отвращение, вам, вероятно, следует поговорить с разработчиками в списках рассылки поддержки, чтобы предложить эту новую функцию. Поддерживающие библиотеки Boost обычно стремятся интегрироваться с (новыми) библиотеками.

Как вы поймете, вы можете обернуть функцию сейчас, делая преобразование. Это faaar от идеала, но это меньше работы, чем поставка патча для Boost Math самостоятельно 🙂

1