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

Duże liczby i biblioteka GMP - problem z kompilacją(?)

Ostatnio zmodyfikowano 2016-06-20 21:07
Autor Wiadomość
Piastlis
» 2016-06-06 23:42:57
C++ jest z jednej strony bardzo zbliżone do asemblera (możliwość korzystania ze zmiennych o wielkości jednego lub kilku bajtów) jak i do korzystania z dość skomplikowanych obiektów.Jakichś czas temu miałem podobny problem.Nie chodziło o liczby pierwsze ale o zadanie na spoj:
http://pl.spoj.com/problems​/TPERML/


Dość infantylny algorytm ale operujący na zmiennej wielkości 100!. Poradziłem sobie w ten sposób że kalkulator operujący na tej zmiennej zaimplementowałem samodzielnie jako zmienną typu string.Kalkulator czyli + - / * mod dosłownie mieści się na 1 ekranie ,niezbędną wiedzę żeby taki kalkulator napisać masz z podstawówki.....
Jeżeli chcesz dość wydajnie obliczać liczby pierwsze zainteresuj się sitami.. np. na początek Eratostenesa...        
P-148943
oxygenium79
Temat założony przez niniejszego użytkownika
» 2016-06-07 08:05:41
Nie, w sita nie chcę włazić, jedyne czego mi potrzeba, to GMP.
W PHP udało mi się to zrobić bez problemu, a tutaj nie potrafię.
P-148946
Piastlis
» 2016-06-07 11:08:33
Pomysł który przedstawił ci kol. @mateczek to właśnie proste sito Eratostenesa.Uwzględnienie liczb podzielnych przez 2 i 3 redukuje ilość obliczeń do 1/3 ale np. jeżeli uwzględnisz 2,3 i 5 to zredukujesz do 1/4 (wystarczy sprawdzić 8 wartości w grupie 30):).

C/C++
int kroki[ 30 ] = { 1, 6, 5, 4, 3, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 2, 1, 4, 3, 2, 1, 6, 5, 4, 3, 2, 1, 2 };

for( unsigned long long k = 5; k <= max; k += kroki[ k % 30 ] ) {
    if( liczba % k == 0 ) {
        pierwsza = false;
        break; }
P-148950
oxygenium79
Temat założony przez niniejszego użytkownika
» 2016-06-07 12:57:16
Dzięki, ale nie. :-)
Chcę tylko zmienić zmienne na GMP, żeby przekroczyć granicę 18446744073709551597.
Reszta mnie nie interesuje, tyle mi wystarczy.
P-148951
Piastlis
» 2016-06-07 18:45:34
Ok... Rozumiem.Ale po co Ci dodatkowa biblioteka dla działań podstawowych..+-\*%...To potrafi c++ samo z siebie...Jak GMP nie daje sobie rady to "szkoda czasu i atłasu".
P-148952
mateczek
» 2016-06-07 18:49:51
biblioteka potrzebna do operacji na większych liczbach !!!! które nie mieszczą się na 64 bitach
P-148953
oxygenium79
Temat założony przez niniejszego użytkownika
» 2016-06-07 20:10:44
GMP jak najbardziej daje sobie radę, ja po prostu nie potrafiłem tego napisać, nie zrozumieliśmy się. :-)
Ale przysiadłem i napisałem sam, wygląda to tak i działa (choć nie tak szybko, jak poprzednia wersja bez GMP, ale za to mogą być duże liczby):
C/C++
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <gmp.h>
using namespace std;

int main()
{
    cout.precision( 20 ); // dokladnosc wyswietlania liczb - to chyba nie jest potrzebne
   
    mpz_t liczba;
    mpz_init_set_str( liczba, "50446744073709551651", 10 ); // tu ustawiamy nieparzysta liczbe, od ktorej chcemy zaczac szukanie
    mpz_t trojka;
    mpz_init_set_str( trojka, "3", 10 );
    mpz_t p3;
    mpz_init_set_str( p3, "0", 10 );
    mpz_t granica;
    mpz_init_set_str( granica, "0", 10 );
    mpz_t dzielnik;
    mpz_init_set_str( dzielnik, "6", 10 );
    mpz_t dzielnik1;
    mpz_init_set_str( dzielnik1, "0", 10 );
    mpz_t dzielnik2;
    mpz_init_set_str( dzielnik2, "0", 10 );
    mpz_t zmiana;
    mpz_init_set_str( zmiana, "1", 10 );
    mpz_t reszta1;
    mpz_init_set_str( reszta1, "0", 10 );
    mpz_t reszta2;
    mpz_init_set_str( reszta2, "0", 10 );
    mpz_t skok6;
    mpz_init_set_str( skok6, "6", 10 );
    mpz_t skok2;
    mpz_init_set_str( skok2, "2", 10 );
    mpz_t iloczyn;
    mpz_init_set_str( iloczyn, "0", 10 );
    mpz_t porownanie;
    mpz_init_set_str( porownanie, "0", 10 );
   
    int sprawdzenie = 0;
   
    while( sprawdzenie == 0 ) // sprawdzanie kolejnych liczb nieparzystych
    {
        gmp_printf( "%s: %Zd\n", "Liczba", liczba );
       
        sprawdzenie = 1; // zakladamy, ze liczba jest pierwsza
       
        mpz_mod( p3, liczba, trojka );
       
        if( mpz_cmp( p3, porownanie ) == 0 ) { sprawdzenie = 0; } // sprawdzamy podzielnosc przez 3
        else
        {
            mpz_set_str( dzielnik, "6", 10 );
            mpz_sqrt( granica, liczba );
           
            while( sprawdzenie == 1 && mpz_cmp( dzielnik, granica ) <= 0 ) // sprawdzanie podzielnosci danej liczby
            {
                mpz_add( dzielnik1, dzielnik, zmiana );
                mpz_sub( dzielnik2, dzielnik, zmiana );
               
                mpz_mod( reszta1, liczba, dzielnik1 );
                mpz_mod( reszta2, liczba, dzielnik2 );
                mpz_mul( iloczyn, reszta1, reszta2 );
               
                if( mpz_cmp( iloczyn, porownanie ) == 0 ) { sprawdzenie = 0; } else { mpz_add( dzielnik, dzielnik, skok6 ); }
            }
        }
        if( sprawdzenie == 1 ) // jesli trafimy na liczbe pierwsza, to ja wyswietlamy
        {
            cout << endl;
            cout << "\t";
            gmp_printf( "%s liczba jest pierwsza: %Zd\n", "Ta", liczba );
            cout << endl;
            cout << endl;
            cout << "\t" << "Rekord w C++ bez GMP: 18446744073709551557 w 19 s - wiekszej liczby sie nie da bez GMP(!).";
            cout << endl;
            cout << "\t" << "Rekord w C++ z GMP dla 18446744073709551557: 83 s - niestety, sporo wolniej.";
            cout << endl;
            cout << "\t" << "Rekord w C++ z GMP: dla 50446744073709551651 w 169 s.";
        }
        mpz_add( liczba, liczba, skok2 ); // przechodzimy do nastepnej liczby nieparzystej
    }
   
    cout << endl;
   
    return 0;
}
P-148956
oxygenium79
Temat założony przez niniejszego użytkownika
» 2016-06-09 10:13:30
Haha, tylko że w ferworze walki zrobiłem w tym całym programie kardynalny błąd. Łatwo go poprawić, ale kto nie widzi, niech poczeka aż wstawię poprawioną wersję...
P-148977
1 2 3 « 4 » 5 6
Poprzednia strona Strona 4 z 6 Następna strona