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

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

Ostatnio zmodyfikowano 2016-06-20 21:07

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-05 11:36:11

Taki problem napotkałem teraz:

To jest dzielenie:
mpz_div (wynik, liczba, dzielnik);
Ale wynikiem będzie liczba całkowita.

W dokumentacji GMP nie znalazłem, jak zrobić odpowiednik:
liczba % i == 0 // dzieleniee modulo

EDIT:
Chyba znalazłem:
https://gmplib.org/manual/Integer-Division.html
To będzie pewnie któreś z tych, tylko nie do końca wiem, które.

P-148884

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-05 12:12:59

OK, doszedłem do czegoś takiego:

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <gmp.h>

int main()
{
int sprawdzenie = 0;

mpz_t liczba;
mpz_init_set_str( liczba, "25", 10 );
mpz_t granica;
mpz_init_set_str( granica, "0", 10 );
mpz_t dzielnik;
mpz_init_set_str( dzielnik, "2", 10 );
mpz_t reszta;
mpz_init_set_str( reszta, "0", 10 );

while( sprawdzenie == 0 ) {

gmp_printf( "%s is an liczba %Zd\n", "here", liczba );
std::cout << std::endl;
sprawdzenie = 1; // zakladamy, ze liczba jest pierwsza
mpz_sqrt( granica, liczba ); // wyliczamy maksymalny dzielnik do sprawdzenia

while( sprawdzenie == 1 && dzielnik <= granica ) //to pewnie trzeba bedzie zmienic
{
mpz_cdiv_r( reszta, liczba, dzielnik ); // sprawdzamy, czy z dzielenia zostala reszta

if( reszta == 0 ) { sprawdzenie = 0; } // jesli nie ma reszty, to liczba nie jest pierwsza
mpz_add( dzielnik, dzielnik, 1 ); // zamiast "dzielnik = dzielnik +1;", ale nie dziala
}

if( sprawdzenie == 1 ) {

std::cout << std::endl << "\t" << liczba << " jest liczba pierwsza.";
std::cout << std::endl;
std::cout << std::endl;
std::cout << "\t" << "rekord w C++: 18446744073709551557 w 128 sekund - wiecej sie nie da(!)";
}
liczba = liczba + 2; // przechodzimy do kolejnej nieparzystej (pewnie trzeba bedzie zmienic)
}
return 0;
}

Problemem jest teraz:
Jak zamienić "dzielnik = dzielnik +1;" na zgodne z GMP.
Nie będzie też pewnie działać "dzielnik<=granica".

P-148886

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-05 15:59:31

Wygładziłem mój poprzedni programik, za Waszą radą zmieniłem liczby float na całkowite. Zaleta jest dodatkowa taka, że znacznie szybciej działa(!).
Dla mnie wszystko jest tu nowością, bo po raz ostatni miałem styczność z programowaniem kilkanaście lat temu w BASIC na C64.

No cóż, teraz muszę znaleźć kogoś, kto pomoże mi to przerobić tak, żeby można było sięgnąć dalej, niż unsigned long long:

#include <cstdlib>
#include <iostream>
#include <math.h>
#include <gmp.h>

int main()
{
std::cout.precision( 20 ); // dokladnosc wyswietlania liczb

unsigned long long liczba = 18446744073709551557; // liczba startowa - rekordzistka z php: 20000000000000000009 w 3988 sekund
// 20000000000000000009
// granica dla unsigned long long 18446744073709551615
int sprawdzenie = 0;

while( sprawdzenie == 0 ) {

std::cout << "Liczba: " << liczba;
std::cout << std::endl;
sprawdzenie = 1; // zakladamy, ze liczba jest pierwsza
unsigned long long granica = sqrt( liczba );
unsigned long long dzielnik = 2;

while( sprawdzenie == 1 && dzielnik <= granica )
{
if( liczba % dzielnik == 0 ) { sprawdzenie = 0; }
dzielnik = dzielnik + 1;
} // std::cout << std::endl;

if( sprawdzenie == 1 )
{
std::cout << std::endl << "\t" << liczba << " jest liczba pierwsza.";
std::cout << std::endl;
std::cout << std::endl;
std::cout << "\t" << "rekord w C++: 18446744073709551557 w 38 sekund - wiecej sie nie da(!)";
}
liczba = liczba + 2;
}
std::cout << std::endl;

return 0;
}

P-148888

mateczek

» 2016-06-05 17:34:41

rekord w C++: 18446744073709551557 w 38 sekund - wiecej sie nie da(!)

1 zawsze się da !!!

