Разработка компиляторов

       

Понижение силы операций


Данное преобразование особенно эффективно при применении к вычислениям внутри тел циклов, хотя это не является его необходимым контекстным условием.

Основная идея понижения силы операций - это замена (в частных случаях) использования более дорогих операций более дешевыми (умножения - сложением или сдвигом, возведения в степень - умножением и т.д.) Обычно используются следующие тождества:

  • x*2k x << k
  • x2 x * x
  • 2*x x+x
  • n*x (n -1)*x + x
  • xn xn-1 * x

Два последних тождества и дают возможность применения преобразования к циклам. На иллюстрации приведен пример такого преобразования. В данном случае умножение внутри тела цикла было заменено сложением.



Содержание раздела