Implementazione radice primitiva

Carmela bb

Nuovo Utente
1
0
Salve a tutti, ho implementato un programma che consente di capire se un numero inserito da tastiera è una radice primitiva di un numero primo sempre inserito da tastiera.
Io vorrei che l'utente inserisca un valore fin quando quel valore è una radice primitiva e dopo farlo terminare , ma non riesco a capire cosa fare
Vi metto il codice per intero:
C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>

#define N 100
int Euclide(int a, int b);
int calcola (long int a,long int m, int n);

int Euclide(int a, int b) // prototipo della funzione Euclide //
{
    int r;
    while(b != 0) //ripetere finché non riduciamo a zero
    {
         r = a % b;
         a = b;
         b = r; //scambiamo il ruolo di a e b
    }
    return a; //... e quando b è (o è diventato) 0, il risultato è a
}

int calcola (long int a,long int m, int n)
{
    int r;
    int y = 1;
    
    while (m > 0)
    {
        r = m % 2;
        //esponenziazione veloce
        if(r == 1)
        {
            y = (y*a) % n;
        }
        a = a*a % n;
        m = m/2;
    }
    return y;
}
int main(void)
{
    int numero, mcd,j,k;
    long int g,potenza[N],i,x,risultato, ricerca,generatore=0;
    int controllo = 0, controllo1 = 0;
    int f=0;
    int control = 0;
    //Generiamo un numero primo     
    do
    {
        controllo = 0;
        printf("\nGeneriamo un numero\n");
        /*srand(time(NULL));
        numero = rand()%N;
        printf("\nIl numero generato è: %d\n", numero );*/
        printf("\nInserisci un valore: ");
        scanf("%d", &numero);
        for(i=2; (i<numero); i++)
        {
            risultato = numero % i;
            if(risultato == 0 && i!=numero)
            controllo++;
        }
    }
    while(controllo > 0 || numero < 1);
    
    //Generiamo una radice primitiva (generatore)
    do
    {
        printf("\nScegliere un numero minore di %d: ",numero);
        scanf("%ld",&g);
     } while(g > numero);
    for(x=1 ; (x < numero); ++x)
    {
        potenza[x] = calcola(g,x,numero);
        printf("\n %ld elevato %ld mod %d è uguale a % ld\n",g,x,numero,potenza[x]);
    }
        for(x = 1; (x < numero); x++)
        {
        mcd =Euclide (numero, potenza[x]);
        if(mcd == 1)
        {
            for(j=0;(j<numero);j++)
          {
            k=j+1;
            while((k<numero) && (f==0))
            {
                if(potenza[j] == potenza[k])
                {
                    printf("\nelementi uguali trovati: %ld\t%ld\n",potenza[j], potenza[k]);
                        f+=1;
                }
                k++;
            }
         }
         }
         }       
                if(f==0)
                {
                     printf("\nnon ci sono elementi uguali\n");
                            printf("\nIL valore %ld è un generatore\n",g);
                          
                           }
            
}
La parte che io vorrei si ripetesse fin quando non viene trovato il generatore è:
Codice:
do
    {
        printf("\nScegliere un numero minore di %d: ",numero);
        scanf("%ld",&g);
     } while(g > numero);
    for(x=1 ; (x < numero); ++x)
    {
        potenza[x] = calcola(g,x,numero);
        printf("\n %ld elevato %ld mod %d è uguale a % ld\n",g,x,numero,potenza[x]);
    }
        for(x = 1; (x < numero); x++)
        {
        mcd =Euclide (numero, potenza[x]);
        if(mcd == 1)
        {
            for(j=0;(j<numero);j++)
          {
            k=j+1;
            while((k<numero) && (f==0))
            {
                if(potenza[j] == potenza[k])
                {
                    printf("\nelementi uguali trovati: %ld\t%ld\n",potenza[j], potenza[k]);
                        f+=1;
                }
                k++;
            }
         }
         }
         }       
                if(f==0)
                {
                     printf("\nnon ci sono elementi uguali\n");
                            printf("\nIL valore %ld è un generatore\n",g);
                            generatore ++;
                           }
Grazie in anticipo per l'aiuto
 

M1n021

Nuovo Utente
65
15
Ciao, tralasciando per il momento la tua richiesta, ma non sarebbe più semplice qualcosa del genere?

C:
#include <stdio.h>

#define N 100

