f256/conv/to_str/
powers_of_five.rs

1// ---------------------------------------------------------------------------
2// Copyright:   (c) 2022 ff. Michael Amrhein (michael@adrhinum.de)
3// License:     This program is part of a larger application. For license
4//              details please read the file LICENSE.TXT provided together
5//              with the application.
6// ---------------------------------------------------------------------------
7// $Source$
8// $Revision$
9
10use crate::{BigUInt, DivRem, U256};
11
12pub(crate) const MAX_EXP: u32 = 102;
13
14#[inline(always)]
15pub(crate) fn get_power_of_five(n: u32) -> U256 {
16    debug_assert!(n <= MAX_EXP);
17    let (hi, lo) = POWERS_OF_FIVE[n as usize];
18    U256::new(hi, lo)
19}
20
21#[inline]
22pub(crate) fn is_multiple_of_pow5(x: &U256, e: u32) -> bool {
23    if e == 0 {
24        return true;
25    }
26    if e == 1 {
27        return *x % 5_u128 == 0_u128;
28    }
29    let p = get_power_of_five(e);
30    if e <= 55 {
31        return (*x % p.lo).is_zero();
32    }
33    let (_, r) = x.div_rem(&p);
34    r.is_zero()
35}
36
37/// Table of values of 5ⁱ for i ∈ [0..MAX_EXP].
38/// Generated by the following Python code:
39/// ```python
40/// MAX_EXP = 102
41/// B = 1 << 128
42/// for i in range(MAX_EXP + 1):
43///     p = 5 ** i
44///     hi, lo = divmod(p, B)
45///     print(f"    (0x{hi:032x}, 0x{lo:032x}), // 5^{i}")
46/// ```
47#[rustfmt::skip]
48static POWERS_OF_FIVE: [(u128, u128); (MAX_EXP + 1) as usize] = [
49    (0x00000000000000000000000000000000, 0x00000000000000000000000000000001), // 5^0
50    (0x00000000000000000000000000000000, 0x00000000000000000000000000000005), // 5^1
51    (0x00000000000000000000000000000000, 0x00000000000000000000000000000019), // 5^2
52    (0x00000000000000000000000000000000, 0x0000000000000000000000000000007d), // 5^3
53    (0x00000000000000000000000000000000, 0x00000000000000000000000000000271), // 5^4
54    (0x00000000000000000000000000000000, 0x00000000000000000000000000000c35), // 5^5
55    (0x00000000000000000000000000000000, 0x00000000000000000000000000003d09), // 5^6
56    (0x00000000000000000000000000000000, 0x0000000000000000000000000001312d), // 5^7
57    (0x00000000000000000000000000000000, 0x0000000000000000000000000005f5e1), // 5^8
58    (0x00000000000000000000000000000000, 0x000000000000000000000000001dcd65), // 5^9
59    (0x00000000000000000000000000000000, 0x000000000000000000000000009502f9), // 5^10
60    (0x00000000000000000000000000000000, 0x00000000000000000000000002e90edd), // 5^11
61    (0x00000000000000000000000000000000, 0x0000000000000000000000000e8d4a51), // 5^12
62    (0x00000000000000000000000000000000, 0x00000000000000000000000048c27395), // 5^13
63    (0x00000000000000000000000000000000, 0x0000000000000000000000016bcc41e9), // 5^14
64    (0x00000000000000000000000000000000, 0x0000000000000000000000071afd498d), // 5^15
65    (0x00000000000000000000000000000000, 0x00000000000000000000002386f26fc1), // 5^16
66    (0x00000000000000000000000000000000, 0x0000000000000000000000b1a2bc2ec5), // 5^17
67    (0x00000000000000000000000000000000, 0x0000000000000000000003782dace9d9), // 5^18
68    (0x00000000000000000000000000000000, 0x000000000000000000001158e460913d), // 5^19
69    (0x00000000000000000000000000000000, 0x0000000000000000000056bc75e2d631), // 5^20
70    (0x00000000000000000000000000000000, 0x00000000000000000001b1ae4d6e2ef5), // 5^21
71    (0x00000000000000000000000000000000, 0x0000000000000000000878678326eac9), // 5^22
72    (0x00000000000000000000000000000000, 0x0000000000000000002a5a058fc295ed), // 5^23
73    (0x00000000000000000000000000000000, 0x000000000000000000d3c21bcecceda1), // 5^24
74    (0x00000000000000000000000000000000, 0x00000000000000000422ca8b0a00a425), // 5^25
75    (0x00000000000000000000000000000000, 0x000000000000000014adf4b7320334b9), // 5^26
76    (0x00000000000000000000000000000000, 0x00000000000000006765c793fa10079d), // 5^27
77    (0x00000000000000000000000000000000, 0x000000000000000204fce5e3e2502611), // 5^28
78    (0x00000000000000000000000000000000, 0x000000000000000a18f07d736b90be55), // 5^29
79    (0x00000000000000000000000000000000, 0x00000000000000327cb2734119d3b7a9), // 5^30
80    (0x00000000000000000000000000000000, 0x00000000000000fc6f7c40458122964d), // 5^31
81    (0x00000000000000000000000000000000, 0x00000000000004ee2d6d415b85acef81), // 5^32
82    (0x00000000000000000000000000000000, 0x00000000000018a6e32246c99c60ad85), // 5^33
83    (0x00000000000000000000000000000000, 0x0000000000007b426fab61f00de36399), // 5^34
84    (0x00000000000000000000000000000000, 0x000000000002684c2e58e9b04570f1fd), // 5^35
85    (0x00000000000000000000000000000000, 0x00000000000c097ce7bc90715b34b9f1), // 5^36
86    (0x00000000000000000000000000000000, 0x00000000003c2f7086aed236c807a1b5), // 5^37
87    (0x00000000000000000000000000000000, 0x00000000012ced32a16a1b11e8262889), // 5^38
88    (0x00000000000000000000000000000000, 0x0000000005e0a1fd2712875988becaad), // 5^39
89    (0x00000000000000000000000000000000, 0x000000001d6329f1c35ca4bfabb9f561), // 5^40
90    (0x00000000000000000000000000000000, 0x0000000092efd1b8d0cf37be5aa1cae5), // 5^41
91    (0x00000000000000000000000000000000, 0x00000002deaf189c140c16b7c528f679), // 5^42
92    (0x00000000000000000000000000000000, 0x0000000e596b7b0c643c7196d9ccd05d), // 5^43
93    (0x00000000000000000000000000000000, 0x00000047bf19673df52e37f2410011d1), // 5^44
94    (0x00000000000000000000000000000000, 0x00000166bb7f0435c9e717bb45005915), // 5^45
95    (0x00000000000000000000000000000000, 0x00000701a97b150cf18376a85901bd69), // 5^46
96    (0x00000000000000000000000000000000, 0x000023084f676940b7915149bd08b30d), // 5^47
97    (0x00000000000000000000000000000000, 0x0000af298d050e4395d69670b12b7f41), // 5^48
98    (0x00000000000000000000000000000000, 0x00036bcfc1194751ed30f03375d97c45), // 5^49
99    (0x00000000000000000000000000000000, 0x00111b0ec57e6499a1f4b1014d3f6d59), // 5^50
100    (0x00000000000000000000000000000000, 0x00558749db77f70029c77506823d22bd), // 5^51
101    (0x00000000000000000000000000000000, 0x01aba4714957d300d0e549208b31adb1), // 5^52
102    (0x00000000000000000000000000000000, 0x085a36366eb71f04147a6da2b7f86475), // 5^53
103    (0x00000000000000000000000000000000, 0x29c30f1029939b146664242d97d9f649), // 5^54
104    (0x00000000000000000000000000000000, 0xd0cf4b50cfe20765fff4b4e3f741cf6d), // 5^55
105    (0x00000000000000000000000000000004, 0x140c78940f6a24fdffc78873d4490d21), // 5^56
106    (0x00000000000000000000000000000014, 0x643e5ae44d12b8f5fee5aa43256d41a5), // 5^57
107    (0x00000000000000000000000000000065, 0xf537c675815d9ccdfa7c534fbb224839), // 5^58
108    (0x000000000000000000000000000001fd, 0xca16e04b86d41005e46da08ea7ab691d), // 5^59
109    (0x000000000000000000000000000009f4, 0xf2726179a224501d762422c946590d91), // 5^60
110    (0x000000000000000000000000000031c8, 0xbc3be7602ab590934eb4adee5fbd43d5), // 5^61
111    (0x0000000000000000000000000000f8eb, 0xad2b84e0d58bd2e0898765a7deb25329), // 5^62
112    (0x0000000000000000000000000004dc9a, 0x61d998642bbb1e62afa4fc47597b9fcd), // 5^63
113    (0x00000000000000000000000000184f03, 0xe93ff9f4daa797ed6e38ed64bf6a1f01), // 5^64
114    (0x00000000000000000000000000798b13, 0x8e3fe1c84545f7a3271ca2f7bd129b05), // 5^65
115    (0x000000000000000000000000025fb761, 0xc73f68e95a5dd62fc38f2ed6b15d0719), // 5^66
116    (0x0000000000000000000000000bde94e8, 0xe43d0c8ec3d52eeed1cbea3176d1237d), // 5^67
117    (0x0000000000000000000000003b58e88c, 0x75313ec9d329eaaa18fb92f75215b171), // 5^68
118    (0x00000000000000000000000128bc8abe, 0x49f639f11fd195527ce9ded49a6c7735), // 5^69
119    (0x000000000000000000000005cbaeb5b7, 0x71cf21b59f17ea9c70915a27041e5409), // 5^70
120    (0x00000000000000000000001cfa698c95, 0x390ba88c1b77950e32d6c2c31497a42d), // 5^71
121    (0x000000000000000000000090e40fbeea, 0x1d3a4abc8955e946fe31cdcf66f634e1), // 5^72
122    (0x0000000000000000000002d4744eba92, 0x922375aeaead8e62f6f9050d02cf0865), // 5^73
123    (0x000000000000000000000e264589a4dc, 0xdab14c696963c7eed2dd19410e0b29f9), // 5^74
124    (0x0000000000000000000046bf5bb03850, 0x45767e0f0ef2e7aa1e517e454637d1dd), // 5^75
125    (0x0000000000000000000161bcca711991, 0x5b50764b4abe86529797775a5f171951), // 5^76
126    (0x00000000000000000006e8aff4357fd6, 0xc8924f7875b89f9cf5f554c3db737e95), // 5^77
127    (0x000000000000000000228b6fc50b7f31, 0xeadb8d5a4c9b1e10cdcaa7d3494178e9), // 5^78
128    (0x000000000000000000acb92ed9397bf9, 0x9649c2c37f07965404f547206e475c8d), // 5^79
129    (0x0000000000000000035f9dea3e1f6bdf, 0xef70cdd17b25efa418ca63a22764cec1), // 5^80
130    (0x000000000000000010de1593369d1b5f, 0xad34051767bdae347bf3f22ac4f809c5), // 5^81
131    (0x000000000000000054566be0111188de, 0x6204197506b467066bc3bad5d8d830d9), // 5^82
132    (0x0000000000000001a5b01b605557ac57, 0xea147f49218603201ad2a62d3c38f43d), // 5^83
133    (0x00000000000000083c7088e1aab65db7, 0x92667c6da79e0fa0861d3ee22d1cc531), // 5^84
134    (0x00000000000000292e32ac68558fd495, 0xdc006e2446164e229e923a6ae18fd9f5), // 5^85
135    (0x00000000000000cde6fd5e09abcf26ed, 0x4c0226b55e6f86ad18db241667cf41c9), // 5^86
136    (0x000000000000040582f2d6305b0bc2a2, 0x7c0ac18ad82da1617c47b470070c48ed), // 5^87
137    (0x000000000000141b8ebe2ef1c73acd2c, 0x6c35c7b638e426e76d668630233d6ca1), // 5^88
138    (0x0000000000006489c9b6eab8e42601de, 0x1d0ce68f1c74c28523009ef0b0331f25), // 5^89
139    (0x000000000001f6b0f092959c74be0956, 0x914080cb8e47cc99af031ab370ff9bb9), // 5^90
140    (0x000000000009d174b2dcec0e47b62eb0, 0xd64283f9c766ff006b0f858134fe0a9d), // 5^91
141    (0x00000000003117477e509c47668ee974, 0x2f4c93e0e502fb02174d9b8608f63511), // 5^92
142    (0x0000000000f5746577930d6500ca8f44, 0xec7ee364790ee70a7484099e2ccf0955), // 5^93
143    (0x0000000004cb45fb55df42f903f4cc58, 0x9e7a70f65d4a833446943016e00b2ea9), // 5^94
144    (0x0000000017f85de8ad5c4edd13c7fdbb, 0x186434cfd274900560e4f0726037e94d), // 5^95
145    (0x0000000077d9d58b62cd8a5162e7f4a7, 0x79f5080f1c46d01ae478b23be1178e81), // 5^96
146    (0x0000000257412bb8ee03b396ee87c745, 0x61c9284b8d621086765b7b2b6575c885), // 5^97
147    (0x0000000bb445da9ca61281f2a8a6e45a, 0xe8edc979c2ea52a04fc967d8fb4cea99), // 5^98
148    (0x0000003a855d450f3e5c89bd4b4275c6, 0x8ca4ef60ce939d218eef073ce88094fd), // 5^99
149    (0x000001249ad2594c37ceb0b2784c4ce0, 0xbf38ace408e211a7caab24308a82e8f1), // 5^100
150    (0x000005b7061bbe7d1709737c597d8063, 0xbc1b60742c6a5846f557b4f2b48e8cb5), // 5^101
151    (0x00001c931e8ab871732f416dbf7381f2, 0xac88e244de13b962cab688bd86c8bf89), // 5^102
152];
f256/conv/to_str/powers_of_five.rs

f256/conv/to_str/
powers_of_five.rs
