I am studying Computer Graphics and need to design an incremental algorithm for solving the polynomial $y = ax^3 + bx^2 + cx + d$, and then implement that in OpenGL. The input will be the values of $a, b,c,d$ and the desired output is a line/curve to be drawn. The values of $x$ would be in the range $1\leq x\leq100$. The algorithm needs to be very efficient hence I am required to use only addition operation, as multiplication is less efficient.

It would be similar to this technique, but here the polynomial to be considered is the one given above. I have searched a lot on the Internet but cannot find the required solution, because most of the examples solve the equation $y = mx+b$.

Can anyone kindly guide me how to solve it or which method should be applied to solve it?

  • $\begingroup$ Can you clarify what you mean by solving it? What are the inputs, and what is the desired output? Are you given the value of $a,b,c,d,y$ and you want to find a value $x$ such that $ax^3+bx^2+cx+d=y$? Can you edit the question to clarify? Also, what do you mean by "not using multiplication"? I don't even know what that means. What does that mean, and where does that requirement come from? Is there some context that would help us understand your needs? $\endgroup$
    – D.W.
    Mar 14 '18 at 18:38
  • $\begingroup$ @D.W. I have edited my question. The inputs will the values of a, b, c, d, and the output would be a line to be drawn. And for making it efficient, we cannot use multiplication but can use addition only. $\endgroup$ Mar 15 '18 at 2:44

You have f(x). Let g(x) = f(x+1) - f(x). Let h(x) = g(x+1) - g(x). Let k(x) = h(x+1) - h(x). It turns out that k(x) is a constant.

Calculate f(x), g(x), h(x) and k(x) for x = 1. Then you calculate f(x+1) = f(x) + g(x), g(x+1) = g(x) + h(x), h(x+1) = h(x) + k(x), and k(x) is a constant.

  • $\begingroup$ It seems like FDX (forward differences) technique, which of course is answer. $\endgroup$
    – Evil
    Mar 14 '18 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.