DOMANDA [C]Quando unsigned long long int non basta...

Pubblicità
Brasa

Brasa

Utente Attivo
Messaggi
192
Reazioni
19
Punteggio
38
Ciao a tutti e buon Ferragosto! :party:
Premetto che quello che ho imparato sul C proviene da libri e guide, quindi abbiate pazienza se mi porto dietro alcuni errori... Ma ora andiamo al punto della situazione. Sto scrivendo un programma (in C appunto) con lo scopo di calcolare i numeri primi di Mersenne (ovvero i numeri primi risultanti da 2^n -1, se ho capito bene), con il problema che oltre 2^63 -1 inizia a printare il numero 0 (ovviamente). La domanda viene da se, come posso superare questo limite? Ho già cercato su google in tutte le lingue ma non ho capito molto... vi sarei infinitamente grato se potreste aiutarmi.

Codice: 
#include <stdio.h>#include <math.h>
#include <stdlib.h>
#include <stdint.h>
#include <limits.h>
#include <inttypes.h>
#include <malloc.h>
#include <memory.h>
#include <mem.h>


int IsPrime(unsigned int number) {
    if (number <= 1) return 0;
    unsigned int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return 0;
    }
    return 1;
}


 int main(){


int n = 2, x, check;
unsigned long long int result;


for(x = 1; x <= 63; ++x){


    result = pow(2, n) - 1;




    check = IsPrime(result);


    if(check = 1){
        printf("%llu is prime\n",result);
    }


 ++n;
  }
}

Scusate se ho incluso headers inutilizzati, grazie anticipatamente e di nuovo buon Ferragosto! :)

P.s. Ora mi accorgo che alcuni numeri non sono primi tra quelli che vengono printati... :look:
 
Ultima modifica:
non puoi. Il C non è un linguaggio orientato agli oggetti, e visto che hai bisogno di un "tipo" più esteso, non puoi né
creartelo né utilizzarne uno creato da altri. Devi cambiare linguaggio; una possibile soluzione artificiosa utilizzando
funzioni con array di bit non è consigliabile.
Buon Ferragosto anche a te
 
Ultima modifica:
Utilizzando C++ e gcc è possibile utilizzare numeri più grandi ma devi appunto cambiare linguaggio di programmazione.
Per curiosità in quel isPrime fai il test con Lucas-Lehmer?
 
Trepiedi ha detto:
non puoi. Il C non è un linguaggio orientato agli oggetti, e visto che hai bisogno di un "tipo" più esteso, non puoi né
Clicca per espandere...
Sistemi operativi, driver, giochi ecc. sono scritti in C però non c'è un modo per manipolare grandi numeri? Lol.

In ogni modo. Di standard non c'è nulla; puoi
  • Usare una libreria: tra le più celebri c'è GMP (probabilmente già installata nel tuo sistema)
  • Scriverti le tue funzioni per tali operazioni (non è difficile)
  • Usare i compiler intrinsic per usare le istruzioni SIMD come wrapper per
  • Assembly (inline o non) ed usare le SIMD direttamente. (come extrema ratio)

Ci sono alcuni tipi, __int128 per esempio, forniti dai compilatori: sono comunque estensioni e dipendenti dal compilatore, come del resto le ultime due opzioni sopraelencate. Comunque, questi tipi sono trattati come un int64_t ed un uint64_t ed il compilatore provvede a #2 .

Considera, infine, di utilizzare un altro algoritmo: il tuo è quello più banale, ma anche il più inefficiente. Prova il crivello di Eratostene, ad esempio.
 
Ultima modifica:
signore del tempo ha detto:
Sistemi operativi, driver, giochi ecc. sono scritti in C però non c'è un modo per manipolare grandi numeri? Lol.

In ogni modo. Di standard non c'è nulla; puoi
  • Usare una libreria: tra le più celebri c'è GMP (probabilmente già installata nel tuo sistema)
  • Scriverti le tue funzioni per tali operazioni (non è difficile)
  • Usare i compiler intrinsic per usare le istruzioni SIMD come wrapper per
  • Assembly (inline o non) ed usare le SIMD direttamente. (come extrema ratio)

Ci sono alcuni tipi, __int128 per esempio, forniti dai compilatori: sono comunque estensioni e dipendenti dal compilatore, come del resto le ultime due opzioni sopraelencate. Comunque, questi tipi sono trattati come un int64_t ed un uint64_t ed il compilatore provvede a #2 .

Considera, infine, di utilizzare un altro algoritmo: il tuo è quello più banale, ma anche il più inefficiente. Prova il crivello di Eratostene, ad esempio.
Clicca per espandere...

