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

[Brasa]

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.

Spoiler

#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:

 

[Trepiedi]

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

 

[Tinwor]

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?

 

[signore del tempo]

non puoi. Il C non è un linguaggio orientato agli oggetti, e visto che hai bisogno di un "tipo" più esteso, non puoi né

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.

 

[Trepiedi]

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.

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

 

[Brasa]

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

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

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?

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.

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.

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

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

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 :)

 

[pabloski]

Non che abbia ben capito i punti iniziali (scusa la nabbagine) però potrei provare.

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.

 

[Brasa]

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.

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?

 

[pabloski]

quale dimensione massima può raggiungere una variabile di tipo numerico?

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.

 

[Brasa]

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.

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?

 

[signore del tempo]

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?

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.

Pensi ti essere stato colto o inteliggente?
Era meglio se te ne stavi zitto

Potrei dirlo a qualcun altro.

 

[fiLo93]

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

Modera il linguaggio.

Sanzionato

 

[Brasa]

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.

Grazie, e volendo ricreare ipoteticamente questa situazione in C? Come sarebbe strutturato?

 

[signore del tempo]

Grazie, e volendo ricreare ipoteticamente questa situazione in C? Come sarebbe strutturato?

#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;
}

 

[Brasa]

Codice:

Ora credo di aver capito, grazie mille, vediamo che riesco a fare :)
Grazie di nuovo.