Arithmetic shift divison question

  • Thread starter Thread starter bitrex
  • Start date Start date
  • Tags Tags
    Arithmetic Shift
Click For Summary

Discussion Overview

The discussion revolves around an arithmetic shift division question, specifically examining an alternative formula for dividing the product of two variables by 255 using bitwise operations. Participants explore the equivalence of this formula to the original division operation, focusing on the implications of using shifts and the conditions under which the formula holds.

Discussion Character

  • Technical explanation, Debate/contested, Mathematical reasoning

Main Points Raised

  • One participant presents a formula that replaces division by 255 with a combination of shifts and additions, seeking clarification on its correctness and mechanics.
  • Another participant challenges the proposed formula, arguing that it does not yield the correct result when one of the variables is zero.
  • A third participant points out that the algorithm fails for certain values, specifically at 65535 and larger numbers, suggesting that the underlying assumptions about fixed-point representation may be flawed.
  • There is a question about whether the variables b and c are integers, with a suggestion that the formula might depend on the two's complement representation of integers.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the correctness of the proposed formula, with multiple competing views on its validity and applicability based on different scenarios.

Contextual Notes

The discussion highlights potential limitations related to the assumptions about variable types (e.g., integers) and the specific conditions under which the proposed formula may or may not hold true.

bitrex
Messages
190
Reaction score
0
If I have the following function:

a = b * c/255

The following function is apparently equivalent using only shifts:

product = b * c;
a = (product + (product>>8) + 1)>>8;

I am having trouble following how this function works. Since an arithmetic right shift is division by a power of 2 right shift 8 would be division by 256...somehow (product + (product>>8) +1) is compensating for the difference between the two but I'm not sure why it's that and not just (product + 1). I'm too thickheaded to see it, any clarification would be appreciated!
 
Technology news on Phys.org
I don't think your formula is correct. For example, if b was 0, then b*c/255 is zero but your replacement formula would not produce 0.
 
The algorithm fails at 65535 (255*257) and larger numbers.

The algorithm is based on the fact that in hexadecimal fixed point

1/ff = .010101010101 ...

or expressed as a power series:

p/255 = (p/256) + (p/2562) + (p/2563) + (p/2564) + (p/2565) + ...
 
Last edited:
are b and c integers? this might work if integers are stored as two's complement.
 

Similar threads

Python Shifting an array one postion to the left -- Non Function Vs Function
  • · Replies 17 ·
Replies
17
Views
4K
Difficult Understanding Magnitude and Phase Shift of Transfer Function
  • · Replies 4 ·
Replies
4
Views
2K
Leetcode 728 complier issue with mutliple functions
  • · Replies 12 ·
Replies
12
Views
2K
High School Confused about ciphers in the book 'Arithmetic for the Practical Man'
  • · Replies 13 ·
Replies
13
Views
3K
Python How can numpy.dot() be used in Python to solve Markov chain Monte Carlo methods?
  • · Replies 6 ·
Replies
6
Views
3K
Undergrad Red-Shifting vs. Luminosity Question
  • · Replies 3 ·
Replies
3
Views
2K
Creating a TMR0 delay using PIC16F84?
  • · Replies 3 ·
Replies
3
Views
2K
MHB Is the Degree of the Product of Two Polynomials 2n?
  • · Replies 1 ·
Replies
1
Views
2K
Program to list specific permutations of 5 digits
  • · Replies 4 ·
Replies
4
Views
3K
Am I understanding horizontal shift properly?
  • · Replies 3 ·
Replies
3
Views
2K