dmilicev

division_with_shift_operator_v1.c

Aug 16th, 2020
123
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  
  3.     division_with_shift_operator_v1.c
  4.  
  5. https://www.geeksforgeeks.org/divide-two-integers-without-using-multiplication-division-mod-operator/
  6. https://www.go4expert.com/articles/using-shift-operator-faster-division-t3095/
  7. https://www.tutorialspoint.com/cprogramming/c_bitwise_operators.htm
  8.  
  9.     The Joyful Programmer:
  10. Old optimization statement that I learned many, many, many
  11. years ago, when reading an optimization book by Michael Abrash. It goes:
  12.  
  13. "Multiply if you must, but never divide."
  14.  
  15. Remove the multiplication operator. Why? Well,
  16. when C++ is reduced to machine language, it takes the processor (newer ones)
  17. about 30 clock cycles to execute a single multiplication. Division takes over
  18. 60 clock cycles. However, we can reduce the amount of clock cycles by using a
  19. shift operator.
  20.  
  21. That's only 2 clock cycles versus an estimated 30 clock cycles, a 28 clock
  22. cycle difference, which could be essential if you are doing millions of
  23. calculations.
  24.  
  25.  
  26.     You can find all my C programs at Dragan Milicev's pastebin:
  27.  
  28.     https://pastebin.com/u/dmilicev
  29.  
  30. */
  31.  
  32. #include <stdio.h>
  33.  
  34. // Function to divide dividend by divisor and return floor value it
  35. int divide_v1(int dividend, int divisor)
  36. {
  37.     // Calculate sign of divisor i.e. sign will be negative only if
  38.     // either one of them is negative otherwise it will be positive
  39.     int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
  40.  
  41.     // Update both divisor and dividend positive
  42.     dividend = abs(dividend);
  43.     divisor = abs(divisor);
  44.  
  45.     // Initialize the quotient
  46.     int quotient = 0;
  47.  
  48.     while (dividend >= divisor)
  49.     {
  50.         dividend -= divisor;
  51.         ++quotient;
  52.     }
  53.  
  54.     return sign * quotient;
  55. }
  56.  
  57. // Function to divide dividend by divisor and return floor value it
  58. int divide_v2(long long dividend, long long divisor)
  59. {
  60.     int i;
  61.  
  62.     // Calculate sign of divisor i.e., sign will be negative only if
  63.     // either one of them is negative otherwise it will be positive
  64.     int sign = ((dividend < 0) ^ (divisor < 0)) ? -1 : 1;
  65.  
  66.     // remove sign of operands
  67.     dividend = abs(dividend);
  68.     divisor = abs(divisor);
  69.  
  70.     // Initialize the quotient
  71.     long long quotient = 0, temp = 0;
  72.  
  73.     // test down from the highest bit and accumulate the tentative value for valid bit
  74.     for (i=31; i>=0; --i)
  75.     {
  76.         if (temp + (divisor << i) <= dividend)
  77.         {
  78.             temp += divisor << i;
  79.             quotient |= 1LL << i;
  80.         }
  81.     }
  82.  
  83.     return sign * quotient;
  84. }
  85.  
  86.  
  87. int main(void)
  88. {
  89.     int n = 36 , m = 12;
  90.  
  91.     printf(" %d / %d = %d \n", n, m, divide_v1(n, m) );
  92.  
  93.     printf(" %d / %d = %d \n", n, m, divide_v2(n, m) );
  94.  
  95.     return 0;
  96.  
  97. } // main()
  98.  
RAW Paste Data Copied