Reziduu modulo 2s-1
La programarea în procesoare mai vechi, în cazul în care numerele de înmulțire și împărțire au fost efectuate lent, programatorii au recurs la truc pentru a accelera calcule. Deci, biți truc pentru a obține restul împărțirii cu număr egal cu puterea exactă a două, rămâne relevantă astăzi. Tipul de operațiune a # 038; ((1< Să sunt de acord că s> 1 și un număr întreg. Este necesar să se calculeze și mod (2 s -1). Orice număr întreg non-negativ poate fi descompus într-o sumă Prin urmare, un mod (2 s -1) pot fi reprezentate ca Ultima egalitate este posibilă în virtutea faptului că 2 s ≡ 1 mod (2 s -1). Formula rezultată conduce la un calcul recursiv rest algoritm: calculat un mod (2 s -1). Avem nevoie pentru a calcula restul unui. deplasat spre dreapta prin s biți, apoi adăugați bitul inferior s la rezultatul sumei și apoi să ia din nou restul divizării cu 2 s -1. Această operație trebuie efectuată atâta timp cât suma rezultată este mai mică sau egală cu 2 s -1. Algoritmul poate fi reprezentat în mod diferit: diviza reprezentarea bit a numerelor de pe părțile s biți, și le rezuma ca numere, și apoi la valoarea rezultată a aplicării aceleiași operațiuni, atâta timp cât această valoare este mai mare decât împărțitorul. De exemplu, să s = 3. Se calculează restul împărțirea numărului de 100 (10), prin 7. În acest scop, 100 descrie numărul în cod binar, bitul împarte în trei părți: Compute: 100 Mod 7 = ((7 mod 12) + 4) = mod 7 (1 + 4 + 4) mod 7 = 9 mod 7 = [ca 9 = 1 | 001 (2)] = 1 + 1 = 2. Există puține probleme atunci când numărul inițial este egal cu un 2 s -1. algoritmul nu funcționează, precum și necesitatea de a dezasambla caz separat. Adică, dacă am vrut să conta 7 mod 7, care ar avea 7 astfel încât aceste rezultate ar trebui să fie resetat manual. Teoria de mai sus face posibilă pentru a găti un program de exemplu simplu: Numărul x - este numărul inițial, acesta va fi același rezultat. Numărul z - susține că după numărarea nu este necesară. Când te uiți la acest cod, este imediat clar că este inutil în practică. Pe procesoarele moderne de operare divizare nu este la fel de lent pentru a juca un astfel de buclă imbricată. cel puțin în acele probleme pe care le-am avut în a decide dacă procedura se pierde funcționarea normală diviziune. Și dacă luăm în considerare faptul că compilatoare moderne sunt în măsură să înlocuiască diviziunea de 2 s -1 la operațiunile de biți, cu toate că acest lucru nu este întotdeauna un lucru bun, este mai bine să nu-i rezista. Puteți verifica pentru tine, cu acest cod va pierde. O altă conversație începe atunci când numărul S este cunoscut în prealabil (și de obicei este). Chiar mai bine, atunci când aceasta este o putere a lui doi. În acest caz, bucla interioară a procedurii noastre poate fi înlocuită printr-o serie de schimburi de biți și adăugiri și operații. Există truc cunoscut proiectat pentru a contoriza numărul de biți de date într-un număr binar. Presupun că această metodă de numărare vă sunt bine cunoscute. Deci, o mică modificare îi va permite să ia în considerare nu biți, și cantitatea de numere s-bit în afara numărul inițial o. De exemplu, dacă s = 8. bucla interioară merge, există doar aspectul: Puteți merge mai departe și să dovedească faptul că numărul de iterații ale acestui ciclu va fi cu siguranță mai mică decât unele limite (depinde de problema fiind rezolvată). Acest lucru va permite de a implementa în mod repetat ciclu. Competiția de calcul a matricei inverse modulo numărul s = 31. cu toate acestea, se știe că numărul inițial nu depășește 62. 2 făcând posibilă, de asemenea, pentru a elimina bucla interioară, înlocuindu-l cu o operație minoră treizeci și un bit de un bit de treizeci. Astfel, bucla exterioară nu mai mult de două iterații, dintre care a doua operează deja numere pe 32 de biți, dar nu pe 64 de biți face. Poate cineva va reuni pentru a face experimente pe scară largă pentru a testa eficacitatea metodei în practică? Apoi, după compilarea unui program, asigurați-vă că compilatorul a plecat div instruire la locul unde trebuia să fie, și nu sunt aplicate cu codul instrucțiunilor dvs. SSE, în caz contrar, comparația nu este destul de corect. Așa cum am spus mai sus, compilatoare moderne au introdus un astfel de truc pic pentru a împărți cu o putere de doi minus unu, dacă ei știu dinainte că divizorul este de acest tip și „a decis“ că, în acest caz, va fi mai rapid decât orice alte metode de echilibru de calcul (de exemplu, prin intermediul numerelor de diviziune de tip float). Aceasta este, atunci când testarea, asigurați-vă că testul este ceea ce vrei. Eu nu a efectuat astfel de experimente, dar pot spune că truc este util ca viteze de până într-adevăr programul. De exemplu, în concursul menționat mai sus „cap-la“ versiune a lui Gauss a lucrat aproximativ 2400, iar dacă înlocuim funcționarea de a lua funcția de echilibru Articole de discuții pe forum, în acest thread.
P = (1 P; x = z)
pentru (z = 0; x; x >> = s)
z + = x P;
if (x == P)
x = 0;
pentru (z = x; x> P; x = z) z = (z # 038; 0x00FF00FFu) + ((z >> 8) # 038; 0x00FF00FFu);
z = (z # 038; 0x0000FFFFu) + (z >> 16);
>
if (x == P)
x = 0;
int Mod (Int64 x) int32u z;
z = int32u (x # 038; P) + int32u (x >> 31);
z = (z # 038; P) + (z >> 31);
if (z == P)
return 0;
int return (z);
>
In timp ce de lucru imediat redus la 1200 de secunde.
Desigur, efectul maxim este atins prin rescrierea în asamblare, dar asta e altă poveste. Acest articol presupune că nu aveți acces la programare de nivel scăzut.