-- 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;