/*
* Tables allowing to map leading zeros in integer `x` -> The closest power of ten.
* Script for generating the tables' content.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import math
bits_count = 128
next_power_of_ten = lambda x: 10 ** math.ceil(math.log10(x))
values = [2 ** (i - 1) for i in reversed(range(0, bits_count + 1))]
powers = [next_power_of_ten(value) for value in values]
print('// lz | value | next power of ten')
print('//-----+------------------------------------------+------------------')
for lz, (value, power) in enumerate(zip(values, powers)):
if power >= 2 ** (bits_count - 1):
print('/* %3d | %39d */ 0 /* overflow */,' % (lz, value))
else:
print('/* %3d | %39d */ %d,' % (lz, value, power))
*/
/// Acts as a map for any given `x: i128`:
/// Leading zeros count in `x` -> The closest power of ten
#[rustfmt::skip]
#[cfg(feature = "i128")]
#[allow(clippy::all, non_upper_case_globals)]
pub(crate) static i128: [i128; 129] = [
// lz | value | next power of ten
//-----+------------------------------------------+------------------
/* 0 | 170141183460469231731687303715884105728 */ 0 /* overflow */,
/* 1 | 85070591730234615865843651857942052864 */ 100000000000000000000000000000000000000,
/* 2 | 42535295865117307932921825928971026432 */ 100000000000000000000000000000000000000,
/* 3 | 21267647932558653966460912964485513216 */ 100000000000000000000000000000000000000,
/* 4 | 10633823966279326983230456482242756608 */ 100000000000000000000000000000000000000,
/* 5 | 5316911983139663491615228241121378304 */ 10000000000000000000000000000000000000,
/* 6 | 2658455991569831745807614120560689152 */ 10000000000000000000000000000000000000,
/* 7 | 1329227995784915872903807060280344576 */ 10000000000000000000000000000000000000,
/* 8 | 664613997892457936451903530140172288 */ 1000000000000000000000000000000000000,
/* 9 | 332306998946228968225951765070086144 */ 1000000000000000000000000000000000000,
/* 10 | 166153499473114484112975882535043072 */ 1000000000000000000000000000000000000,
/* 11 | 83076749736557242056487941267521536 */ 100000000000000000000000000000000000,
/* 12 | 41538374868278621028243970633760768 */ 100000000000000000000000000000000000,
/* 13 | 20769187434139310514121985316880384 */ 100000000000000000000000000000000000,
/* 14 | 10384593717069655257060992658440192 */ 100000000000000000000000000000000000,
/* 15 | 5192296858534827628530496329220096 */ 10000000000000000000000000000000000,
/* 16 | 2596148429267413814265248164610048 */ 10000000000000000000000000000000000,
/* 17 | 1298074214633706907132624082305024 */ 10000000000000000000000000000000000,
/* 18 | 649037107316853453566312041152512 */ 1000000000000000000000000000000000,
/* 19 | 324518553658426726783156020576256 */ 1000000000000000000000000000000000,
/* 20 | 162259276829213363391578010288128 */ 1000000000000000000000000000000000,
/* 21 | 81129638414606681695789005144064 */ 100000000000000000000000000000000,
/* 22 | 40564819207303340847894502572032 */ 100000000000000000000000000000000,
/* 23 | 20282409603651670423947251286016 */ 100000000000000000000000000000000,
/* 24 | 10141204801825835211973625643008 */ 100000000000000000000000000000000,
/* 25 | 5070602400912917605986812821504 */ 10000000000000000000000000000000,
/* 26 | 2535301200456458802993406410752 */ 10000000000000000000000000000000,
/* 27 | 1267650600228229401496703205376 */ 10000000000000000000000000000000,
/* 28 | 633825300114114700748351602688 */ 1000000000000000000000000000000,
/* 29 | 316912650057057350374175801344 */ 1000000000000000000000000000000,
/* 30 | 158456325028528675187087900672 */ 1000000000000000000000000000000,
/* 31 | 79228162514264337593543950336 */ 100000000000000000000000000000,
/* 32 | 39614081257132168796771975168 */ 100000000000000000000000000000,
/* 33 | 19807040628566084398385987584 */ 100000000000000000000000000000,
/* 34 | 9903520314283042199192993792 */ 10000000000000000000000000000,
/* 35 | 4951760157141521099596496896 */ 10000000000000000000000000000,
/* 36 | 2475880078570760549798248448 */ 10000000000000000000000000000,
/* 37 | 1237940039285380274899124224 */ 10000000000000000000000000000,
/* 38 | 618970019642690137449562112 */ 1000000000000000000000000000,
/* 39 | 309485009821345068724781056 */ 1000000000000000000000000000,
/* 40 | 154742504910672534362390528 */ 1000000000000000000000000000,
/* 41 | 77371252455336267181195264 */ 100000000000000000000000000,
/* 42 | 38685626227668133590597632 */ 100000000000000000000000000,
/* 43 | 19342813113834066795298816 */ 100000000000000000000000000,
/* 44 | 9671406556917033397649408 */ 10000000000000000000000000,
/* 45 | 4835703278458516698824704 */ 10000000000000000000000000,
/* 46 | 2417851639229258349412352 */ 10000000000000000000000000,
/* 47 | 1208925819614629174706176 */ 10000000000000000000000000,
/* 48 | 604462909807314587353088 */ 1000000000000000000000000,
/* 49 | 302231454903657293676544 */ 1000000000000000000000000,
/* 50 | 151115727451828646838272 */ 1000000000000000000000000,
/* 51 | 75557863725914323419136 */ 100000000000000000000000,
/* 52 | 37778931862957161709568 */ 100000000000000000000000,
/* 53 | 18889465931478580854784 */ 100000000000000000000000,
/* 54 | 9444732965739290427392 */ 10000000000000000000000,
/* 55 | 4722366482869645213696 */ 10000000000000000000000,
/* 56 | 2361183241434822606848 */ 10000000000000000000000,
/* 57 | 1180591620717411303424 */ 10000000000000000000000,
/* 58 | 590295810358705651712 */ 1000000000000000000000,
/* 59 | 295147905179352825856 */ 1000000000000000000000,
/* 60 | 147573952589676412928 */ 1000000000000000000000,
/* 61 | 73786976294838206464 */ 100000000000000000000,
/* 62 | 36893488147419103232 */ 100000000000000000000,
/* 63 | 18446744073709551616 */ 100000000000000000000,
/* 64 | 9223372036854775808 */ 10000000000000000000,
/* 65 | 4611686018427387904 */ 10000000000000000000,
/* 66 | 2305843009213693952 */ 10000000000000000000,
/* 67 | 1152921504606846976 */ 10000000000000000000,
/* 68 | 576460752303423488 */ 1000000000000000000,
/* 69 | 288230376151711744 */ 1000000000000000000,
/* 70 | 144115188075855872 */ 1000000000000000000,
/* 71 | 72057594037927936 */ 100000000000000000,
/* 72 | 36028797018963968 */ 100000000000000000,
/* 73 | 18014398509481984 */ 100000000000000000,
/* 74 | 9007199254740992 */ 10000000000000000,
/* 75 | 4503599627370496 */ 10000000000000000,
/* 76 | 2251799813685248 */ 10000000000000000,
/* 77 | 1125899906842624 */ 10000000000000000,
/* 78 | 562949953421312 */ 1000000000000000,
/* 79 | 281474976710656 */ 1000000000000000,
/* 80 | 140737488355328 */ 1000000000000000,
/* 81 | 70368744177664 */ 100000000000000,
/* 82 | 35184372088832 */ 100000000000000,
/* 83 | 17592186044416 */ 100000000000000,
/* 84 | 8796093022208 */ 10000000000000,
/* 85 | 4398046511104 */ 10000000000000,
/* 86 | 2199023255552 */ 10000000000000,
/* 87 | 1099511627776 */ 10000000000000,
/* 88 | 549755813888 */ 1000000000000,
/* 89 | 274877906944 */ 1000000000000,
/* 90 | 137438953472 */ 1000000000000,
/* 91 | 68719476736 */ 100000000000,
/* 92 | 34359738368 */ 100000000000,
/* 93 | 17179869184 */ 100000000000,
/* 94 | 8589934592 */ 10000000000,
/* 95 | 4294967296 */ 10000000000,
/* 96 | 2147483648 */ 10000000000,
/* 97 | 1073741824 */ 10000000000,
/* 98 | 536870912 */ 1000000000,
/* 99 | 268435456 */ 1000000000,
/* 100 | 134217728 */ 1000000000,
/* 101 | 67108864 */ 100000000,
/* 102 | 33554432 */ 100000000,
/* 103 | 16777216 */ 100000000,
/* 104 | 8388608 */ 10000000,
/* 105 | 4194304 */ 10000000,
/* 106 | 2097152 */ 10000000,
/* 107 | 1048576 */ 10000000,
/* 108 | 524288 */ 1000000,
/* 109 | 262144 */ 1000000,
/* 110 | 131072 */ 1000000,
/* 111 | 65536 */ 100000,
/* 112 | 32768 */ 100000,
/* 113 | 16384 */ 100000,
/* 114 | 8192 */ 10000,
/* 115 | 4096 */ 10000,
/* 116 | 2048 */ 10000,
/* 117 | 1024 */ 10000,
/* 118 | 512 */ 1000,
/* 119 | 256 */ 1000,
/* 120 | 128 */ 1000,
/* 121 | 64 */ 100,
/* 122 | 32 */ 100,
/* 123 | 16 */ 100,
/* 124 | 8 */ 10,
/* 125 | 4 */ 10,
/* 126 | 2 */ 10,
/* 127 | 1 */ 1,
/* 128 | 0 */ 1,
];
/// Acts as a map for any given `x: i64`:
/// Leading zeros count in `x` -> The closest power of ten
#[rustfmt::skip]
#[cfg(feature = "i64")]
#[allow(clippy::all, non_upper_case_globals)]
pub(crate) static i64: [i64; 65] = [
// lz | value | next power of ten
//-----+------------------------------------------+------------------
/* 0 | 9223372036854775808 */ 0 /* overflow */,
/* 1 | 4611686018427387904 */ 0 /* overflow */,
/* 2 | 2305843009213693952 */ 0 /* overflow */,
/* 3 | 1152921504606846976 */ 0 /* overflow */,
/* 4 | 576460752303423488 */ 1000000000000000000,
/* 5 | 288230376151711744 */ 1000000000000000000,
/* 6 | 144115188075855872 */ 1000000000000000000,
/* 7 | 72057594037927936 */ 100000000000000000,
/* 8 | 36028797018963968 */ 100000000000000000,
/* 9 | 18014398509481984 */ 100000000000000000,
/* 10 | 9007199254740992 */ 10000000000000000,
/* 11 | 4503599627370496 */ 10000000000000000,
/* 12 | 2251799813685248 */ 10000000000000000,
/* 13 | 1125899906842624 */ 10000000000000000,
/* 14 | 562949953421312 */ 1000000000000000,
/* 15 | 281474976710656 */ 1000000000000000,
/* 16 | 140737488355328 */ 1000000000000000,
/* 17 | 70368744177664 */ 100000000000000,
/* 18 | 35184372088832 */ 100000000000000,
/* 19 | 17592186044416 */ 100000000000000,
/* 20 | 8796093022208 */ 10000000000000,
/* 21 | 4398046511104 */ 10000000000000,
/* 22 | 2199023255552 */ 10000000000000,
/* 23 | 1099511627776 */ 10000000000000,
/* 24 | 549755813888 */ 1000000000000,
/* 25 | 274877906944 */ 1000000000000,
/* 26 | 137438953472 */ 1000000000000,
/* 27 | 68719476736 */ 100000000000,
/* 28 | 34359738368 */ 100000000000,
/* 29 | 17179869184 */ 100000000000,
/* 30 | 8589934592 */ 10000000000,
/* 31 | 4294967296 */ 10000000000,
/* 32 | 2147483648 */ 10000000000,
/* 33 | 1073741824 */ 10000000000,
/* 34 | 536870912 */ 1000000000,
/* 35 | 268435456 */ 1000000000,
/* 36 | 134217728 */ 1000000000,
/* 37 | 67108864 */ 100000000,
/* 38 | 33554432 */ 100000000,
/* 39 | 16777216 */ 100000000,
/* 40 | 8388608 */ 10000000,
/* 41 | 4194304 */ 10000000,
/* 42 | 2097152 */ 10000000,
/* 43 | 1048576 */ 10000000,
/* 44 | 524288 */ 1000000,
/* 45 | 262144 */ 1000000,
/* 46 | 131072 */ 1000000,
/* 47 | 65536 */ 100000,
/* 48 | 32768 */ 100000,
/* 49 | 16384 */ 100000,
/* 50 | 8192 */ 10000,
/* 51 | 4096 */ 10000,
/* 52 | 2048 */ 10000,
/* 53 | 1024 */ 10000,
/* 54 | 512 */ 1000,
/* 55 | 256 */ 1000,
/* 56 | 128 */ 1000,
/* 57 | 64 */ 100,
/* 58 | 32 */ 100,
/* 59 | 16 */ 100,
/* 60 | 8 */ 10,
/* 61 | 4 */ 10,
/* 62 | 2 */ 10,
/* 63 | 1 */ 1,
/* 64 | 0 */ 1,
];
/// Acts as a map for any given `x: i32`:
/// Leading zeros count in `x` -> The closest power of ten
#[rustfmt::skip]
#[cfg(feature = "i32")]
#[allow(clippy::all, non_upper_case_globals)]
pub(crate) static i32: [i32; 33] = [
// lz | value | next power of ten
//-----+------------------------------------------+------------------
/* 0 | 2147483648 */ 0 /* overflow */,
/* 1 | 1073741824 */ 0 /* overflow */,
/* 2 | 536870912 */ 1000000000,
/* 3 | 268435456 */ 1000000000,
/* 4 | 134217728 */ 1000000000,
/* 5 | 67108864 */ 100000000,
/* 6 | 33554432 */ 100000000,
/* 7 | 16777216 */ 100000000,
/* 8 | 8388608 */ 10000000,
/* 9 | 4194304 */ 10000000,
/* 10 | 2097152 */ 10000000,
/* 11 | 1048576 */ 10000000,
/* 12 | 524288 */ 1000000,
/* 13 | 262144 */ 1000000,
/* 14 | 131072 */ 1000000,
/* 15 | 65536 */ 100000,
/* 16 | 32768 */ 100000,
/* 17 | 16384 */ 100000,
/* 18 | 8192 */ 10000,
/* 19 | 4096 */ 10000,
/* 20 | 2048 */ 10000,
/* 21 | 1024 */ 10000,
/* 22 | 512 */ 1000,
/* 23 | 256 */ 1000,
/* 24 | 128 */ 1000,
/* 25 | 64 */ 100,
/* 26 | 32 */ 100,
/* 27 | 16 */ 100,
/* 28 | 8 */ 10,
/* 29 | 4 */ 10,
/* 30 | 2 */ 10,
/* 31 | 1 */ 1,
/* 32 | 0 */ 1,
];
/// Acts as a map for any given `x: i16`:
/// Leading zeros count in `x` -> The closest power of ten
#[rustfmt::skip]
#[cfg(feature = "i16")]
#[allow(clippy::all, non_upper_case_globals)]
pub(crate) static i16: [i16; 17] = [
// lz | value | next power of ten
//-----+------------------------------------------+------------------
/* 0 | 32768 */ 0 /* overflow */,
/* 1 | 16384 */ 0 /* overflow */,
/* 2 | 8192 */ 10000,
/* 3 | 4096 */ 10000,
/* 4 | 2048 */ 10000,
/* 5 | 1024 */ 10000,
/* 6 | 512 */ 1000,
/* 7 | 256 */ 1000,
/* 8 | 128 */ 1000,
/* 9 | 64 */ 100,
/* 10 | 32 */ 100,
/* 11 | 16 */ 100,
/* 12 | 8 */ 10,
/* 13 | 4 */ 10,
/* 14 | 2 */ 10,
/* 15 | 1 */ 1,
/* 16 | 0 */ 1,
];
/// Acts as a map for any given `x: u128`:
/// Leading zeros count in `x` -> Exponent of the closest power of ten.
/*
* Script for generating the table content.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import math
BITS_COUNT = 128
next_power_of_ten = lambda x: math.ceil(math.log10(x))
values = [2 ** (i - 1) for i in reversed(range(0, BITS_COUNT + 1))]
powers = [next_power_of_ten(value) for value in values]
for lz, (value, power) in enumerate(zip(values, powers)):
if power >= 2 ** (BITS_COUNT - 1):
print('/* %3d | %39d */ 0 /* overflow */,' % (lz, value))
else:
print('/* %3d | %39d */ %d,' % (lz, value, power))
*/
#[rustfmt::skip]
pub(crate) static NEXT_EXPONENT_10: [u8; 129] = [
// lz | min x | next exponent_10
//-----+------------------------------------------+-----------------
/* 0 | 170141183460469231731687303715884105728 */ 39,
/* 1 | 85070591730234615865843651857942052864 */ 38,
/* 2 | 42535295865117307932921825928971026432 */ 38,
/* 3 | 21267647932558653966460912964485513216 */ 38,
/* 4 | 10633823966279326983230456482242756608 */ 38,
/* 5 | 5316911983139663491615228241121378304 */ 37,
/* 6 | 2658455991569831745807614120560689152 */ 37,
/* 7 | 1329227995784915872903807060280344576 */ 37,
/* 8 | 664613997892457936451903530140172288 */ 36,
/* 9 | 332306998946228968225951765070086144 */ 36,
/* 10 | 166153499473114484112975882535043072 */ 36,
/* 11 | 83076749736557242056487941267521536 */ 35,
/* 12 | 41538374868278621028243970633760768 */ 35,
/* 13 | 20769187434139310514121985316880384 */ 35,
/* 14 | 10384593717069655257060992658440192 */ 35,
/* 15 | 5192296858534827628530496329220096 */ 34,
/* 16 | 2596148429267413814265248164610048 */ 34,
/* 17 | 1298074214633706907132624082305024 */ 34,
/* 18 | 649037107316853453566312041152512 */ 33,
/* 19 | 324518553658426726783156020576256 */ 33,
/* 20 | 162259276829213363391578010288128 */ 33,
/* 21 | 81129638414606681695789005144064 */ 32,
/* 22 | 40564819207303340847894502572032 */ 32,
/* 23 | 20282409603651670423947251286016 */ 32,
/* 24 | 10141204801825835211973625643008 */ 32,
/* 25 | 5070602400912917605986812821504 */ 31,
/* 26 | 2535301200456458802993406410752 */ 31,
/* 27 | 1267650600228229401496703205376 */ 31,
/* 28 | 633825300114114700748351602688 */ 30,
/* 29 | 316912650057057350374175801344 */ 30,
/* 30 | 158456325028528675187087900672 */ 30,
/* 31 | 79228162514264337593543950336 */ 29,
/* 32 | 39614081257132168796771975168 */ 29,
/* 33 | 19807040628566084398385987584 */ 29,
/* 34 | 9903520314283042199192993792 */ 28,
/* 35 | 4951760157141521099596496896 */ 28,
/* 36 | 2475880078570760549798248448 */ 28,
/* 37 | 1237940039285380274899124224 */ 28,
/* 38 | 618970019642690137449562112 */ 27,
/* 39 | 309485009821345068724781056 */ 27,
/* 40 | 154742504910672534362390528 */ 27,
/* 41 | 77371252455336267181195264 */ 26,
/* 42 | 38685626227668133590597632 */ 26,
/* 43 | 19342813113834066795298816 */ 26,
/* 44 | 9671406556917033397649408 */ 25,
/* 45 | 4835703278458516698824704 */ 25,
/* 46 | 2417851639229258349412352 */ 25,
/* 47 | 1208925819614629174706176 */ 25,
/* 48 | 604462909807314587353088 */ 24,
/* 49 | 302231454903657293676544 */ 24,
/* 50 | 151115727451828646838272 */ 24,
/* 51 | 75557863725914323419136 */ 23,
/* 52 | 37778931862957161709568 */ 23,
/* 53 | 18889465931478580854784 */ 23,
/* 54 | 9444732965739290427392 */ 22,
/* 55 | 4722366482869645213696 */ 22,
/* 56 | 2361183241434822606848 */ 22,
/* 57 | 1180591620717411303424 */ 22,
/* 58 | 590295810358705651712 */ 21,
/* 59 | 295147905179352825856 */ 21,
/* 60 | 147573952589676412928 */ 21,
/* 61 | 73786976294838206464 */ 20,
/* 62 | 36893488147419103232 */ 20,
/* 63 | 18446744073709551616 */ 20,
/* 64 | 9223372036854775808 */ 19,
/* 65 | 4611686018427387904 */ 19,
/* 66 | 2305843009213693952 */ 19,
/* 67 | 1152921504606846976 */ 19,
/* 68 | 576460752303423488 */ 18,
/* 69 | 288230376151711744 */ 18,
/* 70 | 144115188075855872 */ 18,
/* 71 | 72057594037927936 */ 17,
/* 72 | 36028797018963968 */ 17,
/* 73 | 18014398509481984 */ 17,
/* 74 | 9007199254740992 */ 16,
/* 75 | 4503599627370496 */ 16,
/* 76 | 2251799813685248 */ 16,
/* 77 | 1125899906842624 */ 16,
/* 78 | 562949953421312 */ 15,
/* 79 | 281474976710656 */ 15,
/* 80 | 140737488355328 */ 15,
/* 81 | 70368744177664 */ 14,
/* 82 | 35184372088832 */ 14,
/* 83 | 17592186044416 */ 14,
/* 84 | 8796093022208 */ 13,
/* 85 | 4398046511104 */ 13,
/* 86 | 2199023255552 */ 13,
/* 87 | 1099511627776 */ 13,
/* 88 | 549755813888 */ 12,
/* 89 | 274877906944 */ 12,
/* 90 | 137438953472 */ 12,
/* 91 | 68719476736 */ 11,
/* 92 | 34359738368 */ 11,
/* 93 | 17179869184 */ 11,
/* 94 | 8589934592 */ 10,
/* 95 | 4294967296 */ 10,
/* 96 | 2147483648 */ 10,
/* 97 | 1073741824 */ 10,
/* 98 | 536870912 */ 9,
/* 99 | 268435456 */ 9,
/* 100 | 134217728 */ 9,
/* 101 | 67108864 */ 8,
/* 102 | 33554432 */ 8,
/* 103 | 16777216 */ 8,
/* 104 | 8388608 */ 7,
/* 105 | 4194304 */ 7,
/* 106 | 2097152 */ 7,
/* 107 | 1048576 */ 7,
/* 108 | 524288 */ 6,
/* 109 | 262144 */ 6,
/* 110 | 131072 */ 6,
/* 111 | 65536 */ 5,
/* 112 | 32768 */ 5,
/* 113 | 16384 */ 5,
/* 114 | 8192 */ 4,
/* 115 | 4096 */ 4,
/* 116 | 2048 */ 4,
/* 117 | 1024 */ 4,
/* 118 | 512 */ 3,
/* 119 | 256 */ 3,
/* 120 | 128 */ 3,
/* 121 | 64 */ 2,
/* 122 | 32 */ 2,
/* 123 | 16 */ 2,
/* 124 | 8 */ 1,
/* 125 | 4 */ 1,
/* 126 | 2 */ 1,
/* 127 | 1 */ 0,
/* 128 | 0 */ 0,
];
/// Table allowing to map leading zeros in integer `x` -> Exponent of the closest power of five.
/*
* Script for generating the table content.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import math
BITS_COUNT = 128
for lz in range(0, BITS_COUNT):
exponent_5 = math.floor(lz / math.log2(5))
print('/* %3d | %39d | %38d */ %d,' % (lz, 2 ** (BITS_COUNT - lz - 1), 5 ** exponent_5, exponent_5))
*/
#[rustfmt::skip]
pub(crate) static MAX_EXPONENT_5: [u8; 128] = [
// lz | min value | max multiplier, power of 5 | max exp 5
//-----+-----------------------------------------+-----------------------------------------+----------
/* 0 | 170141183460469231731687303715884105728 | 1 */ 0,
/* 1 | 85070591730234615865843651857942052864 | 1 */ 0,
/* 2 | 42535295865117307932921825928971026432 | 1 */ 0,
/* 3 | 21267647932558653966460912964485513216 | 5 */ 1,
/* 4 | 10633823966279326983230456482242756608 | 5 */ 1,
/* 5 | 5316911983139663491615228241121378304 | 25 */ 2,
/* 6 | 2658455991569831745807614120560689152 | 25 */ 2,
/* 7 | 1329227995784915872903807060280344576 | 125 */ 3,
/* 8 | 664613997892457936451903530140172288 | 125 */ 3,
/* 9 | 332306998946228968225951765070086144 | 125 */ 3,
/* 10 | 166153499473114484112975882535043072 | 625 */ 4,
/* 11 | 83076749736557242056487941267521536 | 625 */ 4,
/* 12 | 41538374868278621028243970633760768 | 3125 */ 5,
/* 13 | 20769187434139310514121985316880384 | 3125 */ 5,
/* 14 | 10384593717069655257060992658440192 | 15625 */ 6,
/* 15 | 5192296858534827628530496329220096 | 15625 */ 6,
/* 16 | 2596148429267413814265248164610048 | 15625 */ 6,
/* 17 | 1298074214633706907132624082305024 | 78125 */ 7,
/* 18 | 649037107316853453566312041152512 | 78125 */ 7,
/* 19 | 324518553658426726783156020576256 | 390625 */ 8,
/* 20 | 162259276829213363391578010288128 | 390625 */ 8,
/* 21 | 81129638414606681695789005144064 | 1953125 */ 9,
/* 22 | 40564819207303340847894502572032 | 1953125 */ 9,
/* 23 | 20282409603651670423947251286016 | 1953125 */ 9,
/* 24 | 10141204801825835211973625643008 | 9765625 */ 10,
/* 25 | 5070602400912917605986812821504 | 9765625 */ 10,
/* 26 | 2535301200456458802993406410752 | 48828125 */ 11,
/* 27 | 1267650600228229401496703205376 | 48828125 */ 11,
/* 28 | 633825300114114700748351602688 | 244140625 */ 12,
/* 29 | 316912650057057350374175801344 | 244140625 */ 12,
/* 30 | 158456325028528675187087900672 | 244140625 */ 12,
/* 31 | 79228162514264337593543950336 | 1220703125 */ 13,
/* 32 | 39614081257132168796771975168 | 1220703125 */ 13,
/* 33 | 19807040628566084398385987584 | 6103515625 */ 14,
/* 34 | 9903520314283042199192993792 | 6103515625 */ 14,
/* 35 | 4951760157141521099596496896 | 30517578125 */ 15,
/* 36 | 2475880078570760549798248448 | 30517578125 */ 15,
/* 37 | 1237940039285380274899124224 | 30517578125 */ 15,
/* 38 | 618970019642690137449562112 | 152587890625 */ 16,
/* 39 | 309485009821345068724781056 | 152587890625 */ 16,
/* 40 | 154742504910672534362390528 | 762939453125 */ 17,
/* 41 | 77371252455336267181195264 | 762939453125 */ 17,
/* 42 | 38685626227668133590597632 | 3814697265625 */ 18,
/* 43 | 19342813113834066795298816 | 3814697265625 */ 18,
/* 44 | 9671406556917033397649408 | 3814697265625 */ 18,
/* 45 | 4835703278458516698824704 | 19073486328125 */ 19,
/* 46 | 2417851639229258349412352 | 19073486328125 */ 19,
/* 47 | 1208925819614629174706176 | 95367431640625 */ 20,
/* 48 | 604462909807314587353088 | 95367431640625 */ 20,
/* 49 | 302231454903657293676544 | 476837158203125 */ 21,
/* 50 | 151115727451828646838272 | 476837158203125 */ 21,
/* 51 | 75557863725914323419136 | 476837158203125 */ 21,
/* 52 | 37778931862957161709568 | 2384185791015625 */ 22,
/* 53 | 18889465931478580854784 | 2384185791015625 */ 22,
/* 54 | 9444732965739290427392 | 11920928955078125 */ 23,
/* 55 | 4722366482869645213696 | 11920928955078125 */ 23,
/* 56 | 2361183241434822606848 | 59604644775390625 */ 24,
/* 57 | 1180591620717411303424 | 59604644775390625 */ 24,
/* 58 | 590295810358705651712 | 59604644775390625 */ 24,
/* 59 | 295147905179352825856 | 298023223876953125 */ 25,
/* 60 | 147573952589676412928 | 298023223876953125 */ 25,
/* 61 | 73786976294838206464 | 1490116119384765625 */ 26,
/* 62 | 36893488147419103232 | 1490116119384765625 */ 26,
/* 63 | 18446744073709551616 | 7450580596923828125 */ 27,
/* 64 | 9223372036854775808 | 7450580596923828125 */ 27,
/* 65 | 4611686018427387904 | 7450580596923828125 */ 27,
/* 66 | 2305843009213693952 | 37252902984619140625 */ 28,
/* 67 | 1152921504606846976 | 37252902984619140625 */ 28,
/* 68 | 576460752303423488 | 186264514923095703125 */ 29,
/* 69 | 288230376151711744 | 186264514923095703125 */ 29,
/* 70 | 144115188075855872 | 931322574615478515625 */ 30,
/* 71 | 72057594037927936 | 931322574615478515625 */ 30,
/* 72 | 36028797018963968 | 4656612873077392578125 */ 31,
/* 73 | 18014398509481984 | 4656612873077392578125 */ 31,
/* 74 | 9007199254740992 | 4656612873077392578125 */ 31,
/* 75 | 4503599627370496 | 23283064365386962890625 */ 32,
/* 76 | 2251799813685248 | 23283064365386962890625 */ 32,
/* 77 | 1125899906842624 | 116415321826934814453125 */ 33,
/* 78 | 562949953421312 | 116415321826934814453125 */ 33,
/* 79 | 281474976710656 | 582076609134674072265625 */ 34,
/* 80 | 140737488355328 | 582076609134674072265625 */ 34,
/* 81 | 70368744177664 | 582076609134674072265625 */ 34,
/* 82 | 35184372088832 | 2910383045673370361328125 */ 35,
/* 83 | 17592186044416 | 2910383045673370361328125 */ 35,
/* 84 | 8796093022208 | 14551915228366851806640625 */ 36,
/* 85 | 4398046511104 | 14551915228366851806640625 */ 36,
/* 86 | 2199023255552 | 72759576141834259033203125 */ 37,
/* 87 | 1099511627776 | 72759576141834259033203125 */ 37,
/* 88 | 549755813888 | 72759576141834259033203125 */ 37,
/* 89 | 274877906944 | 363797880709171295166015625 */ 38,
/* 90 | 137438953472 | 363797880709171295166015625 */ 38,
/* 91 | 68719476736 | 1818989403545856475830078125 */ 39,
/* 92 | 34359738368 | 1818989403545856475830078125 */ 39,
/* 93 | 17179869184 | 9094947017729282379150390625 */ 40,
/* 94 | 8589934592 | 9094947017729282379150390625 */ 40,
/* 95 | 4294967296 | 9094947017729282379150390625 */ 40,
/* 96 | 2147483648 | 45474735088646411895751953125 */ 41,
/* 97 | 1073741824 | 45474735088646411895751953125 */ 41,
/* 98 | 536870912 | 227373675443232059478759765625 */ 42,
/* 99 | 268435456 | 227373675443232059478759765625 */ 42,
/* 100 | 134217728 | 1136868377216160297393798828125 */ 43,
/* 101 | 67108864 | 1136868377216160297393798828125 */ 43,
/* 102 | 33554432 | 1136868377216160297393798828125 */ 43,
/* 103 | 16777216 | 5684341886080801486968994140625 */ 44,
/* 104 | 8388608 | 5684341886080801486968994140625 */ 44,
/* 105 | 4194304 | 28421709430404007434844970703125 */ 45,
/* 106 | 2097152 | 28421709430404007434844970703125 */ 45,
/* 107 | 1048576 | 142108547152020037174224853515625 */ 46,
/* 108 | 524288 | 142108547152020037174224853515625 */ 46,
/* 109 | 262144 | 142108547152020037174224853515625 */ 46,
/* 110 | 131072 | 710542735760100185871124267578125 */ 47,
/* 111 | 65536 | 710542735760100185871124267578125 */ 47,
/* 112 | 32768 | 3552713678800500929355621337890625 */ 48,
/* 113 | 16384 | 3552713678800500929355621337890625 */ 48,
/* 114 | 8192 | 17763568394002504646778106689453125 */ 49,
/* 115 | 4096 | 17763568394002504646778106689453125 */ 49,
/* 116 | 2048 | 17763568394002504646778106689453125 */ 49,
/* 117 | 1024 | 88817841970012523233890533447265625 */ 50,
/* 118 | 512 | 88817841970012523233890533447265625 */ 50,
/* 119 | 256 | 444089209850062616169452667236328125 */ 51,
/* 120 | 128 | 444089209850062616169452667236328125 */ 51,
/* 121 | 64 | 2220446049250313080847263336181640625 */ 52,
/* 122 | 32 | 2220446049250313080847263336181640625 */ 52,
/* 123 | 16 | 2220446049250313080847263336181640625 */ 52,
/* 124 | 8 | 11102230246251565404236316680908203125 */ 53,
/* 125 | 4 | 11102230246251565404236316680908203125 */ 53,
/* 126 | 2 | 55511151231257827021181583404541015625 */ 54,
/* 127 | 1 | 55511151231257827021181583404541015625 */ 54,
];
/// Table allowing to map `x` -> `(10 ^ x, remainder_for_f64_rounding)`
/*
* Script for generating the table content.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
import itertools
exponents_10 = list(range(0, 39))
remainder = lambda rem, exponent_10: rem + 10 ** (exponent_10 - 1) * 4
for (exponent_10, rem) in zip(exponents_10, itertools.accumulate(exponents_10, remainder)):
print('/* %5d */ (%39d, %38d),' % (exponent_10, 10 ** exponent_10, rem))
*/
#[rustfmt::skip]
pub(crate) static POWERS_OF_10: [(u128, u128); 39] = [
// exp10 | 10 ^ exp10 | remainder threshold
//--------|-----------------------------------------|----------------------------------------
/* 0 */ ( 1, 0),
/* 1 */ ( 10, 4),
/* 2 */ ( 100, 44),
/* 3 */ ( 1000, 444),
/* 4 */ ( 10000, 4444),
/* 5 */ ( 100000, 44444),
/* 6 */ ( 1000000, 444444),
/* 7 */ ( 10000000, 4444444),
/* 8 */ ( 100000000, 44444444),
/* 9 */ ( 1000000000, 444444444),
/* 10 */ ( 10000000000, 4444444444),
/* 11 */ ( 100000000000, 44444444444),
/* 12 */ ( 1000000000000, 444444444444),
/* 13 */ ( 10000000000000, 4444444444444),
/* 14 */ ( 100000000000000, 44444444444444),
/* 15 */ ( 1000000000000000, 444444444444444),
/* 16 */ ( 10000000000000000, 4444444444444444),
/* 17 */ ( 100000000000000000, 44444444444444444),
/* 18 */ ( 1000000000000000000, 444444444444444444),
/* 19 */ ( 10000000000000000000, 4444444444444444444),
/* 20 */ ( 100000000000000000000, 44444444444444444444),
/* 21 */ ( 1000000000000000000000, 444444444444444444444),
/* 22 */ ( 10000000000000000000000, 4444444444444444444444),
/* 23 */ ( 100000000000000000000000, 44444444444444444444444),
/* 24 */ ( 1000000000000000000000000, 444444444444444444444444),
/* 25 */ ( 10000000000000000000000000, 4444444444444444444444444),
/* 26 */ ( 100000000000000000000000000, 44444444444444444444444444),
/* 27 */ ( 1000000000000000000000000000, 444444444444444444444444444),
/* 28 */ ( 10000000000000000000000000000, 4444444444444444444444444444),
/* 29 */ ( 100000000000000000000000000000, 44444444444444444444444444444),
/* 30 */ ( 1000000000000000000000000000000, 444444444444444444444444444444),
/* 31 */ ( 10000000000000000000000000000000, 4444444444444444444444444444444),
/* 32 */ ( 100000000000000000000000000000000, 44444444444444444444444444444444),
/* 33 */ ( 1000000000000000000000000000000000, 444444444444444444444444444444444),
/* 34 */ ( 10000000000000000000000000000000000, 4444444444444444444444444444444444),
/* 35 */ ( 100000000000000000000000000000000000, 44444444444444444444444444444444444),
/* 36 */ ( 1000000000000000000000000000000000000, 444444444444444444444444444444444444),
/* 37 */ ( 10000000000000000000000000000000000000, 4444444444444444444444444444444444444),
/* 38 */ (100000000000000000000000000000000000000, 44444444444444444444444444444444444444),
];
/// Table allowing to map `x` -> `5 ^ x`
/*
* Script for generating the table content.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
for exponent_5 in range(0, 56):
print('/* %4d */ %39d,' % (exponent_5, 5 ** exponent_5))
*/
#[rustfmt::skip]
pub(crate) static POWERS_OF_5: [u128; 56] = [
// exp5 | value
//-------|----------------------------------------
/* 0 */ 1,
/* 1 */ 5,
/* 2 */ 25,
/* 3 */ 125,
/* 4 */ 625,
/* 5 */ 3125,
/* 6 */ 15625,
/* 7 */ 78125,
/* 8 */ 390625,
/* 9 */ 1953125,
/* 10 */ 9765625,
/* 11 */ 48828125,
/* 12 */ 244140625,
/* 13 */ 1220703125,
/* 14 */ 6103515625,
/* 15 */ 30517578125,
/* 16 */ 152587890625,
/* 17 */ 762939453125,
/* 18 */ 3814697265625,
/* 19 */ 19073486328125,
/* 20 */ 95367431640625,
/* 21 */ 476837158203125,
/* 22 */ 2384185791015625,
/* 23 */ 11920928955078125,
/* 24 */ 59604644775390625,
/* 25 */ 298023223876953125,
/* 26 */ 1490116119384765625,
/* 27 */ 7450580596923828125,
/* 28 */ 37252902984619140625,
/* 29 */ 186264514923095703125,
/* 30 */ 931322574615478515625,
/* 31 */ 4656612873077392578125,
/* 32 */ 23283064365386962890625,
/* 33 */ 116415321826934814453125,
/* 34 */ 582076609134674072265625,
/* 35 */ 2910383045673370361328125,
/* 36 */ 14551915228366851806640625,
/* 37 */ 72759576141834259033203125,
/* 38 */ 363797880709171295166015625,
/* 39 */ 1818989403545856475830078125,
/* 40 */ 9094947017729282379150390625,
/* 41 */ 45474735088646411895751953125,
/* 42 */ 227373675443232059478759765625,
/* 43 */ 1136868377216160297393798828125,
/* 44 */ 5684341886080801486968994140625,
/* 45 */ 28421709430404007434844970703125,
/* 46 */ 142108547152020037174224853515625,
/* 47 */ 710542735760100185871124267578125,
/* 48 */ 3552713678800500929355621337890625,
/* 49 */ 17763568394002504646778106689453125,
/* 50 */ 88817841970012523233890533447265625,
/* 51 */ 444089209850062616169452667236328125,
/* 52 */ 2220446049250313080847263336181640625,
/* 53 */ 11102230246251565404236316680908203125,
/* 54 */ 55511151231257827021181583404541015625,
/* 55 */ 277555756156289135105907917022705078125,
];
pub(crate) fn power_of_10(pow: u32) -> Option<u128> {
POWERS_OF_10.get(pow as usize).map(|&(res, _)| res)
}
pub(crate) fn rdiv_by_exponent_10(x: u128, exp10: u32) -> u128 {
POWERS_OF_10
.get(exp10 as usize)
.map(|&(divisor, remainder)| {
let res = x / divisor;
if x % divisor > remainder {
res + 1
} else {
res
}
})
.unwrap_or(0)
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn power_of_10_regular_values() {
assert_eq!(power_of_10(0).unwrap(), 1);
assert_eq!(power_of_10(1).unwrap(), 10);
assert_eq!(power_of_10(2).unwrap(), 100);
assert_eq!(power_of_10(20).unwrap(), 100_000_000_000_000_000_000);
}
#[test]
fn power_of_10_overflow() {
assert!(power_of_10(39).is_none());
}
#[test]
fn rdiv_by_exp10_regular_values() {
assert_eq!(rdiv_by_exponent_10(987_659, 0), 987_659);
assert_eq!(rdiv_by_exponent_10(123_444_444, 6), 123);
assert_eq!(rdiv_by_exponent_10(123_444_445, 6), 124);
assert_eq!(rdiv_by_exponent_10(u128::MAX, 40), 0);
}
#[test]
fn rdiv_by_exp10_overflow() {
assert_eq!(rdiv_by_exponent_10(123_444_445, 39), 0);
assert_eq!(rdiv_by_exponent_10(u128::MAX, 40), 0);
}
}