Sign in to follow this  
Ectara

Iterative division

Recommended Posts

Ectara    3097
I need to find a method of finding out how many times a given floating point number n can be divided in half before n becomes less than 1.0 . Simply dividing in half repeatedly and incrementing a counter each time is too slow, and I need this to be as fast as possible.

Share this post


Link to post
Share on other sites
Ectara    3097
Awesome. That's exactly what I'm looking for. While I'm here, is there any fast method for me to determine the final value of n after the last divide?

Share this post


Link to post
Share on other sites
fastcall22    10840
Problem:


Solve for x:








Therefore:
int x = static_cast<int>( ceil( log(n)/log(2) ) );

or

int x = static_cast<int>( log(n)/log(2) ) + 1;


To find the resulting value:
float q = n / pow(2,x);

or

float q = n / (1 << x);

EDIT:
My original post disappeared mysteriously, so I'm putting it here.

[Edited by - _fastcall on April 1, 2010 7:31:39 PM]

Share this post


Link to post
Share on other sites
Ectara    3097
...I don't know what I was thinking on that one. That one should have been obvious. Thanks, you've helped a lot.

Share this post


Link to post
Share on other sites
Zouflain    548
I'm not the most proficient coder ever, but isn't cieling something that you've already turned into an int rather redundant? Int automatically floors any floating point value it's assigned to, so adding one seems a lot faster than the overhead for any other function.

int(2.203838)+1 = (2) + 1 = 3
ceil(2.203838) = (3) = 3 with overhead.

Share this post


Link to post
Share on other sites
Zouflain    548
Eh, and that sort of thing is why I'm not the most proficient coder. Yeah, working around that would cost more overhead so far as I can see than just using the ceil. My mistake.

Share this post


Link to post
Share on other sites
alvaro    21246
If you really need to do this fast, the floating-point types already have this information neatly encoded in the `exponent' field, so with a bit of wizardry you could read the floating-point number as an integer and extract the exponent part. You may have to fight your optimizer for the evil casts to work, though. Also, your portability will seriously suffer from something like this.

int l2(float f) {
int i = *reinterpret_cast<unsigned *>(&f);
return (i>>23)-126;
}



[Edited by - alvaro on April 2, 2010 11:33:17 AM]

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