## Thursday, October 15, 2015

### Cheeky and efficient maths algorithm

There is a very efficient algorithm in Breeze for calculating polynomials. That is, say you have an equation like:

10x3 + 5x2 + 3x + 1

and you want to find the answer for a given x. You could of course calculate x to the power of 3, times it by 10 add this to 5 times x to the power of 2 etc etc...

But a much more efficient way is to observe that the very same equation can be written:

( ( (10 * x) + 5) * x ) + 3 ) * x ) + 1

and run this code:

var i = coefs.length-1
var p = coefs(i)
while (i>0) {
i -= 1
p = p*x + coefs(i)
}

where coefs are the array of numbers that come before the xs, in our case 10, 5, 3 and 1 (note that the 1 is actually 1 x0  = 1). The answer at the end is in the var p.

The code uses vars which are generally considered bad practise but there is an argument for being pragmatic too. We could have been more functional and written:

coefs.drop(1).foldRight(0d)(
(coeff, agg) => (agg + coeff) * x
) + coefs(0)

But it is debatable if it's any nicer.