**1**

# Floating point base 2 logarithm

###
#1
Crossbones+ - Reputation: **3085**

Posted 11 May 2012 - 02:30 PM

###
#4
Members - Reputation: **336**

Posted 11 May 2012 - 03:51 PM

Anyway, maybe look into frexp()? Don't be deceived by the word "exp" in this particular function's name -- it's base 2, not base e. I mean, is 8.1 == 0.506250 * pow(2.0, 4.0) along the lines of what you mean by splitting between fractional and integer parts, where 0.506250 is the fractional part and 4 is the integer part? If so, then frexp() is the function that you're looking for.

**Edited by taby, 11 May 2012 - 04:06 PM.**

###
#5
Crossbones+ - Reputation: **3085**

Posted 11 May 2012 - 04:06 PM

log2(12394) = 13.5973543.

I can easily get the answer 13, however I have remaining significant bits that I would like to use to determine the remaining 0.5973543.Has anyone done this sort of thing before?

**Edited by Ectara, 11 May 2012 - 04:07 PM.**

###
#6
Members - Reputation: **336**

Posted 11 May 2012 - 04:13 PM

No, these are not what I'm looking for; while alvaro is mathematically correct, I have no logarithm function to work with. Basically, I can easily return the integer part of y, where y = log2(x). However, I am having trouble finding the fractional part. For instance:

log2(12394) = 13.5973543.

I can easily get the answer 13, however I have remaining significant bits that I would like to use to determine the remaining 0.5973543.Has anyone done this sort of thing before?

modf() will give you both the numbers 13 and 0.5973543.

fmod() will give you 0.5973543 if you already have 13 on hand and want to leverage it as input (though this route seems a bit wasteful).

**Edited by taby, 11 May 2012 - 04:20 PM.**

###
#8
Members - Reputation: **336**

Posted 11 May 2012 - 04:24 PM

No, that's not what I'm looking for. I get an incomplete answer with my current implementation of log2(). I need to get more information, not less.

Oh, I see what you mean now. You're literally manipulating this on the level of bits because you're being forced to write your own floating point type, and/or you're stuck at the part where you have to write your own base 2 logarithm function? If you could show us what you already have, that'd be super great, otherwise I'm just going to suggest that you stick with the standard library -- which clearly already does everything that you need.

**Edited by taby, 11 May 2012 - 04:43 PM.**

###
#9
Crossbones+ - Reputation: **14318**

Posted 11 May 2012 - 04:38 PM

No, these are not what I'm looking for; while alvaro is mathematically correct, I have no logarithm function to work with. Basically, I can easily return the integer part of y, where y = log2(x). However, I am having trouble finding the fractional part. For instance:

log2(12394) = 13.5973543.

I can easily get the answer 13, however I have remaining significant bits that I would like to use to determine the remaining 0.5973543.Has anyone done this sort of thing before?

The thread is marked "C language", and the C language that come with a library that includes `log'. If your circumstances are different, you are going to have to explain them carefully. Do you have access to assembly? For what processor? What other restrictions do you have?

EDIT: Although I still would like to know the answers to the questions above, I am pretty sure you are looking for something like this: http://www.quinapalus.com/efunc.html

**Edited by alvaro, 11 May 2012 - 04:42 PM.**

###
#10
Crossbones+ - Reputation: **3085**

Posted 11 May 2012 - 05:07 PM

It's a "language with C syntax", I guess. No assembly, any processor with IEEE 754 support and at least 32bit two's complement integers. I can't use the standard library, but I have a great deal of replacements for most of the modules. Except the math.

si32 E_mathLog2if(sf32 x){ register ui32 c; c = _E_floatGetExponentf(x); if(!c){ c = _E_floatGetMantissaf(x); c |= (c >> 1); c |= (c >> 2); c |= (c >> 4); c |= (c >> 8); c |= (c >> 16); c >>= 1; c -= ((c >> 1) & 0x55555555); c = (((c >> 2) & 0x33333333) + (c & 0x33333333)); c = (((c >> 4) + c) & 0x0f0f0f0f); c += (c >> 8); c = (c + (c >> 16)) & 0x3f; if(!c) return 0; c = (ui32)(-(23 - c)); } return _E_floatGetSignf(x) ? ~0 : (si32)c - 127; }

That link does provide interesting concepts, and I've seen it before, but it is for fixed point with a drastically finite range of values; a slew of conditional statements like that will not quite work well with floating point, it seems.

**Edited by Ectara, 11 May 2012 - 05:09 PM.**

###
#11
Members - Reputation: **336**

Posted 11 May 2012 - 05:26 PM

http://www.icsi.berk...s/TR-07-002.pdf

... which gives a link to the site:

http://www.flipcode...._Function.shtml

... which gives the code:

inline float fast_log2(float val) { int *const exp_ptr = reinterpret_cast<int *>(&val); // For interpreting the float as a sequence of bits. int x = *exp_ptr; // This is obviously not the same thing as truncating the float by casting it as an int. const int log_2 = ((x >> 23) & 255) - 128; x &= ~(255 << 23); x += 127 << 23; *exp_ptr = x; // This is obviously not the same thing as casting the int as a float. val = ((-1.0f/3.0f) * val + 2) * val - 2.0f/3.0f; return val + log_2; }

... in which --

**at the end of the function**-- the variable val is within the range of 1 to 2, and the variable log_2 contains the rest of the final result. The precision is not perfect, but it's a start. Best of luck.

**Edited by taby, 11 May 2012 - 05:40 PM.**

###
#12
Crossbones+ - Reputation: **2693**

Posted 11 May 2012 - 06:00 PM

###
#14
Members - Reputation: **336**

Posted 11 May 2012 - 06:17 PM

A quick search turned up http://www.netlib.org/cephes/ which seems to have C source code for all sorts of operations, including base 2 log.

Sweet! Thank you for this.

###
#15
Crossbones+ - Reputation: **6995**

Posted 11 May 2012 - 06:26 PM

For future reference, details like this are kind of a big deal.It's a "language with C syntax", I guess. No assembly, any processor with IEEE 754 support and at least 32bit two's complement integers. I can't use the standard library, but I have a great deal of replacements for most of the modules. Except the math.

You haven't been exactly clear on what you can/can't do with this "language" you're using, but why not use the algorithm on Wikipedia's Binary logarithm page? And if you can't do that, you're going to have to be very, very clear about what your limitations are.

###
#16
Crossbones+ - Reputation: **3085**

Posted 11 May 2012 - 07:00 PM

And as for my platform, I have access to all of C89 syntax, with painstakingly written replacements for almost all of the modules, most of which are beyond the scope of this question. With the exception of logarithms and such because, well, I'm writing them now.

###
#17
Crossbones+ - Reputation: **2338**

Posted 11 May 2012 - 07:38 PM

Divide the value by the integer log2 of it leaving you with the decmial portion.

Double the value.

*It will always be in the range [1,2) at this point.*

Then reapeat until the desired precision is reached:

- Square the value.
- If it is greater than 2, halve it and output a one into the next significant bit of the result

else output a zero into the next significant bit of the result.

**Edited by iMalc, 11 May 2012 - 07:40 PM.**

My website dedicated to sorting algorithms