5
$\begingroup$

Floating point representation encodes a binary number using a mantissa $a$ and exponent $b$ according to $(1+a)\cdot 2^b$, where $a$ is an unsigned fractional fixed point number such that $1\le 1+a < 2$ (in decimal form) and $b$ is a signed integer.

Thus for any value $x$ encoded in floating point, we can make an approximation of the logarithm of $x$ from $a$ and $b$.

What would be an efficient algorithm for doing this (ideally as base 2 but I can convert from any base if needed) if we wanted at least 3 bits of fractional accuracy in decimal equivalent of the result?

What would be an efficient approach be for fixed point?

Regarding floating point, RBJ provides a solution using Horner's Method here to compute $f(u)$ through a series, and then estimate the based 2 log using $xf(x-1) \approx \log_2(x)$ and another approximation using the Taylor series here.

$\endgroup$
3
  • 1
    $\begingroup$ Shouldn't that be $(1+a)\cdot 2^b$ ? $\endgroup$
    – Hilmar
    Commented Jul 3, 2023 at 21:12
  • $\begingroup$ Dan, did you see this? or this? $\endgroup$ Commented Jul 3, 2023 at 21:50
  • 1
    $\begingroup$ @robertbristow-johnson I did not and thank you, very nice. I had something in mind which I think improves it-- will try first and give as an initial answer to be improved on-- if it's not better than what you provided I will otherwise delete this as a duplicate. $\endgroup$ Commented Jul 4, 2023 at 13:58

1 Answer 1

7
$\begingroup$

BOTTOM LINE - DOUBLE PRECISION FLOATING POINT

We can make use of the floating point encoding directly to efficiently determine $\log_2$ for the represented number (and as I show at the end provide the result in dB as well). The following algorithm will provide the result within an accuracy of 0.3 dB from the encoding of a double precision floating point value given as $x$:

  • Extract the 11 bit exponent as unsigned integer $E$ and subtract 1023.
  • Extract the 52 bit mantissa as unsigned integer $M$.
  • Divide $M$ by $2^{52}$ (Shift M 52 bits to the right) to be all fractional in range of [0, 1)
  • $\log_2(x) \approx E - 1023 + M/2^{52} + 2^{-5}$.

DETAILS

IEEE-754 double precision floating point representation is encoded into 64 bits as a sign bit, exponent, and mantissa as depicted in the graphic below:

double precision floating point

The resulting floating point number is given as:

$$x = (-1)^S \cdot (1 + 2^{-52}M) \cdot 2^{(E-1023)} \label{1}\tag{1}$$

Where $M$ and $E$ represent the unsigned integer representations for the binary values stored in the mantissa and exponent respectively.

$$ S \in \{0,1\} \\ 1 \le E < 2^{11}-1 \\ 0 \le M < 2^{52} $$

The exponent is stored with a bias to represent positive and negative exponents rather than using 2's complement as then different numbers can be compared directly using fixed point arithmetic (simple!). The range for the exponent does not include the two values corresponding to a binary number with all zeros or all ones as those two values are used to encode special conditions (infinity, zero, NaN).

From $M$ and $E$ taken directly from the stored floating point representation, we can estimate $\log_2(x)$ for all positive values $x$ with a max error of 0.05 using

$$\log_2(x) \approx E - 1023 + 2^{-52}M + 2^{-5} \label{2}\tag{2}$$

Note that all operations are simple bit shifts, so computationally cheap. This can be improved to higher accuracy with additional curve fitting of the equation $\log_2(1+2^{-52}M)$ which results in an exact solution.

DERIVATION

The following $\log_2$ relationship is from \ref{1}:

$$\frac{x}{1+2^{-52}M} = 2^{(E-1023)} $$

$$\log_2\bigg(\frac{x}{1+2^{-52}M}\bigg) = E-1023 \label{3}\tag{3}$$

We note that denominator term $1+2^{-52}M$ has a range from 1 to 2.

Rewriting \ref{3}:

$$\log_2(x) - \log_2(1+2^{-52}M) = E - 1023 \label{4}\tag{4}$$

And we get the exact relationship for $\log_2(x)$ from the given floating point encoding:

$$\log_2(x) = E - 1023 + \log_2(1+2^{-52}M) \label{5}\tag{5}$$

We can use several approximation methods to replace the $\log_2(1+M/2^{52})$ term depending on accuracy needed, including computations from the Taylor Series expansion or table look-up methods. Observe in the graph below the match by simply subtracting one and adding the closest bit shift offset of 2^{-5} as:

$$\log_2(1+2^{-52}M) \approx 2^{-52}M -1 + 2^{-5}$$

Mantissa Contribution

Given this, we can make a first approximation of $\log_2(x)$ from the exponent directly. This has a peak error of 1 (or add 1/2 to this to reduce the peak error to 0.5 as the error is always negative):

$$\log_2(x) \approx E-1023 \label{6}\tag{6}$$

We can improve this by including the mantissa curve fit as:

$$\log_2(x) \approx E + 2^{-52}M -1023 + 2^{-5} \label{7}\tag{7}$$

Testing this on actual floating point representations I was able to create the following graphic, where the error pattern is consistent with the curve fit used for the $\log_2(1+2^{-52}M) $:

results

Thinking in dB

An interesting perspective since many of us often work in the world of dB units is that we can express a magnitude quantity in dB as either:

$$dB(x) = 20\log_{10}(x)$$

or

$$dB(x) = 6\log_2(x)$$

since $\log_{10}x = \log_2(x)/\log_{2}(10)$.

We see how this results in a simple dB computation as well, and with that we see that using Equation \ref{6} directly could have an error of up to 6 dB (or +/-3 dB if we added the 1/2). This would be unacceptable in most applications, but with Equation \ref{7} the error in dB is reduced to 0.3 dB which would then have wider appeal. A simple one or two more orders of curve fit for the mantissa term would improve this accuracy substantially.

BOTTOM LINE - FIXED POINT

We can play similar tricks for a signed fixed point number $x$ by converting the number represented in an arbitrary Q(m,n) format to Q(2, m+n-2) format. (For further details on Q(m,n) formats, please see https://en.wikipedia.org/wiki/Q_(number_format)) by moving the radix to the left $E$ places ($E$ can be negative). This means determining the minimum $E$ such that dividing $x$ by $2^E$ results in a fractional number between 1 and nearly 2. (which means shift right maintaining fractional values until there is only one integer magnitude bit left, keeping track of the number of shifts needed to derive the value $E$).

The resulting number will then be have a value $1 + F$ having a range between 0 and nearly 1, with $F$ as the fractional part. This results in the following approximation:

$$\log_2(x) \approx E + F + 2^{-5}$$

For example, in 16 bit Q16.0 signed representation, the number 532 would be given in binary as:

$$0000\_0010\_0001\_0100$$

To be in Q(2, 14) format, we would move the radix (which is at the far right to start) 9 places to the left, so $E=9$, and the fractional result in Q2.14 format is $532/2^9 = 1.0390625 = 1 + F$

Therefore, $\log_2(532) \approx 9 + 0.0390625 + 2^{-5} = 9.0703125$

The actual result is $\log_2(532) = 9.05528...$

If we multiply the estimate 9.07 by 6 we get the result in dB as 54.42 dB. The actual dB computation is $20\log_{10}(532)= 54.52$ dB.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.