Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site harvard.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!godot!harvard!breuel
From: breuel@harvard.ARPA (Thomas M. Breuel)
Newsgroups: net.lang.c
Subject: Why 'C' does not need BCD...
Message-ID: <166@harvard.ARPA>
Date: Sun, 25-Nov-84 00:50:50 EST
Article-I.D.: harvard.166
Posted: Sun Nov 25 00:50:50 1984
Date-Received: Mon, 26-Nov-84 02:02:22 EST
Distribution: net
Organization: Harvard University
Lines: 124

|A Fujitsu Eagle transfers data at about 1.8 megabytes per second.  Many
|mainframe disks are even faster.  If you are storing 6-byte (12-digit) BCD
|and are adding two streams, you are transferring 18 bytes per operation.
|Assuming you double-buffer but have only one controller, this is 100K
|operations per second.  You thus have to convert to binary, add, and
|convert back to BCD in approximately 10 microseconds.

This is irrelevant (sorry). You don't 'have to convert to binary, add,
and convert back to BCD in approximately 10 microseconds', since you
don't store your data in BCD on the disk in the first place if you are
working with binary numbers.

The only time when you have to convert to BCD is when you output data
in human readable form. Since output in human readable form is handled
by slow devices, like line printers, laser printers, or microfilm
printers, it hardly matters how quickly you can perform the
conversion.  (Indeed, for laser printers, most of the work is involved
in generating the bit image). In addition, the amount of data that you
present in human readable form is very likely to be only a tiny
fraction of the amount of data you are doing arithmetic with. (This is
due to the limited performance of human beings).

Apart from the above points, there is most likely an operating system
in between your nice, fast disk drives and your ('C') program. Indeed,
this operating system is likely to be UN*X. Since (if I recall
correctly) the calling sequence on the VAX takes more than 10us, and
since UN*X loves to call many functions and to do a lot of copying, it
again hardly matters whether your arithmetic takes 10us or 20us or
100us.

Even if you, as I once did on an IBM360, program your machine in
assembly language and access the disk drives directly (i.e. with
minimum overhead), you would still have to do seeks ('double buffering'
doesn't really help you), either every now-and-then (if you are lucky
enough to have three disk drives), or for every operation (if you are
not lucky enough).

The slowness of disk I/O is not related to transfer rates (1.8 Mbyte/s
is almost as fast as dynamic ram chips), but to seek times and
scheduling problems (DMA, processor interrupt service, ...).

|                                               But I have never seen an
|algorithm for converting binary to decimal without doing divisions.

If you keep on reading, you'll find an algorithm that converts binary
to BCD without division.

|And it's actually worse than that, because a mainframe that powerful
|typically has several controllers so that the full 1.8 megabyte output data
|rate could be maintained if the CPU could keep up with it.

As mentioned above, disk transfer rate is not the limiting factor.

|[somebody else mentioned something like:] 5 digit signed BCD takes
|3 bytes, whereas for a binary representation you have to go from
|16 to 32 bits.

You can do your arithmetic with 32 bits and store data as 24 bits
on disk (that's what UN*X used to do on PDP-11's).

To summarise: binary arithmetic is faster than BCD arithmetic,
binary->ASCII is slower than BCD->ASCII. Binary numbers are equally or
more compact than BCD numbers. Binary numbers are equally readable,
even for accountants, given that your debugger does not only support hex
dumps (BTW, have you ever tried to read BCD in an octal dump?).

WRT 'C', all of this is irrelevant. If you want to use BCD in 'C', write
your own assembly language subroutines, the same way that you write
your own string routines. You then even have the choice between packed
and unpacked BCD, so that your BCD routines can even *be* your string
routines :-). 'C' as the language to write UN*X and UN*X utilities in,
surely does not need BCD.

Sorry for this somewhat lengthy response. I hope it will by {my,the}
last one on the subject.

						Thomas.
						(breuel@harvard)

PS: if you are worried about efficiency in your BCD package, why don't
you just write an sed-script, which replaces all 'calls' to BCD
routines by in-line assembly language. That's how the kernel handles
'bcopy' and friends on the VAX.

PPS: the same sed-script can even be applied to PDP-11 'C' compiler
output without harm, as the 2.9BSD distribution clearly demonstrates --
PDP-11 code does not contain 'calls'...

-----------------------------------------------------------------------

; As promised: routine to convert binary to BCD without division.

; You can write this routine for any machine with BCD arithmetic.
; I can write it only for the 6502, 68000, 8085, IBM360 (:-)), or
; VAX. Of those, I think it looks neatest on the 6502.

; There are likely to be some misspelled mnemonics in here --
; I haven't written 6502 assembly language in 2 years.

; Entry: binary number between 0 and 99 in accumulator
; Exit: BCD number in accumulator (unpack to get ASCII)

	php		; save previous processor mode
	sed		; enable bcd arithmetic
	ldx #8		; #bits to convert
	ldy #0		; clear result
	sty r		
loop:
	asl a		; test msb
	tay		; save binary number
	php		; save result of msb test
	lda r		; multiply bcd by 2
	add r		
	plp		; add one if msb was set
	bcc skip	
	add #1		
skip:
	sta r		; update bcd result
	tya		; restore binary number
	dex		
	bra loop	
	lda r		; return result in accumulator
	plp		; restore processor status
	rts