Salve, ho la necessità (anche se più che necessità è diletto mio personale) di implementare un algoritmo per ordinare un file con numero molto elevato di record. La necessità nasce dal fatto che ho voluto mettere in piedi un algoritmo per calcolare il quadrato di un numero senza arrotondamenti, cioè calcolando tutte le cifre del risultato. L’algoritmo si presta a trovare numeri primi, infatti calcolando potenze di 2, è probabile che (2^n)-1 sia un numero primo. Attualmente (per la cronaca) la potenza di 2 più elevata che ho calcolato è 2^2097152, col suo bel milione e duecentomila cifre circa, che ha impegnato il PC per 31 ore consecutive. Ora vorrei spingermi oltre e calcolare il quadrato di questo numero (cioè 2^4194304).
Per implementare l’algoritmo uso una macro con Vbasic di Excel; l’algoritmo, di per sé, utilizza fondamentalmente il metodo scolastico, riadattato ed ottimizzato per abbattere i tempi di calcolo, utilizzando in parte la teoria di Karatsuba sul prodotto di grandi numeri.
Nel calcolo del quadrato di un numero, vengono prodotti numerosi prodotti parziali, che vanno tutti sommati tra di loro per ottenere il risultato finale. Poiché tali prodotti hanno moltissimi zeri, ho pensato di scriverli in un file nel seguente modo:
SOF
(0000000)0153211319156736 inizio blocco 1
(0000008)2006359777426944
(0000016)1339587672763392
(0000024)1731862006285824
(0000032)1554700352707584
(0000040)1552829365506048
(0000048)0796698894273024
(0000056)0864757347214848
(0000064)1752976499630592
(0000072)2320695182989824
[…]
(0009848)0258685976062464
(0009856)1028503360590336
(0009864)0000000024755712 fine blocco 1
(0000016)6568508741117569 inizio blocco 2
(0000024)8771201892139284
(0000032)1339691768827898
(0000048)0000000000000001R
(0000040)0179692567077668
[…]
(0009848)4426499715922722
(0009864)0000000000000001R
(0009856)1693795015318678
(0009864)6734318929549422
(0009872)0000000162092674 fine blocco 2
(0000032)2928137331654756 inizio blocco 3
(0000040)7571180142944964
(0000048)6796682643262824
(0000056)6788503249583328
(0000064)3482928100699164
[…] così via per n blocchi
(0019696)0109193032505209
(0019704)0868275911930682
(0019712)0000000020899094
(0019712)1726078674486609
(0019720)0000000083092206
(0019728)0000000000000001 fine del blocco n
EOF
Cioè tra parentesi ho indicato la quantità di zeri che segue il numero di 16 cifre. Quello di cui sopra è solo un esempio ma nel caso del calcolo di 2^2097152, questo file ha raggiunto la dimensione di circa 25 Gb.
La chiave di ordinamento del file è il numero tra parentesi, ascending. Come vedete, il file è “quasi ordinato”, se non fosse per il salto di chiave tra un blocco e l’altro.
Ho verificato che, nel calcolo, utilizzando il sort di Windows, la maggior parte del tempo va via per mantenere ordinato questo file, al fine di poter eseguire correttamente la somma finale e calcolare esattamente il prodotto. Suppongo che il sort standard di Windows sia abbastanza generico per adattarsi a numerose casistiche di sort; vorrei implementare un algoritmo dedicato a questo tipo di file, per sfruttare questo “quasi ordinamento” ottimizzando i tempi di elaborazione causati dal sort di Windows.
Avete per caso qualche idea?
Vi ringrazio in anticipo per qualsiasi collaborazione e resto a disposizione per chiarimenti.
Rispondi quotando
