programma in c per i perfetti

Messaggioda eafkuor » 05/04/2005, 15:04

Ho scritto questo programma in c per calcolare i primi numeri perfetti con la formula di Euclide, solo che dopo il 5° numero perfetto comincia a darmi dei risultati negativi, perche' evidentemente il long long int non contiene numeri cosi' grandi. Qualcuno sa come risolvere il problema? Riporto di seguito il sorgente:

#include <stdio.h>
#include <stdlib.h>
#define MAX_AR 1000

long long int pow(long long int n, int p);
long long int squareroot(long long int n);
int isprime(long long int o);

int main(){

int c=0, fine, array[MAX_AR];
register long long int o, n;

while(c<MAX_AR){
array[c]=0;
c++;
}
c=0;

printf("Inserire il numero: ");
scanf("%d", &fine);

for(n=1;n<=fine;n++){ //da n a fine
o=pow(2,n)-1;
if( isprime(o) ){array[c]=((o+1)/2)*o;c++;}
}

printf("Ricavato con la formula di Euclide sono: ", fine);
c=1;
while(array[c]){
printf("%d, ", array[c]);
c++;
}
printf("\b\b.\n");
system("PAUSE");
return 0;
}

long long int pow(long long int n, int p){

int i;
long long int tot;

tot=n*n;
for(i=0;i<p-2;i++)tot*=n;

return tot;

}

int isprime(long long int o){

long long int i;

if(o%2==0)return 0; //non e' primo

for(i=3;i<=squareroot(o);i+=2){
if(o%i==0) return 0; //non e' primo
}

return 1; //e' primo

}

long long int squareroot(long long int n){

long long int q=1;

while((q*q)<=n) q++;

return q;

}


-----------------------
Il bello di essere intelligente e' che puoi divertirti a fare l' imbecille, ma se sei un imbecille non puoi fare il contrario.
Woody Allen
eafkuor
Senior Member
Senior Member
 
Messaggio: 170 di 1106
Iscritto il: 08/03/2004, 15:59
Località: Italy

Messaggioda tony » 07/04/2005, 01:24

Ho tentato di falo girare, ma col c++ della borland non ho i long long
e con quello della microsoft non riesco comunque (lo re-installerò, avevo fatto delle furbate per risparmiare spazio su disco,
ac++identac++io! [:D] )

Tu, eafkuor, che c usi?

