-- Procedure Fig10_46 is a test program for
-- computing the optimal order for performing chained
-- matrix multiplication
with Ada.Text_IO, Ada.Integer_Text_IO;
use Ada.Text_IO, Ada.Integer_Text_IO;
procedure Fig10_46 is
type Array_Of_Int is array( Natural range <> ) of Integer;
type Two_D_Array is array( Natural range <>, Natural range <> ) of Integer;
C : Array_Of_Int( 0..4 ) := ( 50, 10, 40, 30, 5 );
M, Last_Change : Two_D_Array( 1..4, 1..4 );
-- Compute optimal ordering of matrix multiplication
-- C contains number of columns for each of the N matrices
-- C( 0 ) is the number of rows in matrix 1
-- Minimum number of multiplications is left in M( 1, N )
-- Actual ordering can be computed via another procedure
-- using Last_Change
-- M and Last_Change are indexed starting at 1, instead of zero
-- And must be at least ( 1..N, 1..N )
procedure Opt_Matrix( C: Array_Of_Int;
M, Last_Change : in out Two_D_Array ) is
Right, This_M : Integer;
N : Natural := C'Last;
begin
M := ( others => ( others => 0 ) );
Last_Change := M;
for K in 1..N-1 loop -- K is Right-Left
for Left in 1..N-K loop -- For each position
Right := Left + K;
M( Left, Right ) := Integer'Last;
for I in Left..Right-1 loop
This_M := M( Left, I ) + M( I+1, Right )
+ C( Left-1 ) * C( I ) * C( Right );
if This_M < M( Left, Right ) then -- Update min
M( Left, Right ) := This_M;
Last_Change( Left, Right ) := I;
end if;
end loop;
end loop;
end loop;
end Opt_Matrix;
begin
Opt_Matrix( C, M, Last_Change );
for I in 1..4 loop
for J in 1..4 loop
Put( M( I, J ) );
end loop;
New_Line;
end loop;
for I in 1..4 loop
for J in 1..4 loop
Put( Last_Change( I, J ) );
end loop;
New_Line;
end loop;
end Fig10_46;