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

## 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 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 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 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 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 on other sites
What if the number you pass to ceil is a whole number?

##### 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 on other sites
No harm, no foul.

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

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628686
• Total Posts
2984237

• 16
• 13
• 13
• 10
• 10