Non-restoring division of binary numbers

[Tosi]

I'm trying to divide 1011001 / 10 using the non-restoring division method.
This is what i get: http://prntscr.com/8aecs . The remainder is not correct(it should be 0001 and I'm getting a 0111) and I'm wondering where is the mistake.. I've checked about 10 times and i don't see the problem. Can anyone please help me?

 

[rcgldr]

On non-restoring divide, the first step in this case should be a subtract, but it looks like an add was done. The normal sequence for non-restoring divide is if the signs are the same, you subtract, if the signs differ you add.

Depending on the algorithm implementation, there may need to some adjustment before and after to handle negative dividends.

 

[Mark44]

I'm trying to divide 1011001 / 10 using the non-restoring division method.
This is what i get: http://prntscr.com/8aecs . The remainder is not correct(it should be 0001 and I'm getting a 0111) and I'm wondering where is the mistake.. I've checked about 10 times and i don't see the problem. Can anyone please help me?

I don't know anything about the non-restoring division method, but I do know the normal division algorithm. As base-10 numbers, you're dividing 89 by 2, so you should get a quotient of 44 and a remainder of 1.

As a binary number, the quotient looks like 101100.1.

 

[Tosi]

On non-restoring divide, the first step in this case should be a subtract, but it looks like an add was done. The normal sequence for non-restoring divide is if the signs are the same, you subtract, if the signs differ you add.

Depending on the algorithm implementation, there may need to some adjustment before and after to handle negative dividends.

Well I've based the procedure on this example: http://www.cs.pitt.edu/~musfiq/teaching/cs0447/labs/lab07/CS447DivisionExamples.pdf. Based on this and some algorithms that I've seen, as i understood (please correct if I'm wrong, help is highly appreciated) the first step is shifting the remainder(the dividend) to the left and inserting a 0, then (the leftmost 4 bits of the remainder) - (the divisor) (and in my case 0000 - 0010 = 1110(which is a negative number because of the leftmost 1)). Then because the leftmost bits of the remainder are a negative number, we again shift the whole remainder to the left and add a 0 to the end and then adding the divisor and the leftmost 4 bits of the remainder (if it was a positive number or equal to zero, we shift the whole remainder to the left and add a 1 to the end, following, in this case, subtracting instead of adding) and so on..repeating the process (the number of times depending on the number of bits of the dividend) until the end where we shift the leftmost 4 bits to the right, adding a 0 to the beginning.Then taking the leftmost 4 bits as the remainder and the rest as the quotient. I should also mention that in my exercise i was supposed to assume that the divisor and dividend are always positive (with a zero in front of them). Am i wrong somewhere? :/

 

[Tosi]

I don't know anything about the non-restoring division method, but I do know the normal division algorithm. As base-10 numbers, you're dividing 89 by 2, so you should get a quotient of 44 and a remainder of 1.

As a binary number, the quotient looks like 101100.1.

Well the quotient is correct, but the remainder i get is 0111 which is 7.. :/

 

[NocturneX]

At the end, you should perform an arithmetic RC shift, that means : preserve the sign.
Ex. When shifting 1110 to the right, you should get 1111. So, now the remainder is 1111 (-1). Because the remainder is negative, add to it the divisor one last time to get 0001. A friend of mine asked me about this problem precisely, and I went through the whole C++ implementation of this weird kind of division. I had the same problem, but I eventually fixed it. In the tutorial I have been given, this last step was left out, so I figured it out by myself.

The same problem would have arisen had you been performing the division of 00100100 (36) by 00000110 (6).
Your steps would have resulted in the remainder being 01111010 which is obtained by an incorrect RC shift of
11110101. Following my correction of the described algorithm, shifting 11110101 results in 11111010 (-6), and by
adding the divisor (because the remainder is negative at the end), we eventually get remainder 00000000 (0) which is correct.

As a conclusion :
1. When shifting to the right at the end, perform an arithmetic RC shift. (preserve the sign)
2. If the remainder is negative at the end, add the divisor to the remainder and you will get the correct result.

Greetings from Skopje !
http://kolokviumska.blogspot.com/

 

[Tosi]

At the end, you should perform an arithmetic RC shift, that means : preserve the sign.
Ex. When shifting 1110 to the right, you should get 1111. So, now the remainder is 1111 (-1). Because the remainder is negative, add to it the dividend one last time to get 0001. A friend of mine asked me about this problem precisely, and I went through the whole C++ implementation of this weird kind of division. I had the same problem, but I eventually fixed it. In the tutorial I have been given, this last step was left out, so I figured it out by myself.

The same problem would have arisen had you been performing the division of 00100100 (36) by 00000110 (6).
Your steps would have resulted in the remainder being 01111010 which is obtained by an incorrect RC shift of
11110101. Following my correction of the described algorithm, shifting 11110101 results in 11111010 (-6), and by
adding the dividend (because the remainder is negative at the end), we eventually get remainder 00000000 (0) which is correct.

As a conclusion :
1. When shifting to the right at the end, perform an arithmetic RC shift. (preserve the sign)
2. If the remainder is negative at the end, add the dividend to the remainder and you will get the correct result.

Greetings from Skopje !
http://kolokviumska.blogspot.com/

Thanks a lot man :D, this was driving me crazy :)

 

