Newsgroup: it.comp.lang.c++
Titolo: avanti il più veloce

Salve,
il c++ è una realtà affascinante e da poco me ne sto interessando.
Seguendo il libro di Deitel ho trovato il seguente esercizio:
Un intero è detto perfetto se è somma di tutti i suoi divisori (incluso 1,
eccetto il numero stesso).
Es.: 6 = 1 + 2 + 3; 28 = 1 + 2 + 4 + 7 + 14 .
Ora metto su un programmino che trova i numeri perfetti tra 2 e 100.000 e mi
accorgo che è lento.
Allora cerco di aumentarne la velocità ottimizzando il codice e mi sono
stupito dell'incremento ottenuto tanto da spingermi a chiedervi di fare di
meglio.
C'è qualcuno che vorrebbe postare il codice a suo parere più veloce?
Ciao, @lf
PS: Se si tratta di un caso da manuale, vi prego di postarmi la soluzione
degli esperti affinché possa confrontare.
--
I'm a pistol packin' man With a gun in my hand
(AC/DC)

 la soluzione degli esperti affinché possa confrontare.
Io non voglio mettere in dubbio la tua buona fede, ma posta in
questa maniera sembra più una richiesta di svolgere i compiti
in vece tua che brama di imparare.
Certo che se tu postassi il *tuo* codice... toglieresti ogni
dubbio, e sarebbe più facile farti notare eventuali errori e/o
punti di miglioramento.
Ciao.
--
BSD is for UNIX-lovers -- linux is for Windows-haters.

"bark" <a@a.a> wrote in message news:agsj9m$ee9$1...@lacerta.tiscalinet.it...

Beh, per ottimizzare del codice c'è solo un modo: fare delle assunzioni sul
funzionamento dell'algoritmo.
Le ipotesi devono essere valide chiaramente. Qualcosa del tipo che "due
numeri consecutivi non sono mai contemporaneamente divisori dello stesso
numero a meno dell'1 e del 2".
Non saprei effettivamente cosa ipotizzare su un'algoritmo semplice come
questo. Nell'algoritmo classico la complessità è n + 1+2+3+...+n = 2*(n+1) +
upperbound(n/2) ( per n pari eliminare la somma dell'upperbound ). Il tempo
T è O(2n) anche se si tende comunque a dire O(n). C'è da dire che alberi
binari o altre strutture dati più complesse consentono di scendere a O(log
n), ma il fatto che vi si possa implementare un algoritmo migliore è una mia
supposizione. Però ci penserò.
Fabio

 C'č qualcuno che vorrebbe postare il codice a suo parere piů veloce?
pseudo codice, al max
se n e' pari, eulero ha dimostrato che per essere perfetto, basta che 
sia della forma 
2^x * (2^(x+1) - 1)
se la potenza di sinistra e' un numero primo (primi di mersenne)
non si sa se esistano perfetti dispari
per n
si verifica se e' pari con (n & 1) == 0
se si, uso il metodo sopra
altrimenti verifico le divisioni per i primi fino a sqrt(n)
se un numero e' divisore, pongo n /= divisore,  sommo questo e continuo 
fino a sqrt(n) che diminuisce
se alla fine la somma dei divisori e' uguale al numero di partenza e' 
perfetto. occhio ai divisori multipli
divertiti

 se la potenza di sinistra e' un numero primo (primi di mersenne)
scusami, 2^(x+1)-1 deve essere primo, 2^x ovviamente non puo' esserlo

 in vece tua che brama di imparare.
Non si tratta ne di farmi svolgere i compiti (non faccio informatica, sto
imparando per diletto) ne di brama di imparare, diciamo che era una
sfiderella.
Considero non valida l'ipotesi di Paolo Podda in quanto non è stato
dimostrato che i numeri perfetti siano solo pari (mi metto nelle condizioni
di non conoscere il risultato) e chi vuole provare provi.
Ciao, b.

 condizioni di non conoscere il risultato) e chi vuole provare provi.
