From: "Arthur I Schwarz" <Arthur_I_Schwarz@raytheon.com>
To: tej@melbpc.org.au, gcc@gcc.gnu.org
Subject: Re: Algol Front end
Date: Tue, 07 May 2002 16:45:00 -0000 [thread overview]
Message-ID: <OF9D0638EC.40F06B2F-ON88256BB2.007EA2EA@rsc.raytheon.com> (raw)
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
next reply other threads:[~2002-05-07 23:33 UTC|newest]
Thread overview: 20+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-05-07 16:45 Arthur I Schwarz [this message]
-- strict thread matches above, loose matches on Subject: below --
2002-05-14 7:53 Algol front end Robert Dewar
2002-05-14 11:15 ` Trevor Jenkins
2002-05-09 13:44 Algol Front End Gaius Mulley
2002-05-08 12:15 Algol Front end Robert Dewar
2002-05-08 11:47 Arthur I Schwarz
2002-05-08 1:36 BCD [was Re: Algol front end] Bonzini Paolo
2002-05-14 2:52 ` Algol front end Lars Brinkhoff
2002-05-14 7:02 ` Trevor Jenkins
2002-05-07 20:12 Algol Front End Robert Dewar
2002-05-07 19:53 Algol Front end Robert Dewar
2002-05-07 15:15 Robert Dewar
2002-05-07 4:47 Robert Dewar
2002-05-07 13:43 ` Tim Josling
2002-05-07 4:29 Tim Josling
2002-05-06 18:14 Algol Front End Robert Dewar
2002-05-07 6:57 ` Jose E. Marchesi
2002-05-06 16:54 Tony Stratton
2002-05-06 19:23 ` Scott Robert Ladd
2002-05-07 0:47 ` Steven Bosscher
2002-05-07 7:02 ` Paul Koning
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=OF9D0638EC.40F06B2F-ON88256BB2.007EA2EA@rsc.raytheon.com \
--to=arthur_i_schwarz@raytheon.com \
--cc=gcc@gcc.gnu.org \
--cc=tej@melbpc.org.au \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).