» Forum » Programowanie » [C, C++] Szukam pomocy

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

Ostatnio zmodyfikowano 2016-06-20 21:07

Autor Wiadomość

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-09 19:16:47

OK, teraz chyba jest dobrze. "Wystarczy" dodać ewentualne usprawnienia...

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <gmp.h>
using namespace std;

int main()
{
mpz_t liczba;
mpz_init_set_str( liczba, "19446744073709551557", 10 );
// Tu ustawiamy nieparzysta liczbe,
// od ktorej chcemy zaczac szukanie.
// Oczywiscie liczba wieksza od 1.
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, "4", 10 );
mpz_t reszta;
mpz_init_set_str( reszta, "0", 10 );
mpz_t skok1;
mpz_init_set_str( skok1, "1", 10 );
mpz_t skok2;
mpz_init_set_str( skok2, "2", 10 );
mpz_t zero;
mpz_init_set_str( zero, "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, zero ) == 0 & mpz_cmp( liczba, trojka ) != 0 ) { sprawdzenie = 0; }
// sprawdzamy podzielnosc przez 3
// (bedzie mozna wyeliminowac, jesli bedziemy sprawdzac tylko liczby 6k+/-1)
else
{
mpz_set_str( dzielnik, "4", 10 );
mpz_sqrt( granica, liczba );

while( sprawdzenie == 1 && mpz_cmp( dzielnik, granica ) <= 0 ) // sprawdzanie podzielnosci danej liczby
{
mpz_mod( reszta, liczba, dzielnik );
if( mpz_cmp( reszta, zero ) == 0 ) { sprawdzenie = 0; }
else { mpz_add( dzielnik, dzielnik, skok1 ); }
}
}
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-148987

Piastlis

» 2016-06-10 01:07:22

Wersja bez gmp jest i szybsza i bardziej elegancka:

#include <iostream>
using namespace std;

long long pierwsza_badana[ 2 ] = { 504467440737095516, 51 };

long long reszta( long long m1[], long long m2 )
{
long long pomoc =( m1[ 0 ] % m2 ) * 100;
return( pomoc + m1[ 1 ] ) % m2;
}

int main()
{
cout << " Badana liczba : " << pierwsza_badana[ 0 ] << pierwsza_badana[ 1 ] << " : ";
if( reszta( pierwsza_badana, 2 ) == 0 )
{
cout << "Nie";
return 0;
}
if( reszta( pierwsza_badana, 3 ) == 0 )
{
cout << "Nie";
return 0;
}

for( long long n = 6; n <= 7102587139; n = n + 6 )
{
if( reszta( pierwsza_badana, n - 1 ) == 0 )
{
cout << "Nie";
return 0;
}
if( reszta( pierwsza_badana, n + 1 ) == 0 )
{
cout << "Nie ";
return 0;
}
}

cout << "Tak";
return 0;
}

P-148998

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-17 11:41:49

Ale wersja bez GMP nie policzy niczego powyżej 18446744073709551557, więc jest bezużyteczna.

P-149210

Piastlis

» 2016-06-17 13:42:48

Mylisz się.Akurat ta policzy do 922337203685477580799 chociaż po poprawieniu mogłaby do 2^96 = 79228162514264337593543950336 ale jest to bez sensu bo obliczenia trwałyby kilkaset dni...

P-149212

Elaine

» 2016-06-18 19:41:38

Bo algorytm jest kiepski. Mój całkowicie niezoptymalizowany skrypt w Pythonie prawie (na tyle, że jeśli to nie jest liczba pierwsza, to będę sławny i bogaty) udowodnił pierwszość następującej liczby w półtorej minuty; test krzywymi eliptycznymi (nie mój, też w Pythonie) tą pierwszość potwierdził w kilka sekund:
(2^4095.2316… ≈) 613134054080134739556020601126614205010047765533187993525207718423965364191222742495307131246870590729569453883869011511448326780529986032327939153478641001181355496179377091177506439931410114604327357682193701469499932121927228402169291177411045773297995124623852857638158796188690578495954209299462750533794357039558763190506758120747150586650641199538354857920330364891509147330600232600683874052399496719541473090020485963002751762078777772909665137573816468065108188152158940512446161184546079708510348496218461880378775372964113038267747032852936572740662661377038373247732302865962681112138883283901216241967195993358843923527369248298810799556652382659935311411249489344197955564739863351885786066652812028175769079396258340554188799477808537047979172237059792418813963423593890726986294046087781107213325857174982150065302089212947419179391566059263113698232075866042554863427340774653130058975026456698921780494674325754170307135749376024028421689038654955805603039686109247529094495900038893643971618585462631884355710888307464019174783909309485131251156336573648493754149568172078970835892473620997956653514628998967314233238371690860605689657783636866356052059417643044044069621800531658903357273445484170181669120679517

To oczywiście stanowi niezaprzeczalny dowód, że Python jest językiem szybszym niż C++. :P

P-149251

Piastlis

» 2016-06-18 21:03:08

No fajnie...Ale ja próbuję wytłumaczyć koledze @oxygenium79 jak ma operować na liczbach większych niż long long..2^X gdzie X jest w granicach long long nic nie wnosi do tematu....

P-149253

Elaine

» 2016-06-18 21:16:03

W chyba każdej praktycznej implementacji C++ long long ma 64 bity. Logarytm binarny tej liczby to, po zaokrągleniu w górę, 4096. To ponad tysiąc dwieście rzędów wielkości więcej, niż typowa wartość std::numeric_limits<long long>::max().

Jeszcze raz, ta liczba:
613134054080134739556020601126614205010047765533187993525207718423965364191222742495307131246870590729569453883869011511448326780529986032327939153478641001181355496179377091177506439931410114604327357682193701469499932121927228402169291177411045773297995124623852857638158796188690578495954209299462750533794357039558763190506758120747150586650641199538354857920330364891509147330600232600683874052399496719541473090020485963002751762078777772909665137573816468065108188152158940512446161184546079708510348496218461880378775372964113038267747032852936572740662661377038373247732302865962681112138883283901216241967195993358843923527369248298810799556652382659935311411249489344197955564739863351885786066652812028175769079396258340554188799477808537047979172237059792418813963423593890726986294046087781107213325857174982150065302089212947419179391566059263113698232075866042554863427340774653130058975026456698921780494674325754170307135749376024028421689038654955805603039686109247529094495900038893643971618585462631884355710888307464019174783909309485131251156336573648493754149568172078970835892473620997956653514628998967314233238371690860605689657783636866356052059417643044044069621800531658903357273445484170181669120679517

Dla porównania, 2^64:
18446744073709551616

Oraz 2^128:
340282366920938463463374607431768211456

Ale ja próbuję wytłumaczyć koledze @oxygenium79 jak ma operować na liczbach większych niż long long

Kolega to wie, przecież używa GMP.

Swoją drogą, GMP prawdopodobnie będzie wyraźnie szybsze niż samodzielnie pisane bignumy już dla liczb w okolicach 3-4 słów maszynowych, i przewaga będzie tylko rosła wraz ze wzrostem rozmiaru liczb. Szybkie bignumy to raison d'être GMP, dlatego ta biblioteka implementuje wiele podstawowych operacji w asemblerze oraz potrafi dobrać odpowiedni algorytm dla operacji na podstawie rozmiaru liczb (np. mnożenie pisemne dla liczb w okolicach 2^500, mnożenie Schönhage-Strassena dla 2^500000). Czasami problemem są nadmierne alokacje, ale zawsze można przejść z mpz na mpn i alokacjami zająć się samemu.

P-149254

Piastlis

» 2016-06-19 02:32:38

Czytanie ze zrozumieniem ma przyszłość .....Używasz algorytmu operuje nie na liczbach 2^64 czy 2^128 tylko na 2^9223372036854775807.....Operuje nie na liczbie tylko na wykładniku.Stąd te "sensacyjne" wyniki czasowe .A same obliczenia lepiej i szybciej zaimplementować samodzielnie.To tak jak z sortowaniem.Istnieje wiele rodzajów i w każdym przypadku należy dobrać najlepszy.Nie istnieje "jedynie słuszna" biblioteka.

P-149259

1 2 3 4 « 5 » 6

Poprzednia strona

Strona 5 z 6

Następna strona

» Forum » Programowanie » [C, C++] Szukam pomocy