#include <iostream>
#include <cmath>
using namespace std;
bool czyPierwsza( unsigned long long liczba ) {
if( liczba == 1 ) return false;

if( liczba == 2 || liczba == 3 ) return true;
//jak małe cię nie interesują
if( liczba % 2 == 0 ) return false;

if( liczba % 3 == 0 ) return false;

unsigned long long max = sqrt( liczba ); // nie musi być double
bool pierwsza = true;
for( unsigned long long k = 6; k <= max; k += 6 ) {
if( liczba %( k - 1 ) == 0 ) {
pierwsza = false;
break; }
if( liczba %( k + 1 ) == 0 ) {
pierwsza = false;
break; }
}
return pierwsza;
}
int main() {
unsigned long long liczba = 18446744073709551557;
bool pierwsza = czyPierwsza( liczba );
if( pierwsza ) cout << "TAK" << endl; else cout << "NIE" << endl;
}

P-148890

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-05 22:44:05

O, ciekawe...
To teraz muszę dopytać:

if( liczba % 2 == 0 ) return false;

if( liczba % 3 == 0 ) return false;

Tu sprawdzamy, czy nie jest przypadkiem podzielna przez 2 lub 3, zgadza się?

for( unsigned long long k = 6; k <= max; k += 6 ) {
if( liczba %( k - 1 ) == 0 ) {
pierwsza = false;
break; }
if( liczba %( k + 1 ) == 0 ) {
pierwsza = false;
break; }
}

Tego nie rozumiem: dlaczego startujemy od 6 i skaczemy co 6? I czemu potem sprawdzamy tylko k-1 i k+1?

unsigned long long liczba = 18446744073709551557;

Jeśli dobrze rozumiem - program nadal nie będzie działał dla liczb większych od tej?
("unsigned long long" dalej nie sięga)

No i jeszcze fajnie by było, jakby działał w taki sam sposób, jak mój pierwowzór, czyli że sprawdza kolejno liczby, aż trafi na liczbę pierwszą, po czym ją wyświetla, ale to już sam pewnie bym umiał przerobić.

P-148897

mateczek

» 2016-06-06 06:21:02

taka optymalizacja.
Jak poszukasz po Google do czego ludzie doszli i jakie algorytmy wymyślili to pewnie i coś szybszego znajdziesz.
Zawsze można (jak wyszykujesz od początku) tablicować znalezione liczby pierwsze i testować kolejne tylko przy pomocy wcześniej znalezionych

P-148901

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-06 07:18:57

Rzeczywiście, znalazłem. :-D
Fajne to jest.

Ale co z tymi dużymi liczbami zatem?
W php bez problemu udało mi się użyć GMP, tam to jest proste jak konstrukcja gwoździa.
A tutaj droga przez mękę...

P-148902

oxygenium79

Temat założony przez niniejszego użytkownika

» 2016-06-06 23:15:26

No tak, kod działa o połowę szybciej. :-)
Tylko nadal problemem jest to, że nie sięga dalej, niż unsigned long long...

#include <cstdlib>
#include <iostream>
#include <math.h>
// #include <gmp.h>

int main()
{
std::cout.precision( 20 ); // dokladnosc wyswietlania liczb

unsigned long long liczba = 18446744073709551597; // liczba startowa - rekordzistka z php: 20000000000000000009 w 3988 sekund
// 20000000000000000009
// granica dla unsigned long long 18446744073709551615
int sprawdzenie = 0;

while( sprawdzenie == 0 ) {

std::cout << "Liczba: " << liczba;
std::cout << std::endl;
sprawdzenie = 1; // zakladamy, ze liczba jest pierwsza
unsigned long long granica = sqrt( liczba );
unsigned long long dzielnik = 6;

while( sprawdzenie == 1 && dzielnik <= granica )
{
unsigned long long wynik1 = liczba %( dzielnik + 1 );
unsigned long long wynik2 = liczba %( dzielnik - 1 );
if( wynik1 * wynik2 == 0 ) { sprawdzenie = 0; } else { dzielnik = dzielnik + 6; }
}

if( sprawdzenie == 1 )
{
std::cout << std::endl << "\t" << liczba << " jest liczba pierwsza.";
std::cout << std::endl;
std::cout << std::endl;
std::cout << "\t" << "rekord w C++: 18446744073709551597 w 15 sekund - wiekszej liczby sie nie da bez GMP(!)";
}
liczba = liczba + 2;
}
std::cout << std::endl;

return 0;
}

P-148942

1 2 « 3 » 4 5 6

Poprzednia strona

Strona 3 z 6

Następna strona

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