Rollup merge of #128609 - swenson:smaller-faster-dragon, r=Amanieu · model-checking/verify-rust-std@6449537
@@ -12,48 +12,51 @@ use crate::num::flt2dec::{round_up, Decoded, MAX_SIG_DIGITS};
12121313static POW10: [Digit; 10] =
1414[1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000];
15-static TWOPOW10: [Digit; 10] =
16-[2, 20, 200, 2000, 20000, 200000, 2000000, 20000000, 200000000, 2000000000];
17-18-// precalculated arrays of `Digit`s for 10^(2^n)
19-static POW10TO16: [Digit; 2] = [0x6fc10000, 0x2386f2];
20-static POW10TO32: [Digit; 4] = [0, 0x85acef81, 0x2d6d415b, 0x4ee];
21-static POW10TO64: [Digit; 7] = [0, 0, 0xbf6a1f01, 0x6e38ed64, 0xdaa797ed, 0xe93ff9f4, 0x184f03];
22-static POW10TO128: [Digit; 14] = [
23-0, 0, 0, 0, 0x2e953e01, 0x3df9909, 0xf1538fd, 0x2374e42f, 0xd3cff5ec, 0xc404dc08, 0xbccdb0da,
24-0xa6337f19, 0xe91f2603, 0x24e,
15+// precalculated arrays of `Digit`s for 5^(2^n).
16+static POW5TO16: [Digit; 2] = [0x86f26fc1, 0x23];
17+static POW5TO32: [Digit; 3] = [0x85acef81, 0x2d6d415b, 0x4ee];
18+static POW5TO64: [Digit; 5] = [0xbf6a1f01, 0x6e38ed64, 0xdaa797ed, 0xe93ff9f4, 0x184f03];
19+static POW5TO128: [Digit; 10] = [
20+0x2e953e01, 0x3df9909, 0xf1538fd, 0x2374e42f, 0xd3cff5ec, 0xc404dc08, 0xbccdb0da, 0xa6337f19,
21+0xe91f2603, 0x24e,
2522];
26-static POW10TO256: [Digit; 27] = [
27-0, 0, 0, 0, 0, 0, 0, 0, 0x982e7c01, 0xbed3875b, 0xd8d99f72, 0x12152f87, 0x6bde50c6, 0xcf4a6e70,
28-0xd595d80f, 0x26b2716e, 0xadc666b0, 0x1d153624, 0x3c42d35a, 0x63ff540e, 0xcc5573c0, 0x65f9ef17,
29-0x55bc28f2, 0x80dcc7f7, 0xf46eeddc, 0x5fdcefce, 0x553f7,
23+static POW5TO256: [Digit; 19] = [
24+0x982e7c01, 0xbed3875b, 0xd8d99f72, 0x12152f87, 0x6bde50c6, 0xcf4a6e70, 0xd595d80f, 0x26b2716e,
25+0xadc666b0, 0x1d153624, 0x3c42d35a, 0x63ff540e, 0xcc5573c0, 0x65f9ef17, 0x55bc28f2, 0x80dcc7f7,
26+0xf46eeddc, 0x5fdcefce, 0x553f7,
3027];
31283229#[doc(hidden)]
3330pub fn mul_pow10(x: &mut Big, n: usize) -> &mut Big {
3431debug_assert!(n < 512);
32+// Save ourself the left shift for the smallest cases.
33+if n < 8 {
34+return x.mul_small(POW10[n & 7]);
35+}
36+// Multiply by the powers of 5 and shift the 2s in at the end.
37+// This keeps the intermediate products smaller and faster.
3538if n & 7 != 0 {
36- x.mul_small(POW10[n & 7]);
39+ x.mul_small(POW10[n & 7] >> (n & 7));
3740}
3841if n & 8 != 0 {
39- x.mul_small(POW10[8]);
42+ x.mul_small(POW10[8] >> 8);
4043}
4144if n & 16 != 0 {
42- x.mul_digits(&POW10TO16);
45+ x.mul_digits(&POW5TO16);
4346}
4447if n & 32 != 0 {
45- x.mul_digits(&POW10TO32);
48+ x.mul_digits(&POW5TO32);
4649}
4750if n & 64 != 0 {
48- x.mul_digits(&POW10TO64);
51+ x.mul_digits(&POW5TO64);
4952}
5053if n & 128 != 0 {
51- x.mul_digits(&POW10TO128);
54+ x.mul_digits(&POW5TO128);
5255}
5356if n & 256 != 0 {
54- x.mul_digits(&POW10TO256);
57+ x.mul_digits(&POW5TO256);
5558}
56- x
59+ x.mul_pow2(n)
5760}
58615962fn div_2pow10(x: &mut Big, mut n: usize) -> &mut Big {
@@ -62,7 +65,7 @@ fn div_2pow10(x: &mut Big, mut n: usize) -> &mut Big {
6265 x.div_rem_small(POW10[largest]);
6366 n -= largest;
6467}
65- x.div_rem_small(TWOPOW10[n]);
68+ x.div_rem_small(POW10[n] << 1);
6669 x
6770}
6871