un programma per calcolare i primi sarà lungo 10 righe di codice,
e tu fai sfoggio di conoscenze di librerie per dirgli che il c va ancora bene?
Pensi ti essere stato colto o inteliggente?
Vuoi fargli scrivere un programma di 2000 righe di codice, quando ci vogliono
3 minuti?
Per non parlare della portabilità?
E poi __int128? Per uno che deve calcolare i primi lo sai che ci puo' fare con 128 bit?
E poi ho detto: "una possibile soluzione artificiosa utilizzando
funzioni con array di bit non è consigliabile."
Era meglio se te ne stavi zitto
 
Trepiedi ha detto:
non puoi. Il C non è un linguaggio orientato agli oggetti, e visto che hai bisogno di un "tipo" più esteso, non puoi né
creartelo né utilizzarne uno creato da altri. Devi cambiare linguaggio; una possibile soluzione artificiosa utilizzando
funzioni con array di bit non è consigliabile.
Buon Ferragosto anche a te
Clicca per espandere...

C'è solo un problema, questo piccolo programma poi verrà implementato in un altro scritto in C e non vorrei dover tradurre 1200 righe in C++... Thanks

Tinwor ha detto:
Utilizzando C++ e gcc è possibile utilizzare numeri più grandi ma devi appunto cambiare linguaggio di programmazione.
Per curiosità in quel isPrime fai il test con Lucas-Lehmer?
Clicca per espandere...

No, quel IsPrime() è un prototipo di funzione copiato da un altro programma (pigrizia) che dice se un numero è primo o meno...
Però mi accorgo che nonostante sia corretto il codice mi printa 15 come numero primo. Mi sa che riscriverò quella parte con il metodo indicato da te e poi posterò il codice, grazie.

signore del tempo ha detto:
Sistemi operativi, driver, giochi ecc. sono scritti in C però non c'è un modo per manipolare grandi numeri? Lol.

In ogni modo. Di standard non c'è nulla; puoi
  • Usare una libreria: tra le più celebri c'è GMP (probabilmente già installata nel tuo sistema)
  • Scriverti le tue funzioni per tali operazioni (non è difficile)
  • Usare i compiler intrinsic per usare le istruzioni SIMD come wrapper per
  • Assembly (inline o non) ed usare le SIMD direttamente. (come extrema ratio)

Ci sono alcuni tipi, __int128 per esempio, forniti dai compilatori: sono comunque estensioni e dipendenti dal compilatore, come del resto le ultime due opzioni sopraelencate. Comunque, questi tipi sono trattati come un int64_t ed un uint64_t ed il compilatore provvede a #2 .

Considera, infine, di utilizzare un altro algoritmo: il tuo è quello più banale, ma anche il più inefficiente. Prova il crivello di Eratostene, ad esempio.
Clicca per espandere...

Non che abbia ben capito i punti iniziali (scusa la nabbagine) però potrei provare. Una costante che sia 'a', di cui si definisce una dimensione, va a occupare una data dimensione di RAM giusto? Lo chiedo perché non avendo fonti di studio definite che io mi porti dietro delle false convinzioni è probabilissimo... Grazie del tuo aiuto

Trepiedi ha detto:
un programma per calcolare i primi sarà lungo 10 righe di codice,
e tu fai sfoggio di conoscenze di librerie per dirgli che il c va ancora bene?
Pensi ti essere stato colto o inteliggente?
Vuoi fargli scrivere un programma di 2000 righe di codice, quando ci vogliono
3 minuti?
Per non parlare della portabilità?
E poi __int128? Per uno che deve calcolare i primi lo sai che ci puo' fare con 128 bit?
E poi ho detto: "una possibile soluzione artificiosa utilizzando
funzioni con array di bit non è consigliabile."
Era meglio se te ne stavi zitto
Clicca per espandere...

Esprimere un disaccordo è anche giusto ma senza offendere gli altri... Ognuno aiuta come può, ma dare risposte del genere non aiuta molto, in primis perché ora non vedo l'utilità di questa tua risposta. Se ci sono 3 utenti ad esempio io leggerò le loro risposte e vedrò quale mi sembra più adatta (nulla togliendo che lo siano tutte). Se te lo dico io che sono di natura rissoso renditi conto che forse c'è qualche problema...




Grazie a tutti per le risposte, buona programmazione :)
 
Brasa ha detto:
Non che abbia ben capito i punti iniziali (scusa la nabbagine) però potrei provare.
Clicca per espandere...

Il primo punto riguarda questa https://gmplib.org/

E' una libreria che implementa numeri interi di dimensioni arbitrarie. E ovviamente implementa pure le funzioni per manipolarli. Imho sarebbe la scelta più logica e cross-platform, altrimenti devi assumerti delle responsabilità per poter usare gli altri metodi.

