Re: ratio implementation

[Dirk Herrmann]

Marius Vollmer wrote:

>Bill Schottstaedt <address@hidden> writes:
>
>>There is an implementation of ratios for Guile (based on CVS version
>>of 27-Jul-03) at ccrma-ftp.stanford.edu:/pub/Lisp/gratio.tar.gz.
>>Rather than send a huge diff, I placed the new versions of the changed
>>files (all from the libguile directory) in the tarball along with
>>*.diff showing the changes.
>
>
>Good work, thanks!  However, I don't think we should restrict us to
>longs as the numerator/denominator, we should use fixnums and bignums.
>Your patch is a very good basis for this and it should be quite
>straightforward to make it use SCM integers as the
>numerator/denominator.
>
>That is, instead of using "long", I'd say we simply use "SCM" and
>instead of "+", "==", etc, we use use "scm_sum", "scm_num_eq_p", etc.
>Also, instead of mallocing scm_t_ratio, we can use double cells, which
>should be more efficient.
>
>Any takers?

Hello together,

the last couple of days I have been looking closely at Guile's 
typecodes, and
I figured that we could improve the treating of numbers in a general way.  I
have to admit that I have not looked into Rob's code, thus my 
observations and
suggestions are based on the current CVS solution only.

Currently, fixnums are realized as immediates, while all other number types
(bignums, reals and complexs) are realized as smobs.  On the other hand, 
there
are at the moment two unused tc7 codes.

My suggestion is to use one of the free tc7 codes to represent a 'number'
type.  First, it would simplify parts of the smob code and free three smob
numbers.  Second, it would make type dispatch for numbers a little faster at
some places.  Third, in contrast to smobs which use 16 type code bits, a
smaller number of typecode bits may be required, making it possible to store
more information in the SCM_CELL_TYPE mask.

In addition to the tc7 bits, additional bits can be used for subtyping the
suggested scm_tc7_number type.  The following subtypes need to be provided:

- bignums, holding a pointer to a gmp structure
- doubles, holding a 64 bit double precision number
- fraction, holding two SCM values for nominator and denominator
- complex, holding two SCM values for real and imaginary part

The following subtypes can be provided additionally to support certain
features:

- fixnums, holding an inum SCM value.  This type can be provided to allow
  inexact fixnum values.
- floats, holding a 32 bit single precision number
- further floating point representations like mpfr numbers
- fixed point numbers
- ...

For example, the four bits above the tc7 bits could be defined as follows
(still using only 11 bits for type information, compared to 16 bits with the
current solution):

xsss

with x indicating the exactness, and sss indicating the subtype.  The 
subtypes
could, for example, be assigned as follows (certainly, only the mandatory
types listed above would need to be supported):

000 - Fixnum (inum in cell word #2), optional to allow inexact fixnums
001 - Bignum (gmp struct ptr in cell word #2), typically exact, optionally
      inexact to allow inexact bignums.
010 - fraction (all combinations of fixnums and bignums stored as SCM
      values in double cell words #2 #3), typically exact, optionally 
inexact
      if inexact fixnums or inexact bignums are to be supported.
011 - fixed point number (implementation not clear yet, just listed for
      completeness), exact or inexact
100 - float (32 bit float in cell word #2), always inexact
101 - double (64 bit float in double cell words #2 #3), always inexact
110 - mpfr (gmp struct ptr in cell word #2), always inexact
111 - complex, stored as SCM values in double cell words #2 #3, possible
      combinations are (double double) - always inexact, (float, float) -
      always inexact, (fixedpoint fixedpoint) - inexact or exact,
      (mpfr mpfr) - always inexact, or all combinations of fixnums, bignums
      and fractions - typically exact, optionally inexact

Since fractions and complex numbers are represented in terms of pairs of 
other
numbers, operations on fractions and complex numbers can be delegated to
operations that work on the remaining, more basic representations.

The limitations on the possible combinations for real and imaginary part of
complex numbers has the background that it does not seem to make sense to me
to represent real and imaginary part with different precision.

Even if no inexact fixnums, bignums and rationals are to be supported it 
does
still make sense to provide the exactness bit for faster operation of the
exact? predicate.


I had been planning, as a first step, to simply allocate that scm_tc7_number
typecode and turn bignums, doubles and complex numbers into subtypes of that
type.  I had not originally intended to add rationals in the same run.  
Maybe
I could help to prepare their addition.  However, there are still a 
number of
changes with respect to separating memoization and execution in the 
evaluator,
so it may take some time until I start to work on it.

Best regards
Dirk Herrmann