大数相除

yangchuanju · 发表于 2024-10-19 16:26

大数竖式相除
在中小学我们都学习过多位数的竖式除法，
对于16位以上的高位除法，在16位数字计算系统中再用直接相除法就得不到精确的数字解了，
为利用16位数字系统中的Excel进行计算，我模仿通用的多位数的竖式除法设计出了一种
高位大数的竖式除法程序——
1、选定要相除的两个大数之后，首先将两个大数从右向左分节，可按每7位（或6位）分成一节。
（因16位数字计算系统只能处理15位有效数字，故每节位数不能超过7节）
2、将被除数、除数分别排列在计算表的第1、第2行，每小节数字占据一个单元格。
3、计算表的第3行用于放置相除的商（试商）。
被除数：a1 a2 a3 a4 a5 a6，除数：b1 b2 b3，商：c1 c2 c3
4、试商一c1——取除数的第1节除以被除数的前2节的整数部分（int(a1*10^7+a2)/b1）；
当b1较小时宜取除数的第2节除以被除数的前3节的整数部分（int(a1*10^14+a2*10^7+a3)/(b1*10^7+b2）。
5、相乘——分别用试商一c1乘以除数的各节，将相乘之积d11=c1*b1,d12=c1*b2,d13=c1*b3放置到第4行的a2 a3 a4之下（空出一个单元格）；
6、进位——由于乘积d11,d12,d13的位数一般都要高于7位，接着需要对乘积进行一次进位处理，
将乘积变成e10,e11,e12,e13多一节的乘积数；
7、相减——分别用a1 a2 a3 a4减去e10 e11 e12 e13，得到差数f10 f11 f12 f13；
若f10是负数则需要手动调减c1，直至差f10=0，f11>0。
8、借位——如果差数f11 f12 f13中有负数则需向上借一个或几个数，使之各个差数都是正数，
借位后的差数变为g11,g12,g13，同时将被除数中的a5复制下来放到g13后，该行各节数字就是下一级的被除数。
9、试商一c2——取除数的第1节除以一级差数的前2节的整数部分（int(g11*10^7+g12)/b1）；
当b1较小时宜取除数的第2节除以一级差数的前3节的整数部分（int(g11*10^14+g12*10^7+g13)/(b1*10^7+b2）。
10、相乘——分别用试商一c2乘以除数的各节，将相乘之积d21=c2*b1,d22=c2*b2,d23=c2*b3放置到第8行的a3 a4 a5之下（空出2个单元格）；
11、进位——由于乘积d21,d22,d23的位数一般都要高于7位，接着需要对乘积进行一次进位处理，
将乘积变成e20,e21,e22,e23多一节的乘积数；
11、相减——分别用g11 g12 g13 a5减去e20 e21 e22 e23，得到差数f20 f21 f22 f23；
若f20是负数则需要手动调减c2，直至差f20=0，f21>0。
12、借位——如果差数f21 f22 f23中有负数则需向上借一个或几个数，使之各个差数都是正数，
借位后的差数变为g21,g22,g23，同时将被除数中的a6复制下来放到g23后，该行各节数字就是下一级的被除数。
13、第3级试商、相乘、进位、相减、借位与第2级试商、相乘、进位、相减、借位方法相同；
14、最后一级借位处理后的差数就是两大数相除后的余数。

yangchuanju · 发表于 2024-10-19 16:27

例
被除数a 40 2386166 7741036 228256 3565610 2100994
除数b 23058 4300921 3693951
试商c 17450 7182477 8390509
相乘d1 —— 402362100 75051071450 64459444950
进位e1 40 2369605 1077895 9444950
相减f1 0 16561 6663141 -9216694 3565610
借位g1 0 16561 6663140 783306 3565610
相乘d2 —— —— 1.65614E+11 3.08913E+13 2.65317E+13
进位e2 —— 16561 6643792 8814488 8096627
相减f2 —— 0 19349 -18031182 -4531017
借位g2 —— 0 19347 1968817 5468983 2100994
相乘d3 —— —— —— 1.93468E+11 3.60869E+13 3.09941E+13
进位e3 —— —— 19346 11965213 9458201 9111059
相减f3 —— —— 1 -9996396 -3989218 -7010065
借位g3 —— —— 0 3603 6010781 2989935

yangchuanju · 发表于 2024-10-19 16:44

大数相除
已知2^61-1=2305843009213693951，是一个19为数字，
可以认为它是一个大整数。
在计算LL检验的余数列时需用它做除数（模数）求余；
当这个大数大于10^15时，在16位数字系统中得不到准确的余数；
在求余过程中需要对上一个余数进行平方操作，平方数不能大于15位，故可按每7位一组分节；
上面例子中的被除数是求余之中的第6级余数，对其进行了分节——平方——进位——试商——相乘——相减等一系列操作，最后得到第7级余数；
按照该程序算下去，至第59级余数为0，表明2^61-1是一个梅森素数。

yangchuanju · 发表于 2024-10-19 16:44

大数相除
已知2^61-1=2305843009213693951，是一个19为数字，
可以认为它是一个大整数。
在计算LL检验的余数列时需用它做除数（模数）求余；
当这个大数大于10^15时，在16位数字系统中得不到准确的余数；
在求余过程中需要对上一个余数进行平方操作，平方数不能大于15位，故可按每7位一组分节；
上面例子中的被除数是求余之中的第6级余数，对其进行了分节——平方——进位——试商——相乘——相减等一系列操作，最后得到第7级余数；
按照该程序算下去，至第59级余数为0，表明2^61-1是一个梅森素数。

太阳 · 发表于 2024-10-21 08:01

素数判断难度大，找不到捷径的方法，找不到正确的素数公式

太阳 · 发表于 2024-10-22 05:28

已知:方程\(a^2+ab+b^2-c＝0\)，有\(n\)组正整数解
整数\(a＞0\)，\(b＞0\)，\(3＞n＞1\)，素数\(p＞0\)
求证:\(c＝p\)
已知:方程\(a^2+ab+b^2-c＝0\)，有\(n\)组正整数解
整数\(a＞0\)，\(b＞0\)，\(m＞1\)，\(n＞2\)，\(t＞1\)，奇数\(c＞0\)
求证:\(c＝mt\)
已知:方程\(a^2+ab+b^2-c＝0\)，有正整数解，\(c＝2^k-1\)，\(c＝mt\)
整数\(a＞0\)，\(b＞0\)，\(m＞1\)，\(t＞1\)，奇数\(c＞0\)，素数\(k＞0\)，\(p＞0\)，\(y＞0\)
求证:\(m＝p\)，\(t＝y\)

太阳 · 发表于 2024-10-22 05:30

方程\(a^2+ab+b^2-c＝0\)，最多有2组正整数解，判断c是素数

太阳 · 发表于 2024-10-22 05:31

已知:方程\(a^2+ab+b^2-c＝0\)，有正整数解，\(c＝2^k-1\)，\(c＝mt\)
整数\(a＞0\)，\(b＞0\)，\(m＞1\)，\(t＞1\)，奇数\(c＞0\)，素数\(k＞0\)，\(p＞0\)，\(y＞0\)
求证:\(m＝p\)，\(t＝y\)

yangchuanju · 发表于 2024-10-22 11:26

用每小节6位的大数相除法，可以求出2^127-1用LL检验法的各级余数，第125级余数等于0，表明2^127-1是一个梅森素数；
但用7位分节时，试商、相乘过程中出现大于10^16的中间数，导致余数不全是准确的，求不出正确结果！
2^127-1=170141183460469231731687303715884105727<39> 0-125级LL检验余数表，第125级余数等于0——
r0 4
r1 14
r2 194
r3 37634
r4 1416 317954
r5 2 5956 546822 746114
r6 4 23861 667741 36022 825635 656102 100994
r7 148 295852 275705 128589 952510 455019 292911
r8 17 934813 421766 634732 12365 957609 373869
r9 85 902463 759488 963702 490017 444612 81724
r10 116 475895 319100 247619 106962 527555 61737
r11 49 976279 66382 381059 963127 566460 774395
r12 160 668395 611328 156886 231636 609761 589125
r13 94 281146 402315 220816 856494 248417 316624
r14 108 7687 823445 325965 842618 64742 685120
r15 31 734492 925565 95550 179541 226941 707640
r16 40 502963 312906 587195 23713 454534 295598
r17 94 88105 965254 764875 368473 681747 882892
r18 144 493995 864766 378690 749087 262700 586682
r19 20 955297 820352 149233 36565 636331 346012
r20 158 915090 152235 934934 479130 912004 389942
r21 52 870398 708381 174466 959392 316679 307296
r22 151 490860 312186 869918 440828 859019 512842
r23 95 80894 369933 623491 452109 744508 211636
r24 16 832551 656452 962969 322409 924830 603304
r25 50 174049 518004 850581 182191 673210 576861
r26 144 336566 379264 365321 651202 616996 55222
r27 130 822199 398052 164937 252409 514558 681721
r28 102 532921 936216 636347 982935 976260 898227
r29 113 510945 853789 792879 800143 796642 24867
r30 0 818764 630715 300415 439121 721750 598757
r31 98 873676 748258 741042 292766 411306 359072
r32 115 157140 590183 601330 851495 358050 270577
r33 61 932212 331753 972177 49746 744878 494891
r34 162 235341 974786 734396 644569 954762 754962
r35 138 222088 850540 840559 618349 986527 965434
r36 12 643335 933642 280592 896036 123803 678462
r37 107 874906 898446 614736 459591 766452 551411
r38 105 127310 369349 743611 680099 371735 190865
r39 9 288955 258648 756974 993511 313169 148987
r40 22 544078 789156 567134 84495 7232 388871
r41 145 330281 715042 877722 945273 276030 728719
r42 2 984059 486841 25471 869552 930115 409684
r43 37 572228 739714 97091 268646 718694 828173
r44 137 863838 131209 681188 612129 313912 947511
r45 56 951438 527019 760670 940985 275669 549587
r46 33 425539 749822 146052 823924 594117 170181
r47 107 32723 30256 277290 622289 200228 566672
r48 53 753380 576481 396758 706859 471945 799623
r49 47 99113 889942 965118 806100 149717 565037
r50 99 592518 53374 632198 667753 856515 678006
r51 71 264320 53401 377760 498554 706288 870501
r52 93 303582 26251 481068 288102 203876 23525
r53 120 228733 67825 856598 36469 60895 809969
r54 118 32048 866201 789290 845587 608054 171643
r55 2 650987 91797 688081 935257 855065 994022
r56 145 145919 991993 592884 437642 677980 118562
r57 62 997327 855360 484015 702535 758367 792966
r58 83 98680 626625 704955 924126 176100 860767
r59 47 102745 120534 589629 594563 604260 423772
r60 23 86037 567407 917159 207583 474834 256176
r61 1 648903 944353 85502 350569 803700 249218
r62 146 1941 445125 883362 200107 861188 525242
r63 58 72554 876864 5167 998859 270477 790277
r64 85 183974 222777 764635 811000 451869 83253
r65 2 178744 815368 192602 929511 49691 246435
r66 142 650016 674409 483015 140356 448611 524239
r67 131 180293 24080 215139 431333 296642 157751
r68 23 796400 979692 190167 798559 40061 980681
r69 94 691321 662907 57932 605046 718559 371950
r70 28 963125 299159 837855 551115 831455 735161
r71 151 145149 675516 943070 949943 379933 758640
r72 76 394190 749566 845285 279900 410093 15143
r73 47 725036 928709 433877 841763 22477 907753
r74 104 312534 247659 63865 391654 129512 337576
r75 18 945859 719359 721770 108285 233329 380324
r76 164 494116 784207 12462 580689 820261 92953
r77 19 312431 404447 51481 513679 243141 178566
r78 27 736528 190775 597167 138586 218006 816402
r79 2 300146 40010 405501 321960 790364 494805
r80 148 671707 681260 870148 526487 891403 27688
r81 44 689644 596926 350087 83033 86752 357927
r82 114 252518 218238 942159 527597 790043 383515
r83 132 347767 817386 283653 136701 980558 442215
r84 82 898165 451862 550147 177322 318323 559762
r85 82 550532 64404 830850 169960 592302 750413
r86 75 643059 898515 530266 520341 907002 980339
r87 123 982986 142288 470036 528246 58979 625829
r88 82 251894 353697 560270 857485 942566 454845
r89 138 612996 512155 828504 361896 311563 427332
r90 38 110442 230077 683457 296715 174480 894554
r91 139 824088 758964 839080 901930 176959 179789
r92 91 384193 27872 879688 983922 241190 87851
r93 169 520666 637091 361903 503058 366366 526051
r94 169 25277 276139 840475 937137 620617 270244
r95 75 767585 679605 360512 739263 520802 144959
r96 49 956247 714329 574425 552443 869563 509087
r97 0 183690 4880 779837 464570 338561 315540
r98 163 703822 629639 553167 738612 906045 835358
r99 169 82445 910970 886147 479859 194469 813067
r100 4 415171 566587 865141 382642 765195 174023
r101 110 59221 777184 243569 539344 972552 339165
r102 5 64148 876153 793895 511724 877772 701976
r103 26 339871 245616 999480 560619 437480 231895
r104 92 58826 383142 394228 174232 88236 221101
r105 25 358529 928264 30171 413979 572591 657174
r106 57 391611 503696 291044 494362 875786 761933
r107 4 628408 976566 823773 472049 228202 71599
r108 62 888400 681175 191832 847866 264356 373833
r109 83 454791 660308 671184 475704 797189 993564
r110 134 424104 788780 27271 116197 574228 580517
r111 15 898780 365670 245164 798848 628558 77094
r112 158 133952 358979 283618 604204 477670 831346
r113 6 721506 539191 163416 499937 441762 326133
r114 0 882594 379818 242655 466533 853441 665046
r115 161 925513 938892 243375 929285 60210 27401
r116 80 309984 59206 838477 625980 764275 616860
r117 111 61271 103311 825402 106204 765050 643448
r118 8 300180 540889 597001 844078 179358 966103
r119 132 515367 850942 399280 896079 195237 732275
r120 46 864209 815407 210576 219476 880150 425377
r121 51 366641 762479 717422 620116 634081 8320
r122 142 797848 550190 257259 709111 711506 44974
r123 87 676307 88191 859152 273331 489412 200665
r124 0 0 0 18 446744 73709 551616
r125 0 0 0 0 0 0 0
每小节6位，中间节不够6位的前面应补0至6位！

yangchuanju · 发表于 2024-10-22 11:40

2^127-1=170141183460469231731687303715884105727<39> 0-125级LL检验商数表，第0-6级，第125级余数等于0——
0 0
1 0
2 0
3 0
4 0
5 0
6 0
7 0 95164 864801 105677 36244 285904 13549
8 129 255359 313198 696597 920401 408587 723150
9 1 890533 61609 652598 787773 242611 864405
10 43 371235 169864 73266 353290 607937 632731
11 79 737509 252277 199665 711774 231654 585836
12 14 679740 780684 350017 774342 584696 555374
13 151 723015 105806 460882 970146 860493 497337
14 52 244461 841252 48645 702557 244226 910402
15 68 564590 -160266 349718 553900 239393 842554
16 5 919072 741585 84155 107846 271135 62000
17 9 641933 856104 149689 402380 246332 582730
18 52 30740 24662 970888 577090 281796 317740
19 122 712881 245458 719833 745170 422595 311930
20 2 580941 884898 443002 248407 613258 914600
21 148 429706 226509 433277 165932 997460 845758
22 16 429173 717543 403367 49838 236434 253836
23 134 884924 -72722 531000 353271 184855 245138
24 53 134557 373511 556731 74859 807980 994970
25 1 665292 256138 664561 410712 785647 540639
26 14 796154 545485 9859 215630 31306 851311
27 122 445629 -21322 271843 438514 988989 681943
28 100 589683 -143105 785555 667752 399268 122756
29 61 789861 25684 688322 125224 838560 211580
30 75 729665 14366 668145 329568 219567 570590
31 0 3940 113186 447406 849075 713814 276425
32 57 458187 106009 107101 373900 407250 336115
33 77 942134 638879 616987 379832 746238 961868
34 22 543624 337683 547775 884157 92737 818971
35 154 696856 165721 230539 765309 205393 445304
36 112 291130 563498 786257 212900 723198 706396
37 0 939537 37886 366530 488236 565302 221553
38 68 396112 579296 277817 323295 132823 941802
39 64 956356 601636 521302 452130 25657 997468
40 0 507135 827095 183362 551019 148411 771248
41 2 987139 727809 890755 417042 191671 764960
42 124 137439 827 668699 914113 214717 430325
43 0 52336 599757 311728 516717 267542 773503
44 8 297064 495240 367086 269964 89633 809808
45 111 709801 693400 546333 508904 126878 235716
46 19 63381 859262 6222 54929 326128 309918
47 6 566703 515527 775331 339781 172430 978681
48 67 332338 745144 864435 706578 650744 751817
49 16 982519 250365 137329 4492 563492 20670
50 13 38151 516860 787901 155527 223597 147343
51 58 296700 719178 888379 623729 326625 285379
52 29 849347 520547 12620 589513 930408 21262
53 51 166673 710973 799325 984245 978768 784602
54 84 958550 76376 467120 989406 891973 700508
55 81 882377 189274 335422 140540 834490 581775
56 0 41305 299622 9471 474947 301293 560960
57 123 822684 560061 755012 48315 487075 246788
58 23 325706 546727 693436 117982 614880 107581
59 40 586238 -81053 791513 935847 303536 28445
60 13 40162 15819 766999 429036 723213 881378
61 3 132487 500811 870602 511386 719425 444228
62 0 15980 165192 249714 767142 201607 123640
63 125 287519 -116977 567813 748645 947911 537955
64 19 821312 872827 761856 399676 192518 839262
65 42 648753 -84017 303061 423990 601420 832236
66 0 27899 940942 850475 554350 717216 120392
67 119 600832 -72228 419960 6041 428692 768984
68 101 141116 617803 179554 433941 884284 523834
69 3 328228 287052 866454 428651 25916 150367
70 52 700035 440523 175967 920858 21024 837431
71 4 930391 396325 594749 980766 885121 646977
72 134 269997 456079 860391 526894 629743 138665
73 34 301350 570018 683895 747778 395134 152122
74 13 386994 868139 409349 864856 380700 617753
75 63 953386 122334 412310 506854 919877 373350
76 2 109692 628232 568532 632321 640976 558923
77 159 34478 -67532 680355 677843 203235 776983
78 2 192120 679810 533030 649949 610091 896176
79 4 521627 159456 970934 869565 247488 651411
80 0 31095 774096 368559 615945 660751 517105
81 129 911384 270909 523989 837375 130612 231145
82 11 738276 962565 856778 595207 500151 45356
83 76 722388 158473 22492 723796 104783 36304
84 102 949393 497648 396932 473057 725439 932643
85 40 390607 -61892 316958 263533 509996 530827
86 40 52562 263344 271460 866362 290296 713164
87 33 630144 62881 866087 343195 366118 996670
88 90 347207 -227609 430585 322189 581564 293222
89 39 763295 324303 787406 715100 523148 555133
90 112 927172 664953 79741 999204 188277 303884
91 8 536474 105977 878806 557448 664308 384875
92 114 909132 519334 612879 47746 529698 42884
93 49 83182 363589 760879 978287 940351 406124
94 168 902412 -118100 41422 276705 187527 422365
95 167 916689 -6567 702156 304539 918904 418225
96 33 740961 23963 552906 677388 277772 406496
97 14 667975 353967 801612 223294 460653 674901
98 0 198 317757 93423 379230 798161 447120
99 157 510021 -37821 821564 475155 256775 542985
100 168 30296 -432502 475959 216709 254347 839632
101 0 114573 906011 34287 875478 716590 553006
102 71 194005 189235 680511 731609 564026 631761
103 0 150731 312185 848632 673957 263850 17177
104 4 77724 176617 98872 665845 380891 616286
105 49 810559 340574 158603 790355 391426 926575
106 3 779537 834656 946123 477653 664580 527083
107 19 359199 248506 789575 222557 574887 732744
108 0 125908 197055 309661 808554 617826 60458
109 23 245112 440110 775637 943546 114001 995149
110 40 934840 756393 973191 603545 35512 518551
111 106 204973 -102865 508681 810981 453013 434959
112 1 485655 688849 611558 838624 582022 494544
113 146 974097 511535 695387 538526 206160 929203
114 0 265536 240183 61982 794988 661894 157983
115 0 4578 390860 127851 917455 298571 831719
116 154 106557 454622 2622 711355 120440 204557
117 37 907891 601578 575829 156530 42630 857450
118 72 496298 4985 433048 817372 456933 114137
119 0 404916 643990 365736 868490 309763 630116
120 103 210300 -239791 748616 27165 924239 407098
121 12 908421 799773 995780 779408 738434 87041
122 15 507896 632007 454920 346147 99655 768112
123 119 848852 205030 912813 202183 883089 186967
124 45 180917 801722 603405 792200 428798 695441
125 0 0 0 0 0 0 2
每小节6位，中间节不够6位的前面应补0至6位，第125级余数应等于0！

		自动登录	找回密码
密码			注册

大数相除

浏览过的版块