What are the trade-offs between the methods? Wouldn't most programs want to implement the algebraic evaluation since there are less recursive calls than method 1?
myxamediyar
NicoV7's question inspired me to calculate the number of stuff De Costeljau's algorithm has to do for a fixed u and v. Correct me if I am wrong please!
Let's say every floating point operation requires the same compute time and uses the same amount of resources and each element in the array takes a unit of memory.
Then I think the calculation would need something like 3(n(n-1)/2) fp operations for every row reduction and then apply 3(m(m-1)/2) operations so in total, 3(mn(n-1)/2) + m(m-1)/2)) fp operations which would need to be performed. I can imagine that intermediary levels in recursion would require copying the arrays over, but let's say we're clever about it and only use the same m + n size array of vectors for every recursive call. Then since de costeljau's algorithm has to perform n-1 recursive calls for input size n, we have m + m * (n-1) = mn recursive calls. So, on top of peforming fp math, it has to do mn + m + n extra stuff.
What are the trade-offs between the methods? Wouldn't most programs want to implement the algebraic evaluation since there are less recursive calls than method 1?
NicoV7's question inspired me to calculate the number of stuff De Costeljau's algorithm has to do for a fixed u and v. Correct me if I am wrong please! Let's say every floating point operation requires the same compute time and uses the same amount of resources and each element in the array takes a unit of memory. Then I think the calculation would need something like 3(n(n-1)/2) fp operations for every row reduction and then apply 3(m(m-1)/2) operations so in total, 3(mn(n-1)/2) + m(m-1)/2)) fp operations which would need to be performed. I can imagine that intermediary levels in recursion would require copying the arrays over, but let's say we're clever about it and only use the same m + n size array of vectors for every recursive call. Then since de costeljau's algorithm has to perform n-1 recursive calls for input size n, we have m + m * (n-1) = mn recursive calls. So, on top of peforming fp math, it has to do mn + m + n extra stuff.