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ść
Elaine
» 2016-06-19 16:55:25
Używasz algorytmu operuje nie na liczbach 2^64 czy 2^128 tylko na 2^9223372036854775807.....Operuje nie na liczbie tylko na wykładniku.
To byłoby dość skomplikowane z matematycznego punktu widzenia, bo tej liczby nie się przedstawić jako 2^x, gdzie x jest algebraiczne (a więc tym bardziej wymierne czy całkowite), a komputery mają powszechnie znane problemy z działaniami na liczbach przestępnych.

Nie, te algorytmy operują na samej liczbie. Po prostu używają bardziej zaawansowanych struktur matematycznych.
P-149266
oxygenium79
Temat założony przez niniejszego użytkownika
» 2016-06-19 17:29:15
"Mylisz się.Akurat ta policzy do 922337203685477580799 chociaż po poprawieniu mogłaby do 2^96 = 79228162514264337593543950336"

Fajnie, ale powyżej 79228162514264337593543950336 już nie policzy, więc... tak jak pisałem, dla mnie jest bezużyteczna.
P-149271
Piastlis
» 2016-06-19 18:41:46
Ręce opadają...Tak standardowo można podzielić 64bit na 32bit ...dostajesz 32bit wyniku i 32 bit reszty.Takie działanie zajmuje cpu około 20-40 taktów(zależy od procka).Sposób który zaproponowałem dla liczb licznik 2^96 : mianownik 2^48 "kosztuje" tylko 3* (dwa dzielenia lub reszta ,jedno mnożenie i dodawanie) czyli 60-120 taktów. Ciekawe  ile "kosztuje" podzielenie takich samych liczb w gmp...
P-149273
Elaine
» 2016-06-19 19:59:04
<< deleted >>
P-149274
oxygenium79
Temat założony przez niniejszego użytkownika
» 2016-06-20 12:56:22
"Ciekawe  ile "kosztuje" podzielenie takich samych liczb w gmp... "

Koszty nie grają roli, warunkiem jest brak jakiegokolwiek ograniczenia.
P-149292
darko202
» 2016-06-20 13:27:47
1.
jeśli nie chcesz ograniczeń to jak to już ktoś wcześniej napisał
stwórz własny typ liczby i zaimplementuj do tego arytmetykę
nie jest tego dużo co widać na :
http://main.edu.pl/pl​/user.phtml?op=lesson&n=32
masz już tam gotowe algorytmy

2.
kiedyś miałem zadanie napisać program liczący duże silnie i oparłem go na własnym typie danych
vector(int) + zrealizowałem na nim potrzebne mi * (mnożenie) oparte na sposobie pisemnym 
zajęło to w sumie 1-2 godziny
sprawdziłem że liczył np. 1 000 000! bez problemu

tak bym sam zrobił.
będzie to szybsze - zwłaszcza, ze masz z tym już tyle czasu problem

3.
ewentualnie lepiej szukać - na pewno ktoś już to realizował

przeglądając od razu wpadłem na opis biblioteki BIGNUM
http://www.ttmath.org/samples

przykład mnożenia wygląda ciekawie, oparte chyba o znaki i bitowo(2)  
C/C++
#include <ttmath/ttmath.h>
#include <iostream>

int main()
{
    ttmath::UInt < 2 > a, b, c;
   
    a = "1234";
    b = 3456;
    c = a * b;
   
    std::cout << c << std::endl;
}

jest dostęp do źródeł (download)
można obejrzeć i rozwinąć jakby nadal było za mało

Powodzenia
P-149294
oxygenium79
Temat założony przez niniejszego użytkownika
» 2016-06-20 18:48:51
OK, dzięki za porady. Tylko zaznaczam, że C++ to ja się "uczę" od miesiąca, więc większość tego o czym piszecie to jest dla mnie czarna magia. :-)
Na razie udało mi się wypieścić coś takiego - i generalnie działa, choć strasznie wolno. Zwłaszcza całość znacznie opóźnia zastosowany przeze mnie licznik (około dwukrotnie dłużej program pracuje z tym licznikiem0). Nie udało mi się też zrobić tak, żeby można było wprowadzić liczbę startową po uruchomieniu programu, tylko trzeba ją wcześniej podać w kodzie i skompilować:
C/C++
#include <time.h>
#include <cstdlib>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <gmp.h>
using namespace std;

