<p>While it won't always be the most efficient algorithm, this question has a very close relationship with addition chains; any algorithm for computing $A$ quickly by addition chains translates into an algorithm for computing $f(B) = AB$ by repeated addition (each addition, of course, being an $O(n)$ operation).  Contrariwise, a quick algorithm for computing $AB$ for any $B$ leads to a quick algorithm for computing $A$, but of course this algorithm doesn't necessarily have to have the form of an addition chain; still, that seems like an excellent place to start.  Have a look at <a href="http://en.wikipedia.org/wiki/Addition_chain">http://en.wikipedia.org/wiki/Addition_chain</a> or check out vol. 2 of <i>The Art Of Computer Programming</i> for more details.</p>

CC BY-SA 2.5
2010-10-28T23:45:02.420Z
2010-10-28T23:45:02.420Z
Steven Stadnicki
<p>The paper called <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.162.2268"><strong>Multiplication by a constant is sublinear</strong></a> (<a href="http://www.lirmm.fr/~imbert/pdfs/constmult_arith18.pdf">PDF</a>) gives an algorithm for $\mathcal{O}\left(\frac{n}{\log n}\right)$ shift/addition operations, where $n$ is the size of the constant.</p>

<p>Essentially, it works by looking for the $1$-bits in the constant, shifting and adding the number to be multiplied only for those $1$ bits in the constant (like long multiplication for binary, where a $0$ bit in the bottom number to be multiplied means the top is not shifted and added, while a $1$ bit means the top is shifted and added). However this is still $\mathcal{O}\left(n\right)$, because there can be $\mathcal{O}(n)$ $1$-bits in the constant.</p>

<p>The paper then talks about changing the number representation of the constant into the double-base number system, where apparently, the non-$0$-bits are sparser, if the conversion is done correctly (it is a very redundant number system). They calculate just how sparse it is; the number of non-zero bits is bounded to less than $\mathcal{O}(n)$, thus there is a sublinear number of additions required. However it is still $\mathcal{O}\left(\frac{nm} {\log n}\right)$ actual operations, due to the $\mathcal{O}(m)$ cost of each addition (where $n$ is the size of the constant, and $m$ is the size of the other number).</p>

<p>So to answer your question, yes there is a similar result to matrix-vector multiplication, in that you get a $\log n$ speedup if it is constant; but of course this speedup is only over naive long-multiplication, and there exists multiplication algorithms that are far better than $\mathcal{O}\left(\frac{n^2} {\log n}\right)$ you can get with this algorithm.</p>

CC BY-SA 3.0
2013-10-15T09:52:48.207Z
This appeared in ARITH 2007 as http://dx.doi.org/10.1109/ARITH.2007.24 (for completeness).
András Salamon
CC BY-SA 3.0
2013-10-15T01:53:11.377Z
2013-11-04T03:52:50.637Z
2013-11-04T03:52:50.637Z
Realz Slaw
<p>To expand upon Steven Stadnicki's idea, we can quicky construct a naive algorithm that does better than matrix multiplication using the Discrete Fourier Transform.</p>

<p>We count the number of ones in $A$.  If less than half the bits are ones, we construct a linked list of their positions.  To multiply, we simply shift $B$ left by each position in the list (multiplying by that bit that's represented) and add the results.</p>

<p>If more than half of the bits are ones, we do the same as above, but we use the zeros instead to populate the list of positions.  The idea is that we'll subtract this sum from the sum that would be obtained by multiplying by all ones.  To get the sum of all ones, we shift $B$ by the number of bits in $A$ and subtract $B$ from this.  Then we can subtract our sum obtained from the linked list.</p>

<p>We can call that the naive linked-list algorithm.  Its running time is $O(n^2)$ in the worst case, but $O(|B| \sqrt{\frac{|A|}{2\pi}})$ in the average case, which is faster than DFT for small $|A|$.</p>

<p>To use the idea of lists optimally, we use divide-and-conquer.  We split $A$ in half, and find the sizes of the associated lists using the naive algorithm.  If they're greater than 5, we call the naive algorithm again on halves greater than 5 until we manage to cut all halves to less than five.  (This is because we can reduce this to 4 subtractions)</p>

<p>Even better still, we improve our divide-and-conquer algorithm.  We iterate through all possible combinations of branching, greedily picking the best one.  This preprocessing takes approximately the same time as the actual multiplication.</p>

<p>If we are allowed infinite freedom with pre-processing, we solve the optimized divide-and-conquer algorithm for all branches optimally.  This takes time $O(2^{|A|})$ in the worst case, but it should be ~optimal by addition chain methods.</p>

<p>I'm working on calculating more exact values for the above algorithms.</p>

CC BY-SA 2.5
2010-11-08T08:11:20.580Z
Hi Matt: What is $|A|$ and $|B|$?
Turbo
CC BY-SA 2.5
2010-11-17T17:03:16.153Z
$|A|$ is the size of $A$, basically the number of elements in $A$.  This is equivalent to your $n$, i.e. $|A| \equiv n$.  The same for $|B|$.  However, this formula still holds when $n$ is different for $A$ and $B$.
Matt Groff
CC BY-SA 2.5
2010-10-29T03:13:46.627Z
2010-10-29T09:42:56.067Z
2010-10-29T09:42:56.067Z
Matt Groff
<p>As suggested by Matt Groff, you may be interested to look into the practice community for inspirations (or if $n$ in your situation is within the bit width of a current CPU). Indeed, the problem of integer multiplication by a constant has been considered by many compiler writers and circuit designers, although they are usually interested in "multipler-less multipler" (multiply using shift, add, and subtract). One of the early references I am aware of is (I learned this from Hacker's Delight section 8.4.):</p>

<p>Bernstein, R. (1986), Multiplication by integer constants. Software: Practice and Experience, 16: 641–652. <a href="http://onlinelibrary.wiley.com/doi/10.1002/spe.4380160704/abstract">doi: 10.1002/spe.4380160704</a></p>

<p>More modern work by Vincent Lefèvre can be found <a href="http://www.vinc17.org/research/mulbyconst/index.en.html">here</a> (be sure to see follow-up works to his), and he also notes a CMU project on <a href="http://www.spiral.net/hardware/multless.html">efficient circuit synthesis</a> (see the references there). The latter project even considers simultaneous multiplication by a set of constants.</p>

<p>P.S. I encourage you to consider changing your username to something recognizable.</p>

CC BY-SA 2.5
2010-10-30T02:21:38.240Z
2010-10-30T02:21:38.240Z
Maverick Woo
<p>I am not sure whether this is directly relevant to the question, but the following elementary result might be of interest. Given a fixed natural number $k$, the operation $n \to kn$ can be realized by a sequential automaton, provided that $n$ is written in reversed binary notation (that is, Least Significant Bit First). The number of states of the automaton is $k/2^r$ where $2^r$ is the largest power of $2$ dividing $k$. For instance, the operation $n \to 6n$ is realized by the following automaton.
<a href="https://i.sstatic.net/lhbmw.gif" rel="noreferrer"><img src="https://i.sstatic.net/lhbmw.gif" alt="enter image description here"></a></p>

<p>For instance, $185 = 1 + 8 + 16 + 32 + 128$ and $6 \times 185 = 1110 = 2 + 4 + 16 + 64 + 1024$. Thus, in reverse binary, $185$ is written as $10011101$ and $1110$ (bad choice, I know...) as $01101010001$. Processing the entry $\color{red}{10011101}$ on this automaton gives the path 
$$
\xrightarrow{\color{green}0} 
0 \xrightarrow{\color{red}1\mid \color{blue}1} 
1 \xrightarrow{\color{red}0\mid \color{blue}1} 
0 \xrightarrow{\color{red}0\mid \color{blue}0} 
0 \xrightarrow{\color{red}1\mid \color{blue}1} 
1 \xrightarrow{\color{red}1\mid \color{blue}0} 
2 \xrightarrow{\color{red}1\mid \color{blue}1} 
2 \xrightarrow{\color{red}0\mid \color{blue}0} 
1 \xrightarrow{\color{red}1\mid \color{blue}0} 
2 \xrightarrow{\color{green}{01}}
$$
which gives the correct output $\color{blue}{01101010001}$.
The type of sequential automaton I am using here was called <em>subsequential</em> by Schützenberger: as you can see there is an <em>initial prefix</em> (in green) and a <em>terminal output function</em> (also in green). For more details how this sequential machine can be computed in a systematic way, see this <a href="http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Exposes/Sequential.pdf" rel="noreferrer">link</a>.</p>

CC BY-SA 3.0
2015-08-17T02:49:18.827Z
The construction of a sequential automaton realizing the operation $n \to kn$ can be done for any $k$. However, computing this automaton might be easier for $k$ prime.
J.-E. Pin
CC BY-SA 3.0
2015-08-17T02:51:10.143Z
$\frac{k}{2^r}$ is exponential.
Turbo
CC BY-SA 3.0
2015-08-17T03:17:03.530Z
$k$ is a fixed constant, not related to $n$.
J.-E. Pin
CC BY-SA 3.0
2015-08-16T20:07:21.217Z
2015-08-16T20:07:21.217Z
J.-E. Pin
<p><span class="math-container">$n$</span> is a parameter in the problem.</p>
<p>For every <span class="math-container">$n$</span> we pick a random integer <span class="math-container">$a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$</span> where <span class="math-container">$n\in\{1,2,\dots\}$</span>.</p>
<p><strong>Problem</strong>: Given <span class="math-container">$n$</span> what is the complexity of multiplication function <span class="math-container">$f_n(x)=a_nx$</span> where <span class="math-container">$x\in\{0,1,\dots,2^n-1\}$</span>?</p>
<p>One is allowed to pre-process integers <span class="math-container">$a_n$</span> as appropriate.</p>
<p><strong>Upper Bound:</strong> We already have two different <span class="math-container">$n^{1+\epsilon}$</span> complexity algorithms by <span class="math-container">$\mathsf{FFT}$</span> and extension of Karatsuba.</p>
<p>The query here is whether <span class="math-container">$\epsilon=0$</span> by anything cleverer?</p>
<p><strong>Conjecture:</strong> <span class="math-container">$\exists c&gt;0,n_0&gt;0$</span> such that at every <span class="math-container">$n\in\mathbb Z_{&gt;n_0}$</span> the number of constants <span class="math-container">$a_n$</span> where <span class="math-container">$\epsilon=0$</span> is supported is <span class="math-container">$&gt;2^{cn}$</span>.</p>

CC BY-SA 2.5
2010-10-28T08:28:59.867Z
Given $A$, just construct a lookup table with $2^n$ entries. (Obviously this isn't what you wanted, but I think you should make your requirements more specific...)
Jukka Suomela
CC BY-SA 2.5
2010-10-28T09:06:53.830Z
I think that the question makes perfect sense in the standard Boolean circuit model.
Noam
CC BY-SA 2.5
2010-10-28T14:27:50.683Z
Could you summarize the obvious upper and lower bounds, and the best results that you are aware of? It shows that you care about the problem and that you've thought about it, and it gives everyone else more incentive to think about your problem.
Robin Kothari
CC BY-SA 2.5
2010-10-28T16:14:31.907Z
I think the asker implicitly means that the preprocessed part must take only $n^{O(1)}$ space. (The matrix-vector mult has that property.)
Ryan Williams
<cc.complexity-theory><ds.algorithms><circuit-complexity><algebraic-complexity><arithmetic-circuits>
Integer multiplication when one integer is fixed
Turbo
# Integer multiplication when one integer is fixed

(Asked by: username_0 on 2010-10-28)

$n$ is a parameter in the problem.

For every $n$ we pick a random integer $a\_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.

**Problem**: Given $n$ what is the complexity of multiplication function $f\_n(x)=a\_nx$ where $x\in\{0,1,\dots,2^n-1\}$?

One is allowed to pre-process integers $a\_n$ as appropriate.

**Upper Bound:** We already have two different $n^{1+\epsilon}$ complexity algorithms by $\mathsf{FFT}$ and extension of Karatsuba.

The query here is whether $\epsilon=0$ by anything cleverer?

**Conjecture:** $\exists c>0,n\_0>0$ such that at every $n\in\mathbb Z\_{>n\_0}$ the number of constants $a\_n$ where $\epsilon=0$ is supported is $>2^{cn}$.

**Tags:** cc.complexity-theory, ds.algorithms, circuit-complexity, algebraic-complexity, arithmetic-circuits

> **Comments:**
> **username_1**: Given $A$, just construct a lookup table with $2^n$ entries. (Obviously this isn't what you wanted, but I think you should make your requirements more specific...)  
> **username_2**: I think that the question makes perfect sense in the standard Boolean circuit model.  
> **username_3**: Could you summarize the obvious upper and lower bounds, and the best results that you are aware of? It shows that you care about the problem and that you've thought about it, and it gives everyone else more incentive to think about your problem.  
> **username_4**: I think the asker implicitly means that the preprocessed part must take only $n^{O(1)}$ space. (The matrix-vector mult has that property.)  

---

## 5 answers

### Answer by username_5 on 2010-10-28. Score: 21

While it won't always be the most efficient algorithm, this question has a very close relationship with addition chains; any algorithm for computing $A$ quickly by addition chains translates into an algorithm for computing $f(B) = AB$ by repeated addition (each addition, of course, being an $O(n)$ operation). Contrariwise, a quick algorithm for computing $AB$ for any $B$ leads to a quick algorithm for computing $A$, but of course this algorithm doesn't necessarily have to have the form of an addition chain; still, that seems like an excellent place to start. Have a look at <http://en.wikipedia.org/wiki/Addition_chain> or check out vol. 2 of *The Art Of Computer Programming* for more details.


---

### Answer by username_6 on 2013-10-15. Score: 19

The paper called [**Multiplication by a constant is sublinear**](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.162.2268) ([PDF](http://www.lirmm.fr/~imbert/pdfs/constmult_arith18.pdf)) gives an algorithm for $\mathcal{O}\left(\frac{n}{\log n}\right)$ shift/addition operations, where $n$ is the size of the constant.

Essentially, it works by looking for the $1$-bits in the constant, shifting and adding the number to be multiplied only for those $1$ bits in the constant (like long multiplication for binary, where a $0$ bit in the bottom number to be multiplied means the top is not shifted and added, while a $1$ bit means the top is shifted and added). However this is still $\mathcal{O}\left(n\right)$, because there can be $\mathcal{O}(n)$ $1$-bits in the constant.

The paper then talks about changing the number representation of the constant into the double-base number system, where apparently, the non-$0$-bits are sparser, if the conversion is done correctly (it is a very redundant number system). They calculate just how sparse it is; the number of non-zero bits is bounded to less than $\mathcal{O}(n)$, thus there is a sublinear number of additions required. However it is still $\mathcal{O}\left(\frac{nm} {\log n}\right)$ actual operations, due to the $\mathcal{O}(m)$ cost of each addition (where $n$ is the size of the constant, and $m$ is the size of the other number).

So to answer your question, yes there is a similar result to matrix-vector multiplication, in that you get a $\log n$ speedup if it is constant; but of course this speedup is only over naive long-multiplication, and there exists multiplication algorithms that are far better than $\mathcal{O}\left(\frac{n^2} {\log n}\right)$ you can get with this algorithm.

> **Comments:**
> **username_7**: This appeared in ARITH 2007 as http://dx.doi.org/10.1109/ARITH.2007.24 (for completeness).  

---

### Answer by username_8 on 2010-10-29. Score: 17

To expand upon username_5's idea, we can quicky construct a naive algorithm that does better than matrix multiplication using the Discrete Fourier Transform.

We count the number of ones in $A$. If less than half the bits are ones, we construct a linked list of their positions. To multiply, we simply shift $B$ left by each position in the list (multiplying by that bit that's represented) and add the results.

If more than half of the bits are ones, we do the same as above, but we use the zeros instead to populate the list of positions. The idea is that we'll subtract this sum from the sum that would be obtained by multiplying by all ones. To get the sum of all ones, we shift $B$ by the number of bits in $A$ and subtract $B$ from this. Then we can subtract our sum obtained from the linked list.

We can call that the naive linked-list algorithm. Its running time is $O(n^2)$ in the worst case, but $O(|B| \sqrt{\frac{|A|}{2\pi}})$ in the average case, which is faster than DFT for small $|A|$.

To use the idea of lists optimally, we use divide-and-conquer. We split $A$ in half, and find the sizes of the associated lists using the naive algorithm. If they're greater than 5, we call the naive algorithm again on halves greater than 5 until we manage to cut all halves to less than five. (This is because we can reduce this to 4 subtractions)

Even better still, we improve our divide-and-conquer algorithm. We iterate through all possible combinations of branching, greedily picking the best one. This preprocessing takes approximately the same time as the actual multiplication.

If we are allowed infinite freedom with pre-processing, we solve the optimized divide-and-conquer algorithm for all branches optimally. This takes time $O(2^{|A|})$ in the worst case, but it should be ~optimal by addition chain methods.

I'm working on calculating more exact values for the above algorithms.

> **Comments:**
> **username_0**: Hi Matt: What is $|A|$ and $|B|$?  
> **username_8**: $|A|$ is the size of $A$, basically the number of elements in $A$.  This is equivalent to your $n$, i.e. $|A| \equiv n$.  The same for $|B|$.  However, this formula still holds when $n$ is different for $A$ and $B$.  

---

### Answer by username_9 on 2010-10-30. Score: 10

As suggested by username_8, you may be interested to look into the practice community for inspirations (or if $n$ in your situation is within the bit width of a current CPU). Indeed, the problem of integer multiplication by a constant has been considered by many compiler writers and circuit designers, although they are usually interested in "multipler-less multipler" (multiply using shift, add, and subtract). One of the early references I am aware of is (I learned this from Hacker's Delight section 8.4.):

Bernstein, R. (1986), Multiplication by integer constants. Software: Practice and Experience, 16: 641–652. [doi: 10.1002/spe.4380160704](http://onlinelibrary.wiley.com/doi/10.1002/spe.4380160704/abstract)

More modern work by Vincent Lefèvre can be found [here](http://www.vinc17.org/research/mulbyconst/index.en.html) (be sure to see follow-up works to his), and he also notes a CMU project on [efficient circuit synthesis](http://www.spiral.net/hardware/multless.html) (see the references there). The latter project even considers simultaneous multiplication by a set of constants.

P.S. I encourage you to consider changing your username to something recognizable.


---

### Answer by username_10 on 2015-08-16. Score: 9

I am not sure whether this is directly relevant to the question, but the following elementary result might be of interest. Given a fixed natural number $k$, the operation $n \to kn$ can be realized by a sequential automaton, provided that $n$ is written in reversed binary notation (that is, Least Significant Bit First). The number of states of the automaton is $k/2^r$ where $2^r$ is the largest power of $2$ dividing $k$. For instance, the operation $n \to 6n$ is realized by the following automaton.
[![enter image description here](https://i.sstatic.net/lhbmw.gif)](https://i.sstatic.net/lhbmw.gif)

For instance, $185 = 1 + 8 + 16 + 32 + 128$ and $6 \times 185 = 1110 = 2 + 4 + 16 + 64 + 1024$. Thus, in reverse binary, $185$ is written as $10011101$ and $1110$ (bad choice, I know...) as $01101010001$. Processing the entry $\color{red}{10011101}$ on this automaton gives the path
$$
\xrightarrow{\color{green}0}
0 \xrightarrow{\color{red}1\mid \color{blue}1}
1 \xrightarrow{\color{red}0\mid \color{blue}1}
0 \xrightarrow{\color{red}0\mid \color{blue}0}
0 \xrightarrow{\color{red}1\mid \color{blue}1}
1 \xrightarrow{\color{red}1\mid \color{blue}0}
2 \xrightarrow{\color{red}1\mid \color{blue}1}
2 \xrightarrow{\color{red}0\mid \color{blue}0}
1 \xrightarrow{\color{red}1\mid \color{blue}0}
2 \xrightarrow{\color{green}{01}}
$$
which gives the correct output $\color{blue}{01101010001}$.
The type of sequential automaton I am using here was called *subsequential* by Schützenberger: as you can see there is an *initial prefix* (in green) and a *terminal output function* (also in green). For more details how this sequential machine can be computed in a systematic way, see this [link](http://www.liafa.univ-paris-diderot.fr/~jep/PDF/Exposes/Sequential.pdf).

> **Comments:**
> **username_10**: The construction of a sequential automaton realizing the operation $n \to kn$ can be done for any $k$. However, computing this automaton might be easier for $k$ prime.  
> **username_0**: $\frac{k}{2^r}$ is exponential.  
> **username_10**: $k$ is a fixed constant, not related to $n$.  

---

