Re: Immediate doubles (up to 2^256) and rationals coming to Guile 3

[Mark H Weaver]

Mark H Weaver <address@hidden> writes:

> Here's the format of fixrats on 64-bit systems:
>
>   Srrrrrrxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0111
>   |\____/\___________________________________________________/\__/
>   |  |                          |                              |
>   | rank (6 bits)             data (53 bits)                  tag
>  sign

I've since thought of another way to represent fixrats, which allow
simpler packing and unpacking operations, although it would also mean
sacrificing one bit of precision:

   rrrrrrxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxS00111
   \____/\__________________________________________________/|\___/
     |                          |                            |  |
    rank (6 bits)             data (52 bits)              sign  tag

In this new representation, the positions of the numerator and
denominator are swapped.  Now, the numerator occupies the
most-significant data bits (with its most-significant bit removed), and
the denominator occupies the lowest data bits.  The 6-bit rank field is
now 1 less than the integer-length of the numerator, i.e. the rank is
equal to the number of data bits allocated to the numerator.

This allows for an elegant packing operation:

  if (SCM_I_INUMP (numerator) && SCM_I_INUMP (denominator))
    {
      union { double f; uint64_t u; } u;
      u.f  = SCM_I_INUM (numerator);
      u.u += SCM_I_INUM (denominator);
      if ((scm_t_inum) u.f == SCM_I_INUM (numerator))
        {
          u.u += 0xc010000000000000;
          u.u = (u.u << 6) | (u.u >> 58);
          if ((u.u & 0x1f) == 0)
            return SCM_PACK (u.u | scm_fixrat_tag);
        }
    }

We start by converting the numerator into an IEEE double.  We then use
unsigned integer addition to add the denominator to the 64-bit
representation of that double.  We now check that this new IEEE double
has integer part equal to the numerator.  If it doesn't, this indicates
either that the numerator is too large to be represented exactly, or
that the denominator is too large to fit in the remaining bits.

The only thing that remains to be done at this point is to rotate left 6
bits, so that the 5 highest exponent bits become the lowest 5 bits,
where the fixrat tag will go, and to add a value which adjusts the IEEE
biased exponent field to be 0 when the numerator is 1 or -1.

In the code above, I make one final check to make sure the low 5 bits
are zeroes, before applying the 5-bit tag.  However, it's possible that
this final test might be safely omitted.  I'll need to take a careful
look at that.

On 32-bit systems, we can use the same approach, but using IEEE singles
(C floats) instead of doubles, and with a 3-bit tag.  This would allow
fixrats that can be written with 24 binary digits or less.

I went ahead and implemented this, and it is _marginally_ faster than
the earlier version, but not as much as I hoped for.  So, I'm not yet
sure whether to make the switch, but I wanted to post about it anyway.

       Mark