This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Algol Front end



  If anyone does have any good information on optimising packed decimal
code
  (other than Knuth's routines for converting to and from decimal) I would
be
  interested to hear about it.

Don't know much about the 'good' but here is a tradeoff between space and
time.

For Addition:

    When treated as an integer, the sum of any two decimal numbers, [0..9],
    is less than or equal to 18, hence, the sum adds at most 1-bit to the
    resultant when both numbers are treated as a binary. Using a carry,
from
    the preceding step, adds one number, but not one digit, to the
resultant.

    Using this result, we could:

    int sum[16] = { 0x0000, 0x0001, 0x0002, 0x0003, 0x0004
                  , 0x0005, 0x0006, 0x0007, 0x0008, 0x0009
                  , 0x0100, 0x0101, 0x0102, 0x0103, 0x0104
                  , 0x0105, 0x0106, 0x0107, 0x0108, 0x0109 };

    int value = sum[pack1 + pack2];

    int value = sum[pack1 + pack2 + carry]; if there is a carry

    Being inefficient (at two bytes) a 512 term array could handle
    adding 2-digit decimal numbers, and cutting down the number of
    required accesses.

    The change is:

    long sum[308] = { ... };   // where 'long' is at least 32-bits

For Multiplication.
    Multiplication can be handled in a similar fashion with two bits added
    to the result (9 * 9 = 81 & log(2) 81 = 6), with a carry of at most '9'
    from the preceding multiplication.

    Division and subtraction can be handled in a similar fashion.

I have forgotten how negative numbers are treated and so, the above
arguments
may have to be tweaked.

I don't know the timing and haven't seen the algorithms and results
mentioned. The above argument changes a computation from an algorithm to a
table lookup. If the table lookup is faster than the algorithm, it wins,
otherwise, it loses. It probably is unusable for putting into a toaster but
may be suitable for your use.

art




Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]