[NocturneX]

Thanks a lot man :D, this was driving me crazy :)

When I was speaking of dividend, I actually meant divisor. I edited my post and hope you got it right )

 

[Tosi]

When I was speaking of dividend, I actually meant divisor. I edited my post and hope you got it right )

Oh, i didn't notice XD . But when i was reading that for some reason, in my head I pictured the divisor instead of the dividend XD Don't worry I understood what you meant, thanks again :) .

 

[Tosi]

I have another question with this method since i can't find any examples.. In the case where the divisor is bigger than the dividend and bigger than four bits. How many bits(zeros) should i write on the left of the remainder at the beginning(the part of the remainder where i do the subtracting and adding). In the examples I've seen the divisor is smaller than four bits and smaller than the dividend, so everywhere there are four bits for the leftmost part of the remainder. And also, I wasn't sure if the number the procedure is repeated depends on the number of bits of the dividend?

 

[rcgldr]

In the few old mini-computers (one was a computer automation alpha 16) that actually used a non-restoring divide, division consisted of division of a 32 bit dividend by a 16 bit divisor (this was also the norm for most "16 bit" mini computers for division regardless of the algorithm). If the first step didn't change the sign of the dividend, then an overflow condition was detected. Otherwise, it ended up with a 16 bit quotient in what was the lower bits of the dividend, and the remainder in what was the upper 16 bits of the dividend. On a PC and most processors, integer division starts off with a dividend with twice as many bits at the divisor, resulting in a quotient and remainder with the same number of bits as the divisor.

Some old mini-computers used a version of non-restoring divide that handled signed integer division, with some pre and/or post processing, with slight variations in the non-restoring divide algorithm.

 

[Tosi]

Well, I've started with a dividend with twice as many bits as the divisor and this is what i get: http://prntscr.com/8bnxx
The remainder is way off again :/ Someone knows what should i do differently?

 

[matt.b]

At the end, you should perform an arithmetic RC shift, that means : preserve the sign.
Ex. When shifting 1110 to the right, you should get 1111. So, now the remainder is 1111 (-1). Because the remainder is negative, add to it the divisor one last time to get 0001. A friend of mine asked me about this problem precisely, and I went through the whole C++ implementation of this weird kind of division. I had the same problem, but I eventually fixed it. In the tutorial I have been given, this last step was left out, so I figured it out by myself.

The same problem would have arisen had you been performing the division of 00100100 (36) by 00000110 (6).
Your steps would have resulted in the remainder being 01111010 which is obtained by an incorrect RC shift of
11110101. Following my correction of the described algorithm, shifting 11110101 results in 11111010 (-6), and by
adding the divisor (because the remainder is negative at the end), we eventually get remainder 00000000 (0) which is correct.

As a conclusion :
1. When shifting to the right at the end, perform an arithmetic RC shift. (preserve the sign)
2. If the remainder is negative at the end, add the divisor to the remainder and you will get the correct result.

Greetings from Skopje !
http://kolokviumska.blogspot.com/

I wanted to ask about dividing the numbers 27/95. With the non restoring algorithm at the end before we shift right we get a remainder 0111 1000. With the arithmetic shift to the right, we clone the most significant bit and we get 0011 1100. The remainder is positive so we don't add the divisor. This remainder is incorrect, normally it should be 0001 1011 that is 27. But I've noticed if I put 1 as the most significant bit and add the divisor I get the correct remainder of 27. What could be wrong in this division of these numbers? I really need an answer as quickly as possible...

 

[NocturneX]

I wanted to ask about dividing the numbers 27/95. With the non restoring algorithm at the end before we shift right we get a remainder 0111 1000. With the arithmetic shift to the right, we clone the most significant bit and we get 0011 1100. The remainder is positive so we don't add the divisor. This remainder is incorrect, normally it should be 0001 1011 that is 27. But I've noticed if I put 1 as the most significant bit and add the divisor I get the correct remainder of 27. What could be wrong in this division of these numbers? I really need an answer as quickly as possible...

