Addition Machines
Robert W. Floyd, Donald E. Knuth · SIAM Journal on Computing · 1990
It is possible to compute gcd $(x, y)$ efficiently with only $O(\log xy)$ additions and subtractions, when three arithmetic registers are available but not when there are only two. Several other functions, such as $x^y \bmod z$, are also efficiently computable in a small number of registers, using only addition, subtraction, and comparison.