Last digit of polynomial value

There is a simple-looking problem.

Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and integer value $x$, find last digit of polynomial value at point $x$, or, equivalently, $p(x) \mod 10$.

My approach was to use Horner's rule for $p(x)$:

$$ c_{0} + c_{1} x + \dots + c_{n - 1} x^{n - 1} = c_{0} + x \left( c_{1} + x \left( c_{2} + x \left( c_{3} + \dots + x \left( c_{n - 2} + x c_{n - 1} \right) \dots \right) \right) \right) ,$$

but for every multiplication we take current value modulo 10. Here is a Python function implementing this algorithm.

def solve(c, x):
    xmod = x % 10
    value = c[-1] % 10
    for i in range(len(c) - 2, -1, -1):
        value = (value * xmod + c[i]) % 10
    return value

Are there better algorithms in sense of computational complexity (i.e. faster)?

Remainder modulo 10 instead of last digit

What is the last digit of -206? It is 6 by convention. It is not 4, the least positive remainder of -206 divided by 10.

For simplicity, we will compute the value of polynomial modulo 10. We will just say "the remainder of some number" to mean the least positive remainder of that number divided by 10. (The idea and algorithm in this answer can be adapted easily if 10 is replaced by another number.)
Periodicity of the remainders of powers

The remainder of $x, x^2, x^3, x^4, \cdots$ are periodical for any integer $x$. Let $r(n)$ be remainder of $n$.

• $r(x^k)=0$ if $r(x)=0$

• $r(x^k)=1$ if $r(x)=1$

• $r(x^k)=x$ if $r(x)=5,6$

• $r(x^k)=r(x^{k+2})$ if $r(x)=9$

• $r(x^k)=r(x^{k+4})$ if $r(x)=2,3,4,7,8$

$k$ goes over all positive integers if $r(x)=0,2,4,5,6,8$.
$k$ goes over all nonnegative integers if $r(x)=1,3,7,9$.
Algorithm

Because of the periodicity, we can reduce the number of multiplication to at most 4 and the number of modulo operation to 2 without increasing the number of additions.

Here is the algorithm in Python, which should speak for itself. Note for a list lst, lst[s::g] means the subsequence lst[s], lst[s+g], lst[s+2*g], ... all the way to the end.
# c = [c_0, c_1, ..., c_{n-1}]
# remainder([3,12,5], 2) is 7
def remainder(c, x):
x = x % 10

if x == 0:
return c[0] % 10
if x == 1:
return sum(c) % 10
if x == 5 or x == 6:
return (c[0] + sum(c[1:]) * x) % 10
if x == 9:
return (sum(c[::2]) + 9 * sum(c[1::2])) % 10
if x == 2:
return (c[0] + 2 sum(c[1::4]) + 4 sum(c[2::4]) + 8 sum(c[3::4]) + 6 sum(c[4::4])) % 10
if x == 3:
return (sum(c[::4]) + 3 sum(c[1::4]) + 9 sum(c[2::4]) + 7 * sum(c[3::4])) % 10
if x == 4:
return (c[0] + 4 sum(c[1::2]) + 6 sum(c[2::2])) % 10
if x == 7:
return (sum(c[::4]) + 7 sum(c[1::4]) + 9 sum(c[2::4]) + 3 * sum(c[3::4])) % 10
if x == 8:
return (c[0] + 8 sum(c[1::4]) + 4 sum(c[2::4]) + 2 sum(c[3::4]) + 6 sum(c[4::4])) % 10



If remainder(c,x) will be called repeatedly for the same polynomial c, then we can precompute table d[i], where d[i] = remainder(c,i) for i from 0 to 9. Then for that polynomial c, we can return d[x%10] given x in $O(1)$ time.

We can also cache the result on the fly. This can be done nicely by returning a closure that computes each result fully at most once. That is linear time the first time and constant time later on for numbers with the same remainders.
# For example, r = remainder([3,12,5]); print(r(2)); print(r(2));
def remainder(c):
d = [None] * 10

def remainder_c(x):
x = x % 10

if x == 0:
return d[0] if d[0] else c[0] % 10
if x == 1:
return d[1] if d[1] else sum(c) % 10
if x == 5 or x == 6:
return d[x] if d[x] else (c[0] + sum(c[1:]) * x) % 10
if x == 9:
return d[9] if d[9] else (sum(c[::2]) + 9 * sum(c[1::2])) % 10
if x == 2:
return d[2] if d[2] else (c[0] + 2 sum(c[1::4]) + 4 sum(c[2::4]) + 8 sum(c[3::4]) + 6 sum(c[4::4])) % 10
if x == 3:
return d[3] if d[3] else (sum(c[::4]) + 3 sum(c[1::4]) + 9 sum(c[2::4]) + 7 * sum(c[3::4])) % 10
if x == 4:
return d[4] if d[4] else (c[0] + 4 sum(c[1::2]) + 6 sum(c[2::2])) % 10
if x == 7:
return d[7] if d[7] else (sum(c[::4]) + 7 sum(c[1::4]) + 9 sum(c[2::4]) + 3 * sum(c[3::4])) % 10
if x == 8:
return d[8] if d[8] else (c[0] + 8 sum(c[1::4]) + 4 sum(c[2::4]) + 2 sum(c[3::4]) + 6 sum(c[4::4])) % 10

return remainder_c


There are further micro-tuning for various special situations.

If you are interested in parallel algorithm, you can check Estrin's scheme that can speed up the computation.

StackExchange Computer Science Q#104536, answer score: 4