Author Topic: Efficient Plotting of Polynomials  (Read 469 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • Xombie. I am it.
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4450
  • Rating: +702/-6
  • meow :3
    • View Profile
Efficient Plotting of Polynomials
« on: October 28, 2018, 10:32:12 pm »
Hi folks, I wanted to share a technique I came up with for evaluating sequential points of a polynomial, which is especially useful when you are drawing them. A naive approach would be evaluate the whole polynomial at each point, but the method I'll show you allows you to evaluate at a few points, and then for each subsequent point just use additions.

The basic premise is to use ##f(x)## as a starting point to get to ##f(x+1)##. For example, take ##f(x)=3+2x##. To get to ##f(x+1)##, all you have to do is add 2. Things get more complicated as you go to higher degree polynomials. For example, take ##f(x)=3+2x-3x^{2}+x^{3}##. Then to get to ##f(x+1)##, you need to add ##3x^{2}-3x##. However, you can go even further by finding how to get from ##3x^{2}-3x## to ##3(x+1)^{2}-3(x+1)##.

Now comes the theory.

Take ##f_{1}(x)=f(x+1)-f(x)## and ##f_{n+1}(x)=f_{n}(x+1)-f_{n}(x)##.
Then ##f(x+1)=f(x)+f_{1}(x)## and ##f_{n}(x+1)=f_{n}(x)+f_{n+1}(x)##.

##\begin{aligned}
f_{2}(x) &=f_{1}(x+1)-f_{1}(x),\\
&=(f(x+2)-f(x+1))-(f(x+1)-f(x)),\\
&=f(x+2)-2f(x+1)+f(x).
\end{aligned}##


##\begin{aligned}
f_{3}(x)&=f_{2}(x+1)-f_{2}(x),\\
&=(f(x+3)-2f(x+2)+f(x+1))-(f(x+2)-2f(x+1)+f(x)),\\
&=f(x+3)-3f(x+2)+3f(x+1))-f(x).
\end{aligned}##

And in general,
##f_{n}(x)=\sum_{k=0}^{n}{{n\choose k}(-1)^{k}f(x+n-k)}##
If you set ##x=0##:
##f_{n}(0)=\sum_{k=0}^{n}{{n\choose k}(-1)^{k}f(n-k)}##

So now let's take again, ##f(x)=3+2x-3x^{2}+x^{3}##.
##\begin{aligned}
f(0)&=3,\\
f_{1}(0)&=f(1)-f(0)&=0,\\
f_{2}(0)&=f(2)-2f(1)+f(0)&=0,\\
f_{3}(0)&=f(3)-3f(2)+3f(1)-f(0)&=6,\\
f_{k>3}(0)&=0.\\
\end{aligned}##

So what these values allow us to do, ##{3,0,0,6}##, is use a chain of additions to get the next value, instead of evaluating the cubic polynomial at each x:
##\begin{array}{rrrr}
[&3,&0,&0,&6]\\
[&3,&0,&6,&6]\\
[&3,&6,&12,&6]\\
[&9,&18,&18,&6]\\
[&27,&36,&24,&6]\\
[&63,&60,&30,&6]\\
[&123,&90,&36,&6]\\
[&213,&126,&42,&6]\\
...
\end{array}##

Basically, add the second element to the first, third element to the second, and fourth element to the third. The new value is the first. Repeat. So the next iteration would yield [213+126,126+42,42+6,6]=[339,168,48,6], and indeed, f(8)=339.

I'd like to apologise for how garbled this is, I'm really tired.

Also, you should note that for an n-th degree polynomial, you need to compute up to ##f_{n}(x)##, but everything after that is 0.

Offline johnbchron

  • LV2 Member (Next: 40)
  • **
  • Posts: 33
  • Rating: +1/-0
  • RiskALungForDiving
    • View Profile
Re: Efficient Plotting of Polynomials
« Reply #1 on: October 29, 2018, 08:21:07 am »
Dang. I’m gonna use this in my graphing program I think if i can get a handle on it.
Just a dude who is really bored in school... and a huge nerd.
Click here to give me an internet!

