Numerele în restul anului 2015 (Partea IV - Continuarea refacerii)
La 17 octombrie 2015 am început lucrul la o nouă formă a actualizării fişierelor de numere permanente, care să fie cu câştig de viteză (dar ceva mai multă memorie se consumă, de tratat cu precauţie şi cu echilibru) - aici este implicat VECUNGUL şi este vorba despre noul header ACTUAL2.h, unde munca de actualizare a GIG-urilor este axată pe stringurile (char * în limbajul C) sub a căror formă numerele sunt în fişiere: în clasicul ACTUAL.h, se fac nişte conversii de la char * la mpz_t şi vectorul care acumulează numerele la paşii de actualizare este mpz_t şi nu vector de şiruri de caractere. Poate că se câştigă 30% viteză, când în ACTUAL2.h numerele sunt tratate doar ca char * şi intră într-un vector care este de fapt matrice de caractere, char a[NN][DIM], unde NN poate fi 120000000, iar DIM trebuie să asigure cuprinderea celui mai mare număr de cifre ale numerelor din paşii actualizării: de exemplu, dacă se actualizează GIG80.TXT pe numerele de la 10^52 la 10^80, adică el tot, pentru siguranţă este bine ca DIM să fie 83.
Aici este ceva mai multă memorie consumată în plus faţă de mepezetele unde spaţiul ocupat de un număr în memorie depinde de câte cifre are numărul, putând fi numere de 53, 63, 73, pe când în matricea de caractere toate poziţiile care ajung ocupate cu stringuri trebuie să ocupe "83" în memorie. Totuşi, aici la alocarea statică se consumă jumătate din memoria care ar fi la cea dinamică, plus că statismul conferă o siguranţă; în plus, contează şi sortarea crescătoare a elementelor (făcută cu un heap sort numit HSS, adaptat după HS-ul mepezetelelor); sortarea prin interclasare, cu care am lucrat cândva, ar fi fost ea însăşi o dublare de volum de numere implicate în sortare. Combinaţia matrice dinamică de charuri + interclasare la sortare ar fi consumat poate chiar de 4 ori cât char a[NN][DIM]. Şi aşa memoria calculatorului este pe sponci pentru destule cazuri de actualizare.
Aşadar, în privinţa aparatului actualizator am făcut două reforme importante în timpul luptei pentru regenerarea fondului 2 numeric, pentru viteză şi încăperea elementelor în pasul de actualizare pe măsură ce creşte numărul de numere. Am găsit îmbunătăţiri de făcut şi la NUMSIMPL, MODSPRIM, MODPRIM, MODMIN şi în alte puncte ale codului-sursă; au apărut câteva fişiere noi de căutare, unde se tratează cazurile speciale ale factorilor primi de căutare, 3, 5 şi 7: de exemplu în NUMSIMPL 3, 5 şi 7 nu se mai folosesc în căutări, dar ele sunt tratate optimal şi individual în 357NUMSIMPL.cc. La fel la MODSPRIM (avea mai puţină nevoie), MODPRIM (care avea şi ceva greşeli în felul cum erau folosite unele variabile la căutare, ce ducea la rezultate nedrepte) şi MODMIN. Am mai greşit în 2014 la folosirea vectorilor de factori primi pentru căutarea în jos, la fişierele MODSPRIM şi MODPRIM, şi am remarcat.
A apărut şi un header nou, 357.h, pentru fişierele cu 357 în faţă, MODSPRIM, MODPRIM şi MODMIN; 357NUMSIMPL nu are nevoie de el. În 357.h am mutat din SUMPART.h mai multe funcţii individualizate, de calcul al sumelor parţiale de divizori pentru numerele 3, 5 şi 7, pe 64 de biţi şi în MPZ.
Am schimbat şi modul de tratare a fişierelor cu rezultate, în timpul actualizării: să ţină cont de numărul exact de cifre, într-adevăr, şi de divizare, şi în plus şi de cât de mult să parcurgă din ele la fiecare pas, pentru prinderea tuturor numerelor adecvate; acum nu mai contează dacă fişierul este de tip "sus" sau "jos", dar al doilea caracter din numele fişierului (de pe discul unde se află) este o cifră care arată în câte ordine zecimale de mărime se pot afla elemente alăturate din fişier: aceasta depinde de cât de mare este diferenţa dintre cel mai mic şi cel mai mare factor (prim, deocamdată) de legătură dintre numere, folosit la căutare.
Dacă maximul este de mai puţin de 10 ori mai mic decât minimul, se consideră o singură trecere peste ordin, că în fişier, pentru un număr cu un număr N de cifre, vecinii de deasupra sau de dedesubt pot avea tot N cifre, sau cel puţin N-1, sau maxim N+1, căci dacă factorul prim vecin este de 7 ori mai mare sau mai mic se poate totuşi trece peste un ordin zecimal, în sus sau în jos (dacă s-ar folosi un singur factor prim de legătură, şi numerele din fişierul rezultat ar fi strict crescătoare şi a doua cifră din nume poate fi 0, numerele cu un acelaşi număr de cifre fiind aşezate compact). Dacă maximul este de (10, 100) de ori minimul, pot fi deosebiri de două cifre între numere învecinate.
Ultima poziţie din fişier, dacă nu respectă filtrarea abundenţială pentru zona de GIG respectivă, este schimbată în 10^1918 + 1, altfel acest număr se pune în continuarea fişierului, fiind totdeauna elementul cel mai mare şi de terminare al unui fişier, la care trebuie să se ajungă cu cât actualizarea se apropie de sfârşitul fişierului. Pentru echilibrarea parcurgerii eficiente a fişierului cu prinderea tuturor numerelor necesare, ţinându-se seama că de regulă fişierele de rezultate nu sunt ordonate strict crescător din cauza mărimilor diferite ale factorilor de legătură cu care se găsesc numerele, se foloseşte această regulă care implică, la fiecare pas, şi o funcţie de cursare (din URC.h) în interiorul fişierului, până la zona de unde trebuie să se înceapă verificarea numerelor, ca şi oprirea la timp în interiorul fişierului, când sfârşitul său nu este suficient de aproape.
Altfel, cu parcurgere integrală de numere din fişier la fiecare pas, mai ales fişierele peste 100 de GB ar cere un timp cumplit de mare, şi trebuia o parcurgere optimală şi echilibrată totodată. Funcţia funcţionează mai bine pe fişiere ordonate crescător, căutând să găsească primul număr (ca string, char *) cu un anumit număr de cifre, iar fişierele de tipul S1S100.TXT, J2S13.TXT şi altele nu sunt tocmai ordonate crescător.
În anul 2014 am implementat trei forme de abordare a depozitului numeric la actualizare, două de jos (MIC() şi MIC2(), unde MIC2() era din cauza creşterii fişierului GIG.TXT şi trebuia să fie compus din bucăţi scrise pe (minim) două hard diskuri diferite) şi MARE() de sus, adică primele două când trebuie actualizată cel puţin partea de jos a fişierului, sau el tot, iar ultima, când este de actualizat o parte a lui de sus. Cu configuraţia de acum, şi cu mai multe GIG-uri, am comentat MIC2()-ul, deşi în 2014 a fost vorba că MIC() nu va mai avea sens pentru o vreme; vremea a trecut.
La 15 noiembrie 2015 am făcut o grupare pe categorii a funcţiilor din headerul mare, TOLIL.h: actualizare de vectori de numere prime, căutări binare, sortări, sume de divizori, validatori de abundenţe, funcţii de citire sau de scriere a numerelor pentru fişiere, funcţii de generat coeficienţi de legătură (nu le-am mai folosit de mult, de când am înţeles că avalanşa de roade numerice se face prin factorii primi din vectorii cu valori din CF-uri); pentru o căutare de genul MODIFSUM ele pot fi bune. Mai sunt şi alte funcţii. Câteva funcţii din TOLIL.h erau perimate şi au ajuns la GUNOI.TXT.
La liniile 16430 şi 16447 din N3.TXT sunt cele două numere octaperfecte care îl au pe 22366891 la puterea a doua.
La 26 decembrie 2015 deja există de mult şi GIG1910.TXT, iar capacitatea totală a celor opt fişiere depăşeşte puterea de stocare a hard diskului de 3 TB. A urmat la rând cel de 2 TB, noul Western Digital Caviar Green, pentru depozitare de texte numerice. Este timp şi pentru alte îmbunătăţiri în sursele numerice.
La 30 decembrie 2015 încă erau 22777 de numere în fondul 1, când am început filtrarea în GIG-uri pentru căutat noile numere de fond 1 care credeam că au venit de când cu regenerarea. Dar sub 100 de cifre nu am găsit nimic, așa că semăna cu o mare zbatere degeaba. Însă la numerele de peste 100 de cifre, s-au găsit mai multe noutăți, până la 200 de cifre, așa că în ultima seară din 2015 erau 22803 numere (am trecut de pragul celei de-a 228-a sute), cu FILTRARE.cc, și apoi cu VECUN.TXT am mai scos două, până pe 1 ianuarie 2016.
Aici este ceva mai multă memorie consumată în plus faţă de mepezetele unde spaţiul ocupat de un număr în memorie depinde de câte cifre are numărul, putând fi numere de 53, 63, 73, pe când în matricea de caractere toate poziţiile care ajung ocupate cu stringuri trebuie să ocupe "83" în memorie. Totuşi, aici la alocarea statică se consumă jumătate din memoria care ar fi la cea dinamică, plus că statismul conferă o siguranţă; în plus, contează şi sortarea crescătoare a elementelor (făcută cu un heap sort numit HSS, adaptat după HS-ul mepezetelelor); sortarea prin interclasare, cu care am lucrat cândva, ar fi fost ea însăşi o dublare de volum de numere implicate în sortare. Combinaţia matrice dinamică de charuri + interclasare la sortare ar fi consumat poate chiar de 4 ori cât char a[NN][DIM]. Şi aşa memoria calculatorului este pe sponci pentru destule cazuri de actualizare.
Aşadar, în privinţa aparatului actualizator am făcut două reforme importante în timpul luptei pentru regenerarea fondului 2 numeric, pentru viteză şi încăperea elementelor în pasul de actualizare pe măsură ce creşte numărul de numere. Am găsit îmbunătăţiri de făcut şi la NUMSIMPL, MODSPRIM, MODPRIM, MODMIN şi în alte puncte ale codului-sursă; au apărut câteva fişiere noi de căutare, unde se tratează cazurile speciale ale factorilor primi de căutare, 3, 5 şi 7: de exemplu în NUMSIMPL 3, 5 şi 7 nu se mai folosesc în căutări, dar ele sunt tratate optimal şi individual în 357NUMSIMPL.cc. La fel la MODSPRIM (avea mai puţină nevoie), MODPRIM (care avea şi ceva greşeli în felul cum erau folosite unele variabile la căutare, ce ducea la rezultate nedrepte) şi MODMIN. Am mai greşit în 2014 la folosirea vectorilor de factori primi pentru căutarea în jos, la fişierele MODSPRIM şi MODPRIM, şi am remarcat.
A apărut şi un header nou, 357.h, pentru fişierele cu 357 în faţă, MODSPRIM, MODPRIM şi MODMIN; 357NUMSIMPL nu are nevoie de el. În 357.h am mutat din SUMPART.h mai multe funcţii individualizate, de calcul al sumelor parţiale de divizori pentru numerele 3, 5 şi 7, pe 64 de biţi şi în MPZ.
Am schimbat şi modul de tratare a fişierelor cu rezultate, în timpul actualizării: să ţină cont de numărul exact de cifre, într-adevăr, şi de divizare, şi în plus şi de cât de mult să parcurgă din ele la fiecare pas, pentru prinderea tuturor numerelor adecvate; acum nu mai contează dacă fişierul este de tip "sus" sau "jos", dar al doilea caracter din numele fişierului (de pe discul unde se află) este o cifră care arată în câte ordine zecimale de mărime se pot afla elemente alăturate din fişier: aceasta depinde de cât de mare este diferenţa dintre cel mai mic şi cel mai mare factor (prim, deocamdată) de legătură dintre numere, folosit la căutare.
Dacă maximul este de mai puţin de 10 ori mai mic decât minimul, se consideră o singură trecere peste ordin, că în fişier, pentru un număr cu un număr N de cifre, vecinii de deasupra sau de dedesubt pot avea tot N cifre, sau cel puţin N-1, sau maxim N+1, căci dacă factorul prim vecin este de 7 ori mai mare sau mai mic se poate totuşi trece peste un ordin zecimal, în sus sau în jos (dacă s-ar folosi un singur factor prim de legătură, şi numerele din fişierul rezultat ar fi strict crescătoare şi a doua cifră din nume poate fi 0, numerele cu un acelaşi număr de cifre fiind aşezate compact). Dacă maximul este de (10, 100) de ori minimul, pot fi deosebiri de două cifre între numere învecinate.
Ultima poziţie din fişier, dacă nu respectă filtrarea abundenţială pentru zona de GIG respectivă, este schimbată în 10^1918 + 1, altfel acest număr se pune în continuarea fişierului, fiind totdeauna elementul cel mai mare şi de terminare al unui fişier, la care trebuie să se ajungă cu cât actualizarea se apropie de sfârşitul fişierului. Pentru echilibrarea parcurgerii eficiente a fişierului cu prinderea tuturor numerelor necesare, ţinându-se seama că de regulă fişierele de rezultate nu sunt ordonate strict crescător din cauza mărimilor diferite ale factorilor de legătură cu care se găsesc numerele, se foloseşte această regulă care implică, la fiecare pas, şi o funcţie de cursare (din URC.h) în interiorul fişierului, până la zona de unde trebuie să se înceapă verificarea numerelor, ca şi oprirea la timp în interiorul fişierului, când sfârşitul său nu este suficient de aproape.
Altfel, cu parcurgere integrală de numere din fişier la fiecare pas, mai ales fişierele peste 100 de GB ar cere un timp cumplit de mare, şi trebuia o parcurgere optimală şi echilibrată totodată. Funcţia funcţionează mai bine pe fişiere ordonate crescător, căutând să găsească primul număr (ca string, char *) cu un anumit număr de cifre, iar fişierele de tipul S1S100.TXT, J2S13.TXT şi altele nu sunt tocmai ordonate crescător.
În anul 2014 am implementat trei forme de abordare a depozitului numeric la actualizare, două de jos (MIC() şi MIC2(), unde MIC2() era din cauza creşterii fişierului GIG.TXT şi trebuia să fie compus din bucăţi scrise pe (minim) două hard diskuri diferite) şi MARE() de sus, adică primele două când trebuie actualizată cel puţin partea de jos a fişierului, sau el tot, iar ultima, când este de actualizat o parte a lui de sus. Cu configuraţia de acum, şi cu mai multe GIG-uri, am comentat MIC2()-ul, deşi în 2014 a fost vorba că MIC() nu va mai avea sens pentru o vreme; vremea a trecut.
La 15 noiembrie 2015 am făcut o grupare pe categorii a funcţiilor din headerul mare, TOLIL.h: actualizare de vectori de numere prime, căutări binare, sortări, sume de divizori, validatori de abundenţe, funcţii de citire sau de scriere a numerelor pentru fişiere, funcţii de generat coeficienţi de legătură (nu le-am mai folosit de mult, de când am înţeles că avalanşa de roade numerice se face prin factorii primi din vectorii cu valori din CF-uri); pentru o căutare de genul MODIFSUM ele pot fi bune. Mai sunt şi alte funcţii. Câteva funcţii din TOLIL.h erau perimate şi au ajuns la GUNOI.TXT.
La liniile 16430 şi 16447 din N3.TXT sunt cele două numere octaperfecte care îl au pe 22366891 la puterea a doua.
La 26 decembrie 2015 deja există de mult şi GIG1910.TXT, iar capacitatea totală a celor opt fişiere depăşeşte puterea de stocare a hard diskului de 3 TB. A urmat la rând cel de 2 TB, noul Western Digital Caviar Green, pentru depozitare de texte numerice. Este timp şi pentru alte îmbunătăţiri în sursele numerice.
La 30 decembrie 2015 încă erau 22777 de numere în fondul 1, când am început filtrarea în GIG-uri pentru căutat noile numere de fond 1 care credeam că au venit de când cu regenerarea. Dar sub 100 de cifre nu am găsit nimic, așa că semăna cu o mare zbatere degeaba. Însă la numerele de peste 100 de cifre, s-au găsit mai multe noutăți, până la 200 de cifre, așa că în ultima seară din 2015 erau 22803 numere (am trecut de pragul celei de-a 228-a sute), cu FILTRARE.cc, și apoi cu VECUN.TXT am mai scos două, până pe 1 ianuarie 2016.
Comentarii
Trimiteți un comentariu