Progresul hardware, episodul 40: Un fiasco programatoric este depistat la timp (pe la 23 ianuarie anul trecut...)
(Aici NU este vorba despre achiziții, ci despre o bibliotecă numerică, una care dacă ar fi fost bună, ar fi fost pusă cu drag să profite pe larg de progresul hardware)
*
VLI (Very large integers), o bibliotecă de precizie fixă extinsă în diferite grade, până la 512 biți, cu preferință pentru multipli de 64 de biți (int128, int192, int256, int320, int384, int448 și int512), reglabilă precizie fixă, s-a dovedit a fi un fiasco în încercarea de a o folosi pentru numerele de maxim 154 de cifre, până pe unde încap 512 biți.
Nu dă voie la amestecarea aritmetică cu întregii hardware, la împărțire, operatorul rest nu este suficient de implementat și nici între tipurile proprii nu dă voie la operații de împărțire directă. În plus, împărțirea a două variabile de un același tip int din VLI (fie el și 128, cel mai mic) durează mult mai mult decât când două mepezetele sunt puse așa, darămite decât când o mepezetea se împarte la un întreg clasic.
Restul împărțirii unui întreg VLI la alt număr (tot VLI) nu poate fi direct comparat cu 0, și nici nu se poate converti la boolean expresia % a unui VLI. Nu se pot folosi numere unsigned long long pentru verificarea divizibilității unui VLI cu puteri de factori primi, în plus atribuirea unui întreg clasic cu o valoare de tip int VLI nu se poate face, pe câtă vreme la GMP avem mpz_get_ui. De echivalentul lui mpz_get_d ce să zicem, când VLI nu are virgulă mobilă?...
Citirea și scrierea cu fișiere la VLI se face cu C++ (fstream, iostream), dar VLI-urile nu pot fi citite direct din fișiere; trebuiesc folosite șiruri de caractere, dintr-ale căror valori pe digiți trebuie făcută convertirea în cifrele numărului VLI. Adică în loc să F1>>d, unde d este un întreg VLI, trebuie folosit un char *Y pe locul lui d și caracterelor lui d, cu scăderea de 48 pentru obținerea valorii cifrei, unul câte unul li se face transformarea în cifrele VLI-ului. Și tot așa pentru fiecare număr din fișier, destinat să fie VLI.
Așa nu este eficient.
De altfel, reclama că VLI este mai rapid decât GMP-ul nu se aplică operațiilor de divizibilitate, ci doar unor adunări și înmulțiri, eficiența din grafic scăzând pe măsură ce tipul de date este fixat la mai mulți biți (512 maximum), în plus versiunea pare să fi fost veche din 2012, pe când și GMP-ul era mai vechi decât cel disponibil astăzi. Scăderea presupun că este asemănătoare adunării, dar la numere și divizibilitatea ocupă loc important. Acolo, ei au făcut comparație și pe placă video Nvidia Tesla, unde rapiditatea VLI-ului era chiar mai mare față de GMP decât pe procesor (un Xeon de 8 nuclee, folosit probabil în duet, cum se spunea acolo despre 32 de nuclee logice, obținubile din minim 16 nuclee fizice).
Judecând după numele procesorului, un Xeon de tip Sandy Bridge, chiar că pare să fi fost din martie 2012, când eu nici măcar nu trecusem prima dată la GMP, eram cu MIRACL. Este adevărat că pe Tesla VLI-ul putea da de câteva zeci de ori clasă GMP-ului, când pe procesor cea mai bună rație de performanță era sub 4, dar nu mă aflu în postura de a folosi o Tesla pentru numere, procesoarele și RAM-ul (plus discurile) sunt mai departe motoarele mișcării numerice. Nici nu știu dacă în România se poate cumpăra de undeva vreo placă video Tesla.
Dacă VLI-ul ar fi funcționat cu numerele unsigned long long și cu divizibilitatea, oricum funcțiile pentru numere peste 160 de cifre, cu tot cu vectorii și matricile specifice (aferente), inclusiv funcția PURGANTE(), ar fi fost inutile acolo. De asemenea partea de sus a lui GIG160.TXT, indiferent de front (să ne amintim că acum sunt în lucru două fronturi numerice), de la 155 la 160 de cifre, ar fi fost de exclus, 1.34 * 10 la 154 fiind foarte aproape de 2 la 512. GIG52.TXT, cu cele mai mici numere, s-ar fi încadrat la int192 (192 de biți, cum 2 la 128 este sub 10 la 52, care însă este sub 2 la 192). K, E și vectorii C și C1 ar fi fost, desigur, inutili la VLI, și factorii primi unsigned long long (alias gmp_ui) ar fi trebuit să fie folosibili de către întregii (naturalele, de fapt) din VLI.
În loc de aceasta, trebuia să pun numerele prime tot într-un vector de VLI, și neapărat cu același tip (număr fixat de biți) cu al numărului de bază, adică la un int512 citit din GIG trebuia ca și primele să fie așa, când factorii primi de până la CF160.TXT intră în 192 de biți, iar int512 este mai lent decât int192. Mai mult, până la CF160 sunt numai trei numere prime peste 64 de biți, și pot fi deduse din puterea de 2 a numărului citit, așa încât să rămână în vectorul de prime doar restul, intrabile în 64 de biți; dar la un număr de bază de int256 ele trebuie să fie tot de 256, sau 512 la 512, și NU gmp_ui. Am comparat viteza de împărțire a două inturi 128 unul la altul, față de două mepezetele, cu aceleași valori numerice în ambele tabere, și pe lângă mpz_t, int128 stă cumplit de mult.
Așadar, pentru numere, VLI = FIASCO.
*
VLI (Very large integers), o bibliotecă de precizie fixă extinsă în diferite grade, până la 512 biți, cu preferință pentru multipli de 64 de biți (int128, int192, int256, int320, int384, int448 și int512), reglabilă precizie fixă, s-a dovedit a fi un fiasco în încercarea de a o folosi pentru numerele de maxim 154 de cifre, până pe unde încap 512 biți.
Nu dă voie la amestecarea aritmetică cu întregii hardware, la împărțire, operatorul rest nu este suficient de implementat și nici între tipurile proprii nu dă voie la operații de împărțire directă. În plus, împărțirea a două variabile de un același tip int din VLI (fie el și 128, cel mai mic) durează mult mai mult decât când două mepezetele sunt puse așa, darămite decât când o mepezetea se împarte la un întreg clasic.
Restul împărțirii unui întreg VLI la alt număr (tot VLI) nu poate fi direct comparat cu 0, și nici nu se poate converti la boolean expresia % a unui VLI. Nu se pot folosi numere unsigned long long pentru verificarea divizibilității unui VLI cu puteri de factori primi, în plus atribuirea unui întreg clasic cu o valoare de tip int VLI nu se poate face, pe câtă vreme la GMP avem mpz_get_ui. De echivalentul lui mpz_get_d ce să zicem, când VLI nu are virgulă mobilă?...
Citirea și scrierea cu fișiere la VLI se face cu C++ (fstream, iostream), dar VLI-urile nu pot fi citite direct din fișiere; trebuiesc folosite șiruri de caractere, dintr-ale căror valori pe digiți trebuie făcută convertirea în cifrele numărului VLI. Adică în loc să F1>>d, unde d este un întreg VLI, trebuie folosit un char *Y pe locul lui d și caracterelor lui d, cu scăderea de 48 pentru obținerea valorii cifrei, unul câte unul li se face transformarea în cifrele VLI-ului. Și tot așa pentru fiecare număr din fișier, destinat să fie VLI.
Așa nu este eficient.
De altfel, reclama că VLI este mai rapid decât GMP-ul nu se aplică operațiilor de divizibilitate, ci doar unor adunări și înmulțiri, eficiența din grafic scăzând pe măsură ce tipul de date este fixat la mai mulți biți (512 maximum), în plus versiunea pare să fi fost veche din 2012, pe când și GMP-ul era mai vechi decât cel disponibil astăzi. Scăderea presupun că este asemănătoare adunării, dar la numere și divizibilitatea ocupă loc important. Acolo, ei au făcut comparație și pe placă video Nvidia Tesla, unde rapiditatea VLI-ului era chiar mai mare față de GMP decât pe procesor (un Xeon de 8 nuclee, folosit probabil în duet, cum se spunea acolo despre 32 de nuclee logice, obținubile din minim 16 nuclee fizice).
Judecând după numele procesorului, un Xeon de tip Sandy Bridge, chiar că pare să fi fost din martie 2012, când eu nici măcar nu trecusem prima dată la GMP, eram cu MIRACL. Este adevărat că pe Tesla VLI-ul putea da de câteva zeci de ori clasă GMP-ului, când pe procesor cea mai bună rație de performanță era sub 4, dar nu mă aflu în postura de a folosi o Tesla pentru numere, procesoarele și RAM-ul (plus discurile) sunt mai departe motoarele mișcării numerice. Nici nu știu dacă în România se poate cumpăra de undeva vreo placă video Tesla.
Dacă VLI-ul ar fi funcționat cu numerele unsigned long long și cu divizibilitatea, oricum funcțiile pentru numere peste 160 de cifre, cu tot cu vectorii și matricile specifice (aferente), inclusiv funcția PURGANTE(), ar fi fost inutile acolo. De asemenea partea de sus a lui GIG160.TXT, indiferent de front (să ne amintim că acum sunt în lucru două fronturi numerice), de la 155 la 160 de cifre, ar fi fost de exclus, 1.34 * 10 la 154 fiind foarte aproape de 2 la 512. GIG52.TXT, cu cele mai mici numere, s-ar fi încadrat la int192 (192 de biți, cum 2 la 128 este sub 10 la 52, care însă este sub 2 la 192). K, E și vectorii C și C1 ar fi fost, desigur, inutili la VLI, și factorii primi unsigned long long (alias gmp_ui) ar fi trebuit să fie folosibili de către întregii (naturalele, de fapt) din VLI.
În loc de aceasta, trebuia să pun numerele prime tot într-un vector de VLI, și neapărat cu același tip (număr fixat de biți) cu al numărului de bază, adică la un int512 citit din GIG trebuia ca și primele să fie așa, când factorii primi de până la CF160.TXT intră în 192 de biți, iar int512 este mai lent decât int192. Mai mult, până la CF160 sunt numai trei numere prime peste 64 de biți, și pot fi deduse din puterea de 2 a numărului citit, așa încât să rămână în vectorul de prime doar restul, intrabile în 64 de biți; dar la un număr de bază de int256 ele trebuie să fie tot de 256, sau 512 la 512, și NU gmp_ui. Am comparat viteza de împărțire a două inturi 128 unul la altul, față de două mepezetele, cu aceleași valori numerice în ambele tabere, și pe lângă mpz_t, int128 stă cumplit de mult.
Așadar, pentru numere, VLI = FIASCO.
(Editare în miercurea de 24 ianuarie din 2024: Am revăzut codul pentru VLI, care era valabil și în ianuarie 2018 pe un repository de Github, și am realizat că totuși are și compatibilitate cu întregii pe 64 de biți și niște operații aritmetice potrivite pentru lucrul la numere, pe scurt o serie de detalii pe care NU le văzusem atunci, în 2018. Așa că poate că până la urmă și VLI merită o încercare nouă. Seamănă oarecum cu CGBN-ul pentru CUDA, care însă s-a dovedit a fi dezamăgitor, am mai documentat asta și încă mai trebuie să documentez - o nouă reformă numerică de talia lui PUTERNUM s-a pus la punct în iarna lui 2024.
Deocamdată, știm că sunt importante mai departe memoria mare, forța de procesare și spațiul de stocare - cu amendamentul că nu mai trebuie chiar înotat în terabaiți ca în 2017-2019 la 2021 și că nu se mai folosesc hard disk-uri, ci NVME-uri, și în plus nici nu se mai lucrează cu fondul 2 numeric, ci cu fondul 1 și sisteme de fișiere pentru coeficienții de legătură, care ocupă eminamente spațiu pe disc, dar nu chiar cât o făceau numerele de fond 2 mai anii trecuți. Asta mai trebuie să documentez, că am pus la punct un veritabil sistem de fișiere astă-iarnă, și pentru C cu GMP, și pentru CUDA cu CGBN. Dar VLI-ul, așa limitat pentru 512 biți binari cum este el, ar merita și el încă o șansă, cu noua descoperire a operațiilor sale aritmetice. La VLI nici nu ar fi nevoie de factorii de tip E, iar plajele de numere prime componente s-ar încadra integral în 64 de biți nativi, sub calibrul lui CFV160.TXT. Aș putea chiar face o singură astfel de plajă, una care să includă direct toate numerele prime care suportă numerele mai mici de 2 la 512 al căror raport fracționar ireductibil suma divizorilor/număr are numitorul cel mult egal cu 10. Și adaptarea pe VLI cu C++, măcar la un nivel minim de test concludent, cu compararea rapidității față de GMP, care oricum a mai avut versiuni noi între timp, pe câtă vreme VLI este mai veche și mai nebăgată în seamă chiar și decât CGBN-ul. Tot VLI mai pretinde și o anumită compatibilitate cu CUDA, dar nu cred că are suita suficientă de operații aritmetice pentru numere, aceea trebuie încercată pe partea de CPU.
De fapt, stai! La o privire mai atentă a reprivirii, VLI-ul tocmai și-a re-arătat limitele: nu acceptă operatorii rest și împărțire cu întregii elementari, operații necesare și ele la numere, și, dacă nu suntem atenți la directivele de afișare cu hexa, se afișează mereu în C++ în format hexa, nu zecimal. Trebuie evitată sau comentată sintaxa de hexa de afișare, cout<<hex, ca să vedem mereu forma zecimală a numerelor.
Acestea sunt detalii de bază care compromit VLI-ul ca ipoteză, și așa restrânsă, de lucru nou cu numerele, redocumentând ce am găsit în 2018. CGBN-ul a fost mai gentleman decât tine, VLI!)
Comentarii
Trimiteți un comentariu