Iterative division

This topic is 2813 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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

Share on other sites
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

Share on other sites
Problem:
$\frac{n}{2^x}=1$

Solve for x:
$n=2^x$

$log_2 n =log_2 2^x$

$log_2 n=x$

$\frac{ln(n)}{ln(2)}=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

Share on other sites
...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

Share on other sites
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

Share on other sites
What if the number you pass to ceil is a whole number?

Share this post

Share on other sites
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

Share on other sites
No harm, no foul.

Share this post

Share on other sites
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

Share on other sites

This topic is 2813 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

• Forum Statistics

• Total Topics
628686
• Total Posts
2984237

• 16
• 13
• 13
• 10
• 10