User Tools

Site Tools


8bit log table generator

Logarithm tables are often used in C64 and for much the same reason they were originally invented, that is exploiting the same identities your old slide rule uses for transforming multiplication and division into addition and subtraction:

lg(x*y) = lg(x) + lg(y)
lg(x/y) = lg(x) - lg(y)

Typically they'd be used together with an exponentiation table (to get the approximate result), with the exponent built-in to another table (such as in my atan routine), or on their own for comparison purposes (as for dot products and the like.)

Yet they're also poorly compressible so a generator routine comes in handy. This version is an eight-bit implementation of the classic shift-add algorithm where you repeatedly try to factorize (x²-1)/x² factors out of a normalized number, with the factors' logarithms stored in a pre-calculated table. An alternative would be to use BASIC to get a much smaller, more precise, and frustratingly slow generator. But this seems like a fair tradeoff between size, speed and precision (saving some 145 bytes or so after compression.)

Note that the result is scaled to fit in eight-bits. This can most naturally be viewed a base-two logarithm in 3:5 fixed-point.

table	= $c000		;page aligned

seed	.byte $00,$00
	.byte $02,$05
	.byte $0c,$1f

reduce	pla
	adc seed,y
next	pha
	ldy #5
	sta shift+4

shift	ror shift+4
	sbx #$00
	bcs reduce
	bpl shift

store	sbc #$1f
	sta table
	lsr store+3
	bcc store

enter	dec *+4
	lda #$00
	sta store+3
	asl a
	lda #$00
	bcs next

;	sta table	;do whatever makes most sense for log(0)
base/8bit_logarithm_table_generator_routine.txt · Last modified: 2015-04-17 04:30 (external edit)