Numerele prin 2014, partea V: Alte detalii numerico-algoritmice
În headerul TOLIL.h funcția TOLIL() actualizează fișierele cu factori primi pentru factorizările numerelor. Se folosește un vector-variabilă globală (a, de tip mpz_t) în care sunt citite niște milioane de numere din GIG.TXT (mai multe sau mai puține) și numerele din vector sunt parcurse până când se verifică, din totalul factorilor primi (cei 5321 acum, cei 5173 înainte), câți dintre ei compun numerele din intervalul care a fost încărcat în vector. Sau câți dintre ei vin ca noutate în fișierul corespunzător intervalării. Fișierul PRIME.TXT, cu cele 5321 de numere prime impare (despre 2 am mai arătat că are statut special), este citit în doi vectori (unsigned long long, respectiv mpz_t, după mărimea factorilor).
De exemplu CF240.TXT se vrea a cuprinde cât mai multe sau toate numerele prime din care sunt făcute factorizările numerelor mai mici de 10^240, din GIG.TXT. Nu pot fi deodată încărcate în vector toate numerele din GIG.TXT care au maxim 240 de cifre, fiind prea multe și ocupând mult mai mult spațiu decât se permite, deoarece numărul de numere a crescut în timp foarte mult. Tot în timp, acest fișier de coeficienți a fost actualizat, parcurgându-se părți rezonabile din zona de maxim 240 de cifre a GIG.TXT, sau a N3.TXT + RZ.TXT înainte.
Atunci când numerele nu erau totuși atât de multe ca acum, dar deja prea multe ca să intre toate în vector, era satisfăcător să se încarce în vector doar un interval de numere (precum cele de la 10^100 la 10^240), atâtea câte erau și așa cum erau pe atunci, ca din ele să se stabilească totalul numerelor prime pentru zona <10^240. Presupuneam că intră toate cele necesare, chiar fără inspectarea zonei sub 10^100, unde puteau fi factori primi necuprinși deasupra (zona sub 10^100 a fost inspectată altădată, ca să se cerceteze și din ea factori primi). CF240 s-a mai numit CF200, extins apoi la 240.
Astăzi CF240.TXT poate fi actualizat în mai mulți pași, putându-se întâi lua zona zecimal-exponentă de la 210 la 240, apoi cea de la 180 la 210, apoi de la 160 la 180 și tot așa până la satisfacție. CF240.TXT trebuie redenumit pe parcurs în funcție de limita de sus a căutării, pentru că la execuție programul îl deschide după un nume ce conține exponentul puterii de 10 care limitează sus intervalul căutării. Când căutarea este între 10^210 și 10^240, este CF240.TXT, dar dacă iau numerele de la 10^180 la 10^210 trebuie să se numească CF210.TXT, și analog în celelalte cazuri de căutare pe subintervale.
În TOLIL() intră vectorul încărcat (încărcarea se face în CARONTE.cc, înainte de apelul funcției TOLIL()), iar exponentul puterii superioare a lui 10 (adică al limitei de sus a căutării) este și el un parametru al funcției. Se numește b1. Când limita de sus este 10^1910 (maximul cel mare), parametrul este dat ca 0, și atunci am setat să se lucreze direct pe conținutul fișierului P2.TXT (când el avea 5173 de numere și GIG.TXT era mai mic).
Altfel se lua conținutul unuia dintre fișierele CF, în funcție de valoarea lui b1, și se ordonau factorii lui primi, sau se adăuga o noutate la ei dacă era cazul. Astăzi mărimea lui GIG.TXT cere atenție, și în plus P2.TXT a fost înlocuit cu PRIME2.TXT (care are toate cele 5321 de numere).
De asemenea P.TXT a crescut cu 20 de factori primi pe 64 de biți (are 5193).
Variabila H desemnează numărul de factori primi din fișierul de actualizat, cu proprietatea că ei apar la puteri mai mari de 1 în numerele din GIG.TXT (maxim 328 de factori, până acum). La CF240.TXT H ajunge la 147 (era 94).
Din TOLIL() se verifică dacă numerele din intervalul de căutare conțin noutăți prime pentru fișierul de coeficienți: conținutul lui actual este depozitat și sortat crescător în doi vectori speciali, unul pe 64 de biți și celălalt mpz_t, și cu căutarea binară se verifică dacă în numerele de la GIG.TXT sunt factori primi neprezenți în CF240.TXT (sau cum se mai numește fișierul de coeficienți).
Înainte se separă conținutul CF240.TXT de restul conținutului PRIME.TXT, în alți doi vectori speciali (ei au ce nu are CF240.TXT).
Întâi se verifică factorii din vectorul de 64 de biți: pentru fiecare se ia vectorul mare (a) de sus în jos, trecându-se prin el până când un număr este divizibil cu factorul prim. Atunci factorul se copiază la sfârșitul vectorului pe 64 de biți, în care s-a pus conținutul corespunzător de la CF240.TXT, iar parcurgerea vectorului a se întrerupe și procedeul se reia pentru următorul factor prim din conținutul disjunct de CF240.TXT. Vectorul a este parcurs până la capăt, dacă factorul prim verificat nu este divizorul nimănui.
Apoi se verifică analog factorii primi mai mari de 2^64, neprezenți încă în CF240.TXT. Deocamdată a trecut ceva timp de când numărul lor a rămas 5.
Mai departe vectorul pe 64 de biți actualizat este tratat în funcția MAXPUT(). Întâi cei H factori primi care apar la puteri mai mari de 1 sunt prezervați în ordinea originală din CF240.TXT. Se notează cu D numărul numerelor prime sub 2^64, aflate acum în CF240.TXT, și se verifică numerele dintre H și D (D fiind în mod sigur mai mare decât H, de exemplu 1799, din care H 147).
Pentru fiecare dintre cele 1652 de numere prime, se parcurge vectorul a și se verifică dacă factorul prim curent divide pe cineva de 2 ori (adică de mai mult de o dată). Dacă da, parcurgerea vectorului a se întrerupe și numărul prim trece într-un vector al cărui index crește cu 1, pornind de la H, trecându-se la următorul factor. Apoi H este actualizat cu numărul de numere prime plus-prezente, nou-venite în această căutare.
Noile H numere prime sunt din nou verificate mai departe, să se stabilească în mod clar, fiecare de câte ori divide cel mai mult un număr din GIG.TXT, urmând ca puterile acestea maxime de împărțire să fie scrise în ordine descrescătoare într-un fișier, PUTERI240.TXT, în forma:
3 la puterea 46 este 8862938119652501095929.
5 la puterea 26 este 1490116119384765625.
7 la puterea 20 este 79792266297612001.
13 la puterea 11 este 1792160394037.
19 la puterea 9 este 322687697779.
11 la puterea 11 este 285311670611.
Și tot așa până la al 147-lea număr prim. În această ordine sunt rearanjate cele 147 de numere prime pentru conținutul noului CF240.TXT, cu funcția TOL1(), apelată din MAXPUT().
Pentru subintervalele din GIG.TXT care nu sunt limitate sus de 10^240: să nu se mai verifice noile H numere, ci doar prima parte din MAXPUT care stabilește noile H numere prime care pot fi prezente la puteri supraunitare.
După MAXPUT() urmează TOL2(), unde cele D-H numere prime de după H (1799 - 147 = 1652) sunt aranjate pentru noul CF240.TXT, pentru fiecare dintre ele vectorul a fiind parcurs și numărându-se de câte ori numărul prim este divizorul cuiva. Factorii care sunt cei mai divizori sunt puși primii în CF240.TXT, aceasta fiind ordinea celor 1652.
TOL3() tratează ultimele 5 numere prime, cele peste 2^64, cu aceeași regulă de la TOL2(), adaptată la tipul mpz_t.
Ideea este ca factorii primi care sunt mai divizori să apară mai repede în vectorii de factori primi folosiți la căutarea principală, de numere pentru GIG.TXT/N.TXT, când se fac sumele de divizori, deci să fie ordonate numerele prime într-o metodă de tip Cache, ca pe cât posibil să nu se parcurgă multe numere prime când trebuie făcută suma divizorilor (rapiditate la execuție). Dar acum fișierele cu coeficienți primi s-au mărit mult (CF240 avea 672 de numere prime înainte, nu 1804).
Dacă în loc de CF240.TXT sau de alt CF trebuie făcut chiar noul fișier general de tip P.TXT, fișierul de puteri de la MAXPUT se numește PUTERITOT.TXT (nu PUTERI1910.TXT), iar fișierul de numere prime, P2.TXT (deci nu CF1910.TXT). Pentru această discriminare, parametrul b1 este dat 0 la TOLIL(), și mai departe la aceste funcții (el este 240 pentru CF240.TXT).
De făcut mai multe rânduri de fișiere de coeficienți (CF + P): unul de la VECUN, strict de la fondul I, unde setul de funcții de TOLIL() este TOLVECUN(), și unul cu cele de mai sus, cu mulți factori primi în fișiere. Cu crearea de la fondul I e de așteptat să fie mai mici fișierele.
Marele surplus de factori primi din ultima vreme vine de la înmulțirile cu numere prime de până la 112000 (poate mai mult), unde multe nu s-au regăsit în numerele deja prezente, și pe intervalele de căutare s-au folosit fișiere mai largi de numere prime (inclusiv PRIME2.TXT la FACTORSUBM).
Când un număr de bază se înmulțește cu un număr prim cu care nu se împarte, coeficientul de fracționalitate al abundenței lui devine divizibil cu acel număr prim, sau chiar egal cu el, iar dacă este sub 112000, s-a putut prelua până acum numărul-rezultat.
Toate numerele prime cu care s-au făcut înmulțirile (și împărțirile) au fost din plaja recunoscută în PRIME.TXT (5321).
Dar au putut fi din afara plajei fișierelor de numere prime potrivite intervalelor de căutare (de exemplu numere specifice PRIME.TXT, când căutarea a fost pe numere sub 200 de cifre, unde corespundea CF160.TXT, sau CF240.TXT).
În special la FACTORSUBM().
Cele 20 de numere prime noi din P.TXT sunt toate pe 64 de biți, și precis mai mici de 112000 (pragul maxim de până acum al coeficienților de fracționare a abundențelor numerelor).
Dar creșterea pragului e destul de improbabilizată de limitarea de spațiu de stocare: GIG.TXT nu mai poate fi pe discul de 320 GB zecimali acum, e pe cel de 1 TB zecimal și nu știu dacă pot să folosesc bine un disc extern de 2 TB, USB 2.0 (placa de bază Acer Veriton M490G recunoaște pentru discurile interne capacități de maxim 1 TB, și nu știu dacă unuia extern de 2 TB i-ar vedea ambii teraocteți).
1 TB zecimal înseamnă o mie de miliarde de octeți, nu 2^40 octeți = 1 TB binar. HDD-urile se vând cu capacitățile exprimate zecimal, de fapt 320 de GB zecimali sunt 298.09 binari. 320000000000 / 1073741824.
Încă nu s-a adăugat ceva celor 421 de numere prime mpz_t, de la cele 36 găsite prin PARI/GP.
Legat de coeficienții primi de fracționalitate: presupunem numărul prim 83243 (nu-l știu să fie între cele 5321), un număr de bază A, suma B a divizorilor, și abundența lui 6 + 8191/83243, care duce la coeficientul acesteia de fracționare care are același nume cu al celui de-al 8128-lea număr prim. Atunci B = A * (6+8191/83243).
6*A e natural. Trebuie ca și 8191*A/83243 să fie natural. În locul numărului prim 8191 poate fi numărul compus 8190, numărătorul fracției cu numitor 83243 este prim cu numitorul, dar produsul dintre numărător și A trebuie să fie divizibil cu numitorul, ca fracția să fie număr natural, deci A să fie divizibil cu 83243 pentru ca 83243 să fie și coeficientul de fracționare al abundenței lui A.
Așa că pentru coeficienții primi de fracționare aflați sub 112000, ei nu pot fi numere prime din afara celor 5321, cum numai ele și factori compuși derivați ai lor au fost folosiți la obținerea unele din altele a numerelor pentru GIG.TXT. Adică ele și numerele compuse din ele (putând fi și cu înmulțiri cu 2) au fost coeficienții de legătură folosiți la căutări.
Dacă 83243 nu este un număr prim folosit, niciun număr din GIG.TXT nu poate să aibă abundența conținând vreo 83243-ime.
De exemplu CF240.TXT se vrea a cuprinde cât mai multe sau toate numerele prime din care sunt făcute factorizările numerelor mai mici de 10^240, din GIG.TXT. Nu pot fi deodată încărcate în vector toate numerele din GIG.TXT care au maxim 240 de cifre, fiind prea multe și ocupând mult mai mult spațiu decât se permite, deoarece numărul de numere a crescut în timp foarte mult. Tot în timp, acest fișier de coeficienți a fost actualizat, parcurgându-se părți rezonabile din zona de maxim 240 de cifre a GIG.TXT, sau a N3.TXT + RZ.TXT înainte.
Atunci când numerele nu erau totuși atât de multe ca acum, dar deja prea multe ca să intre toate în vector, era satisfăcător să se încarce în vector doar un interval de numere (precum cele de la 10^100 la 10^240), atâtea câte erau și așa cum erau pe atunci, ca din ele să se stabilească totalul numerelor prime pentru zona <10^240. Presupuneam că intră toate cele necesare, chiar fără inspectarea zonei sub 10^100, unde puteau fi factori primi necuprinși deasupra (zona sub 10^100 a fost inspectată altădată, ca să se cerceteze și din ea factori primi). CF240 s-a mai numit CF200, extins apoi la 240.
Astăzi CF240.TXT poate fi actualizat în mai mulți pași, putându-se întâi lua zona zecimal-exponentă de la 210 la 240, apoi cea de la 180 la 210, apoi de la 160 la 180 și tot așa până la satisfacție. CF240.TXT trebuie redenumit pe parcurs în funcție de limita de sus a căutării, pentru că la execuție programul îl deschide după un nume ce conține exponentul puterii de 10 care limitează sus intervalul căutării. Când căutarea este între 10^210 și 10^240, este CF240.TXT, dar dacă iau numerele de la 10^180 la 10^210 trebuie să se numească CF210.TXT, și analog în celelalte cazuri de căutare pe subintervale.
În TOLIL() intră vectorul încărcat (încărcarea se face în CARONTE.cc, înainte de apelul funcției TOLIL()), iar exponentul puterii superioare a lui 10 (adică al limitei de sus a căutării) este și el un parametru al funcției. Se numește b1. Când limita de sus este 10^1910 (maximul cel mare), parametrul este dat ca 0, și atunci am setat să se lucreze direct pe conținutul fișierului P2.TXT (când el avea 5173 de numere și GIG.TXT era mai mic).
Altfel se lua conținutul unuia dintre fișierele CF, în funcție de valoarea lui b1, și se ordonau factorii lui primi, sau se adăuga o noutate la ei dacă era cazul. Astăzi mărimea lui GIG.TXT cere atenție, și în plus P2.TXT a fost înlocuit cu PRIME2.TXT (care are toate cele 5321 de numere).
De asemenea P.TXT a crescut cu 20 de factori primi pe 64 de biți (are 5193).
Variabila H desemnează numărul de factori primi din fișierul de actualizat, cu proprietatea că ei apar la puteri mai mari de 1 în numerele din GIG.TXT (maxim 328 de factori, până acum). La CF240.TXT H ajunge la 147 (era 94).
Din TOLIL() se verifică dacă numerele din intervalul de căutare conțin noutăți prime pentru fișierul de coeficienți: conținutul lui actual este depozitat și sortat crescător în doi vectori speciali, unul pe 64 de biți și celălalt mpz_t, și cu căutarea binară se verifică dacă în numerele de la GIG.TXT sunt factori primi neprezenți în CF240.TXT (sau cum se mai numește fișierul de coeficienți).
Înainte se separă conținutul CF240.TXT de restul conținutului PRIME.TXT, în alți doi vectori speciali (ei au ce nu are CF240.TXT).
Întâi se verifică factorii din vectorul de 64 de biți: pentru fiecare se ia vectorul mare (a) de sus în jos, trecându-se prin el până când un număr este divizibil cu factorul prim. Atunci factorul se copiază la sfârșitul vectorului pe 64 de biți, în care s-a pus conținutul corespunzător de la CF240.TXT, iar parcurgerea vectorului a se întrerupe și procedeul se reia pentru următorul factor prim din conținutul disjunct de CF240.TXT. Vectorul a este parcurs până la capăt, dacă factorul prim verificat nu este divizorul nimănui.
Apoi se verifică analog factorii primi mai mari de 2^64, neprezenți încă în CF240.TXT. Deocamdată a trecut ceva timp de când numărul lor a rămas 5.
Mai departe vectorul pe 64 de biți actualizat este tratat în funcția MAXPUT(). Întâi cei H factori primi care apar la puteri mai mari de 1 sunt prezervați în ordinea originală din CF240.TXT. Se notează cu D numărul numerelor prime sub 2^64, aflate acum în CF240.TXT, și se verifică numerele dintre H și D (D fiind în mod sigur mai mare decât H, de exemplu 1799, din care H 147).
Pentru fiecare dintre cele 1652 de numere prime, se parcurge vectorul a și se verifică dacă factorul prim curent divide pe cineva de 2 ori (adică de mai mult de o dată). Dacă da, parcurgerea vectorului a se întrerupe și numărul prim trece într-un vector al cărui index crește cu 1, pornind de la H, trecându-se la următorul factor. Apoi H este actualizat cu numărul de numere prime plus-prezente, nou-venite în această căutare.
Noile H numere prime sunt din nou verificate mai departe, să se stabilească în mod clar, fiecare de câte ori divide cel mai mult un număr din GIG.TXT, urmând ca puterile acestea maxime de împărțire să fie scrise în ordine descrescătoare într-un fișier, PUTERI240.TXT, în forma:
3 la puterea 46 este 8862938119652501095929.
5 la puterea 26 este 1490116119384765625.
7 la puterea 20 este 79792266297612001.
13 la puterea 11 este 1792160394037.
19 la puterea 9 este 322687697779.
11 la puterea 11 este 285311670611.
Și tot așa până la al 147-lea număr prim. În această ordine sunt rearanjate cele 147 de numere prime pentru conținutul noului CF240.TXT, cu funcția TOL1(), apelată din MAXPUT().
Pentru subintervalele din GIG.TXT care nu sunt limitate sus de 10^240: să nu se mai verifice noile H numere, ci doar prima parte din MAXPUT care stabilește noile H numere prime care pot fi prezente la puteri supraunitare.
După MAXPUT() urmează TOL2(), unde cele D-H numere prime de după H (1799 - 147 = 1652) sunt aranjate pentru noul CF240.TXT, pentru fiecare dintre ele vectorul a fiind parcurs și numărându-se de câte ori numărul prim este divizorul cuiva. Factorii care sunt cei mai divizori sunt puși primii în CF240.TXT, aceasta fiind ordinea celor 1652.
TOL3() tratează ultimele 5 numere prime, cele peste 2^64, cu aceeași regulă de la TOL2(), adaptată la tipul mpz_t.
Ideea este ca factorii primi care sunt mai divizori să apară mai repede în vectorii de factori primi folosiți la căutarea principală, de numere pentru GIG.TXT/N.TXT, când se fac sumele de divizori, deci să fie ordonate numerele prime într-o metodă de tip Cache, ca pe cât posibil să nu se parcurgă multe numere prime când trebuie făcută suma divizorilor (rapiditate la execuție). Dar acum fișierele cu coeficienți primi s-au mărit mult (CF240 avea 672 de numere prime înainte, nu 1804).
Dacă în loc de CF240.TXT sau de alt CF trebuie făcut chiar noul fișier general de tip P.TXT, fișierul de puteri de la MAXPUT se numește PUTERITOT.TXT (nu PUTERI1910.TXT), iar fișierul de numere prime, P2.TXT (deci nu CF1910.TXT). Pentru această discriminare, parametrul b1 este dat 0 la TOLIL(), și mai departe la aceste funcții (el este 240 pentru CF240.TXT).
De făcut mai multe rânduri de fișiere de coeficienți (CF + P): unul de la VECUN, strict de la fondul I, unde setul de funcții de TOLIL() este TOLVECUN(), și unul cu cele de mai sus, cu mulți factori primi în fișiere. Cu crearea de la fondul I e de așteptat să fie mai mici fișierele.
Marele surplus de factori primi din ultima vreme vine de la înmulțirile cu numere prime de până la 112000 (poate mai mult), unde multe nu s-au regăsit în numerele deja prezente, și pe intervalele de căutare s-au folosit fișiere mai largi de numere prime (inclusiv PRIME2.TXT la FACTORSUBM).
Când un număr de bază se înmulțește cu un număr prim cu care nu se împarte, coeficientul de fracționalitate al abundenței lui devine divizibil cu acel număr prim, sau chiar egal cu el, iar dacă este sub 112000, s-a putut prelua până acum numărul-rezultat.
Toate numerele prime cu care s-au făcut înmulțirile (și împărțirile) au fost din plaja recunoscută în PRIME.TXT (5321).
Dar au putut fi din afara plajei fișierelor de numere prime potrivite intervalelor de căutare (de exemplu numere specifice PRIME.TXT, când căutarea a fost pe numere sub 200 de cifre, unde corespundea CF160.TXT, sau CF240.TXT).
În special la FACTORSUBM().
Cele 20 de numere prime noi din P.TXT sunt toate pe 64 de biți, și precis mai mici de 112000 (pragul maxim de până acum al coeficienților de fracționare a abundențelor numerelor).
Dar creșterea pragului e destul de improbabilizată de limitarea de spațiu de stocare: GIG.TXT nu mai poate fi pe discul de 320 GB zecimali acum, e pe cel de 1 TB zecimal și nu știu dacă pot să folosesc bine un disc extern de 2 TB, USB 2.0 (placa de bază Acer Veriton M490G recunoaște pentru discurile interne capacități de maxim 1 TB, și nu știu dacă unuia extern de 2 TB i-ar vedea ambii teraocteți).
1 TB zecimal înseamnă o mie de miliarde de octeți, nu 2^40 octeți = 1 TB binar. HDD-urile se vând cu capacitățile exprimate zecimal, de fapt 320 de GB zecimali sunt 298.09 binari. 320000000000 / 1073741824.
Încă nu s-a adăugat ceva celor 421 de numere prime mpz_t, de la cele 36 găsite prin PARI/GP.
Legat de coeficienții primi de fracționalitate: presupunem numărul prim 83243 (nu-l știu să fie între cele 5321), un număr de bază A, suma B a divizorilor, și abundența lui 6 + 8191/83243, care duce la coeficientul acesteia de fracționare care are același nume cu al celui de-al 8128-lea număr prim. Atunci B = A * (6+8191/83243).
6*A e natural. Trebuie ca și 8191*A/83243 să fie natural. În locul numărului prim 8191 poate fi numărul compus 8190, numărătorul fracției cu numitor 83243 este prim cu numitorul, dar produsul dintre numărător și A trebuie să fie divizibil cu numitorul, ca fracția să fie număr natural, deci A să fie divizibil cu 83243 pentru ca 83243 să fie și coeficientul de fracționare al abundenței lui A.
Așa că pentru coeficienții primi de fracționare aflați sub 112000, ei nu pot fi numere prime din afara celor 5321, cum numai ele și factori compuși derivați ai lor au fost folosiți la obținerea unele din altele a numerelor pentru GIG.TXT. Adică ele și numerele compuse din ele (putând fi și cu înmulțiri cu 2) au fost coeficienții de legătură folosiți la căutări.
Dacă 83243 nu este un număr prim folosit, niciun număr din GIG.TXT nu poate să aibă abundența conținând vreo 83243-ime.
Comentarii
Trimiteți un comentariu