ti rispiego: se il numero che esamini e' pari, la verifica che ti ho 
proposto e' la piu' veloce
se e' dispari, mooooooooolto probabilmente non e' perfetto (e la 
dimostrazione di cio' e' il piu' antico problema aperto della 
matematica, risalendo ai greci), comunque puoi provare col metodo che ti 
ho descritto
anzi, dato che se esiste un numero perfetto dispari deve essere n^2 
volte un numero primo, deve essere divisibile per almeno 8 primi ed 
avere almeno 29 fattori (non distinti)
[ M. D. Sayers, "An improved lower bound for the total number of factors 
of an odd perfect number," Master's thesis, 
M.App.Sc
., NSW Inst. Tech., 
(1986)] 
deve avere almeno 300 cifre 
[R. P. Brent, G. L. Cohen and H. J. J. te Riele, "Improved techniques 
for lower bounds for odd perfect numbers," Math. Comp., 57 (1991) 
857--868. [MR 92c:11004]
e ha come divisore un primo maggiore di 10^20 [ G. L. Cohen, "On the 
largest component of an odd perfect number," J. Austral. Math. Soc. Ser. 
A, 42 (1987) 280-286.]
direi che puoi benissimo limitarti ai pari 
saluti

direi che puoi benissimo limitarti ai pari 
OT... non resisto pero' a ricordare che comunque
e' bene fare attenzione perche' la matematica riserva
delle sorprese...
Ad esempio i cinesi credevano che un numero p fosse
primo se e soltanto se 2^p - 2 era divisibile
esattamente per p. Quella caratterizzazione pero'
sembra vera perche' vale per la stragrande maggioranza
dei numeri ma e' falsa: il numero piu' piccolo per
cui non vale e' 341 (che non e' primo ma che divide
esattamente 2^341-2).
Io onestamente non vedo tutta questa differenza
filosofica fra 341 e 10^20.
Andrea

 filosofica fra 341 e 10^20.
filosoficamente, non vi e' alcuna differenza, in termini di tempi di 
calcolo, subject del thread, mi pare che ve ne sia eccome.
dovendo essere almeno dell'ordine di 10^30, cioe' 10^15 test di 
primalita'...

primalita'...
Non capisco questa osservazione. Un programma per la
ricerca di numeri perfetti che eviti di controllare i
numeri dispari e' come un programma per la ricerca dei
numeri primi che dica che un numero e' primo se 2^p-2
e' un multiplo di p (o per meglio dire lo sarebbe se
si fosse convinti che quella relazione vale sempre -
sbagliando tratti in errore dal fatto che vale per
molti numeri "piccoli").
Comunque sarebbe un programma errato.
Io semplicemente facevo notare che in passato piu'
di una volta si sono prese cantonate deducendo che
qualcosa era vero per tutti i numeri solo dal fatto
che fosse vero per una enormita' di numeri (quanto
sia una "enormita'" e' qualcosa che cambia con i
tempi... ma resta sempre un concetto debole).
Certo che se sposti il problema dall'algoritmo
(scritto in termini di numeri naturali e sganciato
dalle limitazioni numeriche dei computer di oggi)
e consideri solo la pochezza calcolabile attualmente
allora ti puoi appellare a quei teoremi di lower
bound... Il programma piu' rapido che trova tutti
i numeri perfetti pero' sarebbe forse in questo
contesto una fila di "puts" con delle costanti
e senza calcolo alcuno ;) .
Andrea

 e senza calcolo alcuno ;) .
gia', in effetti essendo noti solo i primi 38 primi di mersenne, piu' 
uno che non si sa se sia il 39simo o piu' alto, e solo 13 sono al di 
sotto delle 300 cifre, potrei benissimo verificare per i pari con uno 
sguardo in una lista precalcolata, e per i dispari usare uno dei tanti 
metodi matematici diversi dal test di primalita', esposti nei lavori 
citati e in altri, ad esempio usare la moltiplicazione tramite FFT
saluti

 
dove posso trovare informazioni circa i teoremi che menzioni?
-- 
real name: Fabrizio Chiarello	| a Debian GNU/Linux | i'm in the could
nick:	   
ckk8.org
		| "Woody" is running | do better category
e-mail:	   
fchia...@inwind.it
	| on Linux v2.4	     | 		  - ckk8

 dove posso trovare informazioni circa i teoremi che menzioni?
su internet, tramite google o altri motori di ricerca

dove posso trovare informazioni circa i teoremi che menzioni?
Se cerchi anche tu paroloni che non capisci per costruirti
una armatura che ti faccia sembrare intelligente agli occhi
degli ignoranti basta usare google e lavorare di copia-incolla.
Ti sconsiglio pero' di cercare di aggiungere frasi tue perche'
come sempre capita commetteresti detestabili strafalcioni:
i dettagli e il pressapochismo non vanno molto d'accordo.
Ti confesso anche che trovo il tuo modo di quotare decisamente
maleducato. Quelle cretinate non le ho dette io e la cosa non
e' evidente dal testo che riporti.
Andrea

 e' evidente dal testo che riporti.
grazie per le cretinate. Ripassare un po' di matematica non ti farebbe 
male, cosi' come abbassare un po' le penne