• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Ectara

Floating point base 2 logarithm

17 posts in this topic

How would one interpolate between logarithmic values? For a bit of context, say I have a floating point value. I can get the integer part of the logarithm by taking the exponent, or in the case of an unnormalized number, the base 2 logarithm of the mantissa and adjust it to where it should lie on the spectrum. However, I would also like to get the fractional part of the logarithm; somehow, using the mantissa, I must get the fractional part of the resulting logarithm that is somewhere between the floored and the ceilinged logarithm. Does anyone know how to do this? Clearly, linear interpolation won't cut it.
0

Share this post


Link to post
Share on other sites
What are the integer and fractional parts of a logarithm? Log is perfectly well defined for floating point numbers (well positive ones), integral or not should not figure into it.
0

Share this post


Link to post
Share on other sites
Like the above two people, I am having some difficulty understanding what you're asking for.

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
0

Share this post


Link to post
Share on other sites
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? Edited by Ectara
0

Share this post


Link to post
Share on other sites
[quote name='Ectara' timestamp='1336774010' post='4939430']
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?
[/quote]

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
0

Share this post


Link to post
Share on other sites
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.
0

Share this post


Link to post
Share on other sites
[quote name='Ectara' timestamp='1336774737' post='4939433']
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.
[/quote]

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
0

Share this post


Link to post
Share on other sites
[quote name='Ectara' timestamp='1336774010' post='4939430']
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?
[/quote]

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: [url="http://www.quinapalus.com/efunc.html"]http://www.quinapalus.com/efunc.html[/url] Edited by alvaro
1

Share this post


Link to post
Share on other sites
This is what I have so far, to return the floored base 2 logarithm. It's a little obfuscated, but mostly working. However, I have a version returning a floating point type that isn't too different, seeing as the fractional part of the answer isn't being returned properly.

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.
[CODE]

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;
}
[/CODE]

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
0

Share this post


Link to post
Share on other sites
Sorry, I really wish I could be of more help, but here's a link to a paper:
[url="http://www.icsi.berkeley.edu/pubs/techreports/TR-07-002.pdf"]http://www.icsi.berk...s/TR-07-002.pdf[/url]

... which gives a link to the site:
[url="http://www.flipcode.com/archives/Fast_log_Function.shtml"]http://www.flipcode...._Function.shtml[/url]

... which gives the code:
[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;
}
[/CODE]

... in which -- [b]at the end of the function[/b] -- 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
0

Share this post


Link to post
Share on other sites
A quick search turned up http://www.netlib.org/cephes/ which seems to have C source code for all sorts of operations, including [url="http://www.netlib.org/cephes/singldoc.html#log2"]base 2 log[/url].
1

Share this post


Link to post
Share on other sites
I did see that; I have an inaccurate approximation, but for this purpose, I need accuracy over speed; as long as it works to comparable precision with the standard C library's log functions.
0

Share this post


Link to post
Share on other sites
[quote name='Adam_42' timestamp='1336780832' post='4939456']
A quick search turned up [url="http://www.netlib.org/cephes/"]http://www.netlib.org/cephes/[/url] which seems to have C source code for all sorts of operations, including [url="http://www.netlib.org/cephes/singldoc.html#log2"]base 2 log[/url].
[/quote]

Sweet! Thank you for this.
0

Share this post


Link to post
Share on other sites
[quote name='Ectara' timestamp='1336777673' post='4939447']
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.
[/quote]
For future reference, details like this are kind of a big deal.

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 [url="http://en.wikipedia.org/wiki/Binary_logarithm"]Wikipedia's Binary logarithm[/url] page? And if you can't do that, you're going to have to be very, very clear about what your limitations are.
1

Share this post


Link to post
Share on other sites
I may be able to rewrite the Python example. This might be what I'm looking for, thank you. I'll be sure to post again if I still have trouble.

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.
0

Share this post


Link to post
Share on other sites
Yep, that's what you want to do, as per the algorithm from Wikipedia...
Divide the value by the integer log2 of it leaving you with the decmial portion.
Double the value. [i]It will always be in the range [1,2) at this point.[/i]
Then reapeat until the desired precision is reached:[list]
[*]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.
[/list] Edited by iMalc
0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0