lördag 19 september 2015

Stora tal

Det finns ett mycket roligt klipp med karaktären Ali G där han ställer sig frågan om en dator någonsin kan räkna ut ett väldigt stort godtyckligt tal. Han får svaret att alla räkneövningar han kan nämna, kan räknas ut av en modern dator. Din miniräknare kommer förmodligen slå i taket när talen blir för stora, men en vanlig PC med Windows kan ge dig precis vilket svar som helst. Det krävs lite trixande under skalet för att få detta att fungera.

Heltal representeras normalt av en bit-struktur, alltså ett antal ettor och nollor. Ett 32-bitars heltal är ett heltal som beskrivs av 32 bitar (4 bytes). Bitrepresentationen är liknar binärrepresentationen av ett tal, vilket innebär att både bitrepresentationen av talet 8 och binärrepresentationen av talet 8 är 1000. Ju större tal man vill beskriva, desto fler bitar behöver man ha, och förr eller senare slår man i taket.

Men det finns en struktur i Windows som heter BigInteger som inte har någon begränsning när det kommer till heltalsrepresentationer och heltalsberäkningar. Det beror på att talen internt lagras som en teckensekvens istället för som ett bitmönster, där varje tecken i sin tur representeras av ett begränsat bitmönster. Då blir det hela en fråga om hur många tecken som får plats i minnet, vilket är väldigt många. För att få se vad BigInteger-strukturen kan göra, kan man skriva in en enkel kod i PowerShell som dubblerar ett tal ett antal gånger. Om jag börjar med talet 1 och dubblar det så får jag 2. Dubblar jag det så får jag 4, 8, 16, 32, 64, 128, 256, och så vidare. Ganska snart blir talet väldigt stort. Redan efter blott 100 dubbleringar landar man på talet 2 535 301 200 456 458 802 993 406 410 752 vars binära representation skulle bli väldigt stor. Men i en BigInteger-struktur är detta bara att betrakta som 31 tecken som avkodas till värden i turordning när beräkningar ska göras.

Så utrustade med BigInteger-strukturen kan vi se vad som händer när vi dubblerar ett tal 500 gånger. För att göra detta, skriv:

$x = New-Object System.Numerics.BigInteger 1; for ($i = 0; $i -le 500; $i++) { $x *= 2; Write-Output $x }

PowerShell levererar svaret på ett ögonblick. Talet 1 dubblat 500 gånger ger oss talet 6 546 781 215 792 283 740 026 379 393 655 198 304 433 284 092 086 129 578 966 582 736 192 267 592 809 349 109 766 540 184 651 808 314 301 773 368 255 120 142 018 434 513 091 770 786 106 657 055 178 752, vilket är ett så stort tal att det nästan är omöjligt att läsa ut och förstå. För att underlätta kan man använda scientific notation. Istället för att skriva ut föregående tal i sin fulla längd, kan man skriva:

6,55 * 10150

Eller:

6,55E150

Båda varianterna säger oss att talet börjar på 6 och innehåller 150 siffror till därefter, varav de första nästkommande är 55 (avrundat). Det totala antalet siffror i talet är alltså antalet siffror till vänster om decimalavgränsaren plus talet till höger om E. 151 stycken.

Så hur står sig en etta dubblerad femhundra gånger mot andra stora tal?

Vårt observerbara Universum uppskattas innehålla 1,7 * 1011 (eller 1,7E11) galaxer. Uppskattningsvis finns 1024 (1E24) stjärnor i Universum.

Båda dessa tal är alltså relativt små i jämförelse med den etta vi dubblade femhundra gånger. Hur är det med antalet atomer i vårt observerbara Universum? Faktum är att även det är ett relativt litet tal i detta sammanhang, nämligen 4 * 1080 (4E80), alltså en fyra följt av åttio nollor. 400 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000.

Så låt oss dubbla vår etta femtusen gånger. Även det räknas fram kvickt av PowerShell. Svaret är 282 493 406 427 885 207 367 041 933 403 229 466 733 779 235 036 908 223 362 737 617 171 423 633 968 541 502 511 617 825 263 342 305 274 671 206 416 862 732 165 528 407 676 139 958 676 671 942 371 453 279 846 862 103 555 703 730 798 023 755 999 290 263 414 138 746 996 425 262 647 505 106 222 430 745 688 071 901 801 071 909 721 466 836 906 811 151 133 473 603 131 174 810 929 399 280 998 101 699 398 944 715 801 811 235 142 753 236 456 432 868 426 363 041 983 113 354 252 997 303 564 408 348 123 661 878 478 353 722 682 766 588 036 480 451 677 385 451 192 294 010 288 486 562 150 551 258 990 678 187 626 397 933 471 267 212 659 382 047 684 908 251 671 777 313 746 267 962 574 481 960 017 676 147 336 443 608 528 865 821 788 061 578 040 438 881 156 396 976 534 679 536 477 744 559 804 314 840 614 495 141 020 847 691 737 745 193 471 783 611 637 455 592 871 506 037 036 173 282 712 025 702 605 093 453 646 018 500 436 656 036 503 814 680 490 899 726 366 531 275 975 724 397 022 092 725 970 923 899 174 562 238 279 814 456 008 771 885 761 907 917 633 109 135 250 592 173 833 771 549 657 868 899 882 724 833 177 350 653 880 665 122 207 329 113 965 244 413 668 948 439 622 163 744 809 859 006 963 982 753 480 759 651 997 582 823 759 605 435 167 770 997 150 230 598 943 486 938 482 234 140 460 796 206 757 230 465 587 420 581 985 312 889 685 791 023 660 711 466 304 041 608 315 840 180 083 623 903 760 913 411 030 936 698 892 365 463 484 655 371 978 555 215 241 419 051 756 637 532 976 736 697 930 030 949 995 728 239 530 882 866 713 856 024 688 223 531 470 672 787 115 758 429 874 008 695 136 417 331 917 435 528 118 587 185 775 028 585 687 114 094 178 329 752 966 233 231 383 772 407 625 995 111 380 343 784 339 467 510 448 938 064 950 157 595 661 802 643 159 880 254 674 421 388 754 566 879 844 560 548 121 596 469 573 480 869 786 916 240 396 682 202 067 625 013 440 093 219 782 321 400 568 004 201 960 905 928 079 577 408 670 605 238 675 195 724 104 384 560 742 962 264 328 294 373 028 338 181 834 383 818 752.

I scientific notation skrivs detta tal 2,82 * 101505 eller 2,82E1505. Med tanke på att vi ännu inte närmat oss någon bortre gräns, så kan man lugnt konstatera att den som äger en vanlig PC förvaltar en svindlande räkningskapacitet.

Inga kommentarer:

Skicka en kommentar