expected type "..." defined at ....... error in Ada

Question

I have such a Karatsuba algorithm implementation I have written in ADA.

   procedure Karatsuba (Factor_1, Factor_2 : in Number; Product : out Number) is
      m : Integer;
      m2 : Integer;
      low1 : Number := (0,1);
      high1 : Number := (0,1);
      low2 : Number := (0,1);
      high2 : Number := (0,1);
      z0 : Index;
      z1 : Index;
      z2 : Index;
      x : Integer;
      y : Integer;
      hc1 : Index;
      hc2 : Index;
   begin
      low1 := (others => 0);
      high1 := (others => 0);
      low2 := (others => 0);
      high2 := (others => 0);  
      if Factor_1'Length = 1 or Factor_2'Length = 1 then
         Standard(Factor_1, Factor_2,Product);
      end if;
      -- calculates the size of the numbers
      m := Integer'Max(Factor_1'Length, Factor_2'Length);
      m2 := m / 2;
      -- split the digit sequences about the middle
      for Factor_1_Index in Factor_1'Range loop
         x := x + 1;
         if x <= m2 then
            low1(Factor_1_Index) := Factor_1(Factor_1_Index);
         else
            high1(hc1) := Factor_1(Factor_1_Index);
            hc1 := hc1 + 1;
         end if;
      end loop;
      for Factor_2_Index in Factor_2'Range loop
         y := y + 1;
         if y <= m2 then
            low2(Factor_2_Index) := Factor_2(Factor_2_Index);
         else
            high2(hc2) := Factor_2(Factor_2_Index);
            hc2 := hc2 + 1;
         end if;
      end loop;
      -- 3 calls made to numbers approximately half the size
      z0 := Karatsuba(low1, low2, Product);
      z1 := Karatsuba((low1 + high1), (low2 + high2), Product);
      z2 := Karatsuba(high1, high2, Product);
      Product := (z2*10**(2*m2))+((z1-z2-z0)*10**(m2))+(z0);
   end Karatsuba;

On the last 4 lines before "end Karatsuba" line, I get the error "expected type 'Index' defined at ...". The errors I'm receiving are, respectively,

expected type "Index" defined at ....
found package or procedure name
there is no applicable operator "+" for type "Number" defined at ......

This is another class that I have assigned some variables:

package ITI8590.Natural_Number_Multiplication is

   type Digit  is range 0 .. 1;
   type Index  is new Positive;
   type Number is array (Index range <>) of Digit;

   for Digit'Size use 1;

   procedure Standard(Factor_1, Factor_2 : in Number; Product : out Number);
   procedure Karatsuba(Factor_1, Factor_2 : in Number; Product : out Number);

end ITI8590.Natural_Number_Multiplication;

Now why I get this error? I couldn't solve it, and I'm stuck in it. Could you help me?

Thanks,

Surely you got more than just that one error message. Please copy-and-paste the entire error message into the question. Karatsuba is a procedure; it doesn't return a value. You're trying to assign its return value to z0, z1, and z2. (BTW, the name of the language is Ada, not ADA. It's not an acronym; it's names after a person.) — Keith Thompson
The error message there is no applicable operator "+" for type "Number" probably means that there is no operator "+" for the type "Number". Which there isn't. Number is an array. Ada does not automatically define numeric operators for arrays that operate on corresponding elements. You can write one yourself, though. — ajb
@ajb: I’m not sure what the format of Number actually corresponds to, but I suspect it’s a representation of binary. In which case the operators are going to be more than ‘operating on corresponding elements’. — Simon Wright

Simon Wright Simon Wright · Accepted Answer · 2015-03-13T14:22:28

Karatsuba is a procedure, so at the end instead of

  z0 := Karatsuba(low1, low2, Product);
  z1 := Karatsuba((low1 + high1), (low2 + high2), Product);
  z2 := Karatsuba(high1, high2, Product);

it should probably read

  Karatsuba(low1, low2, z0);
  Karatsuba((low1 + high1), (low2 + high2), z1);
  Karatsuba(high1, high2, z2);

which requires you to declare z0, z1, z2 as Number rather than Index. Note, Product is an out parameter to the procedure, so all your code achieved was to overwrite it twice with intermediate results (3 times, counting the call to Standard above).

But then you have a problem: the compiler says

yusuf.ada:25:12: unconstrained subtype not allowed (need initialization)
yusuf.ada:25:12: provide initial value or explicit array bounds

which is calling for something related to the way you have declared low1 etc:

  low1 : Number := (0,1);
  high1 : Number := (0,1);
  low2 : Number := (0,1);
  high2 : Number := (0,1);

The trouble with this approach is that you’ve now constrained the bounds of the variables: low1 is fixed to have 2 elements (set to values that you then overwrite), and can’t be expanded. I don’t know how the algorithm is supposed to work, but this seems unlikely to be right; for a start, what happens if the inputs have more than 2 digits?

One approach that might work is to use the number of digits in the input parameters:

Max_Digits : constant Positive := Factor_1’Length + Factor_2’length;
pragma Assert (Product’Length >= Max_Digits, “possible overflow”);
low1 : Number (1 .. Max_Digits) := (others => 0);

etc.

And, as ajb has commented, you’ll need to define operators +, -, *, ** between Numbers and Integers as needed, particularly in the expression (z2*10**(2*m2))+((z1-z2-z0)*10**(m2))+(z0) in the last line of the procedure.

expected type "..." defined at ....... error in Ada

1 Answers