Re: numerical instability and estimate-probability

[Linus Torvalds <torvalds at transmeta dot com>]

In article <20011116173148.B26573@atrey.karlin.mff.cuni.cz> you write:
>
>Actualy in this case we are speaking about frequencies (for probabilities
>it is just OK to use 0 ... 10000 integers).
>
>The frequencies can get very huge, so only sane workaround wihtout FP
>is IMO only inventing the mantisa/exponent at my own :(

Ehh.. Why do you need a mantissa at all?

You're kidding yourself if you think the frequencies are exact, so why
not just do frequencies with logarithmic operations, and always
represent them as powers-of-two - as a simple integer.

I assume that you never do addition of frequencies anyway (what would
that mean?), so you really only ever multiply frequencies with each
other, no?

In which case a logarithmic expression is by far the most convenient, as
it will turn your existing multiplications into just additions, speeding
the thing up in the process.

And if you select a power-of-two, it's easy enough to do approximations
of the log2() operation for any remaining cases where you _do_ want to
approximate add/sub/whatever. 

There is another major reason for using a log2 representation.  If you
do optimizations, you really don't care whether something is called 100
times or 105 times.  You really _only_ care about "orders of magnitude"
differences.  Ie you really fundamentally should only care about the
logarithm of the frequency _anyway_. 

Let's hear it for orders-of-magnitudes.

		Linus