Re: mixed type operations in Octave

[Jaroslav Hajek]

On Tue, Sep 9, 2008 at 7:42 PM, John W. Eaton <address@hidden> wrote:
> On  9-Sep-2008, Jaroslav Hajek wrote:
>
> | On Tue, Sep 9, 2008 at 4:24 AM, John W. Eaton <address@hidden> wrote:
> | > On  8-Sep-2008, Jaroslav Hajek wrote:
> | >
> | > | I'm working on a patch to improve integer arithmetics in Octave.
> | >
> | > What do you mean by improve?  Make them faster?  I think that's OK,
> | > but is it really worth the effort?
> | >
> | I mean:
> | 1. Provide int64 arithmetics.
> | 2. Make them faster (while, of course, preserving the saturation
> | semantics and the warnings). Use integer arithmetics where possible.
> | The primary target for speed are the homogeneous operations.
> | 3. Complete the warnings. I don't get why Matlab possibly gripes at
> | conversion int32(0.5) but always accepts int32(1) + 0.5 silently. I
> | want to make Octave possibly warn here.
> | 4. Restructure the classes in oct-inttypes.h somewhat, replace macros
> | with templates where appropriate, reduce code duplication.
>
> OK.  I'd suggest attacking each of these separately.  Maybe do the
> cleanup of oct-inttypes.h first.

A good suggestion. The problem is that I already started doing
everything together; right now, I'm not even particularly sure how to
split it apart. But I'll have a look at it.

>
> How do you propose to avoid the conversion to double and still provide
> the saturation semantics?  Do the operation in the next widest integer
> type?  Something else?
>

Addition and subtraction can be done using just the native operations.
For instance, addition can be done like this:

T add (T x, T y)
{
  T u;
   if (x >= 0)
     {
        u = std::numeric_limits<T>::max () - x;
        if (y > u)
           ftruncate = true;
        else
           u = y;
      }
    else
     {
        u = std::numeric_limits<T>::min () - x;
        if (y < u)
           ftruncate = true;
        else
           u = y;
      }
    return x + u;
}

or like this (uses the bit properties of two's complement signed int
representation,
is significantly faster)

T add (T x, T y)
{
      T u = x + y;
      T ux = u ^ x, uy = u ^ y;
      if ((ux & uy) < 0)
        {
          u = std::numeric_limits<T>::max () + signbit (~u);
          ftruncate = true;
        }
      return u;
}

Both versions seem to be faster than going via double, the current
implementation.
While version 1 is million percent portable, version 2 may not be if
the target machine does not use two's complement signed integers (i.e.
the signed arithmetic is identical to unsigned). I don't know if there
are any such architectures we actually care of that do not support
this. In fact, even the autoconf manual says that assuming two's
complement is, for practical purposes, safe.
OTOH, on most, if not all, architectures, version 2 will work and is
still considerably faster than version 1.

Multiplication is best done by promoting to a wider integer type,
multiplying, and fit-to-range. Again, avoiding the int-real
conversions is a performance win. If 128-bit int is not available,
64-bit multiplication can be done by using bit shifts.

Division can be done using integer division.

> | Of course, it's Matlab versus common sense again. But I didn't want to
> | go any farther than making 64-bit arithmetics work, and I think that
> | most of the behaviour is already clear in Matlab, just not
> | implemented. The problem is just that the obvious way of implementing
> | int + double does not work well for int64.
>
> | I am all for simply not providing mixed integer ops. It's just that
> | they are defined in oct-inttypes.h, and so I thought they might be
> | used somewhere.
>
> OK.  I think the templates could easily be rewritten so that they only
> work when both operands have the same type.
>
> | The easiest solution is to just leave the templates there using the
> | current approach, and not care that they don't work for octave_int64.
> | Or put them away, and if they happen to be used anywhere in the
> | sources (I didn't check yet), then replace the usage with an explicit
> | conversion. I'll rather do this, if you're fine with it, as it seems
> | nasty to leave broken code around.
>
> How is the code broken?
>
> | The mixed-type comparisons will of
> | course remain, as there is no problem with these.
> |
> | The question is what to do with int64 OP double. Options I see:
> |
> | 1. leave the current (broken) way. Losing some digits with high numbers.
>
> Is this what you mean when you say broken above, that the templates
> won't work properly for 64-bit ints?

yes.

> OK, if we can't come up with a
> portable way to implement 64-bit operations on all systems, then I
> think we will need specializations for the 64-bit types that throw
> errors.
>
> | 2. forbid it, and wait what Matlab will do (but I think they're bound
> | to do something close to 3)
> | 3. use long double if possible (x86), and if not, emulate.
> |
> | which one do you prefer? Now that I think of it, 3 is probably the
> | best in terms of completeness as well as consistency with Matlab,
> | though likely the most laborious.
>
> I think 3 would be fine, if you want to tackle it.  I just don't think
> of it as a high priority project.
>

Probably not, given that current Matlab does not bother with 64-bit
arithmetics. But I think it is a useful thing to have. And the
performance boosts for int32 and lower arithmetics may make it more
usable for real applications, DSP for example.

>
> jwe
>



-- 
RNDr. Jaroslav Hajek
computing expert
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz