Qbasicnews.com
January 22, 2020, 05:56:02 AM
 Pages: 1 [2]
 Author Topic: Optimized Polynomial  (Read 6802 times)
SCM
Wandering Guru

Posts: 311

 « Reply #15 on: August 14, 2003, 08:26:52 PM »

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).
 Logged

hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15)

For God so loved the world, that He gave His only begotten Son,
that whoever believes in Him should not perish, but have eternal life.(John 3:16)
Agamemnus
x/ \z

Posts: 3491

 « Reply #16 on: August 14, 2003, 08:27:49 PM »

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.
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
SCM
Wandering Guru

Posts: 311

 « Reply #17 on: August 16, 2003, 06:45:31 AM »

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.
 Logged

hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15)

For God so loved the world, that He gave His only begotten Son,
that whoever believes in Him should not perish, but have eternal life.(John 3:16)
xhantt
Member

Posts: 90

 « Reply #18 on: August 16, 2003, 10:58:18 PM »

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.
 Logged
SCM
Wandering Guru

Posts: 311

 « Reply #19 on: August 17, 2003, 04:24:34 AM »

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.
 Logged

hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15)

For God so loved the world, that He gave His only begotten Son,
that whoever believes in Him should not perish, but have eternal life.(John 3:16)
ak00ma
Ancient Guru

Posts: 669

 « Reply #20 on: August 17, 2003, 05:37:04 AM »

Quote from: "SCM"
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

Oh shit...only a few months ago we had this in math lesson...
 Logged

B 4 EVER
Agamemnus
x/ \z

Posts: 3491

 « Reply #21 on: August 17, 2003, 08:08:25 AM »

Right, because qb needs to find the start memory address and then get the stored number for the length of the array... right?
 Logged

Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
SCM
Wandering Guru

Posts: 311

 « Reply #22 on: August 17, 2003, 02:27:35 PM »

ak00ma wrote:
Quote
Oh @£^\$...only a few months ago we had this in month lesson...
Sorry, I wasn't around a few months ago, and I noticed that people were doing the Maclauren (Taylor) series the conventional way in Oracle's sine challenge.

Agamemnus wrote:
Quote
Right, because qb needs to find the start memory address and then get the stored number for the length of the array... right?
It is even more efficient if you were to do if by hand.  It usually reduces the number of operations.
 Logged

hrist Jesus came into the world to save sinners, of whom I am first.(I Timothy 1:15)

For God so loved the world, that He gave His only begotten Son,
that whoever believes in Him should not perish, but have eternal life.(John 3:16)
 Pages: 1 [2]