Xref: utzoo comp.graphics:3952 comp.windows.x:6906
Path: utzoo!attcan!uunet!peregrine!elroy!ames!ucsd!orion.cf.uci.edu!paris.ics.uci.edu!venera.isi.edu!raveling
From: raveling@vaxb.isi.edu (Paul Raveling)
Newsgroups: comp.graphics,comp.windows.x
Subject: Re: Luminance from RGB
Message-ID: <7123@venera.isi.edu>
Date: 21 Dec 88 18:52:44 GMT
References: <8241@pasteur.Berkeley.EDU> <518@midgard.Midgard.MN.ORG> <16929@onfcanim.UUCP> <7086@venera.isi.edu> <16960@onfcanim.UUCP>
Sender: news@venera.isi.edu
Reply-To: raveling@vaxb.isi.edu (Paul Raveling)
Organization: USC-Information Sciences Institute
Lines: 72


	BTW, in case it wasn't clear my preceding response was
	suggesting that the "shifty logic" and table lookup with
	interpolation alternatives are more appropriate when the
	function being implemented has a large domain.  Direct
	table lookup is best when the domain is relatively small,
	and I agree that it's the best technique for sheer speed.

	A case where direct table lookup isn't practical is any of
	a few image processing utilities we have.  They examine
	a 5x5 square of pixels with 24 bits of color per pixel
	to determine a new color for the center pixel.  I'd love to
	use direct table lookup for this, but 25*2**24 bytes is a
	tough table to handle.

In article <16960@onfcanim.UUCP> dave@onfcanim.UUCP (Dave Martindale) writes:
>
>Is that a factor of 14 speed improvement over table lookup?  Or a
>factor of 14 improvement over code that contained multiply or divide in
>the inner loop?  A comparison against table lookup is what matters.
>What processor was this on?

	This was several years ago; I believe the algorithm was
	an integer square root function, the processor definitely
	was either an 8088 or an 80286 on an IBM PC.  Since the
	function's domain was unsigned 16-bit integers and the PC's
	memory was quite limited, direct table lookup would have
	been impractical, even though it certainly would be much
	faster.

	I must admit that the factor of 14 is exceptional because of
	the 80x86 processor architecture;  going into assembly language
	allowed carefully recoding some branching logic that produced
	excessive queue flushes, which are a major time waster in this
	family of processors.  Of course a direct table lookup would
	eliminate this problem.


	Note also that there are two different types of table lookup
	to consider:  Direct table lookup and searching.  The variant
	I mentioned in connection with real time avionics software
	used tables containing both x and y values (as in y = f(x) --
	not screen coordinates) to handle continuous functions of
	real numbers.  It did a binary search to find the nearest
	x values to the argument, then used linear interpolation
	to derive the corresponding y value.  In order to support
	the required accuracy most tables contained around 6-10 entries;
	the shortest I can recall was 2 entries, longest about 50.
	The version of the B-1B CADC that I worked on used sets of
	these tables to implement up to 5-dimensional linear interpolation.
	
	This approach is VERY fast for a large class of functions;
	with a mean search requiring something like 3 lookups and
	only simple math, it's faster than computing for lots of things
	with large domains or complex [not simple] equations.  It's
	also good for supporting empirically derived functions, such as
	error correction for the static pressure source on military aircraft;
	this tends to be a bit bizarre in the transonic regime near mach 1.

	BTW, a necessary aid for building that sort of table is a
	utility to do curve fits, then extract a set of (x,y) points
	which keep error less than a given accuracy requirement when
	using linear interpolation between these points.

	Bottom line:  By all means use direct table lookup where it's
	feasible; but don't forget there are a couple other approaches
	that can still save time.


---------------------
Paul Raveling
Raveling@vaxb.isi.edu