Мне нужно вычислить с помощью биномиальных коэффициентов выражения (x + y) ** n, причем n очень велико (порядка 500-1000). Первый алгоритм для вычисления биномиальных коэффициентов, который пришел мне на ум, был multiplicative formula. Так что я закодировал в моей программе, какОшибка округления биномиальных коэффициентов
long double binomial(int k, int m)
{
int i,j;
long double num=1, den=1;
j=m<(k-m)?m:(k-m);
for(i=1;i<=j;i++)
{
num*=(k+1-i);
den*=i;
}
return num/den;
}
Этот код очень быстро на одной основной нити, по сравнению, например, с recursive formula, хотя последний один меньше подвержен ошибкам округления, так как включает в себя только суммы, а не подразделения. Так что я хотел протестировать эти альгоны для больших ценностей и попытался оценить 500 выбрать 250 (заказ 10^160). Я обнаружил, что «относительная ошибка» меньше 10^(- 19), поэтому в основном они одного и того же числа, хотя они отличаются примерно от 10^141.
Так что мне интересно: есть ли способ оценить порядок ошибки вычисления? И есть ли какой-то быстрый способ вычислить биномиальные коэффициенты, более точную, чем мультипликативная формула? Поскольку я не знаю точности своего эго, я не знаю, где усечь серию побуждений, чтобы получить лучшие результаты.
Я искал Google таблицы для биномиальных коэффициентов, поэтому я мог копировать их, но лучший один я нашел остановки при п = 100 ...
Вам будет лучше с большой библиотекой чисел и целым умножением/делением. –
Возможный дубликат [Количество комбинаций (N выберите R) в C++] (http://stackoverflow.com/questions/9330915/number-of-combinations-n-choose-r-in-c) –
Я не думаю, что это дубликат, так как я знаю, что формула правильная, но расчеты округлены и поэтому появляются ошибки. –