Tuesday, June 03, 2014

[qznkgfol] Text-coded decimal

Create a library to directly manipulate numbers encoded in decimal as ASCII strings.  Arbitrary precision, do not convert to binary.

Provide only the operations asymptotically faster than radix conversion: input, output, addition, subtraction, comparison.  Maybe multiplication and division by small factors.  No superlinear operations.  This may be enough for many purposes.

We prefer character strings over a similar alternative of doing arithmetic in base 10^9 because of the expectation that I/O will be the dominant operation, so keeping the numbers in string form is worth the inefficiency of arithmetic.

Original motivation was to avoid the DoS attack of causing excessive CPU consumption by presenting large input, triggering expensive radix conversion, on a program which had been implemented robustly to use arbitrary precision arithmetic to avoid integer overflow.

No comments:

Post a Comment