Offline Xeda112358

  • Xombie. I am it.
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4450
  • Rating: +702/-6
  • meow :3
    • View Profile
Re: Efficient Plotting of Polynomials
« Reply #2 on: October 29, 2018, 09:27:07 am »
For what it's worth, I did get it to work in TI-BASIC. My program only worked up to degree 8 polynomials (I could extend it; it was just a convenient size).
I'm on mobile atm and AFC, so I'll try to describe my code:

What I did is I computed Y1(Xmin+K∆X), for k from 0 to 8, storing them to a list, then I recombined starting from the end  (the last element is a function of all previous elements and itself) applying that sum.

Then for efficiency, I clipped off any trailing zeros in L1.
I started plotting from Xmin to Xmax with step of ∆X:
Code: [Select]
For(X,Xmin,Xmax,∆X
Pt-On(X,L1(1
For(K,1,N-1
L1(K)+L1(K+1→L1(K
End
End

Note that it doesn't work well for non-polynomials like sine and cosine, but it can do rough estimates. I'm also sure it would fail at poles.

Offline johnbchron

  • LV2 Member (Next: 40)
  • **
  • Posts: 33
  • Rating: +1/-0
  • RiskALungForDiving
    • View Profile
Re: Efficient Plotting of Polynomials
« Reply #3 on: October 29, 2018, 01:56:42 pm »
Nice. I hope that I will have the patience to write an equivalent in ICE for my grapher. Also, for what it's worth, I think in your example it was supposed to be :
f (x) = f (x+1) 3x2 + 3x
Just a dude who is really bored in school... and a huge nerd.
Click here to give me an internet!

Offline Xeda112358

  • Xombie. I am it.
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4450
  • Rating: +702/-6
  • meow :3
    • View Profile
Re: Efficient Plotting of Polynomials
« Reply #4 on: October 29, 2018, 02:04:57 pm »
It is basically 3+2(x+1)-3(x+1)2+(x+1)3-(3+2x-3x2+x3) which should be 3x^2-3x (I hope).

Offline johnbchron

  • LV2 Member (Next: 40)
  • **
  • Posts: 33
  • Rating: +1/-0
  • RiskALungForDiving
    • View Profile
Re: Efficient Plotting of Polynomials
« Reply #5 on: October 29, 2018, 07:31:13 pm »
f (x + 1) = 3 + 2(x + 1) - 3(x + 1)2 + (x + 1)3
f (x + 1) = 3 + 2x + 2 - 3(x2 + 2x + 1) + (x3 + 2x2 + x + x2 + 2x + 1)
f (x + 1) = (x3) + (-3x2 + 2x2 + x2) + (2x - 6x + x + 2x) + (3 + 2 - 3 + 1)
f (x + 1) = x3 - x + 3


it leaves -x, which + 3x = 2x.

I could be completely misunderstanding this though...
Just a dude who is really bored in school... and a huge nerd.
Click here to give me an internet!

Offline Xeda112358

  • Xombie. I am it.
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4450
  • Rating: +702/-6
  • meow :3
    • View Profile
Re: Efficient Plotting of Polynomials
« Reply #6 on: October 29, 2018, 07:39:23 pm »
Your computation of f(x+1) is correct, but then you need to subtract f(x), so:
##
\begin{aligned}
f(x+1)-f(x)&=(x^{3}-x+3)-(x^{3}-3x^{2}+2x+3),\\
&=x^{3}-x+3-x^{3}+3x^{2}-2x-3,\\
&=-3x+3x^{2},\\
&=3x^{2}-3x.\\
\end{aligned}
##

Offline johnbchron

  • LV2 Member (Next: 40)
  • **
  • Posts: 33
  • Rating: +1/-0
  • RiskALungForDiving
    • View Profile
Re: Efficient Plotting of Polynomials
« Reply #7 on: October 30, 2018, 06:17:00 am »
Ah yes, I see now
Just a dude who is really bored in school... and a huge nerd.
Click here to give me an internet!