<p>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.</p>

<p>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 <strong><a href="http://en.wikipedia.org/wiki/Partial_evaluation" rel="nofollow">partial evaluation</a></strong>
can eliminate one of the two operations (or both).</p>

<p>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 <strong>partial
evaluation</strong> applied to the computation expressed at a more elementary
level.</p>

<p>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.</p>

CC BY-SA 3.0
2014-05-23T21:05:04.420Z
2014-06-04T19:44:46.833Z
2014-06-04T19:44:46.833Z
babou
<p>I would rephrase the question as follows: </p>

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

<p>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.</p>

<p>$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$.</p>

<p>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.</p>

<p>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$.</p>

<p>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$.</p>

CC BY-SA 3.0
2014-05-24T06:12:51.070Z
2014-05-24T06:19:21.730Z
2014-05-24T06:19:21.730Z
Kaveh
<p>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.</p>

<p>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.</p>

<p>Examples:</p>

<ol>
<li><p>Depending on the representation of $a$ and $b$, simple binary shifts and addition can be used (a huge time saving).</p></li>
<li><p>Alternative multiplication schemes (e.g. <a href="http://en.wikipedia.org/wiki/Karatsuba_algorithm" rel="nofollow">Karatsuba multiplication</a> or <a href="http://en.wikipedia.org/wiki/Russian_peasant_multiplication#Russian_peasant_multiplication" rel="nofollow">Russian peasant multiplication</a>). These schemes actually do less operations to calculate a product than the standard definition of multiplication (on a concrete computer model).</p></li>
<li><p>Partial evaluation is already mentioned, another optimization.</p></li>
<li><p>If this is to be evaluated recursively, a scheme like Horner's algorithm can be very efficient.</p></li>
<li><p>If $a$, $b$ ,$x$ are polynomials in $Q[x]$ then FFT (<a href="http://en.wikipedia.org/wiki/Fast_Fourier_transform" rel="nofollow">Fast Fourier Transform</a>) can do the callculation in an optimal sense ( $O(NlogN)$ ).</p></li>
</ol>

<p>As alternatives to your question</p>

CC BY-SA 3.0
2014-05-26T20:33:53.490Z
2014-06-04T19:44:37.267Z
2014-06-04T19:44:37.267Z
Nikos M.
<p>An "algorithm" for calculating $ax+b$ would take the steps</p>

<ol>
<li>Calculate <em>$a$ times $x$</em></li>
<li>Calculate <em>$b$ plus the result of previous line</em>.</li>
</ol>

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

<p>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?</p>

<h3>More formally</h3>

<p>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$.</p>

CC BY-SA 3.0
2014-05-25T07:19:29.843Z
Do you know the answer or have any references for the easier problems of (1) speeding up $a\cdot x$ or (2) speeding up $x + b$?
usul
CC BY-SA 3.0
2014-05-30T22:14:28.530Z
seems close to [integer multiplication when one integer is fixed](http://cstheory.stackexchange.com/questions/2517/integer-multiplication-when-one-integer-is-fixed)
vzn
<cc.complexity-theory><ds.algorithms><optimization><time-complexity>
Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?
bruno
# Is it possible to optimize the calculation of $ax+b$ once I know $a$ and $b$?

(Asked by: username_0 on 2014-05-23)

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$.

**Tags:** cc.complexity-theory, ds.algorithms, optimization, time-complexity
> **Comments:**
> **username_1**: Do you know the answer or have any references for the easier problems of (1) speeding up $a\cdot x$ or (2) speeding up $x + b$?  
> **username_2**: seems close to [integer multiplication when one integer is fixed](http://cstheory.stackexchange.com/questions/2517/integer-multiplication-when-one-integer-is-fixed)  

---

## 3 answers

### Answer by username_4 on 2014-05-24. Score: 10

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 by username_3 on 2014-05-23. Score: 8

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](http://en.wikipedia.org/wiki/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 by username_5 on 2014-05-26. Score: 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](http://en.wikipedia.org/wiki/Karatsuba_algorithm) or [Russian peasant multiplication](http://en.wikipedia.org/wiki/Russian_peasant_multiplication#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](http://en.wikipedia.org/wiki/Fast_Fourier_transform)) can do the callculation in an optimal sense ( $O(NlogN)$ ).

As alternatives to your question


---

