0

Code for division by 9 in fixed point.

  1. q = 0;              // quotient
  2. y = (x << 3) - x;   // y = x * 7
  3. while(y) {          // until nothing significant
  4.   q += y;           // add (effectively) binary 0.000111
  5.   y >>= 6;          // realign
  6. }
  7. q >>= 6;            // align

Line 2 through 5 in the FIRST execution of while loop is effectively doing
x*.000111 (in decimal representation x*0.1), what it is trying to achieve in subsequent while loops?

Should it not be again multiplying that with 7 and again shifting instead of doing only shifting to take care of recurrence?

Explanation with respect to plain decimal number multiplication as to what is being achieved with only shifting would be nice.

Detailed code explanation here: Divide by 9 without using division or multiplication operator

Improve this question
5
  • It's airway explained in the answer there; why do you need another explanation? Commented Jun 2, 2015 at 7:36
  • @OliverCharlesworth: I wanted to ask more questions there but it was getting long and so i created this one. I thought the discussion was going to fixed point and that is why this question. Commented Jun 2, 2015 at 7:37
  • "what is being achieved with only shifting" Is that your actual question? Commented Jun 2, 2015 at 7:44
  • @Eregrith: yes and why not multiplying and shifting again? I would also appreciate if multiplication with decimal is given as an example to illustrate the shifting point. Commented Jun 2, 2015 at 7:47
  • You need to familiarise yourself with infinite series. For example, (1/4) + (1/4)^2 + (1/4)^3 + (1/4)^4 + (1/4)^5 ... = 1/3. These infinite series correspond to repeating patterns in binary (when the terms are powers of 2). Understand the division by 3 example first and then you will understand division by 9 Commented Jun 2, 2015 at 8:10

2 Answers 2

Reset to default
2

Lets denote 7/64 by the letter F. 7/64 is represented in binary as 0.000111 and is very close to 1/9. But very close is not enough. We want to use F to get exactly to 1/9. It is done in the following way

F+ (F/64) + (F/64^2) + (F/64^3) + (F/64^4)+ (F/64^5) + ...

As we add more elements to this sequence the results gets closer to 1/9 Note each element in the sequence is exactly 1/64 from previous element.

A fast way to divide by 64 is >>6

So effectively you want to build a loop which sums this sequence. You start from F and in each iteration do F>>6 and add it to the sum. Eventually (after enough iterations) the sum will be exactly 1/9.

Ok now, you are ready to understand the code. Instead of using F (which is a fraction and cannot be represented in fixed points) the code multiplies F by x. So the sum of the sequence will be X/9 instead of 1/9 Moreover in order to work with fixed points it is better to store 64*X*F and the result would by 64*X/9.

Later after the summation we can divide by 64 to get the X/9

The code stores in the variable y the value of F*x*64

variable q stores the sum of the sequence. In each loop iteration we generate the next element in the sequence by dividing the previous element by 64 (y>>=6)

Finally after the loop we divide the sum by 64 (q>>=6) and get the result X/9.

Regarding you question. We should not multiply by 7 each time or else we will get a sum of the sequence of

F+ (F^2) + (F^3) + (F^4) + (F^5)...

This would yield a result of ~X/(8+1/7) instead of X/9.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

I got your explanation as to the shifting. Just one last doubt you said we are multiplying initially by 64 "The code stores in the variable y the value of F*x*64". I don't see we are multiplying initially by 64.
I think i understood what you meant. Basically initially in the 0.000111 recurrence we considered only 6 numbers after decimal point which is same as representing everything in q6 format(6 bits reserved for fractional part). So after multiplication we right shift it by 6 so that the result can be represented in q6 format right? I will up vote this as right answer after your comment.
I edited my answer to address your remark in the comment. See the Explanation: F*x*64 = (7/64)*x*64 = 7*x = 8*x-x = (x<<3)-x. And yes, you are correct. Each time we add the next six digits after the decimal point. Thus effectively after N iterations we have a more accurate binary representation of 1/9 using 6*N digits after the decimal point
1

Shifting by one to the left multiplies by two, shifting by one to the right divides by two. Why?

Shifting is the action of taking all the bits from your number and moving them n bits to the left/right. For example:

00101010 is 42 in Binary
42 << 2 means "shift 42 2 bits to the left" the result is
10101000 which is 168 in Binary
we multiplied 42 by 4.

42 >> 2 means "shift 42 2 bits to the right" the result is
00001010 which is 10 in binary (Notice the rightmost bits have been discarded)
we divided 42 by 4.

Similarly : (x << 3) is x * 8, so (x << 3) - x is (x * 8) - x => x * 7

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.