Progresul hardware, episodul 38: Alte discuții interne despre numere, iarna trecută în 2018
Am găsit că există și a doua variantă de tratare a abundenței numărului, cea cu numărător/numitor, care este și cea care merge în miezul scopului căutării numerelor - cum abundențele lor sunt criteriul de depozitare. Cele două numere arată raportul dintre sumă și număr, adică abundența, iar depozitarea acestor perechi numerice în fișiere ar însemna mai puțin spațiu decât cu sumele totale, însă nu chiar cu mult, mult mai puțin, pentru fiecare număr de bază perechea abundențială ocupând un spațiu mediu de, poate, 12-14 octeți, cu posibilitatea de a ajunge peste 15 atunci când numărătorul este de 8 cifre și numitorul de 7, separate prin spațiu (adică 16). Și încă presupunând că sunt numere corect filtrate, fără abundențe aiurea. În situația actuală cu peste 208 miliarde de numere în GIG-uri (numai pentru GIG-uri, nu și pentru noutățile din celelalte fișiere, nota bene), totalul scrierii nr/nm ar da vreo 3 TB. Dar varianta cu sumele ar depăși cu o idee volumul de 22.6 sau câți TB sunt în „cele mari”, ar da vreo 23 de TB în plus, prin comparație. Totuși, 3 este mai mic decât 23, iar la această privire ar părea că varianta nr/nm este cumva abordabilă.
Însă se păstrează principiile problematice cu lipsa inversabilității, a monotoniei crescătoare păstrătoare de corespondență între sume (abundențe) și numere, plus problema cu calculul adițional pentru noile numere - chiar omițând acest calcul în timpul actualizării vecung/vecungul, pe ambele variante de depozitare pentru abundențe, el trebuie făcut pentru rescrierea de la zero a fișierelor de 23 de TB cu sume, sau 3 cu abundențe, în timpul actualizării făcându-se sortare crescătoare a numerelor de bază, dar neputându-se lucra la fel și cu sumele ori rapoartele abundențiale (care mai sunt și perechi numerice), care pierd corespondența vectorială cu numerele, socotind acum și faptul că încărcarea suplimentară a memoriei cu sumele la actualizare, sau chiar și cu mai puțin spațioasele rapoarte abundențiale, ar îngusta mai mult posibilitatea memoriei de 128 de GB din calculatorul (frontul) de lucru numeric de a trata volumul de numere.
Mai eficientă este scrierea sumelor ori abundențelor de la zero, la sfârșitul actualizării, când GIG-urile sunt în formă nouă și memoria este descărcată de vectorul de mepezetele (sau matricea de char-uri, la vecungul) pentru numerele de bază. Numai că s-ar cere cumplit de mult timp pentru re-calculul sumelor și scrierea fișierelor, care ar și lua mulți TB în plus din spațiu, și chiar și în varianta fracționară cu mai puțini TB, tot ar fi mult timp, chiar mai greu de calculat numărătorul și numitorul decât sumadivarea.
De ce mai greu de făcut nr/nm decât SUMADIV/NUMSUM/SM? Pentru că principiul algoritmic prin care se face direct fracția abundențială a numărului, nemaicalculându-se toată suma, în timp ce necesită o mepezetea care să atingă prin repetate înmulțiri valoarea numărului de bază ca să nu parcurgă neapărat toți factorii primi potențial componenți - gmp_ui, mpz_t la numere mai mari - (altfel trebuind să consume timp cu parcurgerea integrală a primilor), cere și împărțiri repetate, chiar destul de multe, prin CMMDC-uri în cascadă, pentru a se ajunge la forma cu numărător și numitor, ca fracție abundențială ireductibilă care să ne arate semnul că numărul nostru merită să fie acolo. Și încă la numerele mici, de până la 10 la puterea 52 (chiar mai jos, cu o limită coborâtă pentru precauție), nu este nevoie ca nr și nm să fie mepezetele, pot rămâne gmp_ui pe faptul că în timpul parcurgerii puterilor de factori primi, dătătoare de sume parțiale ale numărului, valorile în schimbare prin care trec nr și nm nu ajung prea mari pentru gama de până la 10^64.
Însă urcând prin numere, în fapt pentru zdrobitoarea majoritate a numerelor din GIG-uri, felul cum variază nr și nm (chiar dacă CMMDC le taie sistematic aripile de mărime) le determină să ajungă și ele mari, nu cât suma divizorilor, dar trebuie să fie mpz_t, deși în final abundența este cu numere mici, încadrabile în 64 și chiar 32 de biți. La trecerea succesivă prin puterile de factori primi care compun numărul, pe măsură ce se face drumul numărului către suma sa, cu mepezeteaua adițională care crește prin înmulțiri spre valoarea care să dea semnalul de stop parcurgere, raportul nr/nm este, pe rând, abundența divizorilor numărului de bază, rezultați din împărțirea lui la produsul puterilor factorilor primi care NU i-au fost încă parcurși. Iar valorile nr/nm pentru acei divizori, în special în varianta neajustată prin CMMDC, adică fracție reductibilă (dar poate și ca ireductibilă, în fapt nr și nm pornesc de la 1 și după primul CMMDC, înainte de un nou CMMDC, vin cu valoarea precedent CMMDC-izată), pot nu numai să nu respecte regula de filtrare a numerelor pentru GIG-uri, ci valorile lor să depășească gama 2^64, și atunci trebuiesc declarate ca mpz_t.
Dar operația de împărțire este una care consumă resurse aritmetice serioase în procesor, mai ceva decât la înmulțire, chiar și înmulțirile este bine să fie eficient făcute, mai puține în număr, și problema vitezei împărțirii este valabilă și la gmp_ui, dar chiar ca o circumstanță agravantă la mpz_t, care nu este un tip de date hardware, deși autorii GMP-ului au optimizat biblioteca să fie cât mai rapidă, și așadar este unul mai lent. La mpz_t împărțirile cer un timp pe măsură mai mare decât la gmp_ui, iar calculul repetat de cel mai mare divizor comun, aplicat pe rând pentru nr și nm la fiecare pas, față de situația puterii factorului prim curent cu care numărul de bază se divide, presupune tocmai aceasta: împărțiri repetate; prin repetarea de mai sus, ele devin FOARTE repetate. Și sunt împărțiri cu mepezetele. Sunt două forme: mpz_gcd_ui (când prin puterea factorului prim și suma divizorilor ei ne învârtim în jurul unor valori gmp_ui de asociat cu nr și nm) și mpz_gcd (la așa-zișii factori primi de tip K, unde mepezetele sunt și nr, și nm, și puterea și suma parțială de la factorul prim curent). La fiecare pas, nr și nm au treabă în jurul puterii divizorului prim și a sumei divizorilor ei, iar mpz_gcd este un CMMDC chiar mai lent decât celălalt care implică o mepezetea ca rezultat-țintă. Așadar, pentru nr și nm sunt implicate cumplit de multe împărțiri care implică mpz_t, iar la împărțirile de la K (numere foarte mari, ce-i drept), este chiar mpz_t pe linie.
Chiar și unde este numai gmp_ui, împărțirile tot costă ceva, iar intervalele numerice sunt destul de limitate, chiar să nu ne atingem de numerele de 50-52 de cifre, ci mai jos. O minoritate numerică.
Și este și mepezeteaua cu înmulțiri repetate care trebuie comparată, de la un timp încolo, repetat cu numărul de bază, ca la egalitatea cu el să se oprească (adevărat, înmulțirile costă mai puțin decât împărțirile și variabila evită parcurgerea redundantă de factori primi dacă s-a calculat deja ceea ce trebuia, și parcurgerea redundantă s-ar face altfel mereu, adică și ea ar fi foarte repetată, și acolo se fac verificări de divizibilitate între mepezeteaua de bază și factorul prim, care poate fi mepezetea și el la numerele mai mari, iar la cele foarte mari multe mepezetele).
Dar acel număr-semnal trebuie să mai eficientizeze lucrul cu nr/nm. Insuficient, însă, ca algoritmul de făcut direct abundențele să fie unul rapid pentru depozitarea abundențelor în fișiere; costul aritmetic de timp de lucru asupra procesorului, prin avalanșa de împărțiri din CMMDC-urile în cascadă, majoritar mepezetiste, unele chiar pe linie, își spune cuvântul.
Atunci, pasul depozitării directe a sumelor (abundențelor) în fișiere ajutătoare cade.
Dar de ce ar fi fost el pasul următor, dacă ar fi fost un algoritm eficient la el?
Pentru că astfel, la căutarea numerică (NUMSIMPL, MODPRIM, MODIFSUM, VECUN și varietățile lor, inclusiv FACTORSUBM / FACTSUBM cu varietățile, pentru numerele de plecare, cum acolo se construiesc alte sume prin modificare aleatorie, cu RandomLib), nu ar mai fi fost nevoie de calculat sumele și, după caz, de scos abundențele numerelor de bază (VALIDN), aceste valori ar fi fost direct luabile din fișierele lor și mai departe ar fi rămas de făcut doar modificările care duc la sume și abundențe noi de numere noi.
De exemplu, la NUMSIMPL trebuie mereu făcut SUMADIV, sau NUMSUM1, sau SM pentru numărul din GIG ales, apoi VALIDN extrage numărătorul și numitorul prin CMMDC-uri între mepezetele, înainte să se plece spre noi numere validate prin funcția TRAT. Doar NUMERICUL.cc, SUMRED.cc, SUMM.cc și NUMSUM.cc caută numere noi prin sumadivare (sumdivizare), fără să i se calculeze ceva numărului de bază, și pentru ele nu ar fi fost nevoie de pasul depozitării valorilor pentru abundență (sume sau nr cu nm) în fișiere noi. Dar am văzut că este ineficient și costisitor și ca timp, și ca spațiu, și mai mult ca timp de calcul acolo unde nu este nevoie de atâta spațiu (nr cu nm).
Varianta cu sumele calculate total cere mai puțin timp de calcul decât la nr/nm (suma se construiește prin înmulțiri și, de când cu PUTERNUM, prin preluări din vectori și matrici cu valori rapid presalvate pentru puterile factorilor primi divizori și sumele divizorilor lor, astfel eliminându-se niște împărțiri și unele înmulțiri care se făceau înainte, plus oferindu-se larghețe adițională pentru gmp_ui la MODPRIM, dar nu numai), este adevărat că economisirea de la timpul de calcul de aici (față de nr/nm) pălește și cade în fața timpului pentru scrierea droaiei de TB necesitați pentru fișierele de sume; pe de altă parte, dincolo, timpul de scriere scade pentru că nu sunt ditamai sumele, însă presupun că timpul total (calcul și scriere) la nr/nm este peste cel de la sume, din cauza contracompensării ce-o aduce calculul cu atâtea împărțiri și CMMDC-uri. Împărțiri nu se fac numai la CMMDC-urile în sine, ci chiar nr și nm trebuiesc împărțite la CMMDC-uri pentru drumul către o fracție ireductibilă.
*
Și atunci, care să fie următorul pas mare la progresul algoritmic?
Însă se păstrează principiile problematice cu lipsa inversabilității, a monotoniei crescătoare păstrătoare de corespondență între sume (abundențe) și numere, plus problema cu calculul adițional pentru noile numere - chiar omițând acest calcul în timpul actualizării vecung/vecungul, pe ambele variante de depozitare pentru abundențe, el trebuie făcut pentru rescrierea de la zero a fișierelor de 23 de TB cu sume, sau 3 cu abundențe, în timpul actualizării făcându-se sortare crescătoare a numerelor de bază, dar neputându-se lucra la fel și cu sumele ori rapoartele abundențiale (care mai sunt și perechi numerice), care pierd corespondența vectorială cu numerele, socotind acum și faptul că încărcarea suplimentară a memoriei cu sumele la actualizare, sau chiar și cu mai puțin spațioasele rapoarte abundențiale, ar îngusta mai mult posibilitatea memoriei de 128 de GB din calculatorul (frontul) de lucru numeric de a trata volumul de numere.
Mai eficientă este scrierea sumelor ori abundențelor de la zero, la sfârșitul actualizării, când GIG-urile sunt în formă nouă și memoria este descărcată de vectorul de mepezetele (sau matricea de char-uri, la vecungul) pentru numerele de bază. Numai că s-ar cere cumplit de mult timp pentru re-calculul sumelor și scrierea fișierelor, care ar și lua mulți TB în plus din spațiu, și chiar și în varianta fracționară cu mai puțini TB, tot ar fi mult timp, chiar mai greu de calculat numărătorul și numitorul decât sumadivarea.
De ce mai greu de făcut nr/nm decât SUMADIV/NUMSUM/SM? Pentru că principiul algoritmic prin care se face direct fracția abundențială a numărului, nemaicalculându-se toată suma, în timp ce necesită o mepezetea care să atingă prin repetate înmulțiri valoarea numărului de bază ca să nu parcurgă neapărat toți factorii primi potențial componenți - gmp_ui, mpz_t la numere mai mari - (altfel trebuind să consume timp cu parcurgerea integrală a primilor), cere și împărțiri repetate, chiar destul de multe, prin CMMDC-uri în cascadă, pentru a se ajunge la forma cu numărător și numitor, ca fracție abundențială ireductibilă care să ne arate semnul că numărul nostru merită să fie acolo. Și încă la numerele mici, de până la 10 la puterea 52 (chiar mai jos, cu o limită coborâtă pentru precauție), nu este nevoie ca nr și nm să fie mepezetele, pot rămâne gmp_ui pe faptul că în timpul parcurgerii puterilor de factori primi, dătătoare de sume parțiale ale numărului, valorile în schimbare prin care trec nr și nm nu ajung prea mari pentru gama de până la 10^64.
Însă urcând prin numere, în fapt pentru zdrobitoarea majoritate a numerelor din GIG-uri, felul cum variază nr și nm (chiar dacă CMMDC le taie sistematic aripile de mărime) le determină să ajungă și ele mari, nu cât suma divizorilor, dar trebuie să fie mpz_t, deși în final abundența este cu numere mici, încadrabile în 64 și chiar 32 de biți. La trecerea succesivă prin puterile de factori primi care compun numărul, pe măsură ce se face drumul numărului către suma sa, cu mepezeteaua adițională care crește prin înmulțiri spre valoarea care să dea semnalul de stop parcurgere, raportul nr/nm este, pe rând, abundența divizorilor numărului de bază, rezultați din împărțirea lui la produsul puterilor factorilor primi care NU i-au fost încă parcurși. Iar valorile nr/nm pentru acei divizori, în special în varianta neajustată prin CMMDC, adică fracție reductibilă (dar poate și ca ireductibilă, în fapt nr și nm pornesc de la 1 și după primul CMMDC, înainte de un nou CMMDC, vin cu valoarea precedent CMMDC-izată), pot nu numai să nu respecte regula de filtrare a numerelor pentru GIG-uri, ci valorile lor să depășească gama 2^64, și atunci trebuiesc declarate ca mpz_t.
Dar operația de împărțire este una care consumă resurse aritmetice serioase în procesor, mai ceva decât la înmulțire, chiar și înmulțirile este bine să fie eficient făcute, mai puține în număr, și problema vitezei împărțirii este valabilă și la gmp_ui, dar chiar ca o circumstanță agravantă la mpz_t, care nu este un tip de date hardware, deși autorii GMP-ului au optimizat biblioteca să fie cât mai rapidă, și așadar este unul mai lent. La mpz_t împărțirile cer un timp pe măsură mai mare decât la gmp_ui, iar calculul repetat de cel mai mare divizor comun, aplicat pe rând pentru nr și nm la fiecare pas, față de situația puterii factorului prim curent cu care numărul de bază se divide, presupune tocmai aceasta: împărțiri repetate; prin repetarea de mai sus, ele devin FOARTE repetate. Și sunt împărțiri cu mepezetele. Sunt două forme: mpz_gcd_ui (când prin puterea factorului prim și suma divizorilor ei ne învârtim în jurul unor valori gmp_ui de asociat cu nr și nm) și mpz_gcd (la așa-zișii factori primi de tip K, unde mepezetele sunt și nr, și nm, și puterea și suma parțială de la factorul prim curent). La fiecare pas, nr și nm au treabă în jurul puterii divizorului prim și a sumei divizorilor ei, iar mpz_gcd este un CMMDC chiar mai lent decât celălalt care implică o mepezetea ca rezultat-țintă. Așadar, pentru nr și nm sunt implicate cumplit de multe împărțiri care implică mpz_t, iar la împărțirile de la K (numere foarte mari, ce-i drept), este chiar mpz_t pe linie.
Chiar și unde este numai gmp_ui, împărțirile tot costă ceva, iar intervalele numerice sunt destul de limitate, chiar să nu ne atingem de numerele de 50-52 de cifre, ci mai jos. O minoritate numerică.
Și este și mepezeteaua cu înmulțiri repetate care trebuie comparată, de la un timp încolo, repetat cu numărul de bază, ca la egalitatea cu el să se oprească (adevărat, înmulțirile costă mai puțin decât împărțirile și variabila evită parcurgerea redundantă de factori primi dacă s-a calculat deja ceea ce trebuia, și parcurgerea redundantă s-ar face altfel mereu, adică și ea ar fi foarte repetată, și acolo se fac verificări de divizibilitate între mepezeteaua de bază și factorul prim, care poate fi mepezetea și el la numerele mai mari, iar la cele foarte mari multe mepezetele).
Dar acel număr-semnal trebuie să mai eficientizeze lucrul cu nr/nm. Insuficient, însă, ca algoritmul de făcut direct abundențele să fie unul rapid pentru depozitarea abundențelor în fișiere; costul aritmetic de timp de lucru asupra procesorului, prin avalanșa de împărțiri din CMMDC-urile în cascadă, majoritar mepezetiste, unele chiar pe linie, își spune cuvântul.
Atunci, pasul depozitării directe a sumelor (abundențelor) în fișiere ajutătoare cade.
Dar de ce ar fi fost el pasul următor, dacă ar fi fost un algoritm eficient la el?
Pentru că astfel, la căutarea numerică (NUMSIMPL, MODPRIM, MODIFSUM, VECUN și varietățile lor, inclusiv FACTORSUBM / FACTSUBM cu varietățile, pentru numerele de plecare, cum acolo se construiesc alte sume prin modificare aleatorie, cu RandomLib), nu ar mai fi fost nevoie de calculat sumele și, după caz, de scos abundențele numerelor de bază (VALIDN), aceste valori ar fi fost direct luabile din fișierele lor și mai departe ar fi rămas de făcut doar modificările care duc la sume și abundențe noi de numere noi.
De exemplu, la NUMSIMPL trebuie mereu făcut SUMADIV, sau NUMSUM1, sau SM pentru numărul din GIG ales, apoi VALIDN extrage numărătorul și numitorul prin CMMDC-uri între mepezetele, înainte să se plece spre noi numere validate prin funcția TRAT. Doar NUMERICUL.cc, SUMRED.cc, SUMM.cc și NUMSUM.cc caută numere noi prin sumadivare (sumdivizare), fără să i se calculeze ceva numărului de bază, și pentru ele nu ar fi fost nevoie de pasul depozitării valorilor pentru abundență (sume sau nr cu nm) în fișiere noi. Dar am văzut că este ineficient și costisitor și ca timp, și ca spațiu, și mai mult ca timp de calcul acolo unde nu este nevoie de atâta spațiu (nr cu nm).
Varianta cu sumele calculate total cere mai puțin timp de calcul decât la nr/nm (suma se construiește prin înmulțiri și, de când cu PUTERNUM, prin preluări din vectori și matrici cu valori rapid presalvate pentru puterile factorilor primi divizori și sumele divizorilor lor, astfel eliminându-se niște împărțiri și unele înmulțiri care se făceau înainte, plus oferindu-se larghețe adițională pentru gmp_ui la MODPRIM, dar nu numai), este adevărat că economisirea de la timpul de calcul de aici (față de nr/nm) pălește și cade în fața timpului pentru scrierea droaiei de TB necesitați pentru fișierele de sume; pe de altă parte, dincolo, timpul de scriere scade pentru că nu sunt ditamai sumele, însă presupun că timpul total (calcul și scriere) la nr/nm este peste cel de la sume, din cauza contracompensării ce-o aduce calculul cu atâtea împărțiri și CMMDC-uri. Împărțiri nu se fac numai la CMMDC-urile în sine, ci chiar nr și nm trebuiesc împărțite la CMMDC-uri pentru drumul către o fracție ireductibilă.
*
Și atunci, care să fie următorul pas mare la progresul algoritmic?
Comentarii
Trimiteți un comentariu