Rechnen mit sehr großen Zahlen – Very Large Integer
Programmiersprachen sind in der Darstellung von Zahlen auf gewisse Zahlenbereiche eingeschränkt. So ist der größte ganzzahlige Zahlenbereich in C# ulong im Bereich [0 bis 18.446.744.073.709.551.615] (Vorzeichenlose 64-Bit-Ganzzahl) und in Delphi Longword im Bereich [0..4294967295] (32 Bit, ohne Vorzeichen).
Doch was tun wenn man größere Zahlen benötigt?
So verwendet z.B. der RSA Algorithmus (Verschlüsselung von Daten) Primzahlen mit einer Länge von 100 oder mehr Stellen. Nun man programmiert sich einfach einen neuen Zahlentyp. Eine beliebige große Zahl wird einfach in einem Array abgelegt, das im Prinzip so groß werden kann, bis das RAM erschöpft ist. Ich verwende hier in C# den Zahlentyp int im Bereich [-2.147.483.648 bis 2.147.483.647] (32-Bit-Ganzzahl mit Vorzeichen), und in Delphi den Typ integer.
In nachfolgender Grafik sehen Sie wie eine größere Zahl gespeichert wird.
In jedem Arrayeintrag werden aber nur 9 Stellen gespeichert. Der Grund ist ein einfacher: Bei einer Addition könnte man auf die Zahl 3.000.000.000 oder größer stoßen, die aber nicht mehr im Zahlentyp int abspeicherbar wäre. Eine Exception des Programms wäre die Folge. Daher werden nur die besagten 9 Stellen abgelegt und alles darüber im nächsten Eintrag abgelegt.
Hat man das Abspeichern der Zahlen erledigt, muss man die 4 Grundrechnungsarten programmieren (Addition, Subtraktion, Multiplikation und Division). Und ab dann kann man schon rechnen. Für aufwendigere Rechnungen wird man wohl zwangsläufig noch diverse Rechenoperation definieren müssen, aber das hängt von der Anwendung ab.
Hier einige erste Ergebnisse:
- 126346514354126346413286858162654265463518458524 mod 24535663546 = 3244341727
Rechendauer: 100 ms C# - 1263452048 = 97 927 882 155 145 956 512 208 976 170 017 531 066 671 281 426 057 444 710 741 879 235 869 801 743 616 462 116 705 947 660 243 987 697 249 847 925 192 149 283 010 071 974 422 132 313 365 288 007 966 893 770 956 128 037 623 235 500 485 268 235 100 901 602 430 176 042 928 459 542 457 326 430 925 805 623 903 340 672 175 736 156 847 218 799 824 959 618 867 350 224 096 689 679 386 732 957 883 540 341 861 502 769 007 249 297 954 707 171 369 566 323 352 226 114 149 763 212 774 265 254 562 173 808 600 182 747 570 126 066 847 659 474 351 078 177 903 965 730 435 184 529 821 146 503 148 228 938 599 856 018 177 554 009 466 793 866 162 596 323 957 656 602 811 493 675 655 114 295 721 935 000 421 759 416 435 248 491 270 513 746 425 762 502 479 785 697 464 766 266 777 846 078 745 646 812 551 117 195 150 591 531 029 742 475 823 994 752 825 688 632 865 306 084 008 419 746 993 848 185 055 897 222 918 061 229 056 239 478 956 177 460 035 626 572 740 017 988 875 298 508 603 166 735 005 566 608 854 191 845 687 563 150 657 496 191 023 195 164 888 285 102 667 749 643 380 632 796 122 761 100 610 056 760 090 285 529 052 122 206 045 615 608 503 925 059 961 094 407 501 623 293 235 754 541 557 666 771 983 335 884 080 876 437 035 863 297 176 223 816 425 939 882 246 590 709 438 448 450 855 294 950 518 043 438 579 418 238 774 716 147 450 051 960 440 837 562 065 851 971 725 019 747 612 770 411 015 921 534 521 885 054 543 292 898 814 676 969 098 728 187 544 696 798 786 989 913 585 878 974 612 687 416 241 640 607 239 023 590 201 629 201 281 623 036 746 329 016 060 575 063 536 495 133 292 011 599 701 025 234 355 093 981 958 834 397 164 309 037 776 923 953 791 532 939 738 003 016 251 769 881 104 812 563 061 447 950 686 000 601 464 456 505 524 812 808 223 029 243 326 758 001 860 946 096 781 749 919 628 476 472 388 283 717 350 002 297 233 680 928 943 294 666 056 589 748 449 665 211 517 490 586 526 585 473 775 758 100 099 317 126 797 411 038 626 517 319 601 248 635 563 244 497 124 855 027 709 376 968 721 407 244 722 429 874 544 970 866 146 533 152 695 647 271 775 087 345 043 300 420 933 143 676 781 601 601 562 000 108 566 507 292 655 809 101 501 862 460 513 086 554 673 729 018 954 118 054 830 114 307 036 635 699 903 536 263 826 741 683 964 238 510 720 788 388 307 809 779 349 762 761 782 475 651 935 379 362 576 902 253 768 422 461 384 668 056 986 315 335 737 305 098 585 136 468 481 760 494 852 378 923 632 275 690 501 656 916 718 427 051 950 551 118 841 450 956 063 449 255 300 433 573 954 150 143 047 723 713 741 227 253 970 539 276 622 614 955 253 885 908 548 141 278 347 872 600 918 335 271 222 441 680 712 362 666 298 225 445 929 635 758 860 002 877 470 911 214 662 279 471 452 051 019 451 316 322 813 500 375 129 320 641 885 170 790 394 245 924 425 475 351 446 697 500 424 115 595 194 552 703 205 860 592 495 082 195 628 427 006 302 951 642 744 298 971 388 224 279 596 914 401 091 679 640 415 375 374 432 226 114 939 224 251 546 495 317 170 513 914 208 714 620 362 626 936 823 237 926 676 357 294 064 032 191 265 011 216 401 490 024 179 203 171 713 104 395 922 960 171 163 759 696 185 237 623 332 920 509 440 954 795 029 771 960 305 332 630 265 315 573 064 852 666 035 716 363 129 689 024 284 377 202 473 674 823 114 692 169 518 776 340 332 335 665 647 057 159 034 440 149 534 841 755 296 276 805 153 873 151 255 089 517 627 344 522 550 909 581 687 555 926 292 256 908 336 699 845 363 262 250 771 836 875 440 186 544 898 261 982 983 369 272 223 562 596 529 507 104 186 646 459 145 789 061 698 414 798 625 576 070 802 325 204 407 593 321 413 421 983 511 353 484 940 219 329 740 073 306 376 350 659 583 772 757 792 208 064 978 846 853 759 084 881 852 121 758 283 878 608 256 232 230 240 171 587 624 313 475 953 783 253 648 819 373 272 861 420 559 456 266 890 364 787 144 952 465 799 154 299 379 028 784 524 267 603 903 565 260 161 587 135 943 211 305 746 238 506 185 585 146 595 831 426 713 261 868 427 677 774 963 340 863 462 135 675 425 697 132 825 832 629 218 056 907 330 615 947 349 057 489 690 763 778 214 220 073 028 901 298 513 706 623 092 677 922 592 101 655 654 923 774 507 975 361 654 522 809 639 039 152 495 310 612 346 150 573 889 699 323 185 325 546 207 436 929 794 274 232 564 447 903 570 689 008 142 901 740 915 779 995 892 726 097 343 183 876 432 356 009 874 578 492 896 055 699 138 440 992 003 488 500 459 629 032 436 601 356 776 696 073 563 900 176 623 702 071 051 965 391 322 205 338 768 205 943 477 565 794 339 995 213 360 019 292 284 069 055 763 770 137 172 623 276 436 981 649 482 877 607 831 475 811 445 564 352 785 415 301 267 919 930 491 070 005 128 355 002 202 811 470 466 874 581 629 861 366 701 549 922 272 072 135 922 351 904 418 378 535 373 124 258 416 123 285 504 551 661 642 752 796 623 458 039 312 104 616 679 447 900 930 385 802 656 719 335 496 571 521 085 619 942 322 883 814 616 720 156 157 658 594 987 172 967 186 044 128 576 248 138 664 126 125 913 619 986 342 654 610 497 169 453 548 534 917 938 119 329 735 484 531 789 588 414 683 797 273 572 378 381 821 785 165 549 561 638 633 429 332 055 806 618 408 901 609 904 062 137 705 216 832 159 018 328 033 246 703 538 981 770 907 363 653 622 960 351 216 769 597 722 967 072 732 619 609 281 582 319 198 727 984 926 142 267 176 393 748 030 354 556 712 919 071 973 731 193 598 780 660 892 159 599 634 898 373 098 373 475 501 619 534 287 935 091 937 158 874 905 681 745 617 698 221 066 223 546 882 376 058 147 121 802 273 537 456 284 326 374 127 950 239 451 428 192 000 598 422 096 665 678 094 015 694 742 628 445 816 820 860 233 998 723 808 357 247 488 184 493 257 678 611 297 994 391 386 810 853 484 203 582 624 384 103 990 929 563 811 278 929 896 171 002 202 050 623 473 982 904 584 420 801 736 243 594 951 680 828 603 248 940 654 863 674 893 732 852 895 091 041 740 259 427 590 673 982 233 500 835 490 105 278 150 747 102 587 218 572 937 362 082 506 294 120 827 007 318 106 790 093 288 913 110 386 432 564 039 245 537 185 623 897 174 685 438 590 732 671 192 039 265 676 149 091 330 612 416 324 005 429 875 734 829 044 681 309 364 189 358 647 172 490 522 100 441 841 365 695 722 505 090 610 911 893 660 450 362 217 731 140 765 160 562 605 949 039 967 826 610 869 638 568 385 482 236 641 349 820 702 275 463 025 558 977 097 424 278 704 379 346 363 605 804 662 075 944 883 923 988 839 584 253 238 733 798 115 470 500 328 745 076 068 785 227 956 877 617 064 443 844 346 515 276 342 056 843 857 327 172 258 235 281 400 610 408 272 351 503 072 498 754 578 921 272 349 278 799 899 005 128 735 925 376 705 019 432 207 222 699 963 066 291 326 536 833 928 167 172 441 993 824 592 760 324 977 516 071 602 149 736 196 382 254 464 886 384 974 863 211 392 847 783 697 718 970 761 485 377 208 598 508 478 236 912 900 625 206 123 628 679 543 324 117 063 208 441 804 383 201 664 517 997 619 427 740 417 320 637 550 638 008 650 340 601 911 233 085 584 982 227 442 841 142 588 101 570 798 952 859 104 793 901 859 497 031 762 099 902 694 774 877 631 463 606 055 562 444 025 816 866 290 200 969 696 606 254 191 848 602 758 232 579 569 587 319 616 128 557 542 908 082 821 130 032 076 809 574 579 430 884 976 648 017 993 341 871 380 217 403 660 879 932 472 824 552 531 239 399 573 771 940 822 598 381 450 017 571 015 563 633 424 948 802 658 364 989 965 605 057 186 905 192 923 260 485 226 943 219 795 671 110 388 143 124 449 274 750 940 841 482 370 726 832 501 055 423 070 450 951 166 382 043 802 825 864 195 412 535 175 569 019 412 316 364 179 043 847 967 946 844 852 434 146 811 049 251 173 120 301 583 841 382 983 765 547 045 674 739 834 457 469 080 319 428 925 503 143 396 426 639 498 793 382 053 298 381 543 376 636 368 064 555 707 171 751 948 128 705 961 679 742 079 317 744 355 267 531 198 428 435 172 307 213 161 607 072 649 912 271 368 399 163 479 086 530 847 185 491 044 247 504 199 823 005 758 106 124 794 691 551 341 585 107 362 383 337 294 048 789 030 319 811 749 768 345 663 002 488 669 903 793 436 735 720 940 301 265 450 426 575 156 960 812 414 124 378 610 350 377 756 523 991 794 711 972 098 664 099 865 408 338 499 140 498 497 665 468 438 024 443 466 983 622 393 215 749 259 206 275 245 121 659 972 063 130 616 101 062 969 065 512 357 151 715 327 656 616 462 463 858 815 551 249 472 325 856 089 091 711 176 232 084 581 473 315 944 859 768 315 037 852 233 961 631 997 158 974 797 628 044 125 568 638 288 019 976 943 968 123 026 171 508 234 447 756 800 681 655 786 660 126 520 123 471 608 217 699 761 839 842 768 561 634 828 259 530 982 806 666 727 852 760 060 765 573 900 798 695 092 902 979 692 445 686 298 606 159 819 433 396 999 151 709 684 544 143 956 329 695 242 953 434 661 104 552 883 324 709 717 425 570 019 933 293 833 086 773 731 989 109 170 478 114 796 917 250 655 822 887 277 152 156 434 025 733 610 889 750 557 540 791 114 800 652 817 929 349 257 323 280 804 122 453 358 188 474 438 314 420 630 970 454 535 854 980 562 119 227 000 945 654 415 428 381 311 469 784 498 080 800 554 727 531 323 076 832 692 145 330 415 951 614 228 648 995 106 337 373 738 376 058 230 543 709 815 873 359 071 979 634 807 050 475 592 405 681 516 456 859 748 288 899 923 078 341 075 727 932 744 231 984 876 878 100 679 182 446 293 947 088 458 184 501 771 141 653 317 143 216 009 595 388 918 268 352 526 960 159 181 101 573 171 767 661 525 045 759 578 412 070 337 991 520 493 797 563 778 682 521 850 840 257 428 230 099 364 115 396 319 674 846 612 267 041 901 688 693 988 952 403 472 919 117 223 332 386 929 482 814 728 872 760 039 998 644 441 566 555 675 724 118 236 737 068 824 707 865 759 345 603 368 325 197 329 877 557 741 303 018 594 631 416 526 225 163 298 498 103 979 664 578 494 873 383 465 464 077 286 523 481 696 335 537 661 135 065 173 851 055 263 315 790 225 519 143 710 079 336 156 586 175 189 139 144 566 525 048 404 327 792 792 107 672 468 954 291 319 485 644 571 339 864 532 514 631 624 276 247 520 617 560 403 722 437 960 746 007 868 092 313 945 802 708 447 479 072 359 487 970 299 745 932 671 396 961 818 004 371 559 883 919 023 343 117 722 722 685 575 596 560 720 989 028 021 105 291 628 001 569 305 892 001 588 656 573 694 204 650 560 185 020 518 702 972 666 933 208 891 944 710 315 273 279 940 846 373 007 880 458 656 317 385 180 015 543 853 932 976 564 531 452 010 379 586 017 983 625 982 398 150 557 742 345 858 526 898 929 211 376 549 410 059 810 395 704 935 547 707 809 088 216 170 793 839 286 959 371 570 095 078 076 591 119 280 439 349 169 743 607 386 957 579 180 328 174 827 469 614 443 184 274 119 779 243 574 038 734 842 341 550 835 493 508 022 835 454 087 766 579 596 479 224 152 868 969 628 534 037 759 004 792 476 398 443 195 321 764 456 738 793 128 593 060 921 187 242 145 580 330 492 657 903 184 326 657 571 402 543 317 751 833 935 847 155 377 890 627 468 648 999 181 997 362 257 383 014 414 122 346 789 605 838 550 088 940 308 822 195 040 045 337 712 166 844 228 945 328 051 704 601 848 537 456 725 184 997 604 863 075 324 895 825 401 212 507 352 773 039 519 549 283 627 773 638 414 979 503 939 758 465 785 414 124 289 284 141 066 443 319 945 092 082 912 527 198 221 240 300 153 853 698 883 369 385 596 003 993 757 189 364 257 083 765 365 867 550 026 017 127 981 885 632 411 031 240 723 665 096 583 497 890 474 006 435 766 888 276 873 627 117 634 767 119 752 400 587 950 902 005 894 355 421 403 545 484 164 981 032 976 751 655 597 659 817 291 077 708 701 994 227 657 711 553 933 472 719 942 028 268 798 646 421 612 630 672 108 761 153 112 631 657 641 869 216 861 789 889 318 245 316 938 833 551 553 369 986 196 633 880 960 764 503 138 730 292 687 979 154 599 188 690 465 583 993 206 832 630 897 379 845 720 482 089 805 958 264 061 535 515 348 408 529 343 771 507 535 356 328 346 227 838 437 634 144 331 971 340 881 184 769 010 356 848 321 117 032 671 780 699 425 642 428 456 419 399 507 027 468 999 883 952 220 339 475 748 106 251 019 629 042 240 456 176 027 395 112 469 950 858 040 434 996 033 687 704 042 638 082 524 954 998 947 431 441 731 776 068 533 222 129 757 996 447 520 966 304 234 788 895 942 625 582 689 769 544 401 951 462 958 515 246 263 649 699 580 408 120 607 517 159 559 748 558 997 937 844 784 948 032 760 494 239 479 784 475 333 426 254 317 604 645 858 658 861 145 582 173 405 125 623 711 638 528 956 404 286 048 950 991 060 341 454 428 642 445 896 005 669 141 846 046 576 306 065 592 958 051 495 279 924 197 215 852 050 812 517 943 720 784 826 264 331 676 208 156 640 136 365 123 575 079 139 797 732 363 289 184 630 874 146 277 316 760 179 693 731 381 586 095 005 800 913 544 076 537 971 345 514 987 112 529 098 012 329 121 659 224 147 769 092 557 526 720 477 328 167 291 691 154 697 033 876 987 286 152 564 032 423 361 770 033 351 072 114 552 069 766 584 810 093 250 986 909 404 035 976 617 163 560 523 855 832 272 236 476 741 212 597 840 245 606 469 197 360 195 834 754 439 176 819 386 103 243 633 132 954 969 892 492 837 515 376 985 974 381 087 342 205 862 915 042 922 737 071 633 614 082 116 792 361 413 910 987 285 013 059 741 504 078 517 853 979 207 939 101 687 558 191 050 029 974 703 925 342 018 149 208 489 101 692 304 998 939 539 172 073 656 979 972 180 386 832 223 924 921 324 400 002 980 303 657 240 825 509 648 893 650 941 893 356 678 125 829 764 947 340 846 697 133 656 109 822 555 023 613 202 836 560 870 376 861 242 082 718 629 905 015 739 160 230 241 484 236 550 834 029 178 130 825 642 199 019 335 270 126 406 450 570 138 671 242 492 029 445 459 516 041 600 434 132 562 877 398 694 183 380 620 102 581 892 263 943 930 789 829 753 209 141 102 805 215 042 241 671 267 001 600 370 171 560 600 896 957 900 140 660 733 473 856 131 511 131 478 797 272 792 151 607 397 402 543 707 463 655 538 452 619 634 348 122 588 555 627 346 560 003 882 954 788 997 434 177 789 600 379 077 354 495 987 726 870 364 351 229 421 101 835 684 493 739 469 782 273 216 591 743 648 481 691 062 856 755 189 012 179 159 641 820 097 097 932 997 419 576 664 337 939 173 923 659 567 681 615 943 618 721 881 877 606 075 125 847 105 367 353 695 644 498 619 149 996 045 118 999 887 790 778 302 587 568 759 918 212 890 625
Rechendauer: 126 ms C#
TestVLI.zip
75 KB
mit den entsprechenden Klassenbibliotheken
