Sign in to follow this  
BrickInTheWall

Need a little help analyzing a little program

Recommended Posts

Hello everyone...I'm in a bit of a kerfuffle here. I don't understand part of this code:
#include <iostream>

using namespace std;

unsigned short sqrt( unsigned long a )
{
	unsigned long rem = 0;
	unsigned long root = 0;
	unsigned long divisor = 0;

	for( int i = 0; i < 16; i++ )
	{
		root <<= 1;
		rem = ( ( rem << 2 ) + ( a >> 30 ) );
		a <<= 2;
		divisor = ( root << 1 ) + 1;

		if( divisor <= rem )
		{
			rem -= divisor;
			root++;
		}
	}

	return (unsigned short)root;
}
It's a binary root finder that works only with addition and subtraction. Sadly the book featuring this code doesn't explain it at all! I think I understand the 16 iterations though: variable a is an unsigned long integer. Within 16 itirations and pushing 2 bits each time to the left it will be 0 after the 16th iteration if 1 is entered...since it's an integer root finder, that's the smallest value apart from 0 that you can enter. Did I understand this correctly? What really baffles me though is how the variables rem and divisor work together and what they represent. All I can tell is that they'll start increasing once the 'a' variable overflows (well it doesn't overflow but it'll be 0x000...etc.)...so 0 basically. Anyone have an idea? Cheers, Chris

Share this post


Link to post
Share on other sites
This is a lot of guesswork on my part, but I think I might understand that code well enough to get the gist of it.

The basic idea is you are determining which bits of the root should be set, one at a time starting with the Most Significant bit of the root. However, it starts out by actually setting the LSB of the root and then shifting that bit as well as the previously set bits as it goes on. To determine whether a bit of the root should be set or not we need to know if the remaining quantity to calculate the root from can be divided by the number or not. That is, if the remainder (more on that in a bit) is less than the divisor implies that the remainder can be divided by the divisor wholly. ie, if remainder / divisor > 1 is true then we should set the root current root bit.

The divisor, if you'll notice, is set to what the next root would be if the root bit we are on were to be set. Then by seeing if the remaining amount can be divided by the next root we see if we were correct to assume the bit was set. And when the divisor IS less than the remainder (presumably the remainder is more than 1 time greater than divisor but less than 2 times greater than the divisor) we remove the divisor from our calculations, having taken it into account.

Finally, the remainder increases by a factor of 4 PLUS whatever remaining original number (a) we have to go. That is, I believe the equation works on the 2 highest remaining bits in the original number PLUS the previous remaining number that we haven't taken account of yet.

It is here where I start to get confused again by the workings of the algorithm. I'd need to step through the code in my head or in a debugger and I'm a little too busy to get into that right now. However, I think this wikipedia article might help you a little bit. The algorithms aren't the same, but read the paragraph describing it and hopefully you'll start to better grasp what the function you have is doing.

Hope this helps.

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