Naturalmente con i long semplici, mi va in negativo prima che a te;
ho messo un sacco di printf, e mi pare che vada in palla già nella funz. "pow" come se non riconoscesse dei long, ma solo degli int!
ho le traveggole.
(by the way, il c borland HA GIA' una funz. di questo nome !)
insisterò.

tony
tony
Average Member
Average Member
 
Messaggio: 649 di 873
Iscritto il: 10/11/2005, 23:47
Località: milano

Messaggioda eafkuor » 07/04/2005, 13:53

uso dev-cpp versione 4 (http://www.bloodshed.net/devcpp.html)

comunque mi pare che qualche tempo fa qualcuno ha scritto delle librerie creando un nuovo tipo di dati che puo' contenere numeri enormi, o sbaglio?

-----------------------
Il bello di essere intelligente e' che puoi divertirti a fare l' imbecille, ma se sei un imbecille non puoi fare il contrario.
Woody Allen
eafkuor
Senior Member
Senior Member
 
Messaggio: 173 di 1106
Iscritto il: 08/03/2004, 15:59
Località: Italy

Messaggioda signor.nessuno » 07/04/2005, 16:17

Immagine
Ultima modifica di signor.nessuno il 26/12/2005, 23:20, modificato 1 volta in totale.
signor.nessuno
Junior Member
Junior Member
 
Messaggio: 78 di 240
Iscritto il: 01/01/2005, 23:30
Località: Italy

Messaggioda eafkuor » 08/04/2005, 11:48

grazie [:)]

-----------------------
Il bello di essere intelligente e' che puoi divertirti a fare l' imbecille, ma se sei un imbecille non puoi fare il contrario.
Woody Allen
eafkuor
Senior Member
Senior Member
 
Messaggio: 176 di 1106
Iscritto il: 08/03/2004, 15:59
Località: Italy

Messaggioda tony » 16/04/2005, 01:17

ciao, eafkour
anche se ormai sei orientato verso librerie a precisione illimitata, ho voluto andare a fondo con i guai della tua routine, ed ecco un risultato
ho scaricato e fatto girare il piacevole ambiente di sviluppo "dev-C++" che tu citavi, arrivando ad una prima conclusione da profano (io di C non so praticamente nulla):
i valori negativi da te lamentati non sono negativi in memoria (me ne sono assicurato usando il debugger passo-passo), bensì son dovuti ad una piacevole [:D] illusione ottica della ... PRINTF. roba da pesce d'aprile !
(viva, viva la compatibilità delle varie implementazioni del C ! )

sì: se nella tua printf finale sostituisci il formato %d con %I64d, (non so se si legge bene, è una i maiuscola), ecco che ottieni risultati corretti per altri tre numeri perfetti (quanti ne cape il tuo programma).
credo che il formato ufficiale invece di %I64 dica %ll (elle elle), ma con questo run-time non funzia.
forse è cosa ben nota, ma io l'ho trovato spulciando pazientemente i file di tipo *.h (vedasi inttypes.h), visto che l'help mi pare assai spartano

vale la pena di fare due considerazioni a spanne sulle limitazioni del metodo di Euclide:
il valore di un numero perfetto si calcola come

p = (2^n-1)*( 2^n)/2 = (2^n -1)*2^(n-1) ~= 2^(2n-1) meno un pelo

facendo due conti a spanna si vede che per n=32 p è ancora < 2^63-1(massimo intero positivo contenuto in un long long)
mentre invece per n=33 p sballa.
perciò si sa a priori che è inutile specificare un n > 32, se la variabile che deve ricevere il risultato è di 64 bit.

a latere, un consiglio per accelerare la tua funzione "pow":
il limite del ciclo, "squareroot(o)", calcolalo una volta per tutte al di fuori del ciclo, in anticipo, invece che ad ogni giro.

la cosa ragionevole poi sarebbe di definire "<u>unsigned</u> long long integer" tutte le variabili long long (che qui sono garantite positive) per guadagnare il 64° bit di precisione (nel qual caso per la printf andrebbe indicato %I64u); con questo accorgimento però non ottieni alcun numero in più.

tony
p.s. chi invece ci dice il formato per stampare un long double con la printf?
io non ci sono riuscito (altro bug?)
tony
Average Member
Average Member
 
Messaggio: 657 di 873
Iscritto il: 10/11/2005, 23:47
Località: milano

Messaggioda signor.nessuno » 17/04/2005, 10:05

Immagine
Ultima modifica di signor.nessuno il 26/12/2005, 23:20, modificato 1 volta in totale.
signor.nessuno
Junior Member
Junior Member
 
Messaggio: 79 di 240
Iscritto il: 01/01/2005, 23:30
Località: Italy

Messaggioda signor.nessuno » 17/04/2005, 10:08

Immagine
Ultima modifica di signor.nessuno il 26/12/2005, 23:21, modificato 1 volta in totale.
signor.nessuno
Junior Member
Junior Member
 
Messaggio: 80 di 240
Iscritto il: 01/01/2005, 23:30
Località: Italy

Messaggioda tony » 20/04/2005, 01:20

grazie, signor.nessuno

- <i>il formato per stampare un long double con la printf? [tony]</i>
-- <i>%Lf oppure %Lg o %Le [signor.nessuno]</i>
li avevo provati e, come dicevo, non ci sono riuscito
se ne parla in modo non molto chiaro in uno dei file ".h"

- <i>pare che il formato ufficiale invece di %I64 dica %ll (elle elle), ma con questo run-time non funzia. [tony]</i>
-- <i>Non funziona con %%lld (o %%llu)? [signor.nessuno]</i>
no (e, come dicevo, con un solo % è documentato in "inttypes.h"); col doppio % meno che mai.

ho anche provato ad accendere un'opzione ANSI del "Dev-Cpp", ma senza beneficio.

non ci resta che attendere una prova di eafkuor per sentire se anche sulla sua macchina (sempre col "Dev-Cpp") la modifica da "%d" a "%I64u" elimina il guaio originale dei risultati negativi dopo il quinto.
(non credo possa dipendere dalla macchina o dal sistema operativo; io ho usato un archeologico 486DX con win95)

tony
tony
Average Member
Average Member
 
Messaggio: 669 di 873
Iscritto il: 10/11/2005, 23:47
Località: milano

Messaggioda signor.nessuno » 20/04/2005, 09:38

Immagine
Ultima modifica di signor.nessuno il 26/12/2005, 23:21, modificato 1 volta in totale.
signor.nessuno
Junior Member
Junior Member
 
Messaggio: 82 di 240
Iscritto il: 01/01/2005, 23:30
Località: Italy

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite