Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Policzenie wszystkich kombinacji liczby danej wzorem

Ostatnio zmodyfikowano 2016-04-24 14:46
Autor Wiadomość
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-04-21 08:46:38
Dodałem do programu zmienne GMP. Z tego co sprawdziłem program liczy poprawnie dla y>3. Dla y=1 zawiesza się i tu podejrzewam, że być może próbuje utworzyć wektor y-1 elementowy lub napotyka podobny problem. Niestety program nie liczy poprawnie także dla niektórych y=2. I tu już nie wiem dlaczego tak jest. Przykładowo dla p=181, y=2, x=13 wyniki są poprawne. Ale już dla p=3109888511975, y=2 i x=81 wyniki są zupełnie błędne (za małe) i nie mam pojęcia skąd program je bierze. To tym razem nie powinna być wina zmiennych, skoro dla znacznie większych liczb "w" program liczy poprawnie. Czy to wina zbyt dużego p (które jest ucinane)? Zmienna long long chyba mieści takie liczy bez problemu?

C/C++
#include <iostream>
#include <iomanip>
using namespace std;
//#include <conio>
#include <string>
#include <vector>
#include <cmath>
#include <limits>
#include <stdio.h>
#include <gmp.h>
#include <gmpxx.h>

//====================================================================================================================

void computeW( mpf_class & w, int pX, int pY, int pP, const vector < vector < int >>& pXn, const vector < int >& pXIndxs );
bool isNaturalNum( mpf_class w );

//====================================================================================================================


int main()
{
   
    mpf_set_default_prec( 1000 );
   
   
    long long p;
    int y;
    int x;
   
    cout << "Podaj p: ";
    cin >> p;
    cout << "Podaj y: ";
    cin >> y;
    cout << "Podaj x: ";
    cin >> x;
   
    vector < vector < int > > xn( y - 1, vector < int >( x + 1 ) );
   
    for( auto & vec: xn )
    {
        for( int i = 0; i <= x; ++i )
        {
            vec[ i ] = i;
        }
    }
   
    vector < int > xIndxs( xn.size(), 0 );
    mpf_class w;
    // mpf_init(w);
   
    bool exit = false;
    double counter = 0;
    unsigned long long howManyFound = 0;
   
    cout << "Start " << endl;
   
    while( !exit )
    {
        counter++;
       
        computeW( w, x, y, p, xn, xIndxs );
        // if( isNaturalNum( w ) )
        if( w = w )
        {
            ++howManyFound;
           
            cout << "w = " << fixed << w << "; ";
            for( int i = 0; i < xn.size(); ++i )
            {
                cout << "x" << i + 1 << "=" << xn[ i ][ xIndxs[ i ] ] <<( i == xn.size() - 1 ? ""
                    : ", " );
            }
            cout << endl;
        }
       
        ++xIndxs[ 0 ];
       
        for( int j = xIndxs.size() - 1; j > 0; --j )
        {
            if( xIndxs[ j ] == x )
            {
                if( j == xIndxs.size() - 1 ) { exit = true; break; }
               
                ++xIndxs[ j + 1 ];
               
                for( int pom = j; pom >= 0; --pom )
                {
                    xIndxs[ pom ] = xIndxs[ j + 1 ];
                }
               
                break;
            }
        }
       
        if( xIndxs[ 0 ] == x + 1 )
        {
            if( xIndxs.size() >= 2 )
            {
                ++xIndxs[ 1 ];
                xIndxs[ 0 ] = xIndxs[ 1 ];
            }
            else
            {
                exit = true;
            }
        }
    }
   
    cout << "Koniec" << endl;
    cout << "wszystkich iteracji: " << fixed << setprecision( 0 ) << counter << endl;
    cout << "Policzonych liczb w: " << howManyFound << endl;
    if( pow( 2, y + x ) - pow( p, y ) < 0 )
    {
        cout << "Ujemne" << endl;
    }
   
    getchar();
    return 0;
}
//====================================================================================================================
void computeW( mpf_class & w, int pX, int pY, int pP, const vector < vector < int > >& pXn, const vector < int >& pXIndxs )
{
   
    mpz_class pow1, pow2, pow3;
    mpf_class tmpf;
   
    w = 0;
   
    for( int i = 0; i < pXn.size(); ++i )
    {
        mpz_ui_pow_ui( pow1.get_mpz_t(), 2, pXn[ i ][ pXIndxs[ i ] ] );
        mpz_ui_pow_ui( pow2.get_mpz_t(), pP, i );
        mpz_ui_pow_ui( pow3.get_mpz_t(), 2, i );
       
       
        tmpf = pow1 * pow2;
        tmpf /= pow3;
        w += tmpf;
    }
   
    mpz_ui_pow_ui( pow1.get_mpz_t(), pP, pY - 1 );
    mpz_ui_pow_ui( pow2.get_mpz_t(), 2, pY - 1 );
    tmpf = pow1;
    w += tmpf / pow2;
   
    mpz_ui_pow_ui( pow1.get_mpz_t(), 2, pY - 1 );
    w *= pow1;
   
    mpz_ui_pow_ui( pow1.get_mpz_t(), 2, pX + pY );
    mpz_ui_pow_ui( pow2.get_mpz_t(), pP, pY );
   
    //w /= abs(pow1 - pow2);
    w /= abs( 1 );
}