I punti 3 e 4 sono i più tediosi. Il 4 richiede conoscenze di assembly. Il 3 ( le funzioni intrinseche ) richiede un minimo di lavoro per rendere il programma compilabile tramite compilatori diversi. Stesso discorso vale per il tipo __int128 ( e l'equivalente __m128 di microsoft ).

L'intoppo sta nel fatto che devi accertarti che la cpu su cui girerà il programma abbia il supporto a SSE2 o superiore.
 
pabloski ha detto:
Il primo punto riguarda questa https://gmplib.org/

E' una libreria che implementa numeri interi di dimensioni arbitrarie. E ovviamente implementa pure le funzioni per manipolarli. Imho sarebbe la scelta più logica e cross-platform, altrimenti devi assumerti delle responsabilità per poter usare gli altri metodi.

I punti 3 e 4 sono i più tediosi. Il 4 richiede conoscenze di assembly. Il 3 ( le funzioni intrinseche ) richiede un minimo di lavoro per rendere il programma compilabile tramite compilatori diversi. Stesso discorso vale per il tipo __int128 ( e l'equivalente __m128 di microsoft ).

L'intoppo sta nel fatto che devi accertarti che la cpu su cui girerà il programma abbia il supporto a SSE2 o superiore.
Clicca per espandere...

Grazie mille, la vedo dura con l'assembly ma ora ho più punti su cui lavorare, in ogni caso, quale dimensione massima può raggiungere una variabile di tipo numerico?
 
Brasa ha detto:
quale dimensione massima può raggiungere una variabile di tipo numerico?
Clicca per espandere...

Un tipo intero integrale ha come massima dimensione quella dei registri cpu. Nel caso dei processori x86 moderni si hanno 64 bit per l'alu e 128 bit per le unità sse. Le ultimissime cpu x86 supportano avx, che offre registri a 256 bit.

Se parliamo di GMP, la dimensione è arbitraria.
 
pabloski ha detto:
Un tipo intero integrale ha come massima dimensione quella dei registri cpu. Nel caso dei processori x86 moderni si hanno 64 bit per l'alu e 128 bit per le unità sse. Le ultimissime cpu x86 supportano avx, che offre registri a 256 bit.

Se parliamo di GMP, la dimensione è arbitraria.
Clicca per espandere...


Ok, tutto chiaro ora, grazie... Mi domandavo, negli stress-test va definita la quantitá di RAM da utilizzare e da quella viene di conseguenza la complessitá del problema (parlo di linx), in che modo la RAM viene utilizzata da questo genere di programmi?
 
Brasa ha detto:
Ok, tutto chiaro ora, grazie... Mi domandavo, negli stress-test va definita la quantitá di RAM da utilizzare e da quella viene di conseguenza la complessitá del problema (parlo di linx), in che modo la RAM viene utilizzata da questo genere di programmi?
Clicca per espandere...
Per quanto ne so, praticamente stabilire quanta RAM utilizzare dice al programma la grandezza dell'input per l'algoritmo. Pertanto, più grande è, maggiore sarà il tempo richiesto.

Trepiedi ha detto:
Pensi ti essere stato colto o inteliggente?
Era meglio se te ne stavi zitto
Clicca per espandere...
Potrei dirlo a qualcun altro.
 
Trepiedi ha detto:
un programma per calcolare i primi sarà lungo 10 righe di codice,
e tu fai sfoggio di conoscenze di librerie per dirgli che il c va ancora bene?
Pensi ti essere stato colto o inteliggente?
Vuoi fargli scrivere un programma di 2000 righe di codice, quando ci vogliono
3 minuti?
Per non parlare della portabilità?
E poi __int128? Per uno che deve calcolare i primi lo sai che ci puo' fare con 128 bit?
E poi ho detto: "una possibile soluzione artificiosa utilizzando
funzioni con array di bit non è consigliabile."
Era meglio se te ne stavi zitto
Clicca per espandere...

Modera il linguaggio.

Sanzionato
 
Brasa ha detto:
Grazie, e volendo ricreare ipoteticamente questa situazione in C? Come sarebbe strutturato?
Clicca per espandere...
Codice: 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>


int myCompare(const void *elem1, const void *elem2)
{
   return *((int*)elem1) > *((int*)elem2);
}


int main(int argc, char *argv[]) {
        if (argc < 2) {
           fprintf(stderr, "Uso: %s size.\n", argv[0]); 
           return 1;
         }


        const long long int size = atoll(argv[1]);
        int *v = malloc(size * sizeof(int));
        if (!v) {
           perror("Impossibile allocare la memoria");
         return 1;
        }


       srand(time(NULL));

       for (long long int i = 0; i < size; ++i)
       {
          v[i] = rand();
       }
       
       qsort(v, size, sizeof(v[0]), myCompare);
       
      for (long long int i = 0; i < size; ++i)
          printf("%i\n", v[i]);
 
     free(v);
     return 0;
}
 
Pubblicità
Pubblicità
Indietro
Top