Dwumian Newtona

0

Witam
Napisałem program liczący dwumian Newtona (wg opisu z Wikipedii), ale dla danych 66 37 wynik jest o 2 za mały. Co może być tego przyczyną?

#include<iostream>
using namespace std;
long double newton(int n, int k);
int i, n, k;
int main()
{
    cin >> i;
    for(int l=0; l<i; l++)
    {
            cin >> n;
            cin >> k;
            cout << (unsigned long long int)newton(n,k) << "\n";
    }
}
long double newton(int n, int k)
{
    long double wynik;
    wynik=1;
    for(int i1=1; i1<=k; i1++) wynik=wynik*((long double)n-(long double)i1+1)/(long double)i1;
    return wynik;
}
 

Z góry dzięki za odpowiedzi :)
Pozdrawiam

0

Po co używasz long double? Taka liczba to zazwyczaj "extended precision", która może bez błędu odwzorować liczby całkowite do 2<sup>{63} unsigned long long int to zazwyczaj maksymalnie 2</sup>{64}-1 czyli więcej.

Btw: Jakiego używasz kompilatora? Podejrzewam, że msvc bo w gcc wszystko jest ok. Problem leży właśnie w tym, co to jest long double.

0

Korzystam z gcc
Dla danych 67 33 wynik powinien być równy 14226520737620288370, obecny program daje wynik 14226520737620288368 (o 2 mniejszy od prawidłowego), a jeśli zmienie long double na unsigned long long int to dostaje wynik 8829174638479413 (a więc całkowicie zły). Nie wiem tylko czym jest spowodowany ten błąd. I czy tym spoosobem można to obliczyć (dla innych testów wyniki są poprawne). Korzystałem z funkcji w Pascalu na Wikipedii:

function WspNewtona( n, k : integer ) : integer;
var
    wynik : integer;
    i : integer;
begin
    wynik := 1;

    for i := 1 to k do
        wynik := wynik * (n - i + 1) div i;

    WspNewtona := wynik;
end;
 

A jeśli nie w ten sposób to jak można obliczyć symbol Newtona (rekurencja odpada ze względu na ograniczenia czasowe)?

0

Wynik dla long double jest całkowicie poprawny, tylko z dokładnością do błędu typu liczb. Jak chcesz dokładną liczbę całkowitą, to musisz sobie sam taki typ danych napisać, lub skorzystać z bibliotek, jak np. GMP.

1 użytkowników online, w tym zalogowanych: 0, gości: 1