Horner’s method is a technique to evaluate a polynomial

for some value . When implementing this formula in a computer program in the straightforward way, we need multiplications for all the different powers of . A more efficient imperative implementation could of course memorize the “last” power  of  and compute  by . This would then require two multiplications per summand: one to compute  and one for .

In contrast, Horner’s method evaluates the polynomial with  multiplications. It relies on successively factoring out  in the term above, giving:

This becomes more palpable when written down using tail-recursive³“tail-recursive” means that the recursive invocation of a function is the result of the function and is not used in further calculations. equations:

with

The following RISC-V program implements this tail-recursive scheme using a simple loop (and no function calls). The function horner accepts three parameters: A pointer to the begin and end of the coefficient array and . We use register a0 to hold the accumulator  and initialize it to , the first element in the coefficient array. In each iteration of the loop, the accumulator is multiplied by  and added to .

    .text
    .globl horner

    # a0 Coefficients base
    # a1 Coefficients end
    # a2 x
horner:
    mv     t1, a0
    li     a0, 0
    j      horner_head
horner_loop:
    lw     t0, 0(t1)
    mul    a0, a0, a2
    add    a0, a0, t0
    addi   t1, t1, 4
horner_head:
    bne    t1, a1, horner_loop
    ret