Xref: utzoo comp.lang.misc:3502 comp.arch:11479
Path: utzoo!attcan!uunet!cs.utexas.edu!uwm.edu!gem.mps.ohio-state.edu!apple!usc!henry.jpl.nasa.gov!elroy.jpl.nasa.gov!ucla-cs!math.ucla.edu!sonia!pmontgom
From: pmontgom@sonia.math.ucla.edu (Peter Montgomery)
Newsgroups: comp.lang.misc,comp.arch
Subject: Re: Fast conversions, another urban myth?
Message-ID: <1741@sunset.MATH.UCLA.EDU>
Date: 22 Sep 89 20:36:00 GMT
References: <832@dms.UUCP> <688@UALTAVM.BITNET> <9dAz02zs58y201@amdahl.uts.amdahl.com> <27935@winchester.mips.COM> <3902@yunexus.UUCP>
Sender: news@MATH.UCLA.EDU
Reply-To: pmontgom@math.ucla.edu (Peter Montgomery)
Organization: UCLA Mathematics Department
Lines: 69

In article <3902@yunexus.UUCP> davecb@yunexus.UUCP (David Collier-Brown) writes:
>mash@mips.COM (John Mashey) writes:
>  But the ICL did ascii (well, excess-3) arithmetic because it was
>easy, not because it ran COBOL (it did not), and the CISC had both
>conversion and ascii-arithmetic instructions...  Which means that
>these techniques were not necessarily backed up by evidence.
>
>  Who has evidence?  And how "easy" is, for example,
>	word *add(word *,word*); /* A "word" is 2 ascii characters. */
>on a given RISC machine?
>

	Let W1 and W2 be two words containing decimal numbers in ASCII.
I assume that W1, W2 contain only digits (no signs, decimal points, 
or blanks) and that the less significant ASCII digit
is stored in the less significant binary position.  Recall the ASCII
digits are 0x30 hex (= 48 decimal) to 0x39 (= 57).

	We want to form (cnew, Wsum) = W1 + W2 + cold where cold, cnew 
are binary carries (0 or 1).  A first algorithm could resemble:

	W3 = W1 + W2 + cold - 0x3030;
	if ((W3 & 0x00FF) > 0x0039)
		W3 = W3 + (0x0100 - 0x000A);  /* Carry ones to tens */
	if ((W3 & 0xFF00) > 0x3900) {
		W3 = W3 - 0x0A00;
		cnew = 1;		    /* Carry tens to hundreds */	
	} else { 
		cnew = 0;
	}

If no (decimal) carries during the ASCII add, then the first
estimate for W3 will be correct.  The above algorithm separately checks
each byte in W3 for validity, generating a carry if needed.
We can avoid the IFs by checking all the places at once,
but must be prepared for carry propagation
(e.g., 434 + 168 = 602; the carry from the units digits
affects the hundreds digit).  Here is a more sophisticated
algorithm, which adds two 4-byte ASCII strings (32-bits each), 
producing sum and carry:

	T = W1 + W2 + cold - 0x30303030;
	Tc = (0x39393939 - T) & 0x80808080;
			/* Identify where carries generated */
	W3 = T + (256 - 10)*(Tc >> 7);
	cnew = Tc >> 31;

This code uses 5 integer additions/subtractions, 2 shifts, 1 AND, 
1 integer multiply.  If your RISC architecture lacks an integer 
multiply (shame!), then use (note four adjacent bits will be set
in Tc wherever a carry is generated, and 256 - 10 = 16*15 + 16*3/8):

	T = W1 + W2 + cold - 0x30303030;
	Tc = (0x39393939 - T) & 0xF0F0F0F0;
	W3 = T + Tc + ((Tc & 0x30303030) >> 3);
	cnew = Tc >> 31;

	If the ASCII digits are stored in a string,
this algorithm requires you be able to convert a four-character
string to a 32-bit binary number and vice versa.
Just yesterday, I wanted this operation in order to use
the system hostname as part of the initial seed for a random number
generator, but I didn't know how to do it easily in C or FORTRAN 77
(the TRANSFER intrinsic function in the FORTRAN 8x draft may do it).
How many higher level languages make this primitive operation available?

--------
        Peter Montgomery
        pmontgom@MATH.UCLA.EDU