Optimized Polynomial

[xhantt]

This must work

Code:

sub der(c() as double, d() as double)
  dim i as integer
  dim k as integer

  k = ubound(c)
  for i = 1 to k
    d(i-1) = c(i) * i
  next i
end sub

I think is best to pass the degree of the polinomial as parameter.

[Agamemnus]

what I'd do is I'd use genetic algorithms to create several hundred populations of variables and keep testing them..

[SCM]

Xhant,
That would return the derivative polynomial, but what I was looking for was the value of the derivative at x. Something like

Code:

Function Deriv (x, C())
  code
   "
   "
   "
  Deriv = SomeVariable
end Function

Again looking for an optimized function.

Agamemnus,
You were recently involve in a thread on loop structures. Can you improve Xhantt's polynomial function?

[xhantt]

Ok, i understand, but i will mix the two solutions.

Code:

DEFDBL A-Z

FUNCTION Deriv (x AS DOUBLE, c() AS DOUBLE)
  DIM i AS INTEGER
  DIM k AS INTEGER
  DIM s AS DOUBLE
  DIM xx AS DOUBLE

  s = c(1)  
  k = UBOUND(c)
  xx = 1#
  FOR i = 2 TO k
    xx = xx * x
    s = s + c(i) * i * xx
  NEXT i

  Deriv = s
END FUNCTION

[oracle]

Size of any array (thus the highest power) is:

Code:

UBOUND(array) - LBOUND(array) + 1

Works with array with any starting prefix.

[SCM]

Excellent performance again Xhantt.
Times (1,000,000 iterations): 27.3 sec w/o FFIX and 3.2 sec w/ FFIX.

You beat my optimized derivative (I'll have to improve it).

[Agamemnus]

Code:

DEFDBL A-Z
FUNCTION deriv (x AS DOUBLE, c() AS DOUBLE)
DIM i AS INTEGER, k AS INTEGER, s AS DOUBLE, xx AS DOUBLE
solution = c(1): k = UBOUND(c): xx = 1#: i = 2
1 IF i > k THEN deriv = solution: EXIT FUNCTION
xx = xx * x
solution = solution + c(i) * i * xx
i = i + 1: GOTO 1
END FUNCTION

This could work.

EDIT: put counter in wrong place but it works now.

[SCM]

Sorry for the delay in posting Agamemnus times. I messed up in testing his function, but it is straightened out now.

Code:

w/o FFIX      w/ FFIX
Xhantt's times:     27.2 sec      3.2 sec
Agamemnus' times:   27.8 sec      3.6 sec

These times are on uncompiled code, but the FOR loop seems a little bit faster.

It is also still possible to improve on these times.

[xhantt]

Last try

Code:

DEFDBL A-Z
FUNCTION Deriv2# (x AS DOUBLE, c() AS DOUBLE) STATIC
  DIM i AS INTEGER
  DIM k AS INTEGER
  DIM p AS DOUBLE

  k = UBOUND(c)
  p = c(k) * k
  FOR i = k - 1 TO 1 STEP -1
    p = p * x + c(i) * i
  NEXT i

  Deriv2 = p
END FUNCTION

There's just 2 "mul" instead of 3, to reach just one is another challenge.

[SCM]

This is what I was looking for Xhantt.

Instead of writing polynomials in the conventional way like
ax^3 + bx^2 + cx + d
it is much faster to write them as
((ax + b)x + c)x + d

This is what you did with Deriv2. The results are

Code:

w/o FFIX        w/FFIX
Conventional     35.4 sec        7.9 sec
Deriv  (Xhantt)  27.2 sec        3.2 sec
Deriv2 (Xhantt)  21.7 sec        2.8 sec

You improved an already excellent time.

As far as I know, this is the most efficient way to calculate a polynomial. I suggested this challenge because I wanted to demonstrate the advantages of this method. Unfortunately, not many took any interest in it.

Here are my functions (notice that they do the same thing as yours, though I did it a bit differently)

Code:

DECLARE FUNCTION PofX# (x#, Coef#())
DECLARE FUNCTION dPdx# (x#, Coef#())

DEFDBL A-Z
FUNCTION dPdx (x, Coef())
  P = 0
  FOR j% = UBOUND(Coef) TO 2 STEP -1
    dP = (dP + j% * Coef(j%)) * x
  NEXT
  dPdx = dP + Coef(1)
END FUNCTION

FUNCTION PofX (x, Coef())
  P = 0
  FOR j% = UBOUND(Coef) TO 1 STEP -1
    P = (P + Coef(j%)) * x
  NEXT
  PofX = P + Coef(0)
END FUNCTION

Thank you for participating Xhantt and Agamemnus. Excellent work.

By the way, Xhantt suggested passing the order of the polynomial as a parameter, rather than using UBOUND. He was right. Passing the parameter saves about 3 or 4 tenths of a second off all times. If you are really trying to optimize, don't use UBOUND.