Numerele în 2014, partea III: Detalii algoritmice
Am făcut și câteva surse care caută numere noi folosind biblioteca RandomLib, pentru numere aleatoare, modificând aleator factorizările numerelor de bază, în puteri de numere prime, cu adăugare/eliminare. FACTORSUB.cc face acest lucru pentru numerele de maxim 160 de cifre, iar FACTORSUBM.cc, pentru numerele mai mari. Există și FACTORSUBP.cc, care s-a vrut implementat după un model cu matrice de puteri de numere prime, considerat însă ineficient.
Au apărut metode noi de însumare a divizorilor, bazate pe modificarea factorizării prime a sumei divizorilor numărului de bază - în funcție de coeficientul de legătură, se schimbă factorii primi ai sumei, prin creștere/scădere a puterii, sau adăugare/scoatere cu totul a unui anumit factor prim. Se verifică validitatea noii sume, iar numărul corespunzător (modificat din numărul de bază prin coeficientul de legătură) este scris în fișierul de rezultate, dacă validarea reușește.
Se tratează cazuri diferite, în surse diferite: când coeficientul de legătură este număr prim, sau nu este prim (în ambele cazuri, coeficienții trebuie să fie impari). Aceste metode nu mai calculează integral suma divizorilor pentru oricare număr de test, ci doar pentru numărul de bază de la care se pleacă, iar la parcurgerea vectorului de coeficienți de legătură suma este re-stocată într-o variabilă, cu metoda mpz_set.
MODSPRIM.cc este pentru modificarea sumei divizorilor prin coeficient prim.
MODIFSUM.cc o modifică prin coeficient neprim. Mai lent decât MODSPRIM.
Există și MODMIN.cc, care este un MODSPRIM pentru numerele cu maxim 52 de cifre, unde factorii primi sunt numai întregi pe 64 de biți.
SUMRED.cc calculează integral suma divizorilor, pentru fiecare număr de căutare (cum de altfel se făcea și înainte cu funcțiile SUMADIV*, SUM*, SM*), dar este dedicat numerelor între 52 și 160 de cifre, unde în plus face deosebire între numere în funcție de puterea de 2 la care se împart. Numerelor de maximum 160 de cifre le revin maxim 3 factori primi mai mari de 2^64, care însă sunt deductibili din puterea de 2 la care se divide numărul de bază vizat, și nu au nevoie să fie stocați într-un vector de numere prime.
Puterile de 2 care implică aceste trei numere prime sunt 88, 106 și 126, iar când numărul de bază nu are vreuna dintre aceste puteri, nu se face prelucrarea sumei după respectivul factor prim, mergându-se mai simplu. Pentru discriminarea numerelor s-a duplicat zona de căutare sus/jos, fiind acum două zone, fiecare cu susul și josul său. Prima zonă este pentru numerele de bază libere de acele puteri de 2, iar cealaltă pentru numerele care se împart la 2 de 88, 106 sau 126 de ori. Trecerea la zona 2 se face cu instrucțiunea goto către etichetă.
SUMM.cc face de asemenea calcul integral (nu integrale matematice) pentru sumele de divizori, dar la numerele cu maxim 52 de cifre, unde nici nu există numere prime peste 64 de biți. Are în comun cu SUMRED.cc o sumare integrală simplificată a divizorilor, față de procedeele de la metodele tradiționale SUMADIV ȘI SUM, utilizându-se, respectiv, SUMRED() și SUMRED1() la SUMRED.cc și chiar SM() și SM1() la SUMM.cc. Dar SUMM.cc nu are nevoie să facă deosebire între numere după puterile lor de 2.
Pentru cazul căutării în jos, metodele de sumare integrală a divizorilor au fost precedate de culegerea factorilor primi proprii numărului de bază, culegere făcută cu metoda LOTVEC(). LOTVEC() a fost folosită în fișierele CARONTE*, în VECUN.CPP, devenit VECUN.cc după trecerea la Linux din toamna anului 2012, și mai nou în fișierul NUMERIC.cc care este urmaș al lui CARONTE.cc, unde sunt SUMADIV() și SUM(), chiar și SM() și funcțiile lor corespondente pentru căutarea în jos, care mai au un 1 în nume.
La SUMRED.cc și SUMM.cc se folosește o variantă simplificată și pentru LOTVEC(), anume LOTVECRED(), iar particula RED din denumiri provine de la „reducere”, simplificare.
La GMP și MPIR numerele erau citite din fișier prin gmp_fscanf, și scrise cu gmp_fprintf. Dar acum nu se mai face așa, ci mai optim, prin string cu fgets() și fputs(), și chiar pe blocuri mai mari de date, cu fread() și fwrite(). Când stringul corespunde cerințelor, se face conversie la mpz_t sau invers, de la mpz_t la string.
La citirea din fișier pe string: fgets() și mpz_set_str(), ca numărul să ia conținutul numeric al stringului.
La scrierea în fișier prin string: numărul intră în string prin mpz_get_str(), iar scrierea se face cu fputs().
Am renunțat la scrierea numerelor în fișier pe un singur rând: GIG.TXT (și N-urile, plus P-urile) au câte un număr pe un rând, și este mai eficient așa.
La fread() și fwrite() nu se mai pune problema convertirilor dintre număr și string. Un bloc are aproape 8 MB (MB binari, nu zecimali).
Există și NUMSUM.cc, care calculează integral suma divizorilor pentru fiecare număr de test, iar coeficienții de legătură sunt pari (cu excepția lui 2, toate numerele pare sunt neprime).
Ar trebui și un MODSPAR.cc, care face modificare de sumă pe coeficienți pari de legătură, ca să fie tacâmul complet.
La SUMADIV(), SUM() și SM(): variabila care lua inițial valoarea numărului de test și se împărțea până la 1 pornește acum de la 1 și se înmulțește, iar circulația prin factorii primi din vector încetează când se ajunge la egalitatea cu numărul. Am considerat că este mai eficient cu înmulțiri decât cu împărțiri, deși acum se face comparare repetată cu un mpz_t mare, în loc de compararea repetată cu întregul 1.
La SUMADIV1(), SUM1() și SM1() nu s-a mai folosit deloc această variabilă, acolo vectorii de parcurs fiind semnificativ mai scurți, fiind vorba despre factorii primi proprii numărului de bază.
Altă modificare importantă, cu progres remarcabil al vitezei de aducere a numerelor, a fost schimbarea formulei de validare pentru numerele de fond II. Înainte se făcea pe rând înmulțirea sumei divizorilor cu fiecare element (coeficient de fracționare abundențială) din vectorul G, și se ajunsese la mai multe mii de astfel de elemente, verificându-se de fiecare dată divizibilitatea produsului cu numărul de test și ieșindu-se favorabil (return 1) dacă se găsea divizibilitate.
(va urma)
Au apărut metode noi de însumare a divizorilor, bazate pe modificarea factorizării prime a sumei divizorilor numărului de bază - în funcție de coeficientul de legătură, se schimbă factorii primi ai sumei, prin creștere/scădere a puterii, sau adăugare/scoatere cu totul a unui anumit factor prim. Se verifică validitatea noii sume, iar numărul corespunzător (modificat din numărul de bază prin coeficientul de legătură) este scris în fișierul de rezultate, dacă validarea reușește.
Se tratează cazuri diferite, în surse diferite: când coeficientul de legătură este număr prim, sau nu este prim (în ambele cazuri, coeficienții trebuie să fie impari). Aceste metode nu mai calculează integral suma divizorilor pentru oricare număr de test, ci doar pentru numărul de bază de la care se pleacă, iar la parcurgerea vectorului de coeficienți de legătură suma este re-stocată într-o variabilă, cu metoda mpz_set.
MODSPRIM.cc este pentru modificarea sumei divizorilor prin coeficient prim.
MODIFSUM.cc o modifică prin coeficient neprim. Mai lent decât MODSPRIM.
Există și MODMIN.cc, care este un MODSPRIM pentru numerele cu maxim 52 de cifre, unde factorii primi sunt numai întregi pe 64 de biți.
SUMRED.cc calculează integral suma divizorilor, pentru fiecare număr de căutare (cum de altfel se făcea și înainte cu funcțiile SUMADIV*, SUM*, SM*), dar este dedicat numerelor între 52 și 160 de cifre, unde în plus face deosebire între numere în funcție de puterea de 2 la care se împart. Numerelor de maximum 160 de cifre le revin maxim 3 factori primi mai mari de 2^64, care însă sunt deductibili din puterea de 2 la care se divide numărul de bază vizat, și nu au nevoie să fie stocați într-un vector de numere prime.
Puterile de 2 care implică aceste trei numere prime sunt 88, 106 și 126, iar când numărul de bază nu are vreuna dintre aceste puteri, nu se face prelucrarea sumei după respectivul factor prim, mergându-se mai simplu. Pentru discriminarea numerelor s-a duplicat zona de căutare sus/jos, fiind acum două zone, fiecare cu susul și josul său. Prima zonă este pentru numerele de bază libere de acele puteri de 2, iar cealaltă pentru numerele care se împart la 2 de 88, 106 sau 126 de ori. Trecerea la zona 2 se face cu instrucțiunea goto către etichetă.
SUMM.cc face de asemenea calcul integral (nu integrale matematice) pentru sumele de divizori, dar la numerele cu maxim 52 de cifre, unde nici nu există numere prime peste 64 de biți. Are în comun cu SUMRED.cc o sumare integrală simplificată a divizorilor, față de procedeele de la metodele tradiționale SUMADIV ȘI SUM, utilizându-se, respectiv, SUMRED() și SUMRED1() la SUMRED.cc și chiar SM() și SM1() la SUMM.cc. Dar SUMM.cc nu are nevoie să facă deosebire între numere după puterile lor de 2.
Pentru cazul căutării în jos, metodele de sumare integrală a divizorilor au fost precedate de culegerea factorilor primi proprii numărului de bază, culegere făcută cu metoda LOTVEC(). LOTVEC() a fost folosită în fișierele CARONTE*, în VECUN.CPP, devenit VECUN.cc după trecerea la Linux din toamna anului 2012, și mai nou în fișierul NUMERIC.cc care este urmaș al lui CARONTE.cc, unde sunt SUMADIV() și SUM(), chiar și SM() și funcțiile lor corespondente pentru căutarea în jos, care mai au un 1 în nume.
La SUMRED.cc și SUMM.cc se folosește o variantă simplificată și pentru LOTVEC(), anume LOTVECRED(), iar particula RED din denumiri provine de la „reducere”, simplificare.
La GMP și MPIR numerele erau citite din fișier prin gmp_fscanf, și scrise cu gmp_fprintf. Dar acum nu se mai face așa, ci mai optim, prin string cu fgets() și fputs(), și chiar pe blocuri mai mari de date, cu fread() și fwrite(). Când stringul corespunde cerințelor, se face conversie la mpz_t sau invers, de la mpz_t la string.
La citirea din fișier pe string: fgets() și mpz_set_str(), ca numărul să ia conținutul numeric al stringului.
La scrierea în fișier prin string: numărul intră în string prin mpz_get_str(), iar scrierea se face cu fputs().
Am renunțat la scrierea numerelor în fișier pe un singur rând: GIG.TXT (și N-urile, plus P-urile) au câte un număr pe un rând, și este mai eficient așa.
La fread() și fwrite() nu se mai pune problema convertirilor dintre număr și string. Un bloc are aproape 8 MB (MB binari, nu zecimali).
Există și NUMSUM.cc, care calculează integral suma divizorilor pentru fiecare număr de test, iar coeficienții de legătură sunt pari (cu excepția lui 2, toate numerele pare sunt neprime).
Ar trebui și un MODSPAR.cc, care face modificare de sumă pe coeficienți pari de legătură, ca să fie tacâmul complet.
La SUMADIV(), SUM() și SM(): variabila care lua inițial valoarea numărului de test și se împărțea până la 1 pornește acum de la 1 și se înmulțește, iar circulația prin factorii primi din vector încetează când se ajunge la egalitatea cu numărul. Am considerat că este mai eficient cu înmulțiri decât cu împărțiri, deși acum se face comparare repetată cu un mpz_t mare, în loc de compararea repetată cu întregul 1.
La SUMADIV1(), SUM1() și SM1() nu s-a mai folosit deloc această variabilă, acolo vectorii de parcurs fiind semnificativ mai scurți, fiind vorba despre factorii primi proprii numărului de bază.
Altă modificare importantă, cu progres remarcabil al vitezei de aducere a numerelor, a fost schimbarea formulei de validare pentru numerele de fond II. Înainte se făcea pe rând înmulțirea sumei divizorilor cu fiecare element (coeficient de fracționare abundențială) din vectorul G, și se ajunsese la mai multe mii de astfel de elemente, verificându-se de fiecare dată divizibilitatea produsului cu numărul de test și ieșindu-se favorabil (return 1) dacă se găsea divizibilitate.
(va urma)
Comentarii
Trimiteți un comentariu