-
Notifications
You must be signed in to change notification settings - Fork 529
/
large_powers32.rs
183 lines (180 loc) · 15 KB
/
large_powers32.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
// Adapted from https://github.com/Alexhuszagh/rust-lexical.
//! Precalculated large powers for 32-bit limbs.
/// Large powers (`&[u32]`) for base5 operations.
const POW5_1: [u32; 1] = [5];
const POW5_2: [u32; 1] = [25];
const POW5_3: [u32; 1] = [625];
const POW5_4: [u32; 1] = [390625];
const POW5_5: [u32; 2] = [2264035265, 35];
const POW5_6: [u32; 3] = [2242703233, 762134875, 1262];
const POW5_7: [u32; 5] = [3211403009, 1849224548, 3668416493, 3913284084, 1593091];
const POW5_8: [u32; 10] = [
781532673, 64985353, 253049085, 594863151, 3553621484, 3288652808, 3167596762, 2788392729,
3911132675, 590,
];
const POW5_9: [u32; 19] = [
2553183233, 3201533787, 3638140786, 303378311, 1809731782, 3477761648, 3583367183, 649228654,
2915460784, 487929380, 1011012442, 1677677582, 3428152256, 1710878487, 1438394610, 2161952759,
4100910556, 1608314830, 349175,
];
const POW5_10: [u32; 38] = [
4234999809, 2012377703, 2408924892, 1570150255, 3090844311, 3273530073, 1187251475, 2498123591,
3364452033, 1148564857, 687371067, 2854068671, 1883165473, 505794538, 2988060450, 3159489326,
2531348317, 3215191468, 849106862, 3892080979, 3288073877, 2242451748, 4183778142, 2995818208,
2477501924, 325481258, 2487842652, 1774082830, 1933815724, 2962865281, 1168579910, 2724829000,
2360374019, 2315984659, 2360052375, 3251779801, 1664357844, 28,
];
const POW5_11: [u32; 75] = [
689565697, 4116392818, 1853628763, 516071302, 2568769159, 365238920, 336250165, 1283268122,
3425490969, 248595470, 2305176814, 2111925499, 507770399, 2681111421, 589114268, 591287751,
1708941527, 4098957707, 475844916, 3378731398, 2452339615, 2817037361, 2678008327, 1656645978,
2383430340, 73103988, 448667107, 2329420453, 3124020241, 3625235717, 3208634035, 2412059158,
2981664444, 4117622508, 838560765, 3069470027, 270153238, 1802868219, 3692709886, 2161737865,
2159912357, 2585798786, 837488486, 4237238160, 2540319504, 3798629246, 3748148874, 1021550776,
2386715342, 1973637538, 1823520457, 1146713475, 833971519, 3277251466, 905620390, 26278816,
2680483154, 2294040859, 373297482, 5996609, 4109575006, 512575049, 917036550, 1942311753,
2816916778, 3248920332, 1192784020, 3537586671, 2456567643, 2925660628, 759380297, 888447942,
3559939476, 3654687237, 805,
];
const POW5_12: [u32; 149] = [
322166785, 3809044581, 2994556223, 1239584207, 3962455841, 4001882964, 3053876612, 915114683,
2783289745, 785739093, 4253185907, 3931164994, 1370983858, 2553556126, 3360742076, 2255410929,
422849554, 2457422215, 3539495362, 1720790602, 1908931983, 1470596141, 592794347, 4219465164,
4085652704, 941661409, 2534650953, 885063988, 2355909854, 2812815516, 767256131, 3821757683,
2155151105, 3817418473, 281116564, 2834395026, 2821201622, 2524625843, 1511330880, 2572352493,
330571332, 2951088579, 2730271766, 4044456479, 4212286644, 2444937588, 3603420843, 2387148597,
1142537539, 3299235429, 1751012624, 861228086, 2873722519, 230498814, 1023297821, 2553128038,
3421129895, 2651917435, 2042981258, 1606787143, 2228751918, 447345732, 1930371132, 1784132011,
3612538790, 2275925090, 2487567871, 1080427616, 2009179183, 3383506781, 3899054063, 1950782960,
2168622213, 2717674390, 3616636027, 2079341593, 1530129217, 1461057425, 2406264415, 3674671357,
2972036238, 2019354295, 1455849819, 1866918619, 1324269294, 424891864, 2722422332, 2641594816,
1400249021, 3482963993, 3734946379, 225889849, 1891545473, 777383150, 3589824633, 4117601611,
4220028667, 334453379, 1083130821, 1060342180, 4208163139, 1489826908, 4163762246, 1096580926,
689301528, 2336054516, 1782865703, 4175148410, 3398369392, 2329412588, 3001580596, 59740741,
3202189932, 3351895776, 246185302, 718535188, 3772647488, 4151666556, 4055698133, 2461934110,
2281316281, 3466396836, 3536023465, 1064267812, 2955456354, 2423805422, 3627960790, 1325057500,
3876919979, 2009959531, 175455101, 184092852, 2358785571, 3842977831, 2485266289, 487121622,
4159252710, 4075707558, 459389244, 300652075, 2521346588, 3458976673, 888631636, 2076098096,
3844514585, 2363697580, 3729421522, 3051115477, 649395,
];
const POW5_13: [u32; 298] = [
711442433, 3564261005, 2399042279, 4170849936, 4010295575, 1423987028, 330414929, 1349249065,
4213813618, 3852031822, 4040843590, 2154565331, 3094013374, 1159028371, 3227065538, 2115927092,
2085102554, 488590542, 2609619432, 3602898805, 3812736528, 3269439096, 23816114, 253984538,
1035905997, 2942969204, 3400787671, 338562688, 1637191975, 740509713, 2264962817, 3410753922,
4162231428, 2282041228, 1759373012, 3155367777, 4278913285, 1420532801, 1981002276, 438054990,
1006507643, 1142697287, 1332538012, 2029019521, 3949305784, 818392641, 2491288846, 2716584663,
3648886102, 556814413, 444795339, 4071412999, 1066321706, 4253169466, 2510832316, 672091442,
4083256000, 2165985028, 1841538484, 3549854235, 364431512, 3707648143, 1162785440, 2268641545,
281340310, 735693841, 848809228, 1700785200, 2919703985, 4094234344, 58530286, 965505005,
1000010347, 3381961808, 3040089923, 1973852082, 2890971585, 1019960210, 4292895237, 2821887841,
3756675650, 3951282907, 3885870583, 1008791145, 503998487, 1881258362, 1949332730, 392996726,
2012973814, 3970014187, 2461725150, 2942547730, 3728066699, 2766901132, 3778532841, 1085564064,
2278673896, 1116879805, 3448726271, 774279411, 157211670, 1506320155, 531168605, 1362654525,
956967721, 2148871960, 769186085, 4186232894, 2055679604, 3248365487, 3981268013, 3975787984,
2489510517, 3309046495, 212771124, 933418041, 3371839114, 562115198, 1853601831, 757336096,
1354633440, 1486083256, 2872126393, 522920738, 1141587749, 3210903262, 1926940553, 3054024853,
2021162538, 2262742000, 1877899947, 3147002868, 669840763, 4158174590, 4238502559, 1023731922,
3386840011, 829588074, 3449720188, 2835142880, 2999162007, 813056473, 482949569, 638108879,
3067201471, 1026714238, 4004452838, 2383667807, 3999477803, 771648919, 630660440, 3827121348,
176185980, 2878191002, 2666149832, 3909811063, 2429163983, 2665690412, 907266128, 4269332098,
2022665808, 1527122180, 3072053668, 1072477492, 3006022924, 549664855, 2800340954, 37352654,
1212772743, 2711280533, 3029527946, 2511120040, 1305308377, 3474662224, 4226330922, 442988428,
954940108, 3274548099, 4212288177, 2688499880, 3982226758, 3922609956, 1279948029, 1939943640,
3650489901, 2733364929, 2494263275, 1864579964, 1225941120, 2390465139, 1267503249, 3533240729,
904410805, 2842550015, 2517736241, 1796069820, 3335274381, 673539835, 1924694759, 3598098235,
2792633405, 16535707, 3703535497, 3592841791, 2929082877, 1317622811, 294990855, 1396706563,
2383271770, 3853857605, 277813677, 277580220, 1101318484, 3761974115, 1132150143, 2544692622,
3419825776, 743770306, 1695464553, 1548693232, 2421159615, 2575672031, 2678971806, 1591267897,
626546738, 3823443129, 267710932, 1455435162, 2353985540, 3248523795, 335348168, 3872552561,
2814522612, 2634118860, 3503767026, 1301019273, 1414467789, 722985138, 3070909565, 4253482569,
3744939841, 558142907, 2229819389, 13833173, 77003966, 2763671364, 3905603970, 2931990126,
2280419384, 1879090457, 2934846267, 4284933164, 2331863845, 62191163, 3178861020, 1522063815,
785672270, 1215568492, 2936443917, 802972489, 2956820173, 3916732783, 2893572089, 1391232801,
3168640330, 2396859648, 894950918, 1103583736, 961991865, 2807302642, 305977505, 3054505899,
1048256994, 781017659, 2459278754, 3164823415, 537658277, 905753687, 464963300, 4149131560,
1029507924, 2278300961, 1231291503, 414073408, 3630740085, 2345841814, 475358196, 3258243317,
4167625072, 4178911231, 2927355042, 655438830, 3138378018, 623200562, 2785714112, 273403236,
807993669, 98,
];
const POW5_14: [u32; 595] = [
1691320321, 2671006246, 1682531301, 2072858707, 1240508969, 3108358191, 1125119096, 2470144952,
1610099978, 1690632660, 1941696884, 2663506355, 1006364675, 3909158537, 4147711374, 1072663936,
4078768933, 745751659, 4123687570, 471458681, 655028926, 4113407388, 3945524552, 985625313,
1254424514, 2127508744, 570530434, 945388122, 3194649404, 2589065070, 2731705399, 202030749,
2090780394, 3348662271, 1481754777, 1130635472, 4025144705, 1924486271, 2578567861, 125491448,
1558036315, 994248173, 3817216711, 763950077, 1030439870, 959586474, 3845661701, 483795093,
1637944470, 2275463649, 3398804829, 1758016486, 2665513698, 2004912571, 1094885097, 4223064276,
3307819021, 651121777, 1757003305, 3603542336, 129917786, 2215974994, 3042386306, 2205352757,
3944939700, 3710987569, 97967515, 1217242524, 930630949, 3660328512, 1787663098, 1784141600,
2500542892, 4034561586, 3444961378, 785043562, 3869499367, 885623728, 2625011087, 3053789617,
1965731793, 3900511934, 2648823592, 3851062028, 3321968688, 799195417, 1011847510, 1369129160,
1348009103, 2876796955, 2915408967, 3305284948, 263399535, 1715990604, 2645821294, 1587844552,
2624912049, 3035631499, 2306636348, 3499275462, 675152704, 854794152, 4004972748, 1739996642,
1333476491, 4012621867, 3658792931, 3297985728, 2864481726, 3066357406, 785287846, 1671499798,
433044045, 1919608025, 264833858, 3999983367, 1116778570, 1301982149, 4213901070, 4081649357,
536169226, 1389008649, 188923873, 373495152, 2551132278, 1800758715, 3951840330, 2632334454,
3118778225, 1034046547, 1862428410, 3037609062, 1994608505, 29051798, 2571685694, 264151332,
2260643090, 2717535964, 3508441116, 3283713017, 1903365635, 923575694, 1219598101, 2288281570,
3676533911, 1014136356, 555142354, 2389170030, 4185108175, 884862419, 836141292, 2957159173,
1997444768, 4233903127, 2876184692, 3089125070, 1480848293, 1097600237, 299700527, 2507669891,
2982628312, 2114881043, 2529576251, 2812279824, 2987750993, 4241938954, 2204775591, 1037094060,
829315638, 1231047149, 52608178, 3735136637, 3455232602, 962039123, 488286513, 50685385,
3516451821, 843975207, 1572355722, 675489076, 2428445672, 1555117248, 3708476086, 10375249,
4172112346, 2117510871, 2227658327, 3187664554, 3050656558, 328034318, 3179601324, 1247769761,
3439263953, 1431538938, 2962525068, 1213366289, 3813013550, 2651093719, 1860661503, 3933716208,
264320617, 789980519, 2257856172, 102000748, 977269860, 1113845122, 3008928583, 1461738106,
557786285, 2926560363, 1038106190, 3643478847, 828004507, 457818698, 1933056971, 373408056,
2076808229, 3160935130, 2781854874, 2519636100, 177606000, 4237103862, 3977834316, 1621936232,
2599050516, 319893558, 3343370366, 765044144, 976657331, 7026264, 294277429, 3829376742,
3029627280, 2705178718, 3614653880, 230519152, 3288033233, 293525479, 3805751881, 3227511198,
2520308544, 3648103003, 1111086184, 437622105, 2232033852, 3239146386, 584244184, 1450926016,
2462430443, 3226534010, 298582169, 4214576928, 1762099469, 964985185, 1585788148, 1641127666,
787006566, 2315956284, 3258232694, 2275058964, 2541003317, 1508235863, 2613339827, 4080647514,
1152057965, 3149266279, 731345410, 914737650, 65395712, 1884566942, 1379520432, 2611027720,
4163073378, 2619704967, 2746552541, 1388822415, 3005141199, 843440249, 4288674003, 3136174279,
4051522914, 4144149433, 3427566947, 3419023197, 3758479825, 3893877676, 96899594, 1657725776,
253618880, 434129337, 1499045748, 2996992534, 4036042074, 2110713869, 906222950, 928326225,
2541827893, 1604330202, 226792470, 4022228930, 815850898, 1466012310, 3377712199, 292769859,
2822055597, 3225701344, 3052947004, 385831222, 705324593, 4030158636, 3540280538, 2982120874,
2136414455, 255762046, 3852783591, 3262064164, 2358991588, 3756586117, 4143612643, 3326743817,
2897365738, 807711264, 3719310016, 3721264861, 3627337076, 944539331, 3640975513, 3712525681,
1162911839, 2008243316, 2179489649, 2867584109, 261861553, 3570253908, 2062868357, 2220328623,
3857004679, 3744109002, 4138041873, 1451860932, 2364975637, 2802161722, 2680106834, 753401584,
1223182946, 1245401957, 4163377735, 3565815922, 2216942838, 4036140094, 71979081, 3924559643,
400477238, 551750683, 1174153235, 859969898, 1185921017, 1711399735, 812991545, 4051735761,
3549118738, 1631653329, 3631835958, 3648867800, 1206500363, 2155893137, 361030362, 3454286017,
2505909489, 1083595169, 453595313, 1510564703, 1706163902, 1632924345, 1381875722, 1661526119,
1082778324, 3571910052, 1140625929, 851544870, 1145546234, 2938573139, 907528924, 1304752338,
1764668294, 1788942063, 1700368828, 104979467, 1413911959, 3327497828, 1956384744, 1272712474,
2815637534, 3307809377, 1320574940, 1111968962, 4073107827, 434096622, 169451929, 3201183459,
3331028877, 2852366972, 3369830128, 2924794558, 3106537952, 3739481231, 1612955817, 4138608722,
2721281595, 2755775390, 843505117, 982234295, 1157276611, 814674632, 4246504726, 3532006708,
992340967, 1647538031, 204696133, 193866982, 3899126129, 300851698, 1379496684, 1759463683,
1354782756, 1374637239, 3410883240, 1073406229, 3038431791, 1053909855, 3607043270, 173719711,
3733903830, 171820911, 1573050589, 932781534, 4183534770, 2158849555, 372245998, 3573073830,
841339264, 2759200520, 1610547277, 2603293319, 3890906486, 1557138278, 3964109906, 677238797,
537994297, 1124184993, 4287078344, 4207654540, 2943022776, 2977947524, 3255359985, 4098397558,
2274666217, 2915862060, 243524940, 2467726756, 2869020032, 507521339, 3403121914, 522051455,
1803903108, 3471254194, 473535371, 1948602036, 3352095732, 3116527002, 1795743673, 775867940,
2551469548, 3757442064, 3162525227, 3765412747, 3040105484, 1927625810, 48214767, 2997207130,
1342349989, 2536583992, 1501320191, 3592287317, 887432730, 967585477, 3334212779, 948663609,
1064513472, 15386372, 2465931737, 3230242590, 3036652803, 2063155087, 1927500726, 2821790499,
2187774383, 501520074, 3688568496, 3606711121, 2576459247, 3176542345, 378322447, 156541411,
1400607301, 1406179107, 677848877, 2253753529, 193196070, 4207435024, 4166396241, 509467541,
2906024136, 1221753746, 3375413222, 431327897, 2749265123, 2848827671, 3412997614, 2051920238,
1283516885, 1300498239, 1957256104, 2634010560, 3531900395, 360276850, 1461184973, 2012063967,
2873572430, 2914608609, 4289554777, 1539331673, 1859532928, 4213441063, 538215691, 3512720863,
4258743698, 3040408445, 982396546, 343095663, 4138069496, 1021581857, 214185242, 1968079460,
2864275059, 3347192726, 4096783459, 3259169450, 3707808869, 142485006, 399610869, 230556456,
2219467721, 4191227798, 2242548189, 3136366572, 179755707, 3464881829, 452317775, 3887426070,
3446430233, 1473370015, 1576807208, 3964523248, 419325089, 2373067114, 1596072055, 1928415752,
3635452689, 1005598891, 3335462724, 3290848636, 3669078247, 1178176812, 2110774376, 3068593619,
1253036518, 908857731, 3631223047, 4138506423, 2903592318, 3596915748, 3289036113, 3721512676,
2704409359, 3386016968, 3676268074, 2185259502, 1096257611, 3360076717, 3548676554, 170167319,
3360064287, 3899940843, 9640,
];
pub(crate) const POW5: [&'static [u32]; 14] = [
&POW5_1, &POW5_2, &POW5_3, &POW5_4, &POW5_5, &POW5_6, &POW5_7, &POW5_8, &POW5_9, &POW5_10,
&POW5_11, &POW5_12, &POW5_13, &POW5_14,
];