Looping through all representable decimals in ascending order

Question

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.

Have you read The Jon's answer here? https://stackoverflow.com/questions/3801440/binary-representation-of-a-net-decimal Perhaps it can shed some light. As far as I can understand, it might not be possible, since there are multiple representations for the same number. — Alexandru Clonțea, Sep 22 '18 at 22:05
@AlexandruClonțea: Iterating through all representable values is of course possible. One would skip non-canonical representations (for any desired assignment of canonical). — Eric Postpischil, Sep 23 '18 at 00:15
@EricPostpischil ah.... good point. It might be time to go sleep. Brain slow. Cannot edit my comment this late, and I still think that that post might be useful — Alexandru Clonțea, Sep 23 '18 at 00:22
@AlexandruClonțea: I've read the article, I know how the `decimal` data type looks in memory. Still I haven't found a good way to enumerate or count the representable decimals between two given decimals min and max. — D.R., Sep 23 '18 at 09:19

Eric Postpischil · Accepted Answer · 2018-09-23T14:40:12.773

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 / 10^e.

Define the canonical representation of (s, f, e) to be (s, f • 10ⁿ, e+n) for the greatest integer n for which f • 10ⁿ < 2⁹⁶ and e ≤ 28. If e is not 28, the canonical significand is in ceiling(2⁹⁶/10), 2⁹⁶−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.

Thank you for your time, I'll test it out, but a first "think it through" looks very promising! Would upvote multiple times if possible :) — D.R., Sep 23 '18 at 15:38

Looping through all representable decimals in ascending order

1 Answers1