CODEWITHSUNDEEP
c#floating-point
D.R.
D.R.

Reputation: 21224

Looping through all representable decimals in ascending order

If I take the lower 31 bits of a float (exponent and mantissa) and loop through them one by one, the resulting floats are in ascending order starting from 0, up to float.MaxValue, then to float.PositiveInfinity and then further on to the many different bit patterns of float.NaN.

This nice property doesn't seem to hold for the decimal data type. Is there a way to loop through all representable decimal values (between a lower and an upper bound) in ascending order in a similar way?

Bonus: Is there at quick way to count the possible numbers?

Additional information: It's okay to count 1.0 and 1.00 as two different numbers.

Upvotes: 1

Views: 118

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 223747

The decimal format has a sign bit s, a 96-bit significand f, and an exponent e from 0 to 28, inclusive. The represented value of (s, f, e) is (−1)s • f / 10e.

Define the canonical representation of (s, f, e) to be (s, f • 10n, e+n) for the greatest integer n for which f • 10n < 296 and e ≤ 28. If e is not 28, the canonical significand is in ceiling(296/10), 296−1, inclusive.

We can iterate through the non-negative decimal values in ascending order by:

    Set s = 0, e = 28.
    For f from 0 to 2^96 - 1, inclusive:
        Process (s, f, e) as a decimal value.
    For e from 27 down to 0, inclusive:
        For f from ceiling(2^96 / 10) to 2^96 - 1, inclusive:
            Process (s, f, e) as a decimal value.

We can see this is ascending order since each loop on f starts with a greater represented value than the previous loop ended with. We can see each representable value is included because the value for any canonical representation (s, f, e) appears in the loop on f where e has the value e. We can see no value is duplicated because each representable value is processed just once, in its canonical representation.

To restrict this to particular lower and upper bounds L and U, we can find the canonical representations of L and U. The components of these representations tells us where to start and end f and e. An alternative form of the algorithm may be more suitable for this. Let fL and eL be the e and f of the canonical representation of L, and similarly for fU and eU. Then an algorithm is:

    (0) Set s to 0, f to fL, and e to eL.
    (1) If e ≤ eU and f > fU, stop.
    (2) Process (s, f, e) as a decimal number.
    (3) Set f to f+1.
    (4) If f is less than 2^96, go to (1).
    (5) Set e to e-1 and f to f/10.
    (6) Go to (1).

The extension to negative numbers is obvious.

Upvotes: 1

Related Questions