int main()
{
    // wyswietlenie czasu rozpoczecia
    time_t czas;
    struct tm * ptr;
    time( & czas );
    ptr = localtime( & czas );
    char * data = asctime( ptr );
    cout << endl;
    cout << "\t";
    cout << "Start: " << data;
   
    // zmienne do obliczenia czasu pojedynczej liczby
    time_t start, koniec;
    double roznica;
   
    mpz_t liczba;
    mpz_init_set_str( liczba, "500000000000000000000117", 10 );
    // Tu wstawiamy liczbe naturalna,
    // od ktorej chcemy zaczac szukanie.
   
    // Sprawiamy, ze liczba bedzie spelniala warunek 6k+1.
    mpz_t wynik6;
    mpz_init( wynik6 );
    mpz_t skok1;
    mpz_init_set_str( skok1, "1", 10 );
    mpz_t szostka;
    mpz_init_set_str( szostka, "6", 10 );
    mpz_cdiv_q( wynik6, liczba, szostka );
    mpz_mul( liczba, wynik6, szostka );
    mpz_add( liczba, liczba, skok1 );
   
    // Zmienne potrzebne do sprawdzenia podzielnosci
    mpz_t granica;
    mpz_init( granica );
    mpz_t dzielnik;
    mpz_init( dzielnik );
    mpz_t reszta;
    mpz_init( reszta );
    mpz_t zero;
    mpz_init_set_str( zero, "0", 10 );
   
    // Zmienne potrzebne do wyswietlania licznika.
    mpz_t podzielnik;
    mpz_init( podzielnik );
    mpz_t podzielnik2;
    mpz_init( podzielnik2 );
    mpz_t podzielnik3;
    mpz_init( podzielnik3 );
    mpz_t podzielnik4;
    mpz_init( podzielnik4 );
    mpz_t podzielnik5;
    mpz_init( podzielnik5 );
    mpz_t podzielnik6;
    mpz_init( podzielnik6 );
    mpz_t podzielnik7;
    mpz_init( podzielnik7 );
    mpz_t podzielnik8;
    mpz_init( podzielnik8 );
    mpz_t podzielnik9;
    mpz_init( podzielnik9 );
    mpz_t dwojka;
    mpz_init_set_str( dwojka, "2", 10 );
    mpz_t trojka;
    mpz_init_set_str( trojka, "3", 10 );
    mpz_t czworka;
    mpz_init_set_str( czworka, "4", 10 );
    mpz_t piatka;
    mpz_init_set_str( piatka, "5", 10 );
    mpz_t siodemka;
    mpz_init_set_str( siodemka, "7", 10 );
    mpz_t osemka;
    mpz_init_set_str( osemka, "8", 10 );
    mpz_t dziewiatka;
    mpz_init_set_str( dziewiatka, "9", 10 );
    mpz_t dziesiatka;
    mpz_init_set_str( dziesiatka, "10", 10 );
   
    int sprawdzenie = 0; // Zmienna do oznaczania pierwszosci.
   
    // sprawdzanie kolejnych liczb nieparzystych
    // spelniajacych zaleznosc 6k+1 (pozniej dodamy 6k-1)
    while( sprawdzenie == 0 )
    {
        cout << endl;
        gmp_printf( "Liczba: %Zd", liczba );
        cout << endl;
       
        // Zaczynamy pomiar czasu sprawdzania danej liczny.
        time( & start );
       
        sprawdzenie = 1; // zakladamy, ze liczba jest pierwsza
       
        // Wyznaczamy maksymalny mozliwy podzielnik.
        mpz_sqrt( granica, liczba );
        // Zaczynamy od sprawdzenia podzielnosci przez 3.
        mpz_set_str( dzielnik, "3", 10 );
       
        // Zerujemy licznik.
        int licznik = 1;
        // Obliczamy rozmiar krokow licznika
        mpz_cdiv_q( podzielnik, granica, dziesiatka );
        mpz_mul( podzielnik2, podzielnik, dwojka );
        mpz_mul( podzielnik3, podzielnik, trojka );
        mpz_mul( podzielnik4, podzielnik, czworka );
        mpz_mul( podzielnik5, podzielnik, piatka );
        mpz_mul( podzielnik6, podzielnik, szostka );
        mpz_mul( podzielnik7, podzielnik, siodemka );
        mpz_mul( podzielnik8, podzielnik, osemka );
        mpz_mul( podzielnik9, podzielnik, dziewiatka );
       
        // sprawdzanie podzielnosci danej liczby
        while( sprawdzenie == 1 && mpz_cmp( dzielnik, granica ) <= 0 )
        {
            if(
            mpz_cmp( podzielnik, dzielnik ) == 0 ||
            mpz_cmp( podzielnik2, dzielnik ) == 0 ||
            mpz_cmp( podzielnik3, dzielnik ) == 0 ||
            mpz_cmp( podzielnik4, dzielnik ) == 0 ||
            mpz_cmp( podzielnik5, dzielnik ) == 0 || // sprawdzanie licznika
            mpz_cmp( podzielnik6, dzielnik ) == 0 ||
            mpz_cmp( podzielnik7, dzielnik ) == 0 ||
            mpz_cmp( podzielnik8, dzielnik ) == 0 ||
            mpz_cmp( podzielnik9, dzielnik ) == 0
            )
            {
                cout << "\r" << licznik << "\/10 za nami"; // wyswietlanie licznika
                licznik = licznik + 1;
            }
           
            // Sprawdzenie podzielnosci i ewentualne wyswietlenie dzielnika.
            mpz_mod( reszta, liczba, dzielnik );
            if( mpz_cmp( reszta, zero ) == 0 )
            {
                gmp_printf( "\rDzielnik: %Zd", dzielnik );
                sprawdzenie = 0;
            }
            else { mpz_add( dzielnik, dzielnik, skok1 ); }
        }
       
        // Przechodzimy do nastepnej liczby nieparzystej
        // spelniajacej zaleznosc 6k+1
        // lub wyswietlamy "brak dzielnika"
        // oraz czas wykonania obliczen.
        if( sprawdzenie == 0 )
        {
            mpz_add( liczba, liczba, szostka );
        }
        else
        {
            gmp_printf( "\rBrak dzielnika" );
        }
        time( & koniec );
        roznica = difftime( koniec, start );
        cout << " | Czas: " << roznica << " s\n";
    }
   
    // Jesli trafimy na liczbe pierwsza, to ja wyswietlamy.
    if( sprawdzenie == 1 )
    {
        cout << endl;
        time( & czas );
        ptr = localtime( & czas );
        char * data = asctime( ptr );
        cout << "\t"; cout << "Koniec: " << data;
        cout << endl;
        cout << "\t";
        gmp_printf( "Ta liczba jest pierwsza: %Zd\n", liczba );
    }
    cout << endl;
   
    return 0;
}
P-149326
Piastlis
» 2016-06-20 21:07:15
Jak to ograniczenia są bez znaczenia...To sprawa podstawowa w temacie kompa...Masz procka za za kilkaset zł który posiada kilka rejestrów pracujących na 2-4Gh.Do tego pamięć 4-8G w podobnej cenie o szybkości 2000-1000MB.Twardziel 1-2T o szybkości 500-100MB. O internecie nie wspomnę... Taki zestaw pozwala ci dokonać jakieś obliczenia np w 2 min.Ile by cię kosztowało lub jakim byłbyś geniuszem by te obliczenia wykonać w 2sek.. 
P-149329
1 2 3 4 5 « 6 »
Poprzednia strona Strona 6 z 6