Arbitrary-Precision Decimal

Track: Data consistency. 8 stages. Languages: Go, Python, JavaScript, Rust.

Money breaks in small ways. A total is off by one cent, a refund rounds the wrong way, a number too big for 64 bits wraps around and turns negative. Your job is to build an exact decimal number type that never does any of this. It reads numbers from text, does math with no rounding errors at all, and rounds only when you ask, in the way you ask. Implement Parse(text), String(), Add, Sub, Mul, Cmp, Round(scale, mode) and Div(other, scale, mode) using your language's names. Every number has a scale: the count of digits after the point. 1.50 has scale 2. The scale is part of how a number prints, but never part of its value. Do not store numbers as floating point. Do not use a ready-made decimal or fraction type, such as Python's decimal module or fractions.Fraction, or a number crate in Rust. Whole-number types from the standard library are fine. For help with the ideas, read the notes.

Where it is used

A shop that adds prices as floats can charge a customer one cent too much or too little. Across millions of orders, the books stop adding up. That is the drift this challenge tests.

Stages

dc1: Read and print numbers (easy)

The fault: text from users and files that a program reads wrongly or accepts when it should not. Parse accepts an optional + or -, one or more digits, then optionally a point and one or more digits, then optionally e or E, an optional sign and one or more digits. Nothing else is a number: not "", .5, 5., 1,000.00, 1_000, 1, 0x10 or NaN. Only 0 to 9 count as digits. The exponent must be between -1000 and 1000, so a short string like 1e99999999 can never ask for a number with millions of digits. String prints the canonical form: a - only for negative numbers, no zeros in front of the first digit (but at least one digit), then a point and exactly scale digits if the scale is above 0. Never an exponent. Zero never has a minus sign. Examples: "007.50" -> 7.50, "+3.25" -> 3.25, "-0.00" -> 0.00, "1e3" -> 1000, "2.5E-3" -> 0.0025, "-1.20e+1" -> -12.0.

The tester will verify: every valid string prints back in exactly the canonical form above, and every invalid string returns an error.

dc2: Add, subtract and multiply exactly (easy)

The fault: floating point drift. In floating point, 0.1 + 0.2 is 0.30000000000000004, and money totals slowly go wrong. Add and Sub are exact and keep the larger scale of the two. Mul is exact and its scale is the two scales added together. Examples: 0.1 + 0.2 -> 0.3, 1.10 + 2.205 -> 3.305, 2.50 - 2.5 -> 0.00, 1.10 * 2.0 -> 2.200.

The tester will verify: sums, differences and products are exact and have the right scale.

dc3: Compare numbers (easy)

The fault: two equal amounts that a program thinks are different, because one was written 1.0 and the other 1.00. Cmp returns -1, 0 or 1 by value. The scale never matters, and neither does the text. Examples: Cmp(1.0, 1.00) -> 0, Cmp(1.5, 1.25) -> 1, Cmp(10, 9) -> 1, Cmp(-0, 0) -> 0.

The tester will verify: every comparison follows the values, including negative numbers and numbers with different scales.

dc4: Round money (medium)

The fault: money rounding. A cent goes the wrong way on negative amounts, or floating point turns 2.675 into 2.67499999... before it rounds. Round(scale, mode) keeps scale digits after the point. A scale at or above the number's own scale just adds zeros. A negative scale rounds to tens, hundreds and so on, and the answer has scale 0. The modes:

A result that rounds to zero prints with no minus sign: Round(-0.004, 2, half_up) -> 0.00.

The tester will verify: each mode rounds every number the right way, including negative numbers, ties, negative scales and results that become zero.

dc5: Round half to even (medium)

The fault: rounding bias. When every tie rounds up, a large set of payments adds up to more than it should. Banks round ties to the even neighbour to cancel this out.

2.5 -> 2, 3.5 -> 4, -2.5 -> -2, 0.125 at scale 2 -> 0.12. A tie is only a tie when every dropped digit after the first 5 is zero. 0.1251 at scale 2 -> 0.13.

The tester will verify: half_even rounds ties to the even neighbour and rounds every non-tie to the nearest value, at positive and negative scales.

dc6: Divide to a set number of digits (medium-hard)

The fault: division precision. 100 / 3 never ends. Rounding it twice, or with too few digits, moves a cent when a bill is split. Div(other, scale, mode) returns the exact quotient rounded once, to scale digits after the point, with mode. The scale is never negative here. Dividing by zero (0, 0.00 or any other zero) returns an error. A quotient that rounds to zero prints with no minus sign: Div(-1, 300, 2, down) -> 0.00. Examples: Div(2, 3, 4, half_up) -> 0.6667, Div(100, 3, 2, half_up) -> 33.33, Div(1001, 8000, 2, half_even) -> 0.13.

The tester will verify: every quotient is the exact answer rounded once with the given mode, and division by zero returns an error.

dc7: Very large numbers (hard)

The fault: overflow. A number that does not fit in 64 bits wraps around without a warning, and a large balance turns negative. Numbers here can have dozens of digits before or after the point, and exponents up to 1000. Every method from the stages above must stay exact. This stage also runs a long mix of every method on random numbers. Example: 9223372036854775807 + 1 -> 9223372036854775808.

The tester will verify: every answer stays exact for numbers far larger than 64 bits, across a long mix of every method.

dc8: Make the math fast (hard)

Add, multiply, subtract, round and divide, over and over on numbers with up to about 25 digits. Keep every answer correct.

The tester will verify: your answers are correct and your code takes at most 1.5 times as long as our solution in the same language.

Read the Arbitrary-Precision Decimal notes in the wiki