Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

Question

An "algorithm" for calculating $ax+b$ would take the steps

1. Calculate $a$ times $x$
2. Calculate $b$ plus the result of previous line.

But if the values of $a$ and $b$ are known, can we create a more efficient algorithm for the task?

Of course, when $a = 1$, I can optimize the previous algorithm by simply skipping the first step, and when $b = 0$, an optimization would be to skip step 2. But is there always an optimization that I can do?

More formally

Let $originalAlgorithm$ be the two-step algorithm above. What I want is a meta-algorithm, $M$ that $$ M(a,b) = optimizedAlgorithm $$ and, of course, $$ optimizedAlgorithm(x) = originalAlgorithm(x) = ax+b $$ but $optimizedAlgorithm$ is more time-efficient than $originalAlgorithm$.

Answer 1

I would rephrase the question as follows:

Consider the function $F$ and the family of functions $F_{a,b}$ defined as $$F_{a,b}(x) = F(a,b,x) =ax+b.$$
Can we compute $F_{a,b}$ faster than the complexity of $F$?
If yes, given $a$ and $b$, can we algorithmically find such an algorithm?

As babou wrote I think the answer depends on your computation model. Let me explain one case: Consider polynomial size circuits with unbounded fan-in AND, OR, and NOT gates. Time is defined as the depth of the circuit.

$F$ is complete for $\mathsf{TC}^0$, so it requires super-constant depth, the best known upper-bound requires roughly depth $\lg n/\lg \lg n$.

If we fix $a,b$ then $F_{a,b}$ is in $\mathsf{AC^0}$ and therefore can be computed by a constant depth circuit. But the depth is constant only in $n$, not in $a,b$. Can we obtain a dependence of depth on $a$ and $b$ which is better than the more uniform case? The answer is no.

Another model is algebraic circuits with binary plus and times gates and constants. $F$ can be computed in depth $2$. It is easy to see that $F_{a,b}$ cannot be computed in depth $1$.

Now assume a modified algebraic model where we have unbounded fan-in gates. Now $F_{a,b}$ can be computed in depth $1$ by applying addition on $a$ copies of $x$ and one copy of $b$ in one step. $F$ still requires depth $2$.

Answer 2

I think the answer to your question is dependent on the exact setting of your problem, and in particular the representations you intend to use for $a$, $b$, and $x$, as well as the available elementary operations on these representations.

What you want to consider is a partial evaluation of the expression $ax+b$ when $a$ and $b$ are known. As you remarked, there does not seem to be much to be done when the elementary operations are addition and product themselves, except for a few specific values such as the identities of addition and product, in which case partial evaluation can eliminate one of the two operations (or both).

If you express these operation as algorithms on specific representations, you can go further in that direction. For example, if you consider integers represented by sequences of bits (which is not too uncommon), product is then an algorithm that uses shifting and binary additions, depending on the binary representation of $a$. The general algorithm can be specialized for the given value of $a$ and then possibly optimized, according possibly to whathever specificities are discovered. I am not sure how much gain can be expected in this case, but this is how I would start analysing it. This is just partial evaluation applied to the computation expressed at a more elementary level.

This applies more generally to the whole expression, or any expression, when developed into more elementary operations. Note that you do not assert that $a$, $b$, and $x$ are integers, or even real numbers. They could be matrices, for example, or complex numbers.

Answer 3

The expression you want to calculate $ax+b$, independent of a specific model or architecture, using only the algebraic / numeric properties of $a$ and $b$, don't see how it can be computed in another way.

However, as previous answers mention, I will use another way, once you have a model (not a Turing machine, but a concrete model of computation) and representation of the numbers/constants $a$, $b$ a multitude of optimizations can be done.

Examples:

1. Depending on the representation of $a$ and $b$, simple binary shifts and addition can be used (a huge time saving).

2. Alternative multiplication schemes (e.g. Karatsuba multiplication or Russian peasant multiplication). These schemes actually do less operations to calculate a product than the standard definition of multiplication (on a concrete computer model).

3. Partial evaluation is already mentioned, another optimization.

4. If this is to be evaluated recursively, a scheme like Horner's algorithm can be very efficient.

5. If $a$, $b$ ,$x$ are polynomials in $Q[x]$ then FFT (Fast Fourier Transform) can do the callculation in an optimal sense ( $O(NlogN)$ ).

As alternatives to your question