Bash - Multiply Bidimensional Matrix

Question

Supposing that I have bidimensional matrix n x n, and we already know n=4 and values 1 - 16 like

I must multiply the parts like:

Array1*Array2 = result

Array3*result = result1

Array4*result1 = result2

ShowMatrix()
{
echo "MyMatrix is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${myArray[i*n+j]}
done
printf '\n';
done
}

I tried to divide it into 4 parts like in the schema, and assign each part to Array1, Array2, Array3 and Array4

cut1()
{
for((i=0;i<$n/2;i++))do
   for((j=0;j<$n/2;j++))do
Array1[i*n+j]=${myArray[i*n+j]}
done
done
}

cut2()
{
for((i=0;i<$n/2;i++))do
   for((j=$n/2;j<$n;j++))do
Array2[i*n+j]=${myArray[i*n+j]}
done
done
}

cut3()
{
for((i=$n/2;i<$n;i++))do
   for((j=0;j<$n/2;j++))do
Array3[i*n+j]=${myArray[i*n+j]}
done
done
}

cut4()
{
for((i=$n/2;i<$n;i++))do
   for((j=$n/2;j<$n;j++))do
Array4[i*n+j]=${myArray[i*n+j]}
done
done
}

After that, I tried to multiply them like in the schema:

Array1*Array2 = result

Array3*result = result1

Array4*result1 = result2

multiply()
{
 for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
     result[i*n+j]=0
     for((k=0;k<$n;k++))do
let "result[i*n+j]=${result[i*n+j]}+${Array1[i*n+k]}*${Array2[k*n+j]}"
done
done
done
}

multiply1()
{
 for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
     result1[i*n+j]=0
     for((k=0;k<$n;k++))do
let "result1[i*n+j]=${result1[i*n+j]}+${result[i*n+k]}*${Array3[k*n+j]}"
done
done
done
}

multiply2()
{
 for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
     result2[i*n+j]=0
     for((k=0;k<$n;k++))do
let "result2[i*n+j]=${result2[i*n+j]}+${result1[i*n+k]}*${Array4[k*n+j]}"
done
done
done
}

And the results, after I called functions:

cut1
cut2
cut3
cut4
multiply
multiply1
multiply2


echo "result is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${result[i*n+j]}
done
printf '\n';
done

echo "result1 is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${result1[i*n+j]}
done
printf '\n';
done

echo "result2 is:"
for((i=0;i<$n;i++))do
   for((j=0;j<$n;j++))do
printf '  '${result2[i*n+j]}
done
printf '\n';
done

Answer 1

The main conceptual problem with the code as written is that you divide a large array into smaller pieces but then don't adjust for the reduced size of those pieces.

Specifically, one definite bug is in the cut functions. When storing back into Array1..Array3, you are using indices of the larger array rather than reduced array. POSIX shell and bash happily expand missing entries and fill them with zeros. So bash isn't going to help you find your bug here.

