Algebra optimization for faster code in programming

November 4th, 2009 Leave a Comment

Every compiler behaves differently and they are able to do different kinds of optimizations. However, there are times when the code is too complicated for the compiler to optimize. As a result, it’ll use the original unoptimized code instead. Therefore, I urge that we do some optimizations manually at our side whenever we could. For example,

  • a + b + c = (a + b) + c
    If a and b are constants, they are computed at compile-time (by grouping the constants together).
  • a * b + a * c = a * (b + c)
    The arithmetic operations are reduced from three to two.
  • a * x * x * x + b *x * x + c * x + d = ((a * x + b) * x + c) * x + d
    The arithmetic operations are reduced from nine to six.
  • x * x * x* x * x * x * x * x = ((x ^ 2 ) ^ 2 ) ^ 2
    The arithmetic operations are reduced from seven to three.

I’ll list the non-optimized equations on the LHS (left-hand-side) and the optimized on the RHS (right-hand-side) without descriptions. They can be understood easily.

Algebra reductions:

  • a + b + c = (a + b) + c
  • a * b + a * c = a * (b + c)
  • a * x * x * x + b * x * x + c * x + d = ((a * x + b) * x + c) * x + d
  • x * x * x * x * x * x * x * x = ((x ^ 2) ^ 2) ^ 2
  • a + a + a + a = a * 4
  • -(-a) = a
  • a – (-b) = a + b
  • a – a = 0
  • a + 0 = a
  • a * 0 = 0
  • a * 1 = a
  • (-a) * (-b) = a * b
  • a/a = 1
  • a/1 = a
  • 0/a = 0
  • (-a == -b) = (a == b)
  • (a + c == b + c) = (a == b)
  • !(a < b) = (a >= b)
  • (a < b && b < c && a < c) = (a < b && b < c)
  • Multiply by constant = shift and add
  • Divide by constant = multiply and shift
  • !(!a) = a
  • (a && b) || (a && c) = a && (b || c)
  • !a && !b = !(a || b)
  • a && !a = false
  • a || !a = true
  • a && true = a
  • a || false = a
  • a && false = false
  • a || true = true
  • a && a = a
  • (a && b) || (a && !b) = a
  • (a && b) || (!a && c) = a ? b : c
  • (a && b) || (!a && c) || (b && c) = a ? b : c
  • (a && b) || (a && b && c) = a && b
  • (a && b) || (a && c) || (a && b && c) = a && (b || c)
  • (a && !b) || (!a && b) = a XOR b

It is very often that we tend to neglect the additional one, two or three arithmetic operations because we have blazing fast computers now (if compared to those P386 back in those years). However, by eliminating these extra arithmetic operations will help improve program efficiency, especially within critical code.

Hence, let’s start writing reduced algebra to get more optimized code now. :)

Tags:
, , ,

Leave a Reply


+ eight = 13