//*****************************************************************************
bool isNaturalNum( mpf_class w )
{
    return mpf_integer_p( w.get_mpf_t() );
}
//*****************************************************************************
P-147484
michal11
» 2016-04-21 12:14:27
P-147487
osobliwy_nick
Temat założony przez niniejszego użytkownika
» 2016-04-21 22:28:57
Czytałem cytowany opis wychodzi na to, że 9223372036854775807 > 3109888511975. Mimo to program nie liczy prawidłowo. I problem na pewno jest ze zmienną p, nie wiem tylko, czy wartości są ucinane bezpośrednio, czy coś się dzieje po "drodze".

Ustawiłbym sobie p też jako zmienną GMP (i problem byłby z głowy), ale nie potrafię znaleźć miejsc w których jest wywoływana, więc nie wiem, które fragmenty zmienić.
P-147525
darko202
» 2016-04-22 09:55:53
Wydaje mi się, że Twój problem leży w realizowanym algorytmie, używany typ liczby tylko zaciemnił Ci problem
tzn. jakiego byś typu nie użył - reprezentacja liczby niewymiernej zawsze jakoś obcina - niewymierność
co rzutuje na obliczenia ?, a tym samym na wyniki

podstawowym problemem są liczby niewymierne, których musisz używać
podam najprostszy trywialny przykład  : 2*(1/3+1/6)

2 - wymierna
1/3 - niewymierna
1/6 - niewymierna
ale złożenie tego daje nam liczbę wymierną 
przy realizacji tego w programie możemy osiągniemy wymierność wyniku    
ale można się spodziewać, że niekoniecznie wynikiem będzie zawsze 1 
tzn. coś tam na dalekim miejscu miedzy (1/3 + 1/6) różni się od 1/2
(nie sprawdzałem ale oczywiście chodzi o pokazaniu problemu, a nie ten konkretny przykład)

stąd dla mnie jest oczywistym jest, że np.

C/C++
for( int i = 0; i < pXn.size(); ++i )
{
    mpz_ui_pow_ui( pow1.get_mpz_t(), 2, pXn[ i ][ pXIndxs[ i ] ] );
    mpz_ui_pow_ui( pow2.get_mpz_t(), pP, i );
    mpz_ui_pow_ui( pow3.get_mpz_t(), 2, i );
   
    tmpf = pow1 * pow2;
    tmpf /= pow3;
    w += tmpf;
}
generuje w każdej operacji błędy (niewymierności).
które mogą rzutować na otrzymywane wyniki


Przyznam się, że nie chce mi się rozgryzać Twojego algorytmu, dlatego być może jest to inne podobne miejsce (albo i tam masz problem)
Myślę, że znasz Ten algorytm na pamięć i znajdziesz to szybko sam.

pytanie czy da się to naprawić  :-)


Osobiście napisałbym inny algorytm do rozwiązania tego problemu "sprawdzić liczbę"
 
w = (2^x1 + 2^x2 * p/2 + 2^x3 * p^2/4 + 2^x4 * p^3/8 + ... + p^(y-1)/2^(y-1))
     * 2^(y-1)
    /(2^(x+y)-p^y)

podzieliłem na 3 kawałki bo każdy z nich jest wymierny (nawet całkowity)

istotne na błędy niewymierność są  / (dzielenia)  i  * (mnożenia)

- dzielenie na pewno bardzo istotne
- mnożenie w pewnych przypadkach chyba też ( ? ale nie zawsze)
- pamiętamy, że potęgowanie to też mnożenie


czy możemy zastąpić je operacją, która usunie ten problem ?
mam przekonanie, że tak "+" dodawanie i "-" odejmowanie

liczba wymierna + liczba wymierna -> liczba wymierna
liczba wymierna - liczba wymierna -> liczba wymierna

teraz już tylko rozwiązać problem "niezmienności" liczby wymiernej
tzn. nie przekroczenia zakresu

nie używałem "zmiennych GMP", ale to może wystarczy - nie jest to jednak podstawowy problem tego algorytmu.

Z powyżej opisanego powodu zmieniłbym  algorytm na używający powyżej opisanych zasad "-" zamiast "/"
"+" zamiast "*" i potęgowania - jeśli "-" nie wystarczy
P-147537
davis.radeon
» 2016-04-24 14:46:35
P-147606
1 2 3 4 « 5 »
Poprzednia strona Strona 5 z 5