Similarly, the multiply functions should only try to multiply the on the bounds of the reduced-sized arrays. By storing a 2D array as a linear array, getting the side of the array is a bit tricker: either you pass the dimensions as I do below, or you can pick up the size from the array (assuming that's been initialized properly) and take the square root.

You mention what you perceive as random behavior. I suspect what's going on here is that dynamic variable look up from your environment or from past execution is feeding values into the various subroutines. To guard against this, I'd declare all local variables inside the function. Of course there the arrays that aren't local, but again, inside the program you should declare these as well.

That is why I think others have suggested you use a more suitable language for doing something like this. And I agree with those assessments.

But if you do have to use POSIX shell, you probably should know and use it better. You can syntax check your code using bash -n. If the code is POSIX compatible, something I highly recommend here, then ksh -n will give you a more thorough and detailed critique of the program.

To help you find bugs in a program of this, kind, I suggest the bash debugger. And for testing the code, I'd suggest Kate Ward's Unit Test program shunit .

I've rewritten the code fixing the bugs. As best as I can tell it follows what you say you want to do and the code that you have. However you've never really described what you are trying to do, or give the expected answer to the specific data you have so I don't have a way independently check things.

The one thing that I would recommend doing but didn't do below is DRY (Do not Repeat Yourself) the code. The 4 cut functions can be folded into a single routine if you pass start and end points and the name of the array you want to store the result in. I think you'd have to use eval here though.

Likewise the 3 multiply functions can be folded into one by passing in the names of the arrays that get worked on.

I have removed duplicate of the array-showing code by beefing up your ShowMatrix routine.

typeset -ir n=4
typeset -a Array=()
typeset -a Array1=()
typeset -a Array2=()
typeset -a Array3=()
typeset -a Array4=()
typeset -a Result=()
typeset -a Result1=()
typeset -a Result2=()


ShowMatrix() {
    typeset arr=$1
    typeset n=$2
    typeset -i i
    echo "Matrix $arr is:"
    for ((i=0;i<n;i++)) ; do
        typeset -i j
        typeset -i val
        for ((j=0;j<n;j++)) ; do
            ((val=${arr}[i*n+j]))
            printf '%5d ' $val
        done
        printf '\n';
    done
}

cut1() {
    typeset -i i
    typeset -i k=0
    for((i=0;i<n/2;i++)) ; do
        typeset -i j
        for((j=0;j<n/2;j++)); do
            ((Array1[k++] = Array[i*n+j]))
        done
    done
}

cut2() {
    typeset -i i
    typeset -i k=0
    for((i=0;i<n/2;i++)) ; do
        typeset -i j
        for((j=n/2;j<n;j++)) ; do
            ((Array2[k++] = Array[i*n+j]))
        done
    done
}

cut3() {
    typeset -i i
    typeset -i k=0
    for((i=n/2;i<n;i++)) ; do
        for((j=0;j<n/2;j++)) ; do
            ((Array3[k++] = Array[i*n+j]))
        done
    done
}

cut4() {
    typeset -i i
    typeset -i k=0
    for((i=n/2;i<n;i++)) ; do
        for((j=n/2;j<n;j++));  do
           ((Array4[k++] = Array[i*n+j]))
        done
    done
}

multiply() {
    typeset -i i
    typeset -i n=$1
    ShowMatrix Array1 $n
    ShowMatrix Array2 $n
    for((i=0;i<n;i++)); do
        typeset -i j
        for((j=0; j < n; j++)); do
            typeset -i l
            ((l=i*n+j))
            ((Result[l]=0))
            typeset -i k
            for((k=0; k<n; k++)) ; do
                    ((Result[l] += Array1[i*n+k]*Array2[k*n+j]))
            done
        done
    done
}

multiply1()
{
    typeset -i n=$1
    ShowMatrix Result $n
    ShowMatrix Array3 $n
    typeset -i i
    for((i=0; i < n; i++)) ; do
        typeset -i j
        for((j=0; j < n; j++)); do
            typeset -i l
            ((l=i*n+j))
            ((Result1[i*n+j]=0))
            typeset -i k
            for ((k=0;k<n;k++));  do
                ((Result1[l] += Result[i*n+k]*Array3[k*n+j]))
            done
        done
    done
}

multiply2() {
    typeset -i i
    typeset -i n=$1
    ShowMatrix Result1 $n
    ShowMatrix Array4 $n
    for ((i=0; i<n; i++)) ; do
        typeset -i j
        for ((j=0; j < n; j++)) ; do
            typeset -i l
            ((l=i*n+j))
            ((Result2[i*n+j]=0))
            typeset -i k
            for((k=0;k<n;k++)); do
                ((Result2[l] += Result1[i*n+k]*Array4[k*n+j]))
            done
        done
    done
}


typeset -i i
for((i=0; i<n*n; i++)) ; do
       ((Array[i]=i+1))
done

cut1
cut2
cut3
cut4

typeset -i n2
((n2 = n / 2))

multiply $n2
multiply1 $n2
multiply2 $n2
ShowMatrix Result2 $n2