int primo(int n)
{
    for(int i = 2; i < n / i; i += 1 + i % 2)
    {
        if(!(n % i))
        {
            return 0;
        }
    }
    return 1;
}

int modulo_potenza(int r, int k, int n)
{
    int m = 1;
    while(k)
    {
        if(k % 2)
        {
            m = m * r % n;
        }
        r = r * r % n;
        k = k / 2;
    }
    return m;
}

int radice_primitiva(int r, int n)
{
    r %= n;
    int v[N] = {0};
    int k;
    for(k = 1; k < n && !v[modulo_potenza(r, k, n)]++; ++k);
    return k == n;
}

int main()
{
    int n = 13;
    int r = 384;
    if(n <= N && primo(n))
    {
        printf("%d\n", radice_primitiva(r, n));
    }
    return 0;
}
 

BAT

Moderatore
Staff Forum
Utente Èlite
12,938
5,788
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
non sarebbe più semplice qualcosa del genere?
suggerimenti per il test di primalità:
1.
per interi <=4 ritorna direttamente il test
n==2 || n==3
(i primi minori o uguali a 4 sono solo il 2 ed il 3)
2.
togliti direttamente di torno i numeri pari dal 4 in poi: sono tutti non primi
3.
fatti i controlli di cui sopra, i divisori da testare vanno dal 3 (incluso) ad incrementi di 2 (3, 5, 7,...); anche se è vero che la terza condizione del for di fatto fa la stessa cosa, ti dimezza direttamente il numero di controlli ed evita di fare l'incremento in modulo, in parole povere fai direttamente
i += 2
nel for perché controlli solo la presenza di eventuali divisori dispari
4.
nella funzione primo(int n) nel for l'intervallo massimo di ricerca dovrebbe avere come limite superiore la radice quadrata intera dell'intero che stai testando, altrimenti il test di primalità fa più operazioni di quante potrebbe (e dovrebbe).
Attenzione alla dimensione in bit dell'intero in input, perché la radice quadrata è un numero in virgola mobile che deve avere una lunghezza in bit doppia per non rischiare di troncare troppo presto i controlli, in parole povere
se hai n a 32 bit --> devi definire un long double a 64 bit per il calcolo della radice quadrata intera che va arrotondata all'intero più vicino. questo accorgimento riduce in maniera drastica le divisioni da provare al crescere di n

Infine, occhio a quando si elevano a potenza i numeri interi: con la crescita esponenziale non ci vuole niente ad andare fuori range, per cui anche se il calcolo dal punto di vista umano è corretto, per il PC ad un certo punto la potenza intera di un intero positivo potrebbe diventare... negativa! a causa della rappresentazione in complemento a 2 degli interi (e per la limitatezza del numero di bit del tipo di dato che si usa).
 

M1n021

Nuovo Utente
65
15
suggerimenti per il test di primalità:
1.
per interi <=4 ritorna direttamente il test
n==2 || n==3
(i primi minori o uguali a 4 sono solo il 2 ed il 3)
2.
togliti direttamente di torno i numeri pari dal 4 in poi: sono tutti non primi
3.
fatti i controlli di cui sopra, i divisori da testare vanno dal 3 (incluso) ad incrementi di 2 (3, 5, 7,...); anche se è vero che la terza condizione del for di fatto fa la stessa cosa, ti dimezza direttamente il numero di controlli ed evita di fare l'incremento in modulo, in parole povere fai direttamente
i += 2
nel for perché controlli solo la presenza di eventuali divisori dispari
Lo so, ma preferisco la forma più concisa:
C:
for(int i = 2; i <= n / i; i += 1 + i % 2)

4.
nella funzione primo(int n) nel for l'intervallo massimo di ricerca dovrebbe avere come limite superiore la radice quadrata intera dell'intero che stai testando, altrimenti il test di primalità fa più operazioni di quante potrebbe (e dovrebbe).
Attenzione alla dimensione in bit dell'intero in input, perché la radice quadrata è un numero in virgola mobile che deve avere una lunghezza in bit doppia per non rischiare di troncare troppo presto i controlli, in parole povere
se hai n a 32 bit --> devi definire un long double a 64 bit per il calcolo della radice quadrata intera che va arrotondata all'intero più vicino. questo accorgimento riduce in maniera drastica le divisioni da provare al crescere di n
In realtà con la condizione
C:
i <= n / i
sto già limitando i controlli a quelli strettamente necessari senza scomodare la funzione sqrt(). Infatti:

i<=n^(1/2) => i^2<=n => i<=n/i

dove l'ultimo passaggio serve a limitare il rischio di overflow.

Infine, occhio a quando si elevano a potenza i numeri interi: con la crescita esponenziale non ci vuole niente ad andare fuori range, per cui anche se il calcolo dal punto di vista umano è corretto, per il PC ad un certo punto la potenza intera di un intero positivo potrebbe diventare... negativa! a causa della rappresentazione in complemento a 2 degli interi (e per la limitatezza del numero di bit del tipo di dato che si usa).
Certo, è una cosa di cui in generale bisogna tener conto, ma nel caso specifico della funzione modulo_potenza() (o equivalentemente della funzione calcola() postata dall'OP), non c'è alcun pericolo concreto di overflow, in quanto il massimo valore che si può raggiungere equivale a (N-1)^2.


P.S.
Nel precedente post ho dimenticato di mettere l'uguale (nel senso che ho scritto < al posto <=) nella condizione del for della funzione primo().
 
  • Mi piace
Reazioni: Moffetta88 e BAT

BAT

Moderatore
Staff Forum
Utente Èlite
12,938
5,788
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
i<=n^(1/2) => i^2<=n => i<=n/i

dove l'ultimo passaggio serve a limitare il rischio di overflow.
non ci avevo mai pensato a questa disuguaglianza, e pensare che avevo sempre fatto i controlli sul limite superiore proprio come hai fatto tu. Poi durante credo il primo corso di programmazione, ci "imposero" il limite con la radice quadrata e l'ho sempre dato per scontato. Qualche libro/note universitarie dove approfondire ulteriormente ce l'hai? vorrei darci un'occhiata.
P.S.
Per evitare sqrt() si può calcolare la radice quadrata intera di n (intero) velocemente (a patto che n sia ragionevolmente piccolo) con ricerca binaria e moltiplicazioni.
 
  • Mi piace
Reazioni: M1n021

M1n021

Nuovo Utente
65
15
Qualche libro/note universitarie dove approfondire ulteriormente ce l'hai? vorrei darci un'occhiata.
No mi dispiace, programmo per diletto e sono giunto a quella condizione ragionandoci.

Un intero n può essere sempre scritto come prodotto di due fattori interi, ossia n=a*b con a<=b. Il massimo valore che a può assumere è ovviamente a=b=sqrt(n), da cui si deduce che se non abbiamo trovato divisori fino a sqrt(n) (incluso), di sicuro non ne troveremo andando oltre, possiamo quindi fermarci e concludere che n è primo.
Da qui la condizione i<=sqrt(n), che tramite semplici passaggi algebrici diventa i^2<=n (elevando ambo i membri al quadrato) e poi i<=n/i (dividendo ambo i membri per i).
 

Andretti60

Utente Èlite
5,960
4,559
Scusate amici, ma state guardando gli alberi senza vedere la foresta.
Non state rispondendo alla domanda della discussione, ossia perché il codice presentato non faccia quello che dovrebbe fare.

il problema è che il codice è troppo ingarbugliato, troppi cicli innestati l’uno nell’altro lo rendono illeggibile, quindi difficile da capire e quindi difficile da trovare gli sbagli. È normale tra i neofiti, e purtroppo continua a essere un problema anche tra i cosiddetti esperti.

bisogna spezzare il codice in più funzioni, in modo che sia facile da leggere e modificare. Le varie funzioni diventano quindi facili da provare se funzionano, indipendentemente dal resto del programma.

al momento sto usando un iPad, praticamente impossibile, almeno per me, scrivere del codice. Il main dovrebbe contenere solo la lettura di un numero, e un loop dove si legge un secondo numero, e si chiama un metodo che controlla se il secondo numero è una radice primitiva del primo, si esce dal loop in caso affermativo.
 

M1n021

Nuovo Utente
65
15
@Andretti60 Sono completamente d'accordo con te, ho iniziato a postare un codice più semplice proprio per spostare il discorso sull'impostazione generale del programma, specificando di rimandare la domanda della discussione ad un secondo momento.

Che poi non riesco a capire come sia possibile implementare un programma del genere e poi bloccarsi sull'impostazione di un ciclo tutto sommato abbastanza semplice! 😕
 

BAT

Moderatore
Staff Forum
Utente Èlite
12,938
5,788
CPU
1-Neurone
Dissipatore
Ventaglio
RAM
Scarsa
Net
Segnali di fumo
OS
Windows 10000 BUG
Scusate amici, ma state guardando gli alberi senza vedere la foresta.
sono d'accordo con te, però c'è una ragione precisa su cui mi sono soffermato proprio su quel pezzo di codice: l'argomento tratta di numeri primi e, come tu sicuramente sai perché sei un fisico, quando ci hai a che fare si aprono 1000 trappole una dietro l'altra, se non nella teoria, nell'efficienza degli algoritmi.
Da qui la condizione i<=sqrt(n), che tramite semplici passaggi algebrici diventa i^2<=n (elevando ambo i membri al quadrato) e poi i<=n/i (dividendo ambo i membri per i).
è proprio su questo che volevo soffermarmi: dal punto di vista matematico il tuo ragionamento non fa una piega,
TUTTAVIA, dal punto di vista dell'efficienza del codice, ahimé è terribile, ti spiego il perché.
Osseva il ciclo che hai scritto
C:
for(int i = 2; i < n / i; i += 1 + i % 2) {
      if(!(n % i)) { return 0; } }
tralasciando le ineguaglianze (cioè senza soffermarci se è meglio mettere un < o un <=) questo codice è estremeamente inefficiente dal punto di vista computazionale. Anche se è vero che si arriva a controllare i divisori fino alla radice quadrata, un inghippo sta qua:
i < n / i;
questo pezzo del ciclo for esegue una divisione. Non so se lo sai, ma l'operazione di divisione, a livello di circuiteria elettronica è computazionalmente molto onerosa rispetto ad operazioni più semplici come le somme (la moltiplicazione richiede in media il quintuplo del tempo rispetto ad una somma, la divisione richiede , se non ricordo male circa 1,5 volte in più moltiplicazione ).
Adesso consideriamo il numero PRIMO n = 2147483647 =2^31-1
la radice quadrata intera è 46340, cosa significa? significa che, prima di concludere che questo numero è primo, il tuo codice fa 46340 divisioni (la metà, 23170, se controlli solo i dispari), una quantità inaccettabile; invece, se "scomodi" la funzione sqrt(), essa farà poche decine di operazioni; calcolando preventivamente il limite superiore, rende il codice nettamente più efficiente, a memoria servono circa O( (log(n))^2 ) operazioni contro migliaia/decine di migliaia! Ma non è finita, guardiamo l'ultima parte del ciclo:
i += 1 + i % 2
anche se è vero che è un codice molto compatto ed elegante, è estremamente inefficiente, poiché basta un banalissimo
i += 2;
e controllare solo i dispari. NOTA BENE: è una sola somma
se incrementi nell'altro modo esegui sempre almeno 2 somme più il calcolo di un modulo... l'operazione modulo (%) richiede di fare moltiplicazioni e sottrazioni (e divisioni) perchè a livello di ciruciteria non è un'operazione semplice come una somma e d'altra parte non lo è neanche matematicamente in quanto
se a:b=q cor resto r (a diviso b = q con resto r ossia il modulo ) -> a=b*q+r -> r=a-b*q e d'altra parte per calcolare q va fatta una divisione tra interi. In alternativa devi usare l'aritmetica modulare considerando che "a congruo a b modulo r" significa che r è il resto della divisione tra a e b, il che implica che r divide a-b. In simboli
a%b = r <-> r | (a-b) il che implica (a-b)=q*r per qualche intero q da calcolare (con cicli macchina). Insomma comunque la giri, se ti rifiuti di incrementare direttamente con i += 2 il tuo codice calcola un modulo (aggiungendo inefficienza) e fa 2 somme; il tutto moltiplicato per le miglia/decine di migliaia di volte dettate dal numero di divisioni della parte precedente del for.

Se non mi credi ti invito a fare il seguente esercizio:
scrivi 2 funzioni che controllano se un intero n è primo, una con il for elegante che hai postato, l'altra usando la radice quadrata ed il controllo solo dei dispari con incremento di 2. Poi fai la ricerca di numeri primi usando le funzioni precedenti (no crivelli):
tutti i primi fino a 1000, poi fino a 10_000, poi fino a 100_000, poi fino a 1_000_000, poi fino a 1_000_000_000, poi fino a 2_000_000_000 e prendi i tempi di calcolo (da codice oppure con un semplice cronometro),
verifica tu stesso la differenza dei tempi di calcolo.

Vedrai che, anche se asintoticamente/matematicamente, le funzioni fanno la stessa cosa, quella efficiente taglia i tempi di calcolo in modo drastico: fare 100*N o 1000*N operazioni asintoticamente è la stessa cosa, ma 100*N è 10 volte più rapido di 1000*N, il che significa che il tempo di calcolo richiesto è 10 volte inferiore: sul singolo numero non te ne accorgi per la brutale potenza delle CPU moderne, ma quando devi fare le operazioni su milioni o miliardi di numeri vedrai che differenza.

Devi considerare che la matematica è una cosa (bellissima) ma teorica, l'implementazione di algoritmi ha bisogno della matematica ma richiede di trovare il metodo (corretto) migliore e più efficiente possibile per eseguire il calcolo.

Tutto questo mi ha fatto ricordare quanto la teoria dei numeri sia come una bellissima donna da ammirare 😍, ma quando cerchi di domarla sia sfuggente e feroce come un branco di iene 🥶
 
  • Mi piace
Reazioni: valeriooo87

Andretti60

Utente Èlite
5,960
4,559
sono d'accordo con te, però c'è una ragione precisa su cui mi sono soffermato proprio su quel pezzo di codice: l'argomento tratta di numeri primi e, come tu sicuramente sai perché sei un fisico, quando ci hai a che fare si aprono 1000 trappole una dietro l'altra, se non nella teoria, nell'efficienza degli algoritmi...
Ripeto, tutto quello non ha nulla a che fare con la domanda posta dal OP. In questa discussione non state aiutando per nulla, confondete solo le idee. Se volete parlare di efficienza di algoritmi, aprite un’altra discussione che può aiutare anche altri utenti.
 
  • Mi piace
Reazioni: BAT

M1n021

Nuovo Utente
65
15
@BAT sono d'accordo con quanto dici. Sebbene non abbia dimestichezza con la teoria della complessità computazionale, il fatto che i+=2 sia più efficiente di i+=1+i%2 mi sembra abbastanza ovvio, così come calcolare il limite superiore in una sola volta rispetto ad effettuare operazioni ad ogni iterazione; volendo, anche il fatto che la moltiplicazione abbia un "costo" superiore rispetto all'addizione, è abbastanza prevedibile. Da profano però penso che il grado di efficienza richiesto ad un algoritmo dipenda anche e soprattutto da quello che l'algoritmo è chiamato a fare, quindi quando possibile preferisco adottare una strada più elegante, tutto qui! 🙂

Bella la metafora sulla teoria dei numeri! 😂
 

Andretti60

Utente Èlite
5,960
4,559
Per tornare in tema, dovresti riscrivere il main() in questa maniera (o qualcosa del genere):

C:
main()
{
    int n, d;
    n = LeggiIntero();
    while(1==1)
    {
        d = LeggiIntero();
        if (RadicePrimitiva(n,d))
        {
            printf("%d e' radice primitiva", d);
            break;
        }
        printf("%d NON e' radice primitiva", d)
    }
}

in quel modo si capisce subito cosa faccia il main() e come si esca dal ciclo.
Hai ovviamente bisogno di due funzioni, una che legga un numero intero da tastiera (e faccia eventuali controlli) e la funzione principale che guarda se il secondo numero sia infatti una radice primitiva.
Cerca di tenere il corpo delle funzioni più corto possibile (certe aziende hanno un numero massimo di linee permesse in una funzione), se diventa troppo lungo spezzalo in più funzioni. E non innestare cicli o if, crea confusione. Ogni funzione deve fare solo una cosa, e farla bene.
 
U

Utente cancellato 371741

Ospite
Anche a mio avviso codice troppo ingarbugliato, a volte si possono usare delle funzioni anche
se non sono chaiamate piu volte, allo scopo di comprendere meglio il codice e isolare certe operazioni.

A me piace tanto il codingstyle del kernel linux, i tab a 8 e il limite linea a 82 servono propio a non poter ingarbugliare il codice, e semplifcarne la lettura.


So di essere ripetitivo ma se piace priogrammare, oltre al conesgnare il compito, suggerisco sempre di iniziare a scrivere codice seguendo uno stile, quale che sia.
 
  • Mi piace
Reazioni: BAT

Entra

oppure Accedi utilizzando

Discussioni Simili