/* a[1..k] - previous values
** c[1..k+1] - coefficients
**
** Returns an array of results, m+1 elements long (a[1..m]).
** This array is dynamically allocated and must be freed by the
** user.
*/
double* calc_recurrence(int k, double* a, double* c, int m)
{
int i, n;
double* res = malloc((m + 1) * sizeof(*res));
if (!res)
abort();
/* copy a[0..k] to res */
memmove(res, a, (k + 1) * sizeof(double));
/* Compute new elements in the sequence
*/
for (n = k + 1; n <= m; ++n)
{
res[n] = c[n];
for (i = 1; i <= k; ++i)
res[n] += c[i] * res[n - i];
}
return res;
}
Refactorings
No refactoring yet !
Ants
November 2, 2009, November 02, 2009 05:53, permalink
I don't really understand the problem that you are trying to solve (since I don't own that book), but here's a couple quick observations:
If m < k, then the memmove() operation will write past the end of the res array.
Assuming that m >= k:
The second iteration of the outer for() loop will have n == k+2, and thereby accessing c[k+2]. The comments at the beginning of the function say that c[1..k+1], so you'll be reading past the end of the c array.
Is the inner for() loop really suppose to only range from 1..k, rather than 1..k+1 ?
Ants
November 2, 2009, November 02, 2009 05:54, permalink
Strange bug with the website double posted by reply. Strange... Anyway killing this dupe.
getopenid.com/eliben
November 2, 2009, November 02, 2009 16:49, permalink
You're right about the access to c[k+2], it was supposed to be res[n] = c[k + 1]. As for the other, m >= k always, and the inner for loop is OK.
Thanks!
For Jon Bentley's "Programming Pearls", chapter 3 exercise 2