1
$\begingroup$

Binary exponentiation provides an algorithm for calculating a power $a^n$, where you iterate over the binary digits of $a$, and at each step update

$\mathbb{val} \leftarrow \mathbb{val} ^ 2$

$\mathbb{if\ the\ digit\ is\ 1}, \mathbb{val} \leftarrow \mathbb{val} \cdot a$

On the other hand, if you have a Robinson polynomial $P$ (i.e. with coefficients $ \in \{0,1\}$ ), and you want to evaluate it at $x=2$, then applying Horner's method gives you an algorithm, where you iterate over the coefficients of $P$ and at each step update

$\mathbb{val} \leftarrow \mathbb{val} * 2$

$\mathbb{if\ the\ coefficient\ is\ 1}, \mathbb{val} \leftarrow \mathbb{val} + 1$

Both methods provide a "more efficient" implementation of a naive algorithm, and they both seem to have very similar structures. Is there some deeper mathematical relationship going on here? Is this just a coincidence?

$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

You can think of a binary number, say $$1010110_2 = 1*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0*2^0$$

as a Robinson polynomial evaluated at $x = 2$. Lets look exponentiation and apply the Horner Scheme in the exponent:

\begin{align*} \alpha^{1010110_2} &= \alpha^{1*2^6 + 0*2^5 + 1*2^4 + 0*2^3 + 1*2^2 + 1*2^1 + 0*2^0}\\ &=\alpha^{0 +2(1 + 2(1+2(0 +2(1 + 2(0 + 2*1)))))}. \end{align*}

Since the horner scheme is evaluating the nested polynomial "from the inside out" you will get the same result if you apply the repeated squaring procedure: \begin{align*} (10.....) \hspace{0.2cm} v &\leftarrow \alpha^{2} = \alpha^{0 + 2*1}\\ (101....) \hspace{0.2cm} v &\leftarrow \alpha v^2 = \alpha^{1 + 2(0 + 2*1)}\\ (1010...) \hspace{0.2cm} v &\leftarrow v^2 = \alpha^{0+2(1+2(0+2*1))}\\ (10101..) \hspace{0.2cm} v &\leftarrow \alpha v^2 = \alpha^{1 + 2(0+2(1+2(0+2*1)))}\\ (101011.) \hspace{0.2cm} v &\leftarrow \alpha v^2 = \alpha^{1+2(1 + 2(0+2(1+2(0+2*1))))}\\ (1010110) \hspace{0.2cm} v &\leftarrow v^2 = \alpha^{0 + 2(1 + 2(0+2(1+2(0+2*1))))} \end{align*}

$\endgroup$
2
  • $\begingroup$ I see, this is neat, thank you! I still am left wondering if there is some deeper mathematical content that this is scratching the surface of? $\endgroup$ Commented Oct 3 at 0:52
  • $\begingroup$ alternatively take $\log_\alpha$ of the repeated squaring algorithm to get the horners algorithm. I don't think there's anything deeper than this in the connection between the two ideas. However generalizations of the Horner scheme to multiple variables get very deep and complex. $\endgroup$ Commented Oct 3 at 1:00
1
$\begingroup$

The "deep relation" is that those two algorithms are just one, the first being expressed in the exponential domain.

You have the equivalences

$$\times a\leftrightarrow+1\\^2\leftrightarrow\times2$$

E.g. $$a^{110101_b}=((((a^2\times a)^2)^2\times a)^2)^2\times a$$ $$110101_b=((((1\times2+1)\times2)\times2+1)\times2)\times2+1$$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.