.Net 4.0: BigInteger klass
31.05.2009 | Gunnar
Minu eelmine kanne rääkis Fibonacci arvude genereerimisest. Käesolevas kandes astume sammu edasi ja vaatame, kuidas .Net Framework 4.0 aitab meil lahendada järgmise probleemi, millega me kiiresti kasvavate väärtusega algoritmide juures kokku puutume – täisarvu puhvri suuruse ületamine. Järgmises versioonis tuleb meile appi selline klass nagu BigInteger.
Sissejuhatuseks olgu antud eelmisest kandest päris “lame” funktsioon Fibonacci arvude genereerimiseks. See funktsioon teeb arvutused ära siva ja seega on ta igati sobiv katsejänes selle kande jaoks.
{
var previousValue = -1;
var currentResult = 1;
for (var i = 0; i <= x; ++i)
{
var sum = currentResult + previousValue;
previousValue = currentResult;
currentResult = sum;
}
return currentResult;
}
| Sisend |
Tegelik |
Eeldatav |
|
40 |
102334155 |
102334155 |
|
41 |
165580141 |
165580141 |
|
42 |
267914296 |
267914296 |
|
43 |
433494437 |
433494437 |
|
44 |
701408733 |
701408733 |
|
45 |
1134903170 |
1134903170 |
|
46 |
1836311903 |
1836311903 |
|
47 |
-1323752223 |
2971215073 |
|
48 |
512559680 |
4807526976 |
|
49 |
-811192543 |
7778742049 |
|
50 |
-298632863 |
12586269025 |
Kui eelmises kandes me ootasime ära, millal üks versioonidest mõttetult aeglaseks muutub, siis käesolevas kandes ootame ära, millal funktsioon hakkab vääraid tulemusi andma. Piisab sellest, kui võtame sisendite vahemikuks 40 kuni 50.
Alates sisendist 47 muutuvad tulemused erinevaks. Täisarvu puhver 32-bitise arhitektuuriga arvuti peal saab ületatud ja “ring” hakkab uuesti negatiivsete väärtuste poolt pihta. Seega alates 47-st meie funktsioon meile enam adekvaatseid tulemusi ei anna. Kuigi 64-bitise arhitektuuri korral on täisarvude jaoks rohkem ruumi ettenähtud, jõuab sealgi lagi päris kiiresti kätte, kui funktsiooni väärtused kasvavad kiiresti. Ja ei pruugi meid aidata ka long integer kasutamine.
Meie omast kiiremini kasvavad näiteks y=x! (faktoriaal) ja y=xx. Seega mängimine lihtsalt suuremate arvude peal tavatüüpidega pole hea lahendus. Vaja on mingit sellist tüüpi, mis kannataks ära suvalise suurusega täisarvud ning siinkohal tuleb meile appi uus klass.
BigInteger klass
.Net Framework 4.0 pakub meile lahenduseks välja nimeruumis System.Numerics asuva klassi BigInteger. BigInteger klassi jaoks on defineeritud kõik olulisemad operaatorid. Kes soovib, et koodis oleks paremini arusaadav, kus BigInteger mängus on, võib kasutada klassi staatilisi meetodi suurte arvudega tehete tegemisel.
Järgmiseks viime oma Fibonacci arvude genereerimise funktsiooni üle BigInteger klassile. Kood näeb välja selline.
Suuri täisarve kasutades hakkab meie Fibonacci arvude genereerimise funktsioon andma korrektseid tulemusi.
Lõpetuseks veel paar sõna. Oma olemuselt on BigInteger struktuur. Seega sarnaneb ta teistele arvudele, olles value type. Lähemat lugemist leiab MSDN Library artiklist BigInteger Members.