blob: da57fa026b5f67e3490d868fa91b629ee0165a13 [file] [log] [blame]
/* Copyright (C) 2007-2022 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
Under Section 7 of GPL version 3, you are granted additional
permissions described in the GCC Runtime Library Exception, version
3.1, as published by the Free Software Foundation.
You should have received a copy of the GNU General Public License and
a copy of the GCC Runtime Library Exception along with this program;
see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
<http://www.gnu.org/licenses/>. */
#include "bid_internal.h"
// the first entry of nr_digits[i - 1] (where 1 <= i <= 113), indicates
// the number of decimal digits needed to represent a binary number with i bits;
// however, if a binary number of i bits may require either k or k + 1 decimal
// digits, then the first entry of nr_digits[i - 1] is 0; in this case if the
// number is less than the value represented by the second and third entries
// concatenated, then the number of decimal digits k is the fourth entry, else
// the number of decimal digits is the fourth entry plus 1
DEC_DIGITS nr_digits[] = { // only the first entry is used if it is not 0
{1, 0x0000000000000000ULL, 0x000000000000000aULL, 1}
, // 1-bit n < 10^1
{1, 0x0000000000000000ULL, 0x000000000000000aULL, 1}
, // 2-bit n < 10^1
{1, 0x0000000000000000ULL, 0x000000000000000aULL, 1}
, // 3-bit n < 10^1
{0, 0x0000000000000000ULL, 0x000000000000000aULL, 1}
, // 4-bit n ? 10^1
{2, 0x0000000000000000ULL, 0x0000000000000064ULL, 2}
, // 5-bit n < 10^2
{2, 0x0000000000000000ULL, 0x0000000000000064ULL, 2}
, // 6-bit n < 10^2
{0, 0x0000000000000000ULL, 0x0000000000000064ULL, 2}
, // 7-bit n ? 10^2
{3, 0x0000000000000000ULL, 0x00000000000003e8ULL, 3}
, // 8-bit n < 10^3
{3, 0x0000000000000000ULL, 0x00000000000003e8ULL, 3}
, // 9-bit n < 10^3
{0, 0x0000000000000000ULL, 0x00000000000003e8ULL, 3}
, // 10-bit n ? 10^3
{4, 0x0000000000000000ULL, 0x0000000000002710ULL, 4}
, // 11-bit n < 10^4
{4, 0x0000000000000000ULL, 0x0000000000002710ULL, 4}
, // 12-bit n < 10^4
{4, 0x0000000000000000ULL, 0x0000000000002710ULL, 4}
, // 13-bit n < 10^4
{0, 0x0000000000000000ULL, 0x0000000000002710ULL, 4}
, // 14-bit n ? 10^4
{5, 0x0000000000000000ULL, 0x00000000000186a0ULL, 5}
, // 15-bit n < 10^5
{5, 0x0000000000000000ULL, 0x00000000000186a0ULL, 5}
, // 16-bit n < 10^5
{0, 0x0000000000000000ULL, 0x00000000000186a0ULL, 5}
, // 17-bit n ? 10^5
{6, 0x0000000000000000ULL, 0x00000000000f4240ULL, 6}
, // 18-bit n < 10^6
{6, 0x0000000000000000ULL, 0x00000000000f4240ULL, 6}
, // 19-bit n < 10^6
{0, 0x0000000000000000ULL, 0x00000000000f4240ULL, 6}
, // 20-bit n ? 10^6
{7, 0x0000000000000000ULL, 0x0000000000989680ULL, 7}
, // 21-bit n < 10^7
{7, 0x0000000000000000ULL, 0x0000000000989680ULL, 7}
, // 22-bit n < 10^7
{7, 0x0000000000000000ULL, 0x0000000000989680ULL, 7}
, // 23-bit n < 10^7
{0, 0x0000000000000000ULL, 0x0000000000989680ULL, 7}
, // 24-bit n ? 10^7
{8, 0x0000000000000000ULL, 0x0000000005f5e100ULL, 8}
, // 25-bit n < 10^8
{8, 0x0000000000000000ULL, 0x0000000005f5e100ULL, 8}
, // 26-bit n < 10^8
{0, 0x0000000000000000ULL, 0x0000000005f5e100ULL, 8}
, // 27-bit n ? 10^8
{9, 0x0000000000000000ULL, 0x000000003b9aca00ULL, 9}
, // 28-bit n < 10^9
{9, 0x0000000000000000ULL, 0x000000003b9aca00ULL, 9}
, // 29-bit n < 10^9
{0, 0x0000000000000000ULL, 0x000000003b9aca00ULL, 9}
, // 30-bit n ? 10^9
{10, 0x0000000000000000ULL, 0x00000002540be400ULL, 10}
, // 31-bit n < 10^10
{10, 0x0000000000000000ULL, 0x00000002540be400ULL, 10}
, // 32-bit n < 10^10
{10, 0x0000000000000000ULL, 0x00000002540be400ULL, 10}
, // 33-bit n < 10^10
{0, 0x0000000000000000ULL, 0x00000002540be400ULL, 10}
, // 34-bit n ? 10^10
{11, 0x0000000000000000ULL, 0x000000174876e800ULL, 11}
, // 35-bit n < 10^11
{11, 0x0000000000000000ULL, 0x000000174876e800ULL, 11}
, // 36-bit n < 10^11
{0, 0x0000000000000000ULL, 0x000000174876e800ULL, 11}
, // 37-bit n ? 10^11
{12, 0x0000000000000000ULL, 0x000000e8d4a51000ULL, 12}
, // 38-bit n < 10^12
{12, 0x0000000000000000ULL, 0x000000e8d4a51000ULL, 12}
, // 39-bit n < 10^12
{0, 0x0000000000000000ULL, 0x000000e8d4a51000ULL, 12}
, // 40-bit n ? 10^12
{13, 0x0000000000000000ULL, 0x000009184e72a000ULL, 13}
, // 41-bit n < 10^13
{13, 0x0000000000000000ULL, 0x000009184e72a000ULL, 13}
, // 42-bit n < 10^13
{13, 0x0000000000000000ULL, 0x000009184e72a000ULL, 13}
, // 43-bit n < 10^13
{0, 0x0000000000000000ULL, 0x000009184e72a000ULL, 13}
, // 44-bit n ? 10^13
{14, 0x0000000000000000ULL, 0x00005af3107a4000ULL, 14}
, // 45-bit n < 10^14
{14, 0x0000000000000000ULL, 0x00005af3107a4000ULL, 14}
, // 46-bit n < 10^14
{0, 0x0000000000000000ULL, 0x00005af3107a4000ULL, 14}
, // 47-bit n ? 10^14
{15, 0x0000000000000000ULL, 0x00038d7ea4c68000ULL, 15}
, // 48-bit n < 10^15
{15, 0x0000000000000000ULL, 0x00038d7ea4c68000ULL, 15}
, // 49-bit n < 10^15
{0, 0x0000000000000000ULL, 0x00038d7ea4c68000ULL, 15}
, // 50-bit n ? 10^15
{16, 0x0000000000000000ULL, 0x002386f26fc10000ULL, 16}
, // 51-bit n < 10^16
{16, 0x0000000000000000ULL, 0x002386f26fc10000ULL, 16}
, // 52-bit n < 10^16
{16, 0x0000000000000000ULL, 0x002386f26fc10000ULL, 16}
, // 53-bit n < 10^16
{0, 0x0000000000000000ULL, 0x002386f26fc10000ULL, 16}
, // 54-bit n ? 10^16
{17, 0x0000000000000000ULL, 0x016345785d8a0000ULL, 17}
, // 55-bit n < 10^17
{17, 0x0000000000000000ULL, 0x016345785d8a0000ULL, 17}
, // 56-bit n < 10^17
{0, 0x0000000000000000ULL, 0x016345785d8a0000ULL, 17}
, // 57-bit n ? 10^17
{18, 0x0000000000000000ULL, 0x0de0b6b3a7640000ULL, 18}
, // 58-bit n < 10^18
{18, 0x0000000000000000ULL, 0x0de0b6b3a7640000ULL, 18}
, // 59-bit n < 10^18
{0, 0x0000000000000000ULL, 0x0de0b6b3a7640000ULL, 18}
, // 60-bit n ? 10^18
{19, 0x0000000000000000ULL, 0x8ac7230489e80000ULL, 19}
, // 61-bit n < 10^19
{19, 0x0000000000000000ULL, 0x8ac7230489e80000ULL, 19}
, // 62-bit n < 10^19
{19, 0x0000000000000000ULL, 0x8ac7230489e80000ULL, 19}
, // 63-bit n < 10^19
{0, 0x0000000000000000ULL, 0x8ac7230489e80000ULL, 19}
, // 64-bit n ? 10^19
{20, 0x0000000000000005ULL, 0x6bc75e2d63100000ULL, 20}
, // 65-bit n < 10^20
{20, 0x0000000000000005ULL, 0x6bc75e2d63100000ULL, 20}
, // 66-bit n < 10^20
{0, 0x0000000000000005ULL, 0x6bc75e2d63100000ULL, 20}
, // 67-bit n ? 10^20
{21, 0x0000000000000036ULL, 0x35c9adc5dea00000ULL, 21}
, // 68-bit n < 10^21
{21, 0x0000000000000036ULL, 0x35c9adc5dea00000ULL, 21}
, // 69-bit n < 10^21
{0, 0x0000000000000036ULL, 0x35c9adc5dea00000ULL, 21}
, // 70-bit n ? 10^21
{22, 0x000000000000021eULL, 0x19e0c9bab2400000ULL, 22}
, // 71-bit n < 10^22
{22, 0x000000000000021eULL, 0x19e0c9bab2400000ULL, 22}
, // 72-bit n < 10^22
{22, 0x000000000000021eULL, 0x19e0c9bab2400000ULL, 22}
, // 73-bit n < 10^22
{0, 0x000000000000021eULL, 0x19e0c9bab2400000ULL, 22}
, // 74-bit n ? 10^22
{23, 0x000000000000152dULL, 0x02c7e14af6800000ULL, 23}
, // 75-bit n < 10^23
{23, 0x000000000000152dULL, 0x02c7e14af6800000ULL, 23}
, // 76-bit n < 10^23
{0, 0x000000000000152dULL, 0x02c7e14af6800000ULL, 23}
, // 77-bit n ? 10^23
{24, 0x000000000000d3c2ULL, 0x1bcecceda1000000ULL, 24}
, // 78-bit n < 10^24
{24, 0x000000000000d3c2ULL, 0x1bcecceda1000000ULL, 24}
, // 79-bit n < 10^24
{0, 0x000000000000d3c2ULL, 0x1bcecceda1000000ULL, 24}
, // 80-bit n ? 10^24
{25, 0x0000000000084595ULL, 0x161401484a000000ULL, 25}
, // 81-bit n < 10^25
{25, 0x0000000000084595ULL, 0x161401484a000000ULL, 25}
, // 82-bit n < 10^25
{25, 0x0000000000084595ULL, 0x161401484a000000ULL, 25}
, // 83-bit n < 10^25
{0, 0x0000000000084595ULL, 0x161401484a000000ULL, 25}
, // 84-bit n ? 10^25
{26, 0x000000000052b7d2ULL, 0xdcc80cd2e4000000ULL, 26}
, // 85-bit n < 10^26
{26, 0x000000000052b7d2ULL, 0xdcc80cd2e4000000ULL, 26}
, // 86-bit n < 10^26
{0, 0x000000000052b7d2ULL, 0xdcc80cd2e4000000ULL, 26}
, // 87-bit n ? 10^26
{27, 0x00000000033b2e3cULL, 0x9fd0803ce8000000ULL, 27}
, // 88-bit n < 10^27
{27, 0x00000000033b2e3cULL, 0x9fd0803ce8000000ULL, 27}
, // 89-bit n < 10^27
{0, 0x00000000033b2e3cULL, 0x9fd0803ce8000000ULL, 27}
, // 90-bit n ? 10^27
{28, 0x00000000204fce5eULL, 0x3e25026110000000ULL, 28}
, // 91-bit n < 10^28
{28, 0x00000000204fce5eULL, 0x3e25026110000000ULL, 28}
, // 92-bit n < 10^28
{28, 0x00000000204fce5eULL, 0x3e25026110000000ULL, 28}
, // 93-bit n < 10^28
{0, 0x00000000204fce5eULL, 0x3e25026110000000ULL, 28}
, // 94-bit n ? 10^28
{29, 0x00000001431e0faeULL, 0x6d7217caa0000000ULL, 29}
, // 95-bit n < 10^29
{29, 0x00000001431e0faeULL, 0x6d7217caa0000000ULL, 29}
, // 96-bit n < 10^29
{0, 0x00000001431e0faeULL, 0x6d7217caa0000000ULL, 29}
, // 97-bit n ? 10^29
{30, 0x0000000c9f2c9cd0ULL, 0x4674edea40000000ULL, 30}
, // 98-bit n < 10^30
{30, 0x0000000c9f2c9cd0ULL, 0x4674edea40000000ULL, 30}
, // 99-bit n < 10^30
{0, 0x0000000c9f2c9cd0ULL, 0x4674edea40000000ULL, 30}
, // 100-bit n ? 10^30
{31, 0x0000007e37be2022ULL, 0xc0914b2680000000ULL, 31}
, // 101-bit n < 10^31
{31, 0x0000007e37be2022ULL, 0xc0914b2680000000ULL, 31}
, // 102-bit n < 10^31
{0, 0x0000007e37be2022ULL, 0xc0914b2680000000ULL, 31}
, // 103-bit n ? 10^31
{32, 0x000004ee2d6d415bULL, 0x85acef8100000000ULL, 32}
, // 104-bit n < 10^32
{32, 0x000004ee2d6d415bULL, 0x85acef8100000000ULL, 32}
, // 105-bit n < 10^32
{32, 0x000004ee2d6d415bULL, 0x85acef8100000000ULL, 32}
, // 106-bit n < 10^32
{0, 0x000004ee2d6d415bULL, 0x85acef8100000000ULL, 32}
, // 107-bit n ? 10^32
{33, 0x0000314dc6448d93ULL, 0x38c15b0a00000000ULL, 33}
, // 108-bit n < 10^33
{33, 0x0000314dc6448d93ULL, 0x38c15b0a00000000ULL, 33}
, // 109-bit n < 10^33
{0, 0x0000314dc6448d93ULL, 0x38c15b0a00000000ULL, 33}
, // 100-bit n ? 10^33
{34, 0x0001ed09bead87c0ULL, 0x378d8e6400000000ULL, 34}
, // 111-bit n < 10^34
{34, 0x0001ed09bead87c0ULL, 0x378d8e6400000000ULL, 34}
, // 112-bit n < 10^34
{0, 0x0001ed09bead87c0ULL, 0x378d8e6400000000ULL, 34} // 113-bit n ? 10^34
//{ 35, 0x0013426172c74d82ULL, 0x2b878fe800000000ULL, 35 } // 114-bit n < 10^35
};
// midpoint64[i - 1] = 1/2 * 10^i = 5 * 10^(i-1), 1 <= i <= 19
UINT64 midpoint64[] = {
0x0000000000000005ULL, // 1/2 * 10^1 = 5 * 10^0
0x0000000000000032ULL, // 1/2 * 10^2 = 5 * 10^1
0x00000000000001f4ULL, // 1/2 * 10^3 = 5 * 10^2
0x0000000000001388ULL, // 1/2 * 10^4 = 5 * 10^3
0x000000000000c350ULL, // 1/2 * 10^5 = 5 * 10^4
0x000000000007a120ULL, // 1/2 * 10^6 = 5 * 10^5
0x00000000004c4b40ULL, // 1/2 * 10^7 = 5 * 10^6
0x0000000002faf080ULL, // 1/2 * 10^8 = 5 * 10^7
0x000000001dcd6500ULL, // 1/2 * 10^9 = 5 * 10^8
0x000000012a05f200ULL, // 1/2 * 10^10 = 5 * 10^9
0x0000000ba43b7400ULL, // 1/2 * 10^11 = 5 * 10^10
0x000000746a528800ULL, // 1/2 * 10^12 = 5 * 10^11
0x0000048c27395000ULL, // 1/2 * 10^13 = 5 * 10^12
0x00002d79883d2000ULL, // 1/2 * 10^14 = 5 * 10^13
0x0001c6bf52634000ULL, // 1/2 * 10^15 = 5 * 10^14
0x0011c37937e08000ULL, // 1/2 * 10^16 = 5 * 10^15
0x00b1a2bc2ec50000ULL, // 1/2 * 10^17 = 5 * 10^16
0x06f05b59d3b20000ULL, // 1/2 * 10^18 = 5 * 10^17
0x4563918244f40000ULL // 1/2 * 10^19 = 5 * 10^18
};
// midpoint128[i - 20] = 1/2 * 10^i = 5 * 10^(i-1), 20 <= i <= 38
UINT128 midpoint128[] = { // the 64-bit word order is L, H
{{0xb5e3af16b1880000ULL, 0x0000000000000002ULL}
}
, // 1/2 * 10^20 = 5 * 10^19
{{0x1ae4d6e2ef500000ULL, 0x000000000000001bULL}
}
, // 1/2 * 10^21 = 5 * 10^20
{{0x0cf064dd59200000ULL, 0x000000000000010fULL}
}
, // 1/2 * 10^22 = 5 * 10^21
{{0x8163f0a57b400000ULL, 0x0000000000000a96ULL}
}
, // 1/2 * 10^23 = 5 * 10^22
{{0x0de76676d0800000ULL, 0x00000000000069e1ULL}
}
, // 1/2 * 10^24 = 5 * 10^23
{{0x8b0a00a425000000ULL, 0x00000000000422caULL}
}
, // 1/2 * 10^25 = 5 * 10^24
{{0x6e64066972000000ULL, 0x0000000000295be9ULL}
}
, // 1/2 * 10^26 = 5 * 10^25
{{0x4fe8401e74000000ULL, 0x00000000019d971eULL}
}
, // 1/2 * 10^27 = 5 * 10^26
{{0x1f12813088000000ULL, 0x000000001027e72fULL}
}
, // 1/2 * 10^28 = 5 * 10^27
{{0x36b90be550000000ULL, 0x00000000a18f07d7ULL}
}
, // 1/2 * 10^29 = 5 * 10^28
{{0x233a76f520000000ULL, 0x000000064f964e68ULL}
}
, // 1/2 * 10^30 = 5 * 10^29
{{0x6048a59340000000ULL, 0x0000003f1bdf1011ULL}
}
, // 1/2 * 10^31 = 5 * 10^30
{{0xc2d677c080000000ULL, 0x0000027716b6a0adULL}
}
, // 1/2 * 10^32 = 5 * 10^31
{{0x9c60ad8500000000ULL, 0x000018a6e32246c9ULL}
}
, // 1/2 * 10^33 = 5 * 10^32
{{0x1bc6c73200000000ULL, 0x0000f684df56c3e0ULL}
}
, // 1/2 * 10^34 = 5 * 10^33
{{0x15c3c7f400000000ULL, 0x0009a130b963a6c1ULL}
}
, // 1/2 * 10^35 = 5 * 10^34
{{0xd9a5cf8800000000ULL, 0x00604be73de4838aULL}
}
, // 1/2 * 10^36 = 5 * 10^35
{{0x807a1b5000000000ULL, 0x03c2f7086aed236cULL}
}
, // 1/2 * 10^37 = 5 * 10^36
{{0x04c5112000000000ULL, 0x259da6542d43623dULL}
} // 1/2 * 10^38 = 5 * 10^37
};
// midpoint192[i - 39] = 1/2 * 10^i = 5 * 10^(i-1), 39 <= i <= 58
UINT192 midpoint192[] = { // the 64-bit word order is L, M, H
{{0x2fb2ab4000000000ULL, 0x78287f49c4a1d662ULL, 0x0000000000000001ULL}
}
,
// 1/2 * 10^39 = 5 * 10^38
{{0xdcfab08000000000ULL, 0xb194f8e1ae525fd5ULL, 0x000000000000000eULL}
}
,
// 1/2 * 10^40 = 5 * 10^39
{{0xa1cae50000000000ULL, 0xefd1b8d0cf37be5aULL, 0x0000000000000092ULL}
}
,
// 1/2 * 10^41 = 5 * 10^40
{{0x51ecf20000000000ULL, 0x5e313828182d6f8aULL, 0x00000000000005bdULL}
}
,
// 1/2 * 10^42 = 5 * 10^41
{{0x3341740000000000ULL, 0xadec3190f1c65b67ULL, 0x0000000000003965ULL}
}
,
// 1/2 * 10^43 = 5 * 10^42
{{0x008e880000000000ULL, 0xcb39efa971bf9208ULL, 0x0000000000023df8ULL}
}
,
// 1/2 * 10^44 = 5 * 10^43
{{0x0591500000000000ULL, 0xf0435c9e717bb450ULL, 0x0000000000166bb7ULL}
}
,
// 1/2 * 10^45 = 5 * 10^44
{{0x37ad200000000000ULL, 0x62a19e306ed50b20ULL, 0x0000000000e0352fULL}
}
,
// 1/2 * 10^46 = 5 * 10^45
{{0x2cc3400000000000ULL, 0xda502de454526f42ULL, 0x0000000008c213d9ULL}
}
,
// 1/2 * 10^47 = 5 * 10^46
{{0xbfa0800000000000ULL, 0x8721caeb4b385895ULL, 0x000000005794c682ULL}
}
,
// 1/2 * 10^48 = 5 * 10^47
{{0x7c45000000000000ULL, 0x4751ed30f03375d9ULL, 0x000000036bcfc119ULL}
}
,
// 1/2 * 10^49 = 5 * 10^48
{{0xdab2000000000000ULL, 0xc93343e962029a7eULL, 0x00000022361d8afcULL}
}
,
// 1/2 * 10^50 = 5 * 10^49
{{0x8af4000000000000ULL, 0xdc00a71dd41a08f4ULL, 0x000001561d276ddfULL}
}
,
// 1/2 * 10^51 = 5 * 10^50
{{0x6d88000000000000ULL, 0x9806872a4904598dULL, 0x00000d5d238a4abeULL}
}
,
// 1/2 * 10^52 = 5 * 10^51
{{0x4750000000000000ULL, 0xf04147a6da2b7f86ULL, 0x000085a36366eb71ULL}
}
,
// 1/2 * 10^53 = 5 * 10^52
{{0xc920000000000000ULL, 0x628ccc8485b2fb3eULL, 0x00053861e2053273ULL}
}
,
// 1/2 * 10^54 = 5 * 10^53
{{0xdb40000000000000ULL, 0xd97ffd2d38fdd073ULL, 0x003433d2d433f881ULL}
}
,
// 1/2 * 10^55 = 5 * 10^54
{{0x9080000000000000ULL, 0x7effe3c439ea2486ULL, 0x020a063c4a07b512ULL}
}
,
// 1/2 * 10^56 = 5 * 10^55
{{0xa500000000000000ULL, 0xf5fee5aa43256d41ULL, 0x14643e5ae44d12b8ULL}
}
,
// 1/2 * 10^57 = 5 * 10^56
{{0x7200000000000000ULL, 0x9bf4f8a69f764490ULL, 0xcbea6f8ceb02bb39ULL}
}
// 1/2 * 10^58 = 5 * 10^57
};
// midpoint256[i - 59] = 1/2 * 10^i = 5 * 10^(i-1), 59 <= i <= 68
UINT256 midpoint256[] = { // the 64-bit word order is LL, LH, HL, HH
{{0x7400000000000000ULL, 0x1791b6823a9eada4ULL,
0xf7285b812e1b5040ULL, 0x0000000000000007ULL}
}
, // 1/2 * 10^59 = 5 * 10^58
{{0x8800000000000000ULL, 0xebb121164a32c86cULL,
0xa793930bcd112280ULL, 0x000000000000004fULL}
}
, // 1/2 * 10^60 = 5 * 10^59
{{0x5000000000000000ULL, 0x34eb4adee5fbd43dULL,
0x8bc3be7602ab5909ULL, 0x000000000000031cULL}
}
, // 1/2 * 10^61 = 5 * 10^60
{{0x2000000000000000ULL, 0x1130ecb4fbd64a65ULL,
0x75a5709c1ab17a5cULL, 0x0000000000001f1dULL}
}
, // 1/2 * 10^62 = 5 * 10^61
{{0x4000000000000000ULL, 0xabe93f11d65ee7f3ULL,
0x987666190aeec798ULL, 0x0000000000013726ULL}
}
, // 1/2 * 10^63 = 5 * 10^62
{{0x8000000000000000ULL, 0xb71c76b25fb50f80ULL,
0xf49ffcfa6d53cbf6ULL, 0x00000000000c2781ULL}
}
, // 1/2 * 10^64 = 5 * 10^63
{{0x0000000000000000ULL, 0x271ca2f7bd129b05ULL,
0x8e3fe1c84545f7a3ULL, 0x0000000000798b13ULL}
}
, // 1/2 * 10^65 = 5 * 10^64
{{0x0000000000000000ULL, 0x871e5dad62ba0e32ULL,
0x8e7ed1d2b4bbac5fULL, 0x0000000004bf6ec3ULL}
}
, // 1/2 * 10^66 = 5 * 10^65
{{0x0000000000000000ULL, 0x472fa8c5db448df4ULL,
0x90f4323b0f54bbbbULL, 0x000000002f7a53a3ULL}
}
, // 1/2 * 10^67 = 5 * 10^66
{{0x0000000000000000ULL, 0xc7dc97ba90ad8b88ULL,
0xa989f64e994f5550ULL, 0x00000001dac74463ULL}
}
, // 1/2 * 10^68 = 5 * 10^67
{{0x0000000000000000ULL, 0xce9ded49a6c77350ULL,
0x9f639f11fd195527ULL, 0x000000128bc8abe4ULL}
}
, // 1/2 * 10^69 = 5 * 10^68
{{0x0000000000000000ULL, 0x122b44e083ca8120ULL,
0x39e436b3e2fd538eULL, 0x000000b975d6b6eeULL}
}
, // 1/2 * 10^70 = 5 * 10^69
{{0x0000000000000000ULL, 0xb5b0b0c525e90b40ULL,
0x42ea2306dde5438cULL, 0x0000073e9a63254eULL}
}
, // 1/2 * 10^71 = 5 * 10^70
{{0x0000000000000000ULL, 0x18e6e7b37b1a7080ULL,
0x9d255e44aaf4a37fULL, 0x0000487207df750eULL}
}
, // 1/2 * 10^72 = 5 * 10^71
{{0x0000000000000000ULL, 0xf9050d02cf086500ULL,
0x2375aeaead8e62f6ULL, 0x0002d4744eba9292ULL}
}
, // 1/2 * 10^73 = 5 * 10^72
{{0x0000000000000000ULL, 0xba32821c1653f200ULL,
0x6298d2d2c78fdda5ULL, 0x001c4c8b1349b9b5ULL}
}
, // 1/2 * 10^74 = 5 * 10^73
{{0x0000000000000000ULL, 0x45f91518df477400ULL,
0xd9f83c3bcb9ea879ULL, 0x011afd6ec0e14115ULL}
}
, // 1/2 * 10^75 = 5 * 10^74
{{0x0000000000000000ULL, 0xbbbad2f8b8ca8800ULL,
0x83b25a55f43294bcULL, 0x0b0de65388cc8adaULL}
}
, // 1/2 * 10^76 = 5 * 10^75
{{0x0000000000000000ULL, 0x554c3db737e95000ULL,
0x24f7875b89f9cf5fULL, 0x6e8aff4357fd6c89ULL}
} // 1/2 * 10^77 = 5 * 10^76
};
// ten2k64[i] = 10^i, 0 <= i <= 19
UINT64 ten2k64[] = {
0x0000000000000001ULL, // 10^0
0x000000000000000aULL, // 10^1
0x0000000000000064ULL, // 10^2
0x00000000000003e8ULL, // 10^3
0x0000000000002710ULL, // 10^4
0x00000000000186a0ULL, // 10^5
0x00000000000f4240ULL, // 10^6
0x0000000000989680ULL, // 10^7
0x0000000005f5e100ULL, // 10^8
0x000000003b9aca00ULL, // 10^9
0x00000002540be400ULL, // 10^10
0x000000174876e800ULL, // 10^11
0x000000e8d4a51000ULL, // 10^12
0x000009184e72a000ULL, // 10^13
0x00005af3107a4000ULL, // 10^14
0x00038d7ea4c68000ULL, // 10^15
0x002386f26fc10000ULL, // 10^16
0x016345785d8a0000ULL, // 10^17
0x0de0b6b3a7640000ULL, // 10^18
0x8ac7230489e80000ULL // 10^19 (20 digits)
};
// ten2k128[i - 20] = 10^i, 20 <= i <= 38
UINT128 ten2k128[] = { // the 64-bit word order is L, H
{{0x6bc75e2d63100000ULL, 0x0000000000000005ULL}
}
, // 10^20
{{0x35c9adc5dea00000ULL, 0x0000000000000036ULL}
}
, // 10^21
{{0x19e0c9bab2400000ULL, 0x000000000000021eULL}
}
, // 10^22
{{0x02c7e14af6800000ULL, 0x000000000000152dULL}
}
, // 10^23
{{0x1bcecceda1000000ULL, 0x000000000000d3c2ULL}
}
, // 10^24
{{0x161401484a000000ULL, 0x0000000000084595ULL}
}
, // 10^25
{{0xdcc80cd2e4000000ULL, 0x000000000052b7d2ULL}
}
, // 10^26
{{0x9fd0803ce8000000ULL, 0x00000000033b2e3cULL}
}
, // 10^27
{{0x3e25026110000000ULL, 0x00000000204fce5eULL}
}
, // 10^28
{{0x6d7217caa0000000ULL, 0x00000001431e0faeULL}
}
, // 10^29
{{0x4674edea40000000ULL, 0x0000000c9f2c9cd0ULL}
}
, // 10^30
{{0xc0914b2680000000ULL, 0x0000007e37be2022ULL}
}
, // 10^31
{{0x85acef8100000000ULL, 0x000004ee2d6d415bULL}
}
, // 10^32
{{0x38c15b0a00000000ULL, 0x0000314dc6448d93ULL}
}
, // 10^33
{{0x378d8e6400000000ULL, 0x0001ed09bead87c0ULL}
}
, // 10^34
{{0x2b878fe800000000ULL, 0x0013426172c74d82ULL}
}
, // 10^35
{{0xb34b9f1000000000ULL, 0x00c097ce7bc90715ULL}
}
, // 10^36
{{0x00f436a000000000ULL, 0x0785ee10d5da46d9ULL}
}
, // 10^37
{{0x098a224000000000ULL, 0x4b3b4ca85a86c47aULL}
} // 10^38 (39 digits)
};
// might split into ten2k192[] and ten2k256[]
// ten2k256[i - 39] = 10^i, 39 <= i <= 68
UINT256 ten2k256[] = { // the 64-bit word order is LL, LH, HL, HH
{{0x5f65568000000000ULL, 0xf050fe938943acc4ULL,
0x0000000000000002ULL, 0x0000000000000000ULL}
}
, // 10^39
{{0xb9f5610000000000ULL, 0x6329f1c35ca4bfabULL,
0x000000000000001dULL, 0x0000000000000000ULL}
}
, // 10^40
{{0x4395ca0000000000ULL, 0xdfa371a19e6f7cb5ULL,
0x0000000000000125ULL, 0x0000000000000000ULL}
}
, // 10^41
{{0xa3d9e40000000000ULL, 0xbc627050305adf14ULL,
0x0000000000000b7aULL, 0x0000000000000000ULL}
}
, // 10^42
{{0x6682e80000000000ULL, 0x5bd86321e38cb6ceULL,
0x00000000000072cbULL, 0x0000000000000000ULL}
}
, // 10^43
{{0x011d100000000000ULL, 0x9673df52e37f2410ULL,
0x0000000000047bf1ULL, 0x0000000000000000ULL}
}
, // 10^44
{{0x0b22a00000000000ULL, 0xe086b93ce2f768a0ULL,
0x00000000002cd76fULL, 0x0000000000000000ULL}
}
, // 10^45
{{0x6f5a400000000000ULL, 0xc5433c60ddaa1640ULL,
0x0000000001c06a5eULL, 0x0000000000000000ULL}
}
, // 10^46
{{0x5986800000000000ULL, 0xb4a05bc8a8a4de84ULL,
0x00000000118427b3ULL, 0x0000000000000000ULL}
}
, // 10^47
{{0x7f41000000000000ULL, 0x0e4395d69670b12bULL,
0x00000000af298d05ULL, 0x0000000000000000ULL}
}
, // 10^48
{{0xf88a000000000000ULL, 0x8ea3da61e066ebb2ULL,
0x00000006d79f8232ULL, 0x0000000000000000ULL}
}
, // 10^49
{{0xb564000000000000ULL, 0x926687d2c40534fdULL,
0x000000446c3b15f9ULL, 0x0000000000000000ULL}
}
, // 10^50
{{0x15e8000000000000ULL, 0xb8014e3ba83411e9ULL,
0x000002ac3a4edbbfULL, 0x0000000000000000ULL}
}
, // 10^51
{{0xdb10000000000000ULL, 0x300d0e549208b31aULL,
0x00001aba4714957dULL, 0x0000000000000000ULL}
}
, // 10^52
{{0x8ea0000000000000ULL, 0xe0828f4db456ff0cULL,
0x00010b46c6cdd6e3ULL, 0x0000000000000000ULL}
}
, // 10^53
{{0x9240000000000000ULL, 0xc51999090b65f67dULL,
0x000a70c3c40a64e6ULL, 0x0000000000000000ULL}
}
, // 10^54
{{0xb680000000000000ULL, 0xb2fffa5a71fba0e7ULL,
0x006867a5a867f103ULL, 0x0000000000000000ULL}
}
, // 10^55
{{0x2100000000000000ULL, 0xfdffc78873d4490dULL,
0x04140c78940f6a24ULL, 0x0000000000000000ULL}
}
, // 10^56
{{0x4a00000000000000ULL, 0xebfdcb54864ada83ULL,
0x28c87cb5c89a2571ULL, 0x0000000000000000ULL}
}
, // 10^57 (58 digits)
{{0xe400000000000000ULL, 0x37e9f14d3eec8920ULL,
0x97d4df19d6057673ULL, 0x0000000000000001ULL}
}
, // 10^58
{{0xe800000000000000ULL, 0x2f236d04753d5b48ULL,
0xee50b7025c36a080ULL, 0x000000000000000fULL}
}
, // 10^59
{{0x1000000000000000ULL, 0xd762422c946590d9ULL,
0x4f2726179a224501ULL, 0x000000000000009fULL}
}
, // 10^60
{{0xa000000000000000ULL, 0x69d695bdcbf7a87aULL,
0x17877cec0556b212ULL, 0x0000000000000639ULL}
}
, // 10^61
{{0x4000000000000000ULL, 0x2261d969f7ac94caULL,
0xeb4ae1383562f4b8ULL, 0x0000000000003e3aULL}
}
, // 10^62
{{0x8000000000000000ULL, 0x57d27e23acbdcfe6ULL,
0x30eccc3215dd8f31ULL, 0x0000000000026e4dULL}
}
, // 10^63
{{0x0000000000000000ULL, 0x6e38ed64bf6a1f01ULL,
0xe93ff9f4daa797edULL, 0x0000000000184f03ULL}
}
, // 10^64
{{0x0000000000000000ULL, 0x4e3945ef7a25360aULL,
0x1c7fc3908a8bef46ULL, 0x0000000000f31627ULL}
}
, // 10^65
{{0x0000000000000000ULL, 0x0e3cbb5ac5741c64ULL,
0x1cfda3a5697758bfULL, 0x00000000097edd87ULL}
}
, // 10^66
{{0x0000000000000000ULL, 0x8e5f518bb6891be8ULL,
0x21e864761ea97776ULL, 0x000000005ef4a747ULL}
}
, // 10^67
{{0x0000000000000000ULL, 0x8fb92f75215b1710ULL,
0x5313ec9d329eaaa1ULL, 0x00000003b58e88c7ULL}
}
, // 10^68
{{0x0000000000000000ULL, 0x9d3bda934d8ee6a0ULL,
0x3ec73e23fa32aa4fULL, 0x00000025179157c9ULL}
}
, // 10^69
{{0x0000000000000000ULL, 0x245689c107950240ULL,
0x73c86d67c5faa71cULL, 0x00000172ebad6ddcULL}
}
, // 10^70
{{0x0000000000000000ULL, 0x6b61618a4bd21680ULL,
0x85d4460dbbca8719ULL, 0x00000e7d34c64a9cULL}
}
, // 10^71
{{0x0000000000000000ULL, 0x31cdcf66f634e100ULL,
0x3a4abc8955e946feULL, 0x000090e40fbeea1dULL}
}
, // 10^72
{{0x0000000000000000ULL, 0xf20a1a059e10ca00ULL,
0x46eb5d5d5b1cc5edULL, 0x0005a8e89d752524ULL}
}
, // 10^73
{{0x0000000000000000ULL, 0x746504382ca7e400ULL,
0xc531a5a58f1fbb4bULL, 0x003899162693736aULL}
}
, // 10^74
{{0x0000000000000000ULL, 0x8bf22a31be8ee800ULL,
0xb3f07877973d50f2ULL, 0x0235fadd81c2822bULL}
}
, // 10^75
{{0x0000000000000000ULL, 0x7775a5f171951000ULL,
0x0764b4abe8652979ULL, 0x161bcca7119915b5ULL}
}
, // 10^76
{{0x0000000000000000ULL, 0xaa987b6e6fd2a000ULL,
0x49ef0eb713f39ebeULL, 0xdd15fe86affad912ULL}
} // 10^77
};
// ten2mk128[k - 1] = 10^(-k) * 2^exp (k), where 1 <= k <= 34 and
// exp (k) = shiftright128[k - 1] + 128
UINT128 ten2mk128[] = {
{{0x999999999999999aULL, 0x1999999999999999ULL}
}
, // 10^(-1) * 2^128
{{0x28f5c28f5c28f5c3ULL, 0x028f5c28f5c28f5cULL}
}
, // 10^(-2) * 2^128
{{0x9db22d0e56041894ULL, 0x004189374bc6a7efULL}
}
, // 10^(-3) * 2^128
{{0x4af4f0d844d013aaULL, 0x00346dc5d6388659ULL}
}
, // 10^(-4) * 2^131
{{0x08c3f3e0370cdc88ULL, 0x0029f16b11c6d1e1ULL}
}
, // 10^(-5) * 2^134
{{0x6d698fe69270b06dULL, 0x00218def416bdb1aULL}
}
, // 10^(-6) * 2^137
{{0xaf0f4ca41d811a47ULL, 0x0035afe535795e90ULL}
}
, // 10^(-7) * 2^141
{{0xbf3f70834acdaea0ULL, 0x002af31dc4611873ULL}
}
, // 10^(-8) * 2^144
{{0x65cc5a02a23e254dULL, 0x00225c17d04dad29ULL}
}
, // 10^(-9) * 2^147
{{0x6fad5cd10396a214ULL, 0x0036f9bfb3af7b75ULL}
}
, // 10^(-10) * 2^151
{{0xbfbde3da69454e76ULL, 0x002bfaffc2f2c92aULL}
}
, // 10^(-11) * 2^154
{{0x32fe4fe1edd10b92ULL, 0x00232f33025bd422ULL}
}
, // 10^(-12) * 2^157
{{0x84ca19697c81ac1cULL, 0x00384b84d092ed03ULL}
}
, // 10^(-13) * 2^161
{{0x03d4e1213067bce4ULL, 0x002d09370d425736ULL}
}
, // 10^(-14) * 2^164
{{0x3643e74dc052fd83ULL, 0x0024075f3dceac2bULL}
}
, // 10^(-15) * 2^167
{{0x56d30baf9a1e626bULL, 0x0039a5652fb11378ULL}
}
, // 10^(-16) * 2^171
{{0x12426fbfae7eb522ULL, 0x002e1dea8c8da92dULL}
}
, // 10^(-17) * 2^174
{{0x41cebfcc8b9890e8ULL, 0x0024e4bba3a48757ULL}
}
, // 10^(-18) * 2^177
{{0x694acc7a78f41b0dULL, 0x003b07929f6da558ULL}
}
, // 10^(-19) * 2^181
{{0xbaa23d2ec729af3eULL, 0x002f394219248446ULL}
}
, // 10^(-20) * 2^184
{{0xfbb4fdbf05baf298ULL, 0x0025c768141d369eULL}
}
, // 10^(-21) * 2^187
{{0x2c54c931a2c4b759ULL, 0x003c7240202ebdcbULL}
}
, // 10^(-22) * 2^191
{{0x89dd6dc14f03c5e1ULL, 0x00305b66802564a2ULL}
}
, // 10^(-23) * 2^194
{{0xd4b1249aa59c9e4eULL, 0x0026af8533511d4eULL}
}
, // 10^(-24) * 2^197
{{0x544ea0f76f60fd49ULL, 0x003de5a1ebb4fbb1ULL}
}
, // 10^(-25) * 2^201
{{0x76a54d92bf80caa1ULL, 0x00318481895d9627ULL}
}
, // 10^(-26) * 2^204
{{0x921dd7a89933d54eULL, 0x00279d346de4781fULL}
}
, // 10^(-27) * 2^207
{{0x8362f2a75b862215ULL, 0x003f61ed7ca0c032ULL}
}
, // 10^(-28) * 2^211
{{0xcf825bb91604e811ULL, 0x0032b4bdfd4d668eULL}
}
, // 10^(-29) * 2^214
{{0x0c684960de6a5341ULL, 0x00289097fdd7853fULL}
}
, // 10^(-30) * 2^217
{{0x3d203ab3e521dc34ULL, 0x002073accb12d0ffULL}
}
, // 10^(-31) * 2^220
{{0x2e99f7863b696053ULL, 0x0033ec47ab514e65ULL}
}
, // 10^(-32) * 2^224
{{0x587b2c6b62bab376ULL, 0x002989d2ef743eb7ULL}
}
, // 10^(-33) * 2^227
{{0xad2f56bc4efbc2c5ULL, 0x00213b0f25f69892ULL}
}
, // 10^(-34) * 2^230
};
// shiftright128[] contains the right shift count to obtain C2* from the top
// 128 bits of the 128x128-bit product C2 * Kx
int shiftright128[] = {
0, // 128 - 128
0, // 128 - 128
0, // 128 - 128
3, // 131 - 128
6, // 134 - 128
9, // 137 - 128
13, // 141 - 128
16, // 144 - 128
19, // 147 - 128
23, // 151 - 128
26, // 154 - 128
29, // 157 - 128
33, // 161 - 128
36, // 164 - 128
39, // 167 - 128
43, // 171 - 128
46, // 174 - 128
49, // 177 - 128
53, // 181 - 128
56, // 184 - 128
59, // 187 - 128
63, // 191 - 128
66, // 194 - 128
69, // 197 - 128
73, // 201 - 128
76, // 204 - 128
79, // 207 - 128
83, // 211 - 128
86, // 214 - 128
89, // 217 - 128
92, // 220 - 128
96, // 224 - 128
99, // 227 - 128
102 // 230 - 128
};
// maskhigh128[] contains the mask to apply to the top 128 bits of the
// 128x128-bit product in order to obtain the high bits of f2*
// the 64-bit word order is L, H
UINT64 maskhigh128[] = {
0x0000000000000000ULL, // 0 = 128 - 128 bits
0x0000000000000000ULL, // 0 = 128 - 128 bits
0x0000000000000000ULL, // 0 = 128 - 128 bits
0x0000000000000007ULL, // 3 = 131 - 128 bits
0x000000000000003fULL, // 6 = 134 - 128 bits
0x00000000000001ffULL, // 9 = 137 - 128 bits
0x0000000000001fffULL, // 13 = 141 - 128 bits
0x000000000000ffffULL, // 16 = 144 - 128 bits
0x000000000007ffffULL, // 19 = 147 - 128 bits
0x00000000007fffffULL, // 23 = 151 - 128 bits
0x0000000003ffffffULL, // 26 = 154 - 128 bits
0x000000001fffffffULL, // 29 = 157 - 128 bits
0x00000001ffffffffULL, // 33 = 161 - 128 bits
0x0000000fffffffffULL, // 36 = 164 - 128 bits
0x0000007fffffffffULL, // 39 = 167 - 128 bits
0x000007ffffffffffULL, // 43 = 171 - 128 bits
0x00003fffffffffffULL, // 46 = 174 - 128 bits
0x0001ffffffffffffULL, // 49 = 177 - 128 bits
0x001fffffffffffffULL, // 53 = 181 - 128 bits
0x00ffffffffffffffULL, // 56 = 184 - 128 bits
0x07ffffffffffffffULL, // 59 = 187 - 128 bits
0x7fffffffffffffffULL, // 63 = 191 - 128 bits
0x0000000000000003ULL, // 2 = 194 - 192 bits
0x000000000000001fULL, // 5 = 197 - 192 bits
0x00000000000001ffULL, // 9 = 201 - 192 bits
0x0000000000000fffULL, // 12 = 204 - 192 bits
0x0000000000007fffULL, // 15 = 207 - 192 bits
0x000000000007ffffULL, // 21 = 211 - 192 bits
0x00000000003fffffULL, // 22 = 214 - 192 bits
0x0000000001ffffffULL, // 25 = 217 - 192 bits
0x000000000fffffffULL, // 28 = 220 - 192 bits
0x00000000ffffffffULL, // 32 = 224 - 192 bits
0x00000007ffffffffULL, // 35 = 227 - 192 bits
0x0000003fffffffffULL // 38 = 230 - 192 bits
};
// onehalf128[] contains the high bits of 1/2 positioned correctly for
// comparison with the high bits of f2*
// the 64-bit word order is L, H
UINT64 onehalf128[] = {
0x0000000000000000ULL, // 0 bits
0x0000000000000000ULL, // 0 bits
0x0000000000000000ULL, // 0 bits
0x0000000000000004ULL, // 3 bits
0x0000000000000020ULL, // 6 bits
0x0000000000000100ULL, // 9 bits
0x0000000000001000ULL, // 13 bits
0x0000000000008000ULL, // 16 bits
0x0000000000040000ULL, // 19 bits
0x0000000000400000ULL, // 23 bits
0x0000000002000000ULL, // 26 bits
0x0000000010000000ULL, // 29 bits
0x0000000100000000ULL, // 33 bits
0x0000000800000000ULL, // 36 bits
0x0000004000000000ULL, // 39 bits
0x0000040000000000ULL, // 43 bits
0x0000200000000000ULL, // 46 bits
0x0001000000000000ULL, // 49 bits
0x0010000000000000ULL, // 53 bits
0x0080000000000000ULL, // 56 bits
0x0400000000000000ULL, // 59 bits
0x4000000000000000ULL, // 63 bits
0x0000000000000002ULL, // 66 bits
0x0000000000000010ULL, // 69 bits
0x0000000000000100ULL, // 73 bits
0x0000000000000800ULL, // 76 bits
0x0000000000004000ULL, // 79 bits
0x0000000000040000ULL, // 83 bits
0x0000000000200000ULL, // 86 bits
0x0000000001000000ULL, // 89 bits
0x0000000008000000ULL, // 92 bits
0x0000000080000000ULL, // 96 bits
0x0000000400000000ULL, // 99 bits
0x0000002000000000ULL // 102 bits
};
UINT64 ten2mk64[] = {
0x199999999999999aULL, // 10^(-1) * 2^ 64
0x028f5c28f5c28f5dULL, // 10^(-2) * 2^ 64
0x004189374bc6a7f0ULL, // 10^(-3) * 2^ 64
0x00346dc5d638865aULL, // 10^(-4) * 2^ 67
0x0029f16b11c6d1e2ULL, // 10^(-5) * 2^ 70
0x00218def416bdb1bULL, // 10^(-6) * 2^ 73
0x0035afe535795e91ULL, // 10^(-7) * 2^ 77
0x002af31dc4611874ULL, // 10^(-8) * 2^ 80
0x00225c17d04dad2aULL, // 10^(-9) * 2^ 83
0x0036f9bfb3af7b76ULL, // 10^(-10) * 2^ 87
0x002bfaffc2f2c92bULL, // 10^(-11) * 2^ 90
0x00232f33025bd423ULL, // 10^(-12) * 2^ 93
0x00384b84d092ed04ULL, // 10^(-13) * 2^ 97
0x002d09370d425737ULL, // 10^(-14) * 2^100
0x0024075f3dceac2cULL, // 10^(-15) * 2^103
0x0039a5652fb11379ULL, // 10^(-16) * 2^107
};
// ten2mk128trunc[] contains T*, the top Ex >= 128 bits of 10^(-k),
// for 1 <= k <= 34
// the 64-bit word order is L, H
UINT128 ten2mk128trunc[] = {
{{0x9999999999999999ULL, 0x1999999999999999ULL}}, // 10^(-1) * 2^128
{{0x28f5c28f5c28f5c2ULL, 0x028f5c28f5c28f5cULL}}, // 10^(-2) * 2^128
{{0x9db22d0e56041893ULL, 0x004189374bc6a7efULL}}, // 10^(-3) * 2^128
{{0x4af4f0d844d013a9ULL, 0x00346dc5d6388659ULL}}, // 10^(-4) * 2^131
{{0x08c3f3e0370cdc87ULL, 0x0029f16b11c6d1e1ULL}}, // 10^(-5) * 2^134
{{0x6d698fe69270b06cULL, 0x00218def416bdb1aULL}}, // 10^(-6) * 2^137
{{0xaf0f4ca41d811a46ULL, 0x0035afe535795e90ULL}}, // 10^(-7) * 2^141
{{0xbf3f70834acdae9fULL, 0x002af31dc4611873ULL}}, // 10^(-8) * 2^144
{{0x65cc5a02a23e254cULL, 0x00225c17d04dad29ULL}}, // 10^(-9) * 2^147
{{0x6fad5cd10396a213ULL, 0x0036f9bfb3af7b75ULL}}, // 10^(-10) * 2^151
{{0xbfbde3da69454e75ULL, 0x002bfaffc2f2c92aULL}}, // 10^(-11) * 2^154
{{0x32fe4fe1edd10b91ULL, 0x00232f33025bd422ULL}}, // 10^(-12) * 2^157
{{0x84ca19697c81ac1bULL, 0x00384b84d092ed03ULL}}, // 10^(-13) * 2^161
{{0x03d4e1213067bce3ULL, 0x002d09370d425736ULL}}, // 10^(-14) * 2^164
{{0x3643e74dc052fd82ULL, 0x0024075f3dceac2bULL}}, // 10^(-15) * 2^167
{{0x56d30baf9a1e626aULL, 0x0039a5652fb11378ULL}}, // 10^(-16) * 2^171
{{0x12426fbfae7eb521ULL, 0x002e1dea8c8da92dULL}}, // 10^(-17) * 2^174
{{0x41cebfcc8b9890e7ULL, 0x0024e4bba3a48757ULL}}, // 10^(-18) * 2^177
{{0x694acc7a78f41b0cULL, 0x003b07929f6da558ULL}}, // 10^(-19) * 2^181
{{0xbaa23d2ec729af3dULL, 0x002f394219248446ULL}}, // 10^(-20) * 2^184
{{0xfbb4fdbf05baf297ULL, 0x0025c768141d369eULL}}, // 10^(-21) * 2^187
{{0x2c54c931a2c4b758ULL, 0x003c7240202ebdcbULL}}, // 10^(-22) * 2^191
{{0x89dd6dc14f03c5e0ULL, 0x00305b66802564a2ULL}}, // 10^(-23) * 2^194
{{0xd4b1249aa59c9e4dULL, 0x0026af8533511d4eULL}}, // 10^(-24) * 2^197
{{0x544ea0f76f60fd48ULL, 0x003de5a1ebb4fbb1ULL}}, // 10^(-25) * 2^201
{{0x76a54d92bf80caa0ULL, 0x00318481895d9627ULL}}, // 10^(-26) * 2^204
{{0x921dd7a89933d54dULL, 0x00279d346de4781fULL}}, // 10^(-27) * 2^207
{{0x8362f2a75b862214ULL, 0x003f61ed7ca0c032ULL}}, // 10^(-28) * 2^211
{{0xcf825bb91604e810ULL, 0x0032b4bdfd4d668eULL}}, // 10^(-29) * 2^214
{{0x0c684960de6a5340ULL, 0x00289097fdd7853fULL}}, // 10^(-30) * 2^217
{{0x3d203ab3e521dc33ULL, 0x002073accb12d0ffULL}}, // 10^(-31) * 2^220
{{0x2e99f7863b696052ULL, 0x0033ec47ab514e65ULL}}, // 10^(-32) * 2^224
{{0x587b2c6b62bab375ULL, 0x002989d2ef743eb7ULL}}, // 10^(-33) * 2^227
{{0xad2f56bc4efbc2c4ULL, 0x00213b0f25f69892ULL}}, // 10^(-34) * 2^230
};
// ten2mk128M[k - 1] = 10^(-k) * 2^exp (k), where 1 <= k <= 4 and
// exp (k) = shiftright128[k - 1] + 128
// the 64-bit word order is L, H
UINT128 ten2mk128M[] = {
{{0xcccccccccccccccdULL, 0xccccccccccccccccULL}}, // 10^(-1) * 2^131
{{0x3d70a3d70a3d70a4ULL, 0xa3d70a3d70a3d70aULL}}, // 10^(-2) * 2^134
{{0x645a1cac083126eaULL, 0x83126e978d4fdf3bULL}}, // 10^(-3) * 2^137
{{0xd3c36113404ea4a9ULL, 0xd1b71758e219652bULL}} // 10^(-4) * 2^141
};
// ten2mk128truncM[] contains T*, the top Ex >= 128 bits of 10^(-k),
// for 1 <= k <= 4; the top bits which are 0 are not represented
// the 64-bit word order is L, H
UINT128 ten2mk128truncM[] = {
{{0xccccccccccccccccULL, 0xccccccccccccccccULL}}, // 10^(-1) * 2^131
{{0x3d70a3d70a3d70a3ULL, 0xa3d70a3d70a3d70aULL}}, // 10^(-2) * 2^134
{{0x645a1cac083126e9ULL, 0x83126e978d4fdf3bULL}}, // 10^(-3) * 2^137
{{0xd3c36113404ea4a8ULL, 0xd1b71758e219652bULL}} // 10^(-4) * 2^141
};
// shiftright128M[] contains the right shift count to obtain C2* from the top
// 128 bits of the 128x128-bit product C2 * Kx
int shiftright128M[] = {
3, // 131 - 128
6, // 134 - 128
9, // 137 - 128
13 // 141 - 128
};
// maskhigh128M[] contains the mask to apply to the top 128 bits of the
// 128x128-bit product in order to obtain the high bits of f*
// the high 64 bits of the mask are 0, so only the low 64 bits are represented
UINT64 maskhigh128M[] = {
0x0000000000000007ULL, // 3 = 131 - 128 bits
0x000000000000003fULL, // 6 = 134 - 128 bits
0x00000000000001ffULL, // 9 = 137 - 128 bits
0x0000000000001fffULL // 13 = 141 - 128 bits
};
// onehalf128M[] contains 1/2 positioned correctly for
// comparison with the high bits of f*
// the high 64 bits are 0, so only the low 64 bits are represented
UINT64 onehalf128M[] = {
0x0000000000000004ULL, // 3 bits
0x0000000000000020ULL, // 6 bits
0x0000000000000100ULL, // 9 bits
0x0000000000001000ULL // 13 bits
};
// ten2mk192M[k - 1] = 10^(-k-4) * 2^exp (k), where 1 <= k <= 19 and
// exp (k) = shiftright128[k - 1] + 128
// the 64-bit word order is L, M, H
UINT192 ten2mk192M[] = {
{{0xcddd6e04c0592104ULL, 0x0fcf80dc33721d53ULL,
0xa7c5ac471b478423ULL}},
// 10^(-5) * 2^208
{{0xd7e45803cd141a6aULL, 0xa63f9a49c2c1b10fULL,
0x8637bd05af6c69b5ULL}},
// 10^(-6) * 2^211
{{0x8ca08cd2e1b9c3dcULL, 0x3d32907604691b4cULL,
0xd6bf94d5e57a42bcULL}},
// 10^(-7) * 2^215
{{0x3d4d3d758161697dULL, 0xfdc20d2b36ba7c3dULL,
0xabcc77118461cefcULL}},
// 10^(-8) * 2^218
{{0xfdd7645e011abacaULL, 0x31680a88f8953030ULL,
0x89705f4136b4a597ULL}},
// 10^(-9) * 2^221
{{0x2fbf06fcce912addULL, 0xb573440e5a884d1bULL,
0xdbe6fecebdedd5beULL}},
// 10^(-10) * 2^225
{{0xf2ff38ca3eda88b1ULL, 0xf78f69a51539d748ULL,
0xafebff0bcb24aafeULL}},
// 10^(-11) * 2^228
{{0xf598fa3b657ba08eULL, 0xf93f87b7442e45d3ULL,
0x8cbccc096f5088cbULL}},
// 10^(-12) * 2^231
{{0x88f4c3923bf900e3ULL, 0x2865a5f206b06fb9ULL,
0xe12e13424bb40e13ULL}},
// 10^(-13) * 2^235
{{0x6d909c74fcc733e9ULL, 0x538484c19ef38c94ULL,
0xb424dc35095cd80fULL}},
// 10^(-14) * 2^238
{{0x57a6e390ca38f654ULL, 0x0f9d37014bf60a10ULL,
0x901d7cf73ab0acd9ULL}},
// 10^(-15) * 2^241
{{0xbf716c1add27f086ULL, 0x4c2ebe687989a9b3ULL,
0xe69594bec44de15bULL}},
// 10^(-16) * 2^245
{{0xff8df0157db98d38ULL, 0x09befeb9fad487c2ULL,
0xb877aa3236a4b449ULL}},
// 10^(-17) * 2^248
{{0x32d7f344649470faULL, 0x3aff322e62439fcfULL,
0x9392ee8e921d5d07ULL}},
// 10^(-18) * 2^251
{{0x1e2652070753e7f5ULL, 0x2b31e9e3d06c32e5ULL,
0xec1e4a7db69561a5ULL}},
// 10^(-19) * 2^255
{{0x181ea8059f76532bULL, 0x88f4bb1ca6bcf584ULL,
0xbce5086492111aeaULL}},
// 10^(-20) * 2^258
{{0x467eecd14c5ea8efULL, 0xd3f6fc16ebca5e03ULL,
0x971da05074da7beeULL}},
// 10^(-21) * 2^261
{{0x70cb148213caa7e5ULL, 0x5324c68b12dd6338ULL,
0xf1c90080baf72cb1ULL}},
// 10^(-22) * 2^265
{{0x8d6f439b43088651ULL, 0x75b7053c0f178293ULL, 0xc16d9a0095928a27ULL}}
// 10^(-23) * 2^268
};
// ten2mk192truncM[] contains T*, the top Ex >= 192 bits of 10^(-k),
// for 5 <= k <= 23; the top bits which are 0 are not represented
// the 64-bit word order is L, M, H
UINT192 ten2mk192truncM[] = {
{{0xcddd6e04c0592103ULL, 0x0fcf80dc33721d53ULL,
0xa7c5ac471b478423ULL}},
// 10^(-5) * 2^208
{{0xd7e45803cd141a69ULL, 0xa63f9a49c2c1b10fULL,
0x8637bd05af6c69b5ULL}},
// 10^(-6) * 2^211
{{0x8ca08cd2e1b9c3dbULL, 0x3d32907604691b4cULL,
0xd6bf94d5e57a42bcULL}},
// 10^(-7) * 2^215
{{0x3d4d3d758161697cULL, 0xfdc20d2b36ba7c3dULL,
0xabcc77118461cefcULL}},
// 10^(-8) * 2^218
{{0xfdd7645e011abac9ULL, 0x31680a88f8953030ULL,
0x89705f4136b4a597ULL}},
// 10^(-9) * 2^221
{{0x2fbf06fcce912adcULL, 0xb573440e5a884d1bULL,
0xdbe6fecebdedd5beULL}},
// 10^(-10) * 2^225
{{0xf2ff38ca3eda88b0ULL, 0xf78f69a51539d748ULL,
0xafebff0bcb24aafeULL}},
// 10^(-11) * 2^228
{{0xf598fa3b657ba08dULL, 0xf93f87b7442e45d3ULL,
0x8cbccc096f5088cbULL}},
// 10^(-12) * 2^231
{{0x88f4c3923bf900e2ULL, 0x2865a5f206b06fb9ULL,
0xe12e13424bb40e13ULL}},
// 10^(-13) * 2^235
{{0x6d909c74fcc733e8ULL, 0x538484c19ef38c94ULL,
0xb424dc35095cd80fULL}},
// 10^(-14) * 2^238
{{0x57a6e390ca38f653ULL, 0x0f9d37014bf60a10ULL,
0x901d7cf73ab0acd9ULL}},
// 10^(-15) * 2^241
{{0xbf716c1add27f085ULL, 0x4c2ebe687989a9b3ULL,
0xe69594bec44de15bULL}},
// 10^(-16) * 2^245
{{0xff8df0157db98d37ULL, 0x09befeb9fad487c2ULL,
0xb877aa3236a4b449ULL}},
// 10^(-17) * 2^248
{{0x32d7f344649470f9ULL, 0x3aff322e62439fcfULL,
0x9392ee8e921d5d07ULL}},
// 10^(-18) * 2^251
{{0x1e2652070753e7f4ULL, 0x2b31e9e3d06c32e5ULL,
0xec1e4a7db69561a5ULL}},
// 10^(-19) * 2^255
{{0x181ea8059f76532aULL, 0x88f4bb1ca6bcf584ULL,
0xbce5086492111aeaULL}},
// 10^(-20) * 2^258
{{0x467eecd14c5ea8eeULL, 0xd3f6fc16ebca5e03ULL,
0x971da05074da7beeULL}},
// 10^(-21) * 2^261
{{0x70cb148213caa7e4ULL, 0x5324c68b12dd6338ULL,
0xf1c90080baf72cb1ULL}},
// 10^(-22) * 2^265
{{0x8d6f439b43088650ULL, 0x75b7053c0f178293ULL, 0xc16d9a0095928a27ULL}}
// 10^(-23) * 2^268
};
// shiftright192M[] contains the right shift count to obtain C2* from the top
// 192 bits of the 192x192-bit product C2 * Kx if 0 <= ind <= 14 where ind is
// the index in the table, or from the top 128 bits if 15 <= ind <= 18
int shiftright192M[] = {
16, // 208 - 192
19, // 211 - 192
23, // 215 - 192
26, // 218 - 192
29, // 221 - 192
33, // 225 - 192
36, // 228 - 192
39, // 231 - 192
43, // 235 - 192
46, // 238 - 192
49, // 241 - 192
53, // 245 - 192
56, // 248 - 192
59, // 251 - 192
63, // 255 - 192
2, // 258 - 256
5, // 261 - 256
9, // 265 - 256
12 // 268 - 256
};
// maskhigh192M[] contains the mask to apply to the top 192 bits of the
// 192x192-bit product in order to obtain the high bits of f*
// if 0 <= ind <= 14 where ind is the index in the table, then the high 128 bits
// of the 384-bit mask are 0; if 15 <= ind <= 18 then the high 64 bits are 0
UINT64 maskhigh192M[] = {
0x000000000000ffffULL, // 16 = 208 - 192 bits
0x000000000007ffffULL, // 19 = 211 - 192 bits
0x00000000007fffffULL, // 23 = 215 - 192 bits
0x0000000003ffffffULL, // 26 = 218 - 192 bits
0x000000001fffffffULL, // 29 = 221 - 192 bits
0x00000001ffffffffULL, // 33 = 225 - 192 bits
0x0000000fffffffffULL, // 36 = 228 - 192 bits
0x0000007fffffffffULL, // 39 = 231 - 192 bits
0x000007ffffffffffULL, // 43 = 235 - 192 bits
0x00003fffffffffffULL, // 46 = 238 - 192 bits
0x0001ffffffffffffULL, // 49 = 241 - 192 bits
0x001fffffffffffffULL, // 53 = 245 - 192 bits
0x00ffffffffffffffULL, // 56 = 248 - 192 bits
0x07ffffffffffffffULL, // 59 = 251 - 192 bits
0x7fffffffffffffffULL, // 63 = 255 - 192 bits
0x0000000000000003ULL, // 2 = 258 - 256 bits
0x000000000000001fULL, // 5 = 261 - 256 bits
0x00000000000001ffULL, // 9 = 265 - 256 bits
0x0000000000000fffULL // 12 = 268 - 256 bits
};
// onehalf192M[] contains 1/2 positioned correctly for
// comparison with the high bits of f*
// if 0 <= ind <= 14 where ind is the index in the table, then the high 128 bits
// of the 384-bit mask are 0; if 15 <= ind <= 18 then the high 648 bits are 0
UINT64 onehalf192M[] = {
0x0000000000008000ULL, // 16 = 208 - 192 bits
0x0000000000040000ULL, // 19 = 211 - 192 bits
0x0000000000400000ULL, // 23 = 215 - 192 bits
0x0000000002000000ULL, // 26 = 218 - 192 bits
0x0000000010000000ULL, // 29 = 221 - 192 bits
0x0000000100000000ULL, // 33 = 225 - 192 bits
0x0000000800000000ULL, // 36 = 228 - 192 bits
0x0000004000000000ULL, // 39 = 231 - 192 bits
0x0000040000000000ULL, // 43 = 235 - 192 bits
0x0000200000000000ULL, // 46 = 238 - 192 bits
0x0001000000000000ULL, // 49 = 241 - 192 bits
0x0010000000000000ULL, // 53 = 245 - 192 bits
0x0080000000000000ULL, // 56 = 248 - 192 bits
0x0400000000000000ULL, // 59 = 251 - 192 bits
0x4000000000000000ULL, // 63 = 255 - 192 bits
0x0000000000000002ULL, // 2 = 258 - 256 bits
0x0000000000000010ULL, // 5 = 261 - 256 bits
0x0000000000000100ULL, // 9 = 265 - 256 bits
0x0000000000000800ULL // 12 = 268 - 256 bits
};
// ten2mk256M[k - 1] = 10^(-k-23) * 2^exp (k), where 1 <= k <= 11 and
// exp (k) = shiftright128[k - 1] + 128
UINT256 ten2mk256M[] = { // the 64-bit word order is LL, LH, HL, HH
{{0xf23472530ce6e3edULL, 0xd78c3615cf3a050cULL,
0xc4926a9672793542ULL, 0x9abe14cd44753b52ULL}}, // 10^(-24) * 2^335
{{0xe9ed83b814a49fe1ULL, 0x8c1389bc7ec33b47ULL,
0x3a83ddbd83f52204ULL, 0xf79687aed3eec551ULL}}, // 10^(-25) * 2^339
{{0x87f1362cdd507fe7ULL, 0x3cdc6e306568fc39ULL,
0x95364afe032a819dULL, 0xc612062576589ddaULL}}, // 10^(-26) * 2^342
{{0x9ff42b5717739986ULL, 0xca49f1c05120c9c7ULL,
0x775ea264cf55347dULL, 0x9e74d1b791e07e48ULL}}, // 10^(-27) * 2^345
{{0xccb9def1bf1f5c09ULL, 0x76dcb60081ce0fa5ULL,
0x8bca9d6e188853fcULL, 0xfd87b5f28300ca0dULL}}, // 10^(-28) * 2^349
{{0xa3c7e58e327f7cd4ULL, 0x5f16f80067d80c84ULL,
0x096ee45813a04330ULL, 0xcad2f7f5359a3b3eULL}}, // 10^(-29) * 2^352
{{0xb6398471c1ff9710ULL, 0x18df2ccd1fe00a03ULL,
0xa1258379a94d028dULL, 0xa2425ff75e14fc31ULL}}, // 10^(-30) * 2^355
{{0xf82e038e34cc78daULL, 0x4718f0a419800802ULL,
0x80eacf948770ced7ULL, 0x81ceb32c4b43fcf4ULL}}, // 10^(-31) * 2^358
{{0x59e338e387ad8e29ULL, 0x0b5b1aa028ccd99eULL,
0x67de18eda5814af2ULL, 0xcfb11ead453994baULL}}, // 10^(-32) * 2^362
{{0x47e8fa4f9fbe0b54ULL, 0x6f7c154ced70ae18ULL,
0xecb1ad8aeacdd58eULL, 0xa6274bbdd0fadd61ULL}}, // 10^(-33) * 2^365
{{0xd320c83fb2fe6f76ULL, 0xbf967770bdf3be79ULL,
0xbd5af13bef0b113eULL, 0x84ec3c97da624ab4ULL}} // 10^(-34) * 2^368
};
// ten2mk256truncM[] contains T*, the top Ex >= 256 bits of 10^(-k),
// for 24 <= k <= 34; the top bits which are 0 are not represented
UINT256 ten2mk256truncM[] = { // the 64-bit word order is LL, LH, HL, HH
{{0xf23472530ce6e3ecULL, 0xd78c3615cf3a050cULL,
0xc4926a9672793542ULL, 0x9abe14cd44753b52ULL}}, // 10^(-24) * 2^335
{{0xe9ed83b814a49fe0ULL, 0x8c1389bc7ec33b47ULL,
0x3a83ddbd83f52204ULL, 0xf79687aed3eec551ULL}}, // 10^(-25) * 2^339
{{0x87f1362cdd507fe6ULL, 0x3cdc6e306568fc39ULL,
0x95364afe032a819dULL, 0xc612062576589ddaULL}}, // 10^(-26) * 2^342
{{0x775ea264cf55347cULL, 0x9ff42b5717739986ULL,
0xca49f1c05120c9c7ULL, 0x9e74d1b791e07e48ULL}}, // 10^(-27) * 2^345
{{0xccb9def1bf1f5c08ULL, 0x76dcb60081ce0fa5ULL,
0x8bca9d6e188853fcULL, 0xfd87b5f28300ca0dULL}}, // 10^(-28) * 2^349
{{0xa3c7e58e327f7cd3ULL, 0x5f16f80067d80c84ULL,
0x096ee45813a04330ULL, 0xcad2f7f5359a3b3eULL}}, // 10^(-29) * 2^352
{{0xb6398471c1ff970fULL, 0x18df2ccd1fe00a03ULL,
0xa1258379a94d028dULL, 0xa2425ff75e14fc31ULL}}, // 10^(-30) * 2^355
{{0xf82e038e34cc78d9ULL, 0x4718f0a419800802ULL,
0x80eacf948770ced7ULL, 0x81ceb32c4b43fcf4ULL}}, // 10^(-31) * 2^358
{{0x59e338e387ad8e28ULL, 0x0b5b1aa028ccd99eULL,
0x67de18eda5814af2ULL, 0xcfb11ead453994baULL}}, // 10^(-32) * 2^362
{{0x47e8fa4f9fbe0b53ULL, 0x6f7c154ced70ae18ULL,
0xecb1ad8aeacdd58eULL, 0xa6274bbdd0fadd61ULL}}, // 10^(-33) * 2^365
{{0xd320c83fb2fe6f75ULL, 0xbf967770bdf3be79ULL,
0xbd5af13bef0b113eULL, 0x84ec3c97da624ab4ULL}} // 10^(-34) * 2^368
};
// shiftright256M[] contains the right shift count to obtain C2* from the top
// 192 bits of the 256x256-bit product C2 * Kx
int shiftright256M[] = {
15, // 335 - 320
19, // 339 - 320
22, // 342 - 320
25, // 345 - 320
29, // 349 - 320
32, // 352 - 320 // careful of 32-bit machines!
35, // 355 - 320
38, // 358 - 320
42, // 362 - 320
45, // 365 - 320
48 // 368 - 320
};
// maskhigh256M[] contains the mask to apply to the top 192 bits of the
// 256x256-bit product in order to obtain the high bits of f*
UINT64 maskhigh256M[] = {
0x0000000000007fffULL, // 15 = 335 - 320 bits
0x000000000007ffffULL, // 19 = 339 - 320 bits
0x00000000003fffffULL, // 22 = 342 - 320 bits
0x0000000001ffffffULL, // 25 = 345 - 320 bits
0x000000001fffffffULL, // 29 = 349 - 320 bits
0x00000000ffffffffULL, // 32 = 352 - 320 bits
0x00000007ffffffffULL, // 35 = 355 - 320 bits
0x0000003fffffffffULL, // 38 = 358 - 320 bits
0x000003ffffffffffULL, // 42 = 362 - 320 bits
0x00001fffffffffffULL, // 45 = 365 - 320 bits
0x0000ffffffffffffULL // 48 = 368 - 320 bits
};
// onehalf256M[] contains 1/2 positioned correctly for comparison with the
// high bits of f*; the high 128 bits of the 512-bit mask are 0
UINT64 onehalf256M[] = {
0x0000000000004000ULL, // 15 = 335 - 320 bits
0x0000000000040000ULL, // 19 = 339 - 320 bits
0x0000000000200000ULL, // 22 = 342 - 320 bits
0x0000000001000000ULL, // 25 = 345 - 320 bits
0x0000000010000000ULL, // 29 = 349 - 320 bits
0x0000000080000000ULL, // 32 = 352 - 320 bits
0x0000000400000000ULL, // 35 = 355 - 320 bits
0x0000002000000000ULL, // 38 = 358 - 320 bits
0x0000020000000000ULL, // 42 = 362 - 320 bits
0x0000100000000000ULL, // 45 = 365 - 320 bits
0x0000800000000000ULL // 48 = 368 - 320 bits
};
// char_table2[] is used to convert n to string, where 10 <= n <= 99
unsigned char char_table2[180] = {
'1', '0',
'1', '1',
'1', '2',
'1', '3',
'1', '4',
'1', '5',
'1', '6',
'1', '7',
'1', '8',
'1', '9',
'2', '0',
'2', '1',
'2', '2',
'2', '3',
'2', '4',
'2', '5',
'2', '6',
'2', '7',
'2', '8',
'2', '9',
'3', '0',
'3', '1',
'3', '2',
'3', '3',
'3', '4',
'3', '5',
'3', '6',
'3', '7',
'3', '8',
'3', '9',
'4', '0',
'4', '1',
'4', '2',
'4', '3',
'4', '4',
'4', '5',
'4', '6',
'4', '7',
'4', '8',
'4', '9',
'5', '0',
'5', '1',
'5', '2',
'5', '3',
'5', '4',
'5', '5',
'5', '6',
'5', '7',
'5', '8',
'5', '9',
'6', '0',
'6', '1',
'6', '2',
'6', '3',
'6', '4',
'6', '5',
'6', '6',
'6', '7',
'6', '8',
'6', '9',
'7', '0',
'7', '1',
'7', '2',
'7', '3',
'7', '4',
'7', '5',
'7', '6',
'7', '7',
'7', '8',
'7', '9',
'8', '0',
'8', '1',
'8', '2',
'8', '3',
'8', '4',
'8', '5',
'8', '6',
'8', '7',
'8', '8',
'8', '9',
'9', '0',
'9', '1',
'9', '2',
'9', '3',
'9', '4',
'9', '5',
'9', '6',
'9', '7',
'9', '8',
'9', '9'
};
// char_table3[] is used to convert n to string, where 000 <= n <= 999
unsigned char char_table3[3000] = {
'0', '0', '0',
'0', '0', '1',
'0', '0', '2',
'0', '0', '3',
'0', '0', '4',
'0', '0', '5',
'0', '0', '6',
'0', '0', '7',
'0', '0', '8',
'0', '0', '9',
'0', '1', '0',
'0', '1', '1',
'0', '1', '2',
'0', '1', '3',
'0', '1', '4',
'0', '1', '5',
'0', '1', '6',
'0', '1', '7',
'0', '1', '8',
'0', '1', '9',
'0', '2', '0',
'0', '2', '1',
'0', '2', '2',
'0', '2', '3',
'0', '2', '4',
'0', '2', '5',
'0', '2', '6',
'0', '2', '7',
'0', '2', '8',
'0', '2', '9',
'0', '3', '0',
'0', '3', '1',
'0', '3', '2',
'0', '3', '3',
'0', '3', '4',
'0', '3', '5',
'0', '3', '6',
'0', '3', '7',
'0', '3', '8',
'0', '3', '9',
'0', '4', '0',
'0', '4', '1',
'0', '4', '2',
'0', '4', '3',
'0', '4', '4',
'0', '4', '5',
'0', '4', '6',
'0', '4', '7',
'0', '4', '8',
'0', '4', '9',
'0', '5', '0',
'0', '5', '1',
'0', '5', '2',
'0', '5', '3',
'0', '5', '4',
'0', '5', '5',
'0', '5', '6',
'0', '5', '7',
'0', '5', '8',
'0', '5', '9',
'0', '6', '0',
'0', '6', '1',
'0', '6', '2',
'0', '6', '3',
'0', '6', '4',
'0', '6', '5',
'0', '6', '6',
'0', '6', '7',
'0', '6', '8',
'0', '6', '9',
'0', '7', '0',
'0', '7', '1',
'0', '7', '2',
'0', '7', '3',
'0', '7', '4',
'0', '7', '5',
'0', '7', '6',
'0', '7', '7',
'0', '7', '8',
'0', '7', '9',
'0', '8', '0',
'0', '8', '1',
'0', '8', '2',
'0', '8', '3',
'0', '8', '4',
'0', '8', '5',
'0', '8', '6',
'0', '8', '7',
'0', '8', '8',
'0', '8', '9',
'0', '9', '0',
'0', '9', '1',
'0', '9', '2',
'0', '9', '3',
'0', '9', '4',
'0', '9', '5',
'0', '9', '6',
'0', '9', '7',
'0', '9', '8',
'0', '9', '9',
'1', '0', '0',
'1', '0', '1',
'1', '0', '2',
'1', '0', '3',
'1', '0', '4',
'1', '0', '5',
'1', '0', '6',
'1', '0', '7',
'1', '0', '8',
'1', '0', '9',
'1', '1', '0',
'1', '1', '1',
'1', '1', '2',
'1', '1', '3',
'1', '1', '4',
'1', '1', '5',
'1', '1', '6',
'1', '1', '7',
'1', '1', '8',
'1', '1', '9',
'1', '2', '0',
'1', '2', '1',
'1', '2', '2',
'1', '2', '3',
'1', '2', '4',
'1', '2', '5',
'1', '2', '6',
'1', '2', '7',
'1', '2', '8',
'1', '2', '9',
'1', '3', '0',
'1', '3', '1',
'1', '3', '2',
'1', '3', '3',
'1', '3', '4',
'1', '3', '5',
'1', '3', '6',
'1', '3', '7',
'1', '3', '8',
'1', '3', '9',
'1', '4', '0',
'1', '4', '1',
'1', '4', '2',
'1', '4', '3',
'1', '4', '4',
'1', '4', '5',
'1', '4', '6',
'1', '4', '7',
'1', '4', '8',
'1', '4', '9',
'1', '5', '0',
'1', '5', '1',
'1', '5', '2',
'1', '5', '3',
'1', '5', '4',
'1', '5', '5',
'1', '5', '6',
'1', '5', '7',
'1', '5', '8',
'1', '5', '9',
'1', '6', '0',
'1', '6', '1',
'1', '6', '2',
'1', '6', '3',
'1', '6', '4',
'1', '6', '5',
'1', '6', '6',
'1', '6', '7',
'1', '6', '8',
'1', '6', '9',
'1', '7', '0',
'1', '7', '1',
'1', '7', '2',
'1', '7', '3',
'1', '7', '4',
'1', '7', '5',
'1', '7', '6',
'1', '7', '7',
'1', '7', '8',
'1', '7', '9',
'1', '8', '0',
'1', '8', '1',
'1', '8', '2',
'1', '8', '3',
'1', '8', '4',
'1', '8', '5',
'1', '8', '6',
'1', '8', '7',
'1', '8', '8',
'1', '8', '9',
'1', '9', '0',
'1', '9', '1',
'1', '9', '2',
'1', '9', '3',
'1', '9', '4',
'1', '9', '5',
'1', '9', '6',
'1', '9', '7',
'1', '9', '8',
'1', '9', '9',
'2', '0', '0',
'2', '0', '1',
'2', '0', '2',
'2', '0', '3',
'2', '0', '4',
'2', '0', '5',
'2', '0', '6',
'2', '0', '7',
'2', '0', '8',
'2', '0', '9',
'2', '1', '0',
'2', '1', '1',
'2', '1', '2',
'2', '1', '3',
'2', '1', '4',
'2', '1', '5',
'2', '1', '6',
'2', '1', '7',
'2', '1', '8',
'2', '1', '9',
'2', '2', '0',
'2', '2', '1',
'2', '2', '2',
'2', '2', '3',
'2', '2', '4',
'2', '2', '5',
'2', '2', '6',
'2', '2', '7',
'2', '2', '8',
'2', '2', '9',
'2', '3', '0',
'2', '3', '1',
'2', '3', '2',
'2', '3', '3',
'2', '3', '4',
'2', '3', '5',
'2', '3', '6',
'2', '3', '7',
'2', '3', '8',
'2', '3', '9',
'2', '4', '0',
'2', '4', '1',
'2', '4', '2',
'2', '4', '3',
'2', '4', '4',
'2', '4', '5',
'2', '4', '6',
'2', '4', '7',
'2', '4', '8',
'2', '4', '9',
'2', '5', '0',
'2', '5', '1',
'2', '5', '2',
'2', '5', '3',
'2', '5', '4',
'2', '5', '5',
'2', '5', '6',
'2', '5', '7',
'2', '5', '8',
'2', '5', '9',
'2', '6', '0',
'2', '6', '1',
'2', '6', '2',
'2', '6', '3',
'2', '6', '4',
'2', '6', '5',
'2', '6', '6',
'2', '6', '7',
'2', '6', '8',
'2', '6', '9',
'2', '7', '0',
'2', '7', '1',
'2', '7', '2',
'2', '7', '3',
'2', '7', '4',
'2', '7', '5',
'2', '7', '6',
'2', '7', '7',
'2', '7', '8',
'2', '7', '9',
'2', '8', '0',
'2', '8', '1',
'2', '8', '2',
'2', '8', '3',
'2', '8', '4',
'2', '8', '5',
'2', '8', '6',
'2', '8', '7',
'2', '8', '8',
'2', '8', '9',
'2', '9', '0',
'2', '9', '1',
'2', '9', '2',
'2', '9', '3',
'2', '9', '4',
'2', '9', '5',
'2', '9', '6',
'2', '9', '7',
'2', '9', '8',
'2', '9', '9',
'3', '0', '0',
'3', '0', '1',
'3', '0', '2',
'3', '0', '3',
'3', '0', '4',
'3', '0', '5',
'3', '0', '6',
'3', '0', '7',
'3', '0', '8',
'3', '0', '9',
'3', '1', '0',
'3', '1', '1',
'3', '1', '2',
'3', '1', '3',
'3', '1', '4',
'3', '1', '5',
'3', '1', '6',
'3', '1', '7',
'3', '1', '8',
'3', '1', '9',
'3', '2', '0',
'3', '2', '1',
'3', '2', '2',
'3', '2', '3',
'3', '2', '4',
'3', '2', '5',
'3', '2', '6',
'3', '2', '7',
'3', '2', '8',
'3', '2', '9',
'3', '3', '0',
'3', '3', '1',
'3', '3', '2',
'3', '3', '3',
'3', '3', '4',
'3', '3', '5',
'3', '3', '6',
'3', '3', '7',
'3', '3', '8',
'3', '3', '9',
'3', '4', '0',
'3', '4', '1',
'3', '4', '2',
'3', '4', '3',
'3', '4', '4',
'3', '4', '5',
'3', '4', '6',
'3', '4', '7',
'3', '4', '8',
'3', '4', '9',
'3', '5', '0',
'3', '5', '1',
'3', '5', '2',
'3', '5', '3',
'3', '5', '4',
'3', '5', '5',
'3', '5', '6',
'3', '5', '7',
'3', '5', '8',
'3', '5', '9',
'3', '6', '0',
'3', '6', '1',
'3', '6', '2',
'3', '6', '3',
'3', '6', '4',
'3', '6', '5',
'3', '6', '6',
'3', '6', '7',
'3', '6', '8',
'3', '6', '9',
'3', '7', '0',
'3', '7', '1',
'3', '7', '2',
'3', '7', '3',
'3', '7', '4',
'3', '7', '5',
'3', '7', '6',
'3', '7', '7',
'3', '7', '8',
'3', '7', '9',
'3', '8', '0',
'3', '8', '1',
'3', '8', '2',
'3', '8', '3',
'3', '8', '4',
'3', '8', '5',
'3', '8', '6',
'3', '8', '7',
'3', '8', '8',
'3', '8', '9',
'3', '9', '0',
'3', '9', '1',
'3', '9', '2',
'3', '9', '3',
'3', '9', '4',
'3', '9', '5',
'3', '9', '6',
'3', '9', '7',
'3', '9', '8',
'3', '9', '9',
'4', '0', '0',
'4', '0', '1',
'4', '0', '2',
'4', '0', '3',
'4', '0', '4',
'4', '0', '5',
'4', '0', '6',
'4', '0', '7',
'4', '0', '8',
'4', '0', '9',
'4', '1', '0',
'4', '1', '1',
'4', '1', '2',
'4', '1', '3',
'4', '1', '4',
'4', '1', '5',
'4', '1', '6',
'4', '1', '7',
'4', '1', '8',
'4', '1', '9',
'4', '2', '0',
'4', '2', '1',
'4', '2', '2',
'4', '2', '3',
'4', '2', '4',
'4', '2', '5',
'4', '2', '6',
'4', '2', '7',
'4', '2', '8',
'4', '2', '9',
'4', '3', '0',
'4', '3', '1',
'4', '3', '2',
'4', '3', '3',
'4', '3', '4',
'4', '3', '5',
'4', '3', '6',
'4', '3', '7',
'4', '3', '8',
'4', '3', '9',
'4', '4', '0',
'4', '4', '1',
'4', '4', '2',
'4', '4', '3',
'4', '4', '4',
'4', '4', '5',
'4', '4', '6',
'4', '4', '7',
'4', '4', '8',
'4', '4', '9',
'4', '5', '0',
'4', '5', '1',
'4', '5', '2',
'4', '5', '3',
'4', '5', '4',
'4', '5', '5',
'4', '5', '6',
'4', '5', '7',
'4', '5', '8',
'4', '5', '9',
'4', '6', '0',
'4', '6', '1',
'4', '6', '2',
'4', '6', '3',
'4', '6', '4',
'4', '6', '5',
'4', '6', '6',
'4', '6', '7',
'4', '6', '8',
'4', '6', '9',
'4', '7', '0',
'4', '7', '1',
'4', '7', '2',
'4', '7', '3',
'4', '7', '4',
'4', '7', '5',
'4', '7', '6',
'4', '7', '7',
'4', '7', '8',
'4', '7', '9',
'4', '8', '0',
'4', '8', '1',
'4', '8', '2',
'4', '8', '3',
'4', '8', '4',
'4', '8', '5',
'4', '8', '6',
'4', '8', '7',
'4', '8', '8',
'4', '8', '9',
'4', '9', '0',
'4', '9', '1',
'4', '9', '2',
'4', '9', '3',
'4', '9', '4',
'4', '9', '5',
'4', '9', '6',
'4', '9', '7',
'4', '9', '8',
'4', '9', '9',
'5', '0', '0',
'5', '0', '1',
'5', '0', '2',
'5', '0', '3',
'5', '0', '4',
'5', '0', '5',
'5', '0', '6',
'5', '0', '7',
'5', '0', '8',
'5', '0', '9',
'5', '1', '0',
'5', '1', '1',
'5', '1', '2',
'5', '1', '3',
'5', '1', '4',
'5', '1', '5',
'5', '1', '6',
'5', '1', '7',
'5', '1', '8',
'5', '1', '9',
'5', '2', '0',
'5', '2', '1',
'5', '2', '2',
'5', '2', '3',
'5', '2', '4',
'5', '2', '5',
'5', '2', '6',
'5', '2', '7',
'5', '2', '8',
'5', '2', '9',
'5', '3', '0',
'5', '3', '1',
'5', '3', '2',
'5', '3', '3',
'5', '3', '4',
'5', '3', '5',
'5', '3', '6',
'5', '3', '7',
'5', '3', '8',
'5', '3', '9',
'5', '4', '0',
'5', '4', '1',
'5', '4', '2',
'5', '4', '3',
'5', '4', '4',
'5', '4', '5',
'5', '4', '6',
'5', '4', '7',
'5', '4', '8',
'5', '4', '9',
'5', '5', '0',
'5', '5', '1',
'5', '5', '2',
'5', '5', '3',
'5', '5', '4',
'5', '5', '5',
'5', '5', '6',
'5', '5', '7',
'5', '5', '8',
'5', '5', '9',
'5', '6', '0',
'5', '6', '1',
'5', '6', '2',
'5', '6', '3',
'5', '6', '4',
'5', '6', '5',
'5', '6', '6',
'5', '6', '7',
'5', '6', '8',
'5', '6', '9',
'5', '7', '0',
'5', '7', '1',
'5', '7', '2',
'5', '7', '3',
'5', '7', '4',
'5', '7', '5',
'5', '7', '6',
'5', '7', '7',
'5', '7', '8',
'5', '7', '9',
'5', '8', '0',
'5', '8', '1',
'5', '8', '2',
'5', '8', '3',
'5', '8', '4',
'5', '8', '5',
'5', '8', '6',
'5', '8', '7',
'5', '8', '8',
'5', '8', '9',
'5', '9', '0',
'5', '9', '1',
'5', '9', '2',
'5', '9', '3',
'5', '9', '4',
'5', '9', '5',
'5', '9', '6',
'5', '9', '7',
'5', '9', '8',
'5', '9', '9',
'6', '0', '0',
'6', '0', '1',
'6', '0', '2',
'6', '0', '3',
'6', '0', '4',
'6', '0', '5',
'6', '0', '6',
'6', '0', '7',
'6', '0', '8',
'6', '0', '9',
'6', '1', '0',
'6', '1', '1',
'6', '1', '2',
'6', '1', '3',
'6', '1', '4',
'6', '1', '5',
'6', '1', '6',
'6', '1', '7',
'6', '1', '8',
'6', '1', '9',
'6', '2', '0',
'6', '2', '1',
'6', '2', '2',
'6', '2', '3',
'6', '2', '4',
'6', '2', '5',
'6', '2', '6',
'6', '2', '7',
'6', '2', '8',
'6', '2', '9',
'6', '3', '0',
'6', '3', '1',
'6', '3', '2',
'6', '3', '3',
'6', '3', '4',
'6', '3', '5',
'6', '3', '6',
'6', '3', '7',
'6', '3', '8',
'6', '3', '9',
'6', '4', '0',
'6', '4', '1',
'6', '4', '2',
'6', '4', '3',
'6', '4', '4',
'6', '4', '5',
'6', '4', '6',
'6', '4', '7',
'6', '4', '8',
'6', '4', '9',
'6', '5', '0',
'6', '5', '1',
'6', '5', '2',
'6', '5', '3',
'6', '5', '4',
'6', '5', '5',
'6', '5', '6',
'6', '5', '7',
'6', '5', '8',
'6', '5', '9',
'6', '6', '0',
'6', '6', '1',
'6', '6', '2',
'6', '6', '3',
'6', '6', '4',
'6', '6', '5',
'6', '6', '6',
'6', '6', '7',
'6', '6', '8',
'6', '6', '9',
'6', '7', '0',
'6', '7', '1',
'6', '7', '2',
'6', '7', '3',
'6', '7', '4',
'6', '7', '5',
'6', '7', '6',
'6', '7', '7',
'6', '7', '8',
'6', '7', '9',
'6', '8', '0',
'6', '8', '1',
'6', '8', '2',
'6', '8', '3',
'6', '8', '4',
'6', '8', '5',
'6', '8', '6',
'6', '8', '7',
'6', '8', '8',
'6', '8', '9',
'6', '9', '0',
'6', '9', '1',
'6', '9', '2',
'6', '9', '3',
'6', '9', '4',
'6', '9', '5',
'6', '9', '6',
'6', '9', '7',
'6', '9', '8',
'6', '9', '9',
'7', '0', '0',
'7', '0', '1',
'7', '0', '2',
'7', '0', '3',
'7', '0', '4',
'7', '0', '5',
'7', '0', '6',
'7', '0', '7',
'7', '0', '8',
'7', '0', '9',
'7', '1', '0',
'7', '1', '1',
'7', '1', '2',
'7', '1', '3',
'7', '1', '4',
'7', '1', '5',
'7', '1', '6',
'7', '1', '7',
'7', '1', '8',
'7', '1', '9',
'7', '2', '0',
'7', '2', '1',
'7', '2', '2',
'7', '2', '3',
'7', '2', '4',
'7', '2', '5',
'7', '2', '6',
'7', '2', '7',
'7', '2', '8',
'7', '2', '9',
'7', '3', '0',
'7', '3', '1',
'7', '3', '2',
'7', '3', '3',
'7', '3', '4',
'7', '3', '5',
'7', '3', '6',
'7', '3', '7',
'7', '3', '8',
'7', '3', '9',
'7', '4', '0',
'7', '4', '1',
'7', '4', '2',
'7', '4', '3',
'7', '4', '4',
'7', '4', '5',
'7', '4', '6',
'7', '4', '7',
'7', '4', '8',
'7', '4', '9',
'7', '5', '0',
'7', '5', '1',
'7', '5', '2',
'7', '5', '3',
'7', '5', '4',
'7', '5', '5',
'7', '5', '6',
'7', '5', '7',
'7', '5', '8',
'7', '5', '9',
'7', '6', '0',
'7', '6', '1',
'7', '6', '2',
'7', '6', '3',
'7', '6', '4',
'7', '6', '5',
'7', '6', '6',
'7', '6', '7',
'7', '6', '8',
'7', '6', '9',
'7', '7', '0',
'7', '7', '1',
'7', '7', '2',
'7', '7', '3',
'7', '7', '4',
'7', '7', '5',
'7', '7', '6',
'7', '7', '7',
'7', '7', '8',
'7', '7', '9',
'7', '8', '0',
'7', '8', '1',
'7', '8', '2',
'7', '8', '3',
'7', '8', '4',
'7', '8', '5',
'7', '8', '6',
'7', '8', '7',
'7', '8', '8',
'7', '8', '9',
'7', '9', '0',
'7', '9', '1',
'7', '9', '2',
'7', '9', '3',
'7', '9', '4',
'7', '9', '5',
'7', '9', '6',
'7', '9', '7',
'7', '9', '8',
'7', '9', '9',
'8', '0', '0',
'8', '0', '1',
'8', '0', '2',
'8', '0', '3',
'8', '0', '4',
'8', '0', '5',
'8', '0', '6',
'8', '0', '7',
'8', '0', '8',
'8', '0', '9',
'8', '1', '0',
'8', '1', '1',
'8', '1', '2',
'8', '1', '3',
'8', '1', '4',
'8', '1', '5',
'8', '1', '6',
'8', '1', '7',
'8', '1', '8',
'8', '1', '9',
'8', '2', '0',
'8', '2', '1',
'8', '2', '2',
'8', '2', '3',
'8', '2', '4',
'8', '2', '5',
'8', '2', '6',
'8', '2', '7',
'8', '2', '8',
'8', '2', '9',
'8', '3', '0',
'8', '3', '1',
'8', '3', '2',
'8', '3', '3',
'8', '3', '4',
'8', '3', '5',
'8', '3', '6',
'8', '3', '7',
'8', '3', '8',
'8', '3', '9',
'8', '4', '0',
'8', '4', '1',
'8', '4', '2',
'8', '4', '3',
'8', '4', '4',
'8', '4', '5',
'8', '4', '6',
'8', '4', '7',
'8', '4', '8',
'8', '4', '9',
'8', '5', '0',
'8', '5', '1',
'8', '5', '2',
'8', '5', '3',
'8', '5', '4',
'8', '5', '5',
'8', '5', '6',
'8', '5', '7',
'8', '5', '8',
'8', '5', '9',
'8', '6', '0',
'8', '6', '1',
'8', '6', '2',
'8', '6', '3',
'8', '6', '4',
'8', '6', '5',
'8', '6', '6',
'8', '6', '7',
'8', '6', '8',
'8', '6', '9',
'8', '7', '0',
'8', '7', '1',
'8', '7', '2',
'8', '7', '3',
'8', '7', '4',
'8', '7', '5',
'8', '7', '6',
'8', '7', '7',
'8', '7', '8',
'8', '7', '9',
'8', '8', '0',
'8', '8', '1',
'8', '8', '2',
'8', '8', '3',
'8', '8', '4',
'8', '8', '5',
'8', '8', '6',
'8', '8', '7',
'8', '8', '8',
'8', '8', '9',
'8', '9', '0',
'8', '9', '1',
'8', '9', '2',
'8', '9', '3',
'8', '9', '4',
'8', '9', '5',
'8', '9', '6',
'8', '9', '7',
'8', '9', '8',
'8', '9', '9',
'9', '0', '0',
'9', '0', '1',
'9', '0', '2',
'9', '0', '3',
'9', '0', '4',
'9', '0', '5',
'9', '0', '6',
'9', '0', '7',
'9', '0', '8',
'9', '0', '9',
'9', '1', '0',
'9', '1', '1',
'9', '1', '2',
'9', '1', '3',
'9', '1', '4',
'9', '1', '5',
'9', '1', '6',
'9', '1', '7',
'9', '1', '8',
'9', '1', '9',
'9', '2', '0',
'9', '2', '1',
'9', '2', '2',
'9', '2', '3',
'9', '2', '4',
'9', '2', '5',
'9', '2', '6',
'9', '2', '7',
'9', '2', '8',
'9', '2', '9',
'9', '3', '0',
'9', '3', '1',
'9', '3', '2',
'9', '3', '3',
'9', '3', '4',
'9', '3', '5',
'9', '3', '6',
'9', '3', '7',
'9', '3', '8',
'9', '3', '9',
'9', '4', '0',
'9', '4', '1',
'9', '4', '2',
'9', '4', '3',
'9', '4', '4',
'9', '4', '5',
'9', '4', '6',
'9', '4', '7',
'9', '4', '8',
'9', '4', '9',