My algorithm works correctly. Here is a screenshot of my C++ program executing, performing the division of 27 by 95 :

 

[rcgldr]

Well, I've started with a dividend with twice as many bits as the divisor and this is what i get: http://prntscr.com/8bnxx The remainder is way off again :/ Someone knows what should i do differently?

Try using the non-restoring algortihm for positive integers from this website (it's down a bit on the page). In the last step, the remainer is not shifted. Instead, if it's positive no change is made or if it's negative, the divisor is added to it in order to produce the proper remainder.

http://fourier.eng.hmc.edu/e85/lectures/arithmetic_html/node8.html

 

[NocturneX]

Try using the non-restoring algortihm for positive integers from this website (it's down a bit on the page). In the last step, the remainer is not shifted. Instead it's either left alone or if it's negative, the divisor is added to it in order to produce the proper remainder.

http://fourier.eng.hmc.edu/e85/lectures/arithmetic_html/node8.html

The algorithm consists of alternating lefts shifts and additions/subtractions, so if your pattern is SHL-ADD/SUB then you don't end with a SHL, so there is no need to go back. My pattern is ADD/SUB-SHL, so I need to make that right shift at the end. It's a matter of choice, but I admit that following the pattern SHL-ADD/SUB is less confusing.

Concerning the number of bits, you can take as many bits as you want provided you remain consistent throughout the whole process and never let owerflow occur.

 

[rcgldr]

My pattern is ADD/SUB-SHL, so I need to make that right shift at the end.

This requires an extra 1 bit register, usually the carry bit on a processor. Each SHL shifts the sign bit into the carry bit. For the right shift done at the end, the carry bit is shifted back into the remainder in order to restore what was the sign bit on the last SHL. You still have the issue after the right shift (with carry), that if the remainder is negative, you have to add the divisor to do the only "restore" step in the "non-restoring" division.

 

[rbj]

I'm trying to divide 1011001 / 10 using the non-restoring division method.
This is what i get: http://prntscr.com/8aecs . The remainder is not correct(it should be 0001 and I'm getting a 0111) and I'm wondering where is the mistake..

below is a piece of C code that was written to test the procedure for non-restoring division to be implemented in a hardware context (that is why there were all these "goto" statements which is considered bad style for C).

unsigned long divide(unsigned long long numerator, unsigned long denominator, unsigned long *quotient)
	{
	long long accumulator, shift_denominator;
	unsigned long set_bit;
	int word_width;
	
	word_width = 8*sizeof(unsigned long);	// 8 bits per byte
	
	shift_denominator = (long long)denominator;
	shift_denominator <<= word_width-1;
	
	set_bit = 1;
	set_bit <<= word_width-1;
	
	accumulator = numerator;
	
	*quotient = 0;
	
	goto enter_loop;
	
dont_exit_loop:
		shift_denominator >>= 1;
		accumulator += shift_denominator;
		if (accumulator < 0)
			goto bit_is_0;
bit_is_1:
		*quotient |= set_bit;
		set_bit >>= 1;
		if (set_bit == 0)
			goto exit_loop;
		shift_denominator >>= 1;
enter_loop:
		accumulator -= shift_denominator;
		if (accumulator >= 0)
			goto bit_is_1;
bit_is_0:
		// *quotient &= ~set_bit;					// this instruction is not necessary
		set_bit >>= 1;
		if (set_bit != 0)
			goto dont_exit_loop;
		accumulator += shift_denominator;			// undo last subtract to get non-negative remainder
	
exit_loop:
	return (unsigned long)accumulator;				// return remainder and *quotient
	}

notice the line:

accumulator += shift_denominator; // undo last subtract to get non-negative remainder

this is necessary if the LSB of the quotient is 0, instead of 1. this means that you subtracted, but from the POV of restoring division, you shouldn't have and you need to restore it. but it only makes a difference for the very last bit so that your remainder comes out correctly.

BTW, this code i posted is fully tested. it ain't wrong.

 

[Tosi]

Thanks to all of you, now i understand the method completely :D .

 

[rcgldr]

This method also works for signed numbers, but if I remember correctly, for the hardware version used on one of the old mini-computers, if the dividend was negative, it was decremented before the loop (if this switched the sign, then the value was 0x80000000, and overflow was reported), and then the remainder incremented afterwards. No special handing was required for negative divisors. Instead of looking for remainder >= 0 or < 0, the sign bits of the remainder and the divisor were compared to determine if an add step (quotient bit = 0) or subtract step (quotient bit = 1) was needed.