Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!decwrl!sgi!rpw3@rigden.wpd.sgi.com
From: rpw3@rigden.wpd.sgi.com (Rob Warnock)
Newsgroups: comp.compression
Subject: Re: Sound compression
Keywords: sound compression
Message-ID: <105539@sgi.sgi.com>
Date: 22 May 91 06:19:55 GMT
References: <16198@helios.TAMU.EDU> <19524@crdgw1.crd.ge.com> <104045@sgi.sgi.com> <91May15.140250edt.750@neuron.ai.toronto.edu>
Sender: guest@sgi.sgi.com
Reply-To: rpw3@sgi.com (Rob Warnock)
Organization: Silicon Graphics, Inc., Mountain View, CA
Lines: 46

In article <91May15.140250edt.750@neuron.ai.toronto.edu>
radford@ai.toronto.edu (Radford Neal) writes:
+---------------
| In article <104045@sgi.sgi.com> rpw3@sgi.com (Rob Warnock) writes:
| >...paper... which proved that there is no closed functional form without
| >conditionals which will compute "the highest-order one bit".
| 
| Actually, you should be able to quickly find the position of the 
| highest-order one bit of an integer on most machines with floating-point
| instructions by jamming the integer into the mantissa part of a floating-
| point number, along with some appropriate exponent, and then performing
| some operation that will induce the floating-point processor to do a
| normalization.
+---------------

I wasn't arguing against there being practical methods, only noting that
the paper said there are no "closed functional forms without conditionals".
Floating-point normalization is either done iteratively [which requires a
termination test, ie., a "conditional", albeit in the f.p. microcode] or is
done with a "flash" normalizer, i.e., a priority encoder [for which there
is no traditional closed-form mathematical operator!]. In either case, the
paper's results are not contradicted.

Your method is cute; I like it. Yet it seems useful only on machines which
have a "flash" f.p. normalizer *and* don't provide an integer priority-encoder
operation. In my experience, the integer priority-encoder (JFFO, FFS, or CLZ
instruction) is often provided on non-f.p. machines, but rarely the reverse
[since, given the "flash" f.p. normalizer in the datapath, the prio-encoder
operation is "free"].

Let's re-open the question to others: What *other* fast, practical methods
are there to find the "leftmost bit" a.k.a. "binary logarithm" of an integer,
besides:

1. Table-lookup ["small" values only]
2. Brute-force iteration [incl. doing log_2(wordsize) "tree" or "comb" steps]
3. Hardware priority encoder instruction [JFFO, FFS, CLZ, or equiv.]
4. Floating-point normalizer [Neal's method]

It seems that the binary log ought to be a useful element of many kinds of
lossy compression, not just audio...


-Rob