Accumulate the prefix by Horner's method in base two. The loop invariant, in exact arithmetic, is that
digit-'0' converts either permitted digit to its numerical value:var i = 0
var integerPart = 0.0
while (i < bin.length && bin(i) != '.') {
integerPart = 2.0 * integerPart + (bin(i) - '0')
i += 1
}i is the number of processed digits before the point andAppending a digit shifts the old positional value by one binary place and adds that digit, which proves preservation. The loop variant is . At exit, i is the binary-point index or the length if no point occurs, and integerPart is the value of the integer prefix. An empty prefix contributes zero. There is one multiplication per processed digit, with no separate powers or repeated divisions. Short-circuit evaluation prevents an out-of-range access when the point is absent.For
Double, this exact-arithmetic invariant describes the intended value; the operational value is the rounded Horner recurrence. Very long prefixes can lose precision or overflow, as discussed in part (g). A fixed-width return type cannot represent every finite binary digit string exactly.Let The loop invariant, under exact arithmetic, isInitially the suffix is empty. Incorporating digit and dividing by two gives exactly the same formula with replaced by . At exit , the result is . The loop variant is when a point exists. If a no-point input is handled by setting
point be the known point index. Work backwards so that each step uses just one division, rather than separately computing positional weights:var j = bin.length - 1
var fractionalPart = 0.0
while (j > point) {
fractionalPart = (fractionalPart + (bin(j) - '0')) / 2.0
j -= 1
}point=bin.length, the loop is skipped and the fractional contribution is zero; is a loop variant covering that convention too. Trailing zeroes and an empty fractional suffix require no special arithmetic. Floating-point rounding qualifies the exact formula for long inputs.Represent zero by one digit. Since The loop invariant is and ; for positive
int_part is nonnegative, a logical right shift is exactly integer division by two:var digits = 1
var scratch = int_part
while (scratch >= 2) {
scratch = scratch >>> 1
digits += 1
}int_part, also . The loop variant is scratch, strictly decreased whenever the guard holds. On exit, a positive input has , yielding . Therefore digits is the required width, including width one for zero. Shifting avoids an explicit multiplication or division in the code. This uses the supplied assumption that dec.toInt really is the mathematical floor; saturating or invalid conversions are not covered by that assumption.Extract low bits and fill the integer positions from right to left:At the start of an iteration, the loop invariant says that positions contain the correct low bits andThe bitwise AND extracts the remainder modulo two; the shift supplies its quotient. These two facts preserve the loop invariant. The loop variant is . The width established in part (c) ensures that
var remaining = int_part
var pos = digits - 1
while (pos >= 0) {
res(pos) = if ((remaining & 1) == 0) '0' else '1'
remaining = remaining >>> 1
pos -= 1
}remaining is zero at exit, so the first digits entries encode the whole integer part. For zero the single entry becomes '0'. There are no explicit multiplications or divisions, and no extra digit array is needed.Generate the fractional bits by repeated doubling, keeping only the unconverted residual:Let and . The loop invariant is , the first fractional digits have been written, and, in exact arithmetic,Doubling exposes the next digit, and subtracting that digit leaves the next residual in . This proves preservation. The loop variant is . The loop fills the whole suffix, even when the residual has become zero; subsequent bits are zero. There is one multiplication per output bit. With fractional positions, the result is truncated, with exact-arithmetic error . An integer has an all-zero suffix. No rounding-up step is performed.
res(digits) = '.'
var fraction = dec - int_part.toDouble
var out = digits + 1
while (out < res.length) {
fraction = 2.0 * fraction
if (fraction >= 1.0) {
res(out) = '1'
fraction -= 1.0
} else res(out) = '0'
out += 1
}Equivalence partitioning divides the input domain into classes expected to exercise the same relevant behavior, then chooses representatives and boundary cases from each class. It is a way to select tests, not a proof that every member of a class must behave identically in a faulty implementation.
Useful classes for this parser include integer-only inputs, a leading point, a trailing point, and digits on both sides; all-zero inputs and inputs containing ones; leading or trailing zeroes; one-digit and longer blocks; and large integer or tiny fractional magnitudes near floating-point rounding, floating-point overflow and floating-point underflow boundaries. For instance, compare
'1', '1.', '.1', '1.1', '0001.1000', and digit strings just beyond the exact integer precision of Double. Empty digit blocks have the zero convention used above. If a surrounding validator rejects an entirely empty representation or a bare point, test those as separate invalid-format classes. Unexpected digits and multiple points are likewise validator tests, since the conversion fragments assume well-formed input. Include representatives with independently calculated positional values, rather than relying only on inverse conversion.The first proposed identity can fail even without numerical error because binary fractions have nonunique textual representations. Leading zeroes, optional points and trailing fractional zeroes are normalized differently by a fixed-width output convention. It also fails if the input has more significant bits than
Double can preserve, more fractional places than the output buffer can hold, an integer part outside the assumed Int range, or a value that overflows or underflows during decoding. Array identity here must mean equal contents: a newly allocated Scala array is a different software object, so use sameElements rather than reference equality for a content test.The second identity fails when the stored fractional precision truncates a nonzero bit; with two fractional places, becomes zero. It can also fail outside the finite nonnegative input and integer-conversion assumptions. Within those assumptions, enough fractional positions to encode the finite
Double exactly can permit the round trip, but an arbitrary fixed small width does not guarantee it. Every finite Double has a finite binary expansion; saying that a decimal-looking Double necessarily has an infinite binary expansion would confuse the represented number with an exact decimal real.The source's introductory example is internally inconsistent: the displayed digit string has value , whereas its shortened character array encodes . The conversion rules above follow the actual input digits. Round-trip testing needs an independent value oracle as well as the two compositions, because two mutually consistent but incorrect routines can conceal each other's errors.
Articles by others on the same topic
There are currently no matching articles.