master
1const std = @import("std");
2const math = std.math;
3const common = @import("common.zig");
4const FloatStream = @import("FloatStream.zig");
5const isEightDigits = @import("common.zig").isEightDigits;
6const mantissaType = common.mantissaType;
7
8// Arbitrary-precision decimal class for fallback algorithms.
9//
10// This is only used if the fast-path (native floats) and
11// the Eisel-Lemire algorithm are unable to unambiguously
12// determine the float.
13//
14// The technique used is "Simple Decimal Conversion", developed
15// by Nigel Tao and Ken Thompson. A detailed description of the
16// algorithm can be found in "ParseNumberF64 by Simple Decimal Conversion",
17// available online: <https://nigeltao.github.io/blog/2020/parse-number-f64-simple.html>.
18//
19// Big-decimal implementation. We do not use the big.Int routines since we only require a maximum
20// fixed region of memory. Further, we require only a small subset of operations.
21//
22// This accepts a floating point parameter and will generate a Decimal which can correctly parse
23// the input with sufficient accuracy. Internally this means either a u64 mantissa (f16, f32 or f64)
24// or a u128 mantissa (f128).
25pub fn Decimal(comptime T: type) type {
26 const MantissaT = mantissaType(T);
27 std.debug.assert(MantissaT == u64 or MantissaT == u128);
28
29 return struct {
30 const Self = @This();
31
32 /// The maximum number of digits required to unambiguously round a float.
33 ///
34 /// For a double-precision IEEE-754 float, this required 767 digits,
35 /// so we store the max digits + 1.
36 ///
37 /// We can exactly represent a float in base `b` from base 2 if
38 /// `b` is divisible by 2. This function calculates the exact number of
39 /// digits required to exactly represent that float.
40 ///
41 /// According to the "Handbook of Floating Point Arithmetic",
42 /// for IEEE754, with emin being the min exponent, p2 being the
43 /// precision, and b being the base, the number of digits follows as:
44 ///
45 /// `−emin + p2 + ⌊(emin + 1) log(2, b) − log(1 − 2^(−p2), b)⌋`
46 ///
47 /// For f32, this follows as:
48 /// emin = -126
49 /// p2 = 24
50 ///
51 /// For f64, this follows as:
52 /// emin = -1022
53 /// p2 = 53
54 ///
55 /// For f128, this follows as:
56 /// emin = -16383
57 /// p2 = 112
58 ///
59 /// In Python:
60 /// `-emin + p2 + math.floor((emin+ 1)*math.log(2, b)-math.log(1-2**(-p2), b))`
61 pub const max_digits = if (MantissaT == u64) 768 else 11564;
62 /// The max digits that can be exactly represented in a 64-bit integer.
63 pub const max_digits_without_overflow = if (MantissaT == u64) 19 else 38;
64 pub const decimal_point_range = if (MantissaT == u64) 2047 else 32767;
65 pub const min_exponent = if (MantissaT == u64) -324 else -4966;
66 pub const max_exponent = if (MantissaT == u64) 310 else 4934;
67 pub const max_decimal_digits = if (MantissaT == u64) 18 else 37;
68
69 /// The number of significant digits in the decimal.
70 num_digits: usize,
71 /// The offset of the decimal point in the significant digits.
72 decimal_point: i32,
73 /// If the number of significant digits stored in the decimal is truncated.
74 truncated: bool,
75 /// buffer of the raw digits, in the range [0, 9].
76 digits: [max_digits]u8,
77
78 pub fn new() Self {
79 return .{
80 .num_digits = 0,
81 .decimal_point = 0,
82 .truncated = false,
83 .digits = [_]u8{0} ** max_digits,
84 };
85 }
86
87 /// Append a digit to the buffer
88 pub fn tryAddDigit(self: *Self, digit: u8) void {
89 if (self.num_digits < max_digits) {
90 self.digits[self.num_digits] = digit;
91 }
92 self.num_digits += 1;
93 }
94
95 /// Trim trailing zeroes from the buffer
96 pub fn trim(self: *Self) void {
97 // All of the following calls to `Self::trim` can't panic because:
98 //
99 // 1. `parse_decimal` sets `num_digits` to a max of `max_digits`.
100 // 2. `right_shift` sets `num_digits` to `write_index`, which is bounded by `num_digits`.
101 // 3. `left_shift` `num_digits` to a max of `max_digits`.
102 //
103 // Trim is only called in `right_shift` and `left_shift`.
104 std.debug.assert(self.num_digits <= max_digits);
105 while (self.num_digits != 0 and self.digits[self.num_digits - 1] == 0) {
106 self.num_digits -= 1;
107 }
108 }
109
110 pub fn round(self: *Self) MantissaT {
111 if (self.num_digits == 0 or self.decimal_point < 0) {
112 return 0;
113 } else if (self.decimal_point > max_decimal_digits) {
114 return math.maxInt(MantissaT);
115 }
116
117 const dp = @as(usize, @intCast(self.decimal_point));
118 var n: MantissaT = 0;
119
120 var i: usize = 0;
121 while (i < dp) : (i += 1) {
122 n *= 10;
123 if (i < self.num_digits) {
124 n += @as(MantissaT, self.digits[i]);
125 }
126 }
127
128 var round_up = false;
129 if (dp < self.num_digits) {
130 round_up = self.digits[dp] >= 5;
131 if (self.digits[dp] == 5 and dp + 1 == self.num_digits) {
132 round_up = self.truncated or ((dp != 0) and (1 & self.digits[dp - 1] != 0));
133 }
134 }
135 if (round_up) {
136 n += 1;
137 }
138 return n;
139 }
140
141 /// Computes decimal * 2^shift.
142 pub fn leftShift(self: *Self, shift: usize) void {
143 if (self.num_digits == 0) {
144 return;
145 }
146 const num_new_digits = self.numberOfDigitsLeftShift(shift);
147 var read_index = self.num_digits;
148 var write_index = self.num_digits + num_new_digits;
149 var n: MantissaT = 0;
150 while (read_index != 0) {
151 read_index -= 1;
152 write_index -= 1;
153 n += math.shl(MantissaT, self.digits[read_index], shift);
154
155 const quotient = n / 10;
156 const remainder = n - (10 * quotient);
157 if (write_index < max_digits) {
158 self.digits[write_index] = @as(u8, @intCast(remainder));
159 } else if (remainder > 0) {
160 self.truncated = true;
161 }
162 n = quotient;
163 }
164 while (n > 0) {
165 write_index -= 1;
166
167 const quotient = n / 10;
168 const remainder = n - (10 * quotient);
169 if (write_index < max_digits) {
170 self.digits[write_index] = @as(u8, @intCast(remainder));
171 } else if (remainder > 0) {
172 self.truncated = true;
173 }
174 n = quotient;
175 }
176
177 self.num_digits += num_new_digits;
178 if (self.num_digits > max_digits) {
179 self.num_digits = max_digits;
180 }
181 self.decimal_point += @as(i32, @intCast(num_new_digits));
182 self.trim();
183 }
184
185 /// Computes decimal * 2^-shift.
186 pub fn rightShift(self: *Self, shift: usize) void {
187 var read_index: usize = 0;
188 var write_index: usize = 0;
189 var n: MantissaT = 0;
190 while (math.shr(MantissaT, n, shift) == 0) {
191 if (read_index < self.num_digits) {
192 n = (10 * n) + self.digits[read_index];
193 read_index += 1;
194 } else if (n == 0) {
195 return;
196 } else {
197 while (math.shr(MantissaT, n, shift) == 0) {
198 n *= 10;
199 read_index += 1;
200 }
201 break;
202 }
203 }
204
205 self.decimal_point -= @as(i32, @intCast(read_index)) - 1;
206 if (self.decimal_point < -decimal_point_range) {
207 self.num_digits = 0;
208 self.decimal_point = 0;
209 self.truncated = false;
210 return;
211 }
212
213 const mask = math.shl(MantissaT, 1, shift) - 1;
214 while (read_index < self.num_digits) {
215 const new_digit = @as(u8, @intCast(math.shr(MantissaT, n, shift)));
216 n = (10 * (n & mask)) + self.digits[read_index];
217 read_index += 1;
218 self.digits[write_index] = new_digit;
219 write_index += 1;
220 }
221 while (n > 0) {
222 const new_digit = @as(u8, @intCast(math.shr(MantissaT, n, shift)));
223 n = 10 * (n & mask);
224 if (write_index < max_digits) {
225 self.digits[write_index] = new_digit;
226 write_index += 1;
227 } else if (new_digit > 0) {
228 self.truncated = true;
229 }
230 }
231 self.num_digits = write_index;
232 self.trim();
233 }
234
235 /// Parse a bit integer representation of the float as a decimal.
236 // We do not verify underscores in this path since these will have been verified
237 // via parse.parseNumber so can assume the number is well-formed.
238 // This code-path does not have to handle hex-floats since these will always be handled via another
239 // function prior to this.
240 pub fn parse(s: []const u8) Self {
241 var d = Self.new();
242 var stream = FloatStream.init(s);
243
244 stream.skipChars("0_");
245 while (stream.scanDigit(10)) |digit| {
246 d.tryAddDigit(digit);
247 }
248
249 if (stream.firstIs(".")) {
250 stream.advance(1);
251 const marker = stream.offsetTrue();
252
253 // Skip leading zeroes
254 if (d.num_digits == 0) {
255 stream.skipChars("0");
256 }
257
258 while (stream.hasLen(8) and d.num_digits + 8 < max_digits) {
259 const v = stream.readU64Unchecked();
260 if (!isEightDigits(v)) {
261 break;
262 }
263 std.mem.writeInt(u64, d.digits[d.num_digits..][0..8], v - 0x3030_3030_3030_3030, .little);
264 d.num_digits += 8;
265 stream.advance(8);
266 }
267
268 while (stream.scanDigit(10)) |digit| {
269 d.tryAddDigit(digit);
270 }
271 d.decimal_point = @as(i32, @intCast(marker)) - @as(i32, @intCast(stream.offsetTrue()));
272 }
273 if (d.num_digits != 0) {
274 // Ignore trailing zeros if any
275 var n_trailing_zeros: usize = 0;
276 var i = stream.offsetTrue() - 1;
277 while (true) {
278 if (s[i] == '0') {
279 n_trailing_zeros += 1;
280 } else if (s[i] != '.') {
281 break;
282 }
283
284 i -= 1;
285 if (i == 0) break;
286 }
287 d.decimal_point += @as(i32, @intCast(n_trailing_zeros));
288 d.num_digits -= n_trailing_zeros;
289 d.decimal_point += @as(i32, @intCast(d.num_digits));
290 if (d.num_digits > max_digits) {
291 d.truncated = true;
292 d.num_digits = max_digits;
293 }
294 }
295 if (stream.firstIsLower("e")) {
296 stream.advance(1);
297 var neg_exp = false;
298 if (stream.firstIs("-")) {
299 neg_exp = true;
300 stream.advance(1);
301 } else if (stream.firstIs("+")) {
302 stream.advance(1);
303 }
304 var exp_num: i32 = 0;
305 while (stream.scanDigit(10)) |digit| {
306 if (exp_num < 0x10000) {
307 exp_num = 10 * exp_num + digit;
308 }
309 }
310 d.decimal_point += if (neg_exp) -exp_num else exp_num;
311 }
312
313 var i = d.num_digits;
314 while (i < max_digits_without_overflow) : (i += 1) {
315 d.digits[i] = 0;
316 }
317
318 return d;
319 }
320
321 // Compute the number decimal digits introduced by a base-2 shift. This is performed
322 // by storing the leading digits of 1/2^i = 5^i and using these along with the cut-off
323 // value to quickly determine the decimal shift from binary.
324 //
325 // See also https://github.com/golang/go/blob/go1.15.3/src/strconv/decimal.go#L163 for
326 // another description of the method.
327 pub fn numberOfDigitsLeftShift(self: *Self, shift: usize) usize {
328 const ShiftCutoff = struct {
329 delta: u8,
330 cutoff: []const u8,
331 };
332
333 // Leading digits of 1/2^i = 5^i.
334 //
335 // ```
336 // import math
337 //
338 // bits = 128
339 // for i in range(bits):
340 // log2 = math.log(2)/math.log(10)
341 // print(f'.{{ .delta = {int(log2*i+1)}, .cutoff = "{5**i}" }}, // {2**i}')
342 // ```
343 const pow2_to_pow5_table = [_]ShiftCutoff{
344 .{ .delta = 0, .cutoff = "" },
345 .{ .delta = 1, .cutoff = "5" }, // 2
346 .{ .delta = 1, .cutoff = "25" }, // 4
347 .{ .delta = 1, .cutoff = "125" }, // 8
348 .{ .delta = 2, .cutoff = "625" }, // 16
349 .{ .delta = 2, .cutoff = "3125" }, // 32
350 .{ .delta = 2, .cutoff = "15625" }, // 64
351 .{ .delta = 3, .cutoff = "78125" }, // 128
352 .{ .delta = 3, .cutoff = "390625" }, // 256
353 .{ .delta = 3, .cutoff = "1953125" }, // 512
354 .{ .delta = 4, .cutoff = "9765625" }, // 1024
355 .{ .delta = 4, .cutoff = "48828125" }, // 2048
356 .{ .delta = 4, .cutoff = "244140625" }, // 4096
357 .{ .delta = 4, .cutoff = "1220703125" }, // 8192
358 .{ .delta = 5, .cutoff = "6103515625" }, // 16384
359 .{ .delta = 5, .cutoff = "30517578125" }, // 32768
360 .{ .delta = 5, .cutoff = "152587890625" }, // 65536
361 .{ .delta = 6, .cutoff = "762939453125" }, // 131072
362 .{ .delta = 6, .cutoff = "3814697265625" }, // 262144
363 .{ .delta = 6, .cutoff = "19073486328125" }, // 524288
364 .{ .delta = 7, .cutoff = "95367431640625" }, // 1048576
365 .{ .delta = 7, .cutoff = "476837158203125" }, // 2097152
366 .{ .delta = 7, .cutoff = "2384185791015625" }, // 4194304
367 .{ .delta = 7, .cutoff = "11920928955078125" }, // 8388608
368 .{ .delta = 8, .cutoff = "59604644775390625" }, // 16777216
369 .{ .delta = 8, .cutoff = "298023223876953125" }, // 33554432
370 .{ .delta = 8, .cutoff = "1490116119384765625" }, // 67108864
371 .{ .delta = 9, .cutoff = "7450580596923828125" }, // 134217728
372 .{ .delta = 9, .cutoff = "37252902984619140625" }, // 268435456
373 .{ .delta = 9, .cutoff = "186264514923095703125" }, // 536870912
374 .{ .delta = 10, .cutoff = "931322574615478515625" }, // 1073741824
375 .{ .delta = 10, .cutoff = "4656612873077392578125" }, // 2147483648
376 .{ .delta = 10, .cutoff = "23283064365386962890625" }, // 4294967296
377 .{ .delta = 10, .cutoff = "116415321826934814453125" }, // 8589934592
378 .{ .delta = 11, .cutoff = "582076609134674072265625" }, // 17179869184
379 .{ .delta = 11, .cutoff = "2910383045673370361328125" }, // 34359738368
380 .{ .delta = 11, .cutoff = "14551915228366851806640625" }, // 68719476736
381 .{ .delta = 12, .cutoff = "72759576141834259033203125" }, // 137438953472
382 .{ .delta = 12, .cutoff = "363797880709171295166015625" }, // 274877906944
383 .{ .delta = 12, .cutoff = "1818989403545856475830078125" }, // 549755813888
384 .{ .delta = 13, .cutoff = "9094947017729282379150390625" }, // 1099511627776
385 .{ .delta = 13, .cutoff = "45474735088646411895751953125" }, // 2199023255552
386 .{ .delta = 13, .cutoff = "227373675443232059478759765625" }, // 4398046511104
387 .{ .delta = 13, .cutoff = "1136868377216160297393798828125" }, // 8796093022208
388 .{ .delta = 14, .cutoff = "5684341886080801486968994140625" }, // 17592186044416
389 .{ .delta = 14, .cutoff = "28421709430404007434844970703125" }, // 35184372088832
390 .{ .delta = 14, .cutoff = "142108547152020037174224853515625" }, // 70368744177664
391 .{ .delta = 15, .cutoff = "710542735760100185871124267578125" }, // 140737488355328
392 .{ .delta = 15, .cutoff = "3552713678800500929355621337890625" }, // 281474976710656
393 .{ .delta = 15, .cutoff = "17763568394002504646778106689453125" }, // 562949953421312
394 .{ .delta = 16, .cutoff = "88817841970012523233890533447265625" }, // 1125899906842624
395 .{ .delta = 16, .cutoff = "444089209850062616169452667236328125" }, // 2251799813685248
396 .{ .delta = 16, .cutoff = "2220446049250313080847263336181640625" }, // 4503599627370496
397 .{ .delta = 16, .cutoff = "11102230246251565404236316680908203125" }, // 9007199254740992
398 .{ .delta = 17, .cutoff = "55511151231257827021181583404541015625" }, // 18014398509481984
399 .{ .delta = 17, .cutoff = "277555756156289135105907917022705078125" }, // 36028797018963968
400 .{ .delta = 17, .cutoff = "1387778780781445675529539585113525390625" }, // 72057594037927936
401 .{ .delta = 18, .cutoff = "6938893903907228377647697925567626953125" }, // 144115188075855872
402 .{ .delta = 18, .cutoff = "34694469519536141888238489627838134765625" }, // 288230376151711744
403 .{ .delta = 18, .cutoff = "173472347597680709441192448139190673828125" }, // 576460752303423488
404 .{ .delta = 19, .cutoff = "867361737988403547205962240695953369140625" }, // 1152921504606846976
405 .{ .delta = 19, .cutoff = "4336808689942017736029811203479766845703125" }, // 2305843009213693952
406 .{ .delta = 19, .cutoff = "21684043449710088680149056017398834228515625" }, // 4611686018427387904
407 .{ .delta = 19, .cutoff = "108420217248550443400745280086994171142578125" }, // 9223372036854775808
408 .{ .delta = 20, .cutoff = "542101086242752217003726400434970855712890625" }, // 18446744073709551616
409 .{ .delta = 20, .cutoff = "2710505431213761085018632002174854278564453125" }, // 36893488147419103232
410 .{ .delta = 20, .cutoff = "13552527156068805425093160010874271392822265625" }, // 73786976294838206464
411 .{ .delta = 21, .cutoff = "67762635780344027125465800054371356964111328125" }, // 147573952589676412928
412 .{ .delta = 21, .cutoff = "338813178901720135627329000271856784820556640625" }, // 295147905179352825856
413 .{ .delta = 21, .cutoff = "1694065894508600678136645001359283924102783203125" }, // 590295810358705651712
414 .{ .delta = 22, .cutoff = "8470329472543003390683225006796419620513916015625" }, // 1180591620717411303424
415 .{ .delta = 22, .cutoff = "42351647362715016953416125033982098102569580078125" }, // 2361183241434822606848
416 .{ .delta = 22, .cutoff = "211758236813575084767080625169910490512847900390625" }, // 4722366482869645213696
417 .{ .delta = 22, .cutoff = "1058791184067875423835403125849552452564239501953125" }, // 9444732965739290427392
418 .{ .delta = 23, .cutoff = "5293955920339377119177015629247762262821197509765625" }, // 18889465931478580854784
419 .{ .delta = 23, .cutoff = "26469779601696885595885078146238811314105987548828125" }, // 37778931862957161709568
420 .{ .delta = 23, .cutoff = "132348898008484427979425390731194056570529937744140625" }, // 75557863725914323419136
421 .{ .delta = 24, .cutoff = "661744490042422139897126953655970282852649688720703125" }, // 151115727451828646838272
422 .{ .delta = 24, .cutoff = "3308722450212110699485634768279851414263248443603515625" }, // 302231454903657293676544
423 .{ .delta = 24, .cutoff = "16543612251060553497428173841399257071316242218017578125" }, // 604462909807314587353088
424 .{ .delta = 25, .cutoff = "82718061255302767487140869206996285356581211090087890625" }, // 1208925819614629174706176
425 .{ .delta = 25, .cutoff = "413590306276513837435704346034981426782906055450439453125" }, // 2417851639229258349412352
426 .{ .delta = 25, .cutoff = "2067951531382569187178521730174907133914530277252197265625" }, // 4835703278458516698824704
427 .{ .delta = 25, .cutoff = "10339757656912845935892608650874535669572651386260986328125" }, // 9671406556917033397649408
428 .{ .delta = 26, .cutoff = "51698788284564229679463043254372678347863256931304931640625" }, // 19342813113834066795298816
429 .{ .delta = 26, .cutoff = "258493941422821148397315216271863391739316284656524658203125" }, // 38685626227668133590597632
430 .{ .delta = 26, .cutoff = "1292469707114105741986576081359316958696581423282623291015625" }, // 77371252455336267181195264
431 .{ .delta = 27, .cutoff = "6462348535570528709932880406796584793482907116413116455078125" }, // 154742504910672534362390528
432 .{ .delta = 27, .cutoff = "32311742677852643549664402033982923967414535582065582275390625" }, // 309485009821345068724781056
433 .{ .delta = 27, .cutoff = "161558713389263217748322010169914619837072677910327911376953125" }, // 618970019642690137449562112
434 .{ .delta = 28, .cutoff = "807793566946316088741610050849573099185363389551639556884765625" }, // 1237940039285380274899124224
435 .{ .delta = 28, .cutoff = "4038967834731580443708050254247865495926816947758197784423828125" }, // 2475880078570760549798248448
436 .{ .delta = 28, .cutoff = "20194839173657902218540251271239327479634084738790988922119140625" }, // 4951760157141521099596496896
437 .{ .delta = 28, .cutoff = "100974195868289511092701256356196637398170423693954944610595703125" }, // 9903520314283042199192993792
438 .{ .delta = 29, .cutoff = "504870979341447555463506281780983186990852118469774723052978515625" }, // 19807040628566084398385987584
439 .{ .delta = 29, .cutoff = "2524354896707237777317531408904915934954260592348873615264892578125" }, // 39614081257132168796771975168
440 .{ .delta = 29, .cutoff = "12621774483536188886587657044524579674771302961744368076324462890625" }, // 79228162514264337593543950336
441 .{ .delta = 30, .cutoff = "63108872417680944432938285222622898373856514808721840381622314453125" }, // 158456325028528675187087900672
442 .{ .delta = 30, .cutoff = "315544362088404722164691426113114491869282574043609201908111572265625" }, // 316912650057057350374175801344
443 .{ .delta = 30, .cutoff = "1577721810442023610823457130565572459346412870218046009540557861328125" }, // 633825300114114700748351602688
444 .{ .delta = 31, .cutoff = "7888609052210118054117285652827862296732064351090230047702789306640625" }, // 1267650600228229401496703205376
445 .{ .delta = 31, .cutoff = "39443045261050590270586428264139311483660321755451150238513946533203125" }, // 2535301200456458802993406410752
446 .{ .delta = 31, .cutoff = "197215226305252951352932141320696557418301608777255751192569732666015625" }, // 5070602400912917605986812821504
447 .{ .delta = 32, .cutoff = "986076131526264756764660706603482787091508043886278755962848663330078125" }, // 10141204801825835211973625643008
448 .{ .delta = 32, .cutoff = "4930380657631323783823303533017413935457540219431393779814243316650390625" }, // 20282409603651670423947251286016
449 .{ .delta = 32, .cutoff = "24651903288156618919116517665087069677287701097156968899071216583251953125" }, // 40564819207303340847894502572032
450 .{ .delta = 32, .cutoff = "123259516440783094595582588325435348386438505485784844495356082916259765625" }, // 81129638414606681695789005144064
451 .{ .delta = 33, .cutoff = "616297582203915472977912941627176741932192527428924222476780414581298828125" }, // 162259276829213363391578010288128
452 .{ .delta = 33, .cutoff = "3081487911019577364889564708135883709660962637144621112383902072906494140625" }, // 324518553658426726783156020576256
453 .{ .delta = 33, .cutoff = "15407439555097886824447823540679418548304813185723105561919510364532470703125" }, // 649037107316853453566312041152512
454 .{ .delta = 34, .cutoff = "77037197775489434122239117703397092741524065928615527809597551822662353515625" }, // 1298074214633706907132624082305024
455 .{ .delta = 34, .cutoff = "385185988877447170611195588516985463707620329643077639047987759113311767578125" }, // 2596148429267413814265248164610048
456 .{ .delta = 34, .cutoff = "1925929944387235853055977942584927318538101648215388195239938795566558837890625" }, // 5192296858534827628530496329220096
457 .{ .delta = 35, .cutoff = "9629649721936179265279889712924636592690508241076940976199693977832794189453125" }, // 10384593717069655257060992658440192
458 .{ .delta = 35, .cutoff = "48148248609680896326399448564623182963452541205384704880998469889163970947265625" }, // 20769187434139310514121985316880384
459 .{ .delta = 35, .cutoff = "240741243048404481631997242823115914817262706026923524404992349445819854736328125" }, // 41538374868278621028243970633760768
460 .{ .delta = 35, .cutoff = "1203706215242022408159986214115579574086313530134617622024961747229099273681640625" }, // 83076749736557242056487941267521536
461 .{ .delta = 36, .cutoff = "6018531076210112040799931070577897870431567650673088110124808736145496368408203125" }, // 166153499473114484112975882535043072
462 .{ .delta = 36, .cutoff = "30092655381050560203999655352889489352157838253365440550624043680727481842041015625" }, // 332306998946228968225951765070086144
463 .{ .delta = 36, .cutoff = "150463276905252801019998276764447446760789191266827202753120218403637409210205078125" }, // 664613997892457936451903530140172288
464 .{ .delta = 37, .cutoff = "752316384526264005099991383822237233803945956334136013765601092018187046051025390625" }, // 1329227995784915872903807060280344576
465 .{ .delta = 37, .cutoff = "3761581922631320025499956919111186169019729781670680068828005460090935230255126953125" }, // 2658455991569831745807614120560689152
466 .{ .delta = 37, .cutoff = "18807909613156600127499784595555930845098648908353400344140027300454676151275634765625" }, // 5316911983139663491615228241121378304
467 .{ .delta = 38, .cutoff = "94039548065783000637498922977779654225493244541767001720700136502273380756378173828125" }, // 10633823966279326983230456482242756608
468 .{ .delta = 38, .cutoff = "470197740328915003187494614888898271127466222708835008603500682511366903781890869140625" }, // 21267647932558653966460912964485513216
469 .{ .delta = 38, .cutoff = "2350988701644575015937473074444491355637331113544175043017503412556834518909454345703125" }, // 42535295865117307932921825928971026432
470 .{ .delta = 38, .cutoff = "11754943508222875079687365372222456778186655567720875215087517062784172594547271728515625" }, // 85070591730234615865843651857942052864
471 .{ .delta = 39, .cutoff = "58774717541114375398436826861112283890933277838604376075437585313920862972736358642578125" }, // 170141183460469231731687303715884105728
472 };
473
474 std.debug.assert(shift < pow2_to_pow5_table.len);
475 const x = pow2_to_pow5_table[shift];
476
477 // Compare leading digits of current to check if lexicographically less than cutoff.
478 for (x.cutoff, 0..) |p5, i| {
479 if (i >= self.num_digits) {
480 return x.delta - 1;
481 } else if (self.digits[i] == p5 - '0') { // digits are stored as integers
482 continue;
483 } else if (self.digits[i] < p5 - '0') {
484 return x.delta - 1;
485 } else {
486 return x.delta;
487 }
488 return x.delta;
489 }
490 return x.delta;
491 }
492 };
493}