Giving infinite as result when using matrix chain multiplication to find the efficient cost

I am trying to understand Matrix Chain Multiplication. Particularly the problem Given a sequence of matrices, find the most efficient way to multiply these matrices together.

I tried the following but it prints some infinite value for the result. What is it that I am doing incorrectly?

const p = [1, 2, 3, 4, 3];

function mcm(m, i, j) {
 if (i >= j) return 0;
 else {
    let ans = Number.MAX_VALUE;
    let temp;
    for (let k = i; k < j - 1; k++) {
       temp = mcm(m, i, k) + mcm(m, k + 1, j) + m[i - 1] * m[k] * m[j];
       if (ans > temp) ans = temp;
    }
    return ans;
 }
}

console.log(mcm(p, 1, p.length - 1));

22 thoughts on “Giving infinite as result when using matrix chain multiplication to find the efficient cost”

  1. The error is in the end-condition for your for loop:

    for (let k = i; k < j - 1; k++) {
    

    It should be:

    for (let k = i; k < j; k++) {
    

    The reason is that j is included in the range to inspect, and so k should go up to and including j-1.

    You are getting near Infinity because there are cases in your code where the loop performs no iterations at all (when j-i==1) and then the function will return Number.MAX_VALUE, which explains the output you get.

    Reply

Leave a Comment