Ada - Long (Grade-School) Умножение целых чисел BigNum

Question

Я пытаюсь реализовать алгоритм умножения Grade-School в Ada, и в настоящее время я получаю ошибку индексации из границ. Я был бы признателен за любую информацию о том, как исправить ошибку и успешно реализовать алгоритм. Заранее спасибо!

У меня есть посылка BigNumPkg который определяет type BigNum is array(0..Size - 1) of Integer;

Функция, которую я сейчас пытаюсь реализовать, выглядит следующим образом:

FUNCTION "*" (X, Y : BigNum) RETURN BigNum IS
  Product : BigNum:= Zero;
  Carry : Natural := 0;
  Base : Constant Integer := 10;
BEGIN
  FOR I IN REVERSE 0..Size-1 LOOP
     Carry := 0;
     FOR N IN REVERSE 0..Size-1 LOOP
        Product(N + I - 1) := Product(N + I - 1) + Carry + X(N) * Y(I);
        Carry := Product(N + I -1) / Base;
        Product(N + I -1) := Product(N +I-1) mod Base;
     END LOOP;
     Product(I+Size-1) := Product(I+Size-1) + Carry;
  END LOOP;
  RETURN Product;
END "*"; 

Answer 1

Спецификация упаковки:

package Big_Integer is

   Base : constant := 10;
   Size : constant := 3;

   type Extended_Digit is range 0 .. Base * Base;
   subtype Digit is Extended_Digit range 0 .. Base - 1;

   type Instance is array (0 .. Size - 1) of Digit;

   function "*" (Left, Right : in Instance) return Instance;

   function Image (Item : in Instance) return String;

end Big_Integer;

Вы, конечно, можете настроить параметры по мере необходимости, но они хороши для ручной проверки результатов. Обратите внимание, что я не уверен, что диапазон Extended_Digit правильно, но, похоже, работает в этом случае.

Реализация пакета:

with Ada.Strings.Unbounded;

package body Big_Integer is

   function "*" (Left, Right : in Instance) return Instance is
      Carry : Extended_Digit := 0;
      Sum   : Extended_Digit;
   begin
      return Product : Instance := (others => 0) do
         for I in Left'Range loop
            for J in Right'Range loop
               if I + J in Product'Range then
                  Sum := Left (I) * Right (J) + Carry + Product (I + J);

                  Product (I + J) := Sum mod Base;
                  Carry           := Sum / Base;
               else
                  Sum := Left (I) * Right (J) + Carry;

                  if Sum = 0 then
                     Carry := 0;
                  else
                     raise Constraint_Error with "Big integer overflow.";
                  end if;
               end if;
            end loop;

            if Carry /= 0 then
               raise Constraint_Error with "Big integer overflow.";
            end if;
         end loop;
      end return;
   end "*";

   function Image (Item : in Instance) return String is
      Buffer : Ada.Strings.Unbounded.Unbounded_String;
   begin
      for E of reverse Item loop
         Ada.Strings.Unbounded.Append (Buffer, Digit'Image (E));
      end loop;

      return Ada.Strings.Unbounded.To_String (Buffer);
   end Image;

end Big_Integer;

Тестовый водитель:

with Ada.Text_IO;

with Big_Integer;

procedure Use_Big_Integers is
   use all type Big_Integer.Instance;

   procedure Multiply (A, B : in     Big_Integer.Instance);

   procedure Multiply (A, B : in     Big_Integer.Instance) is
      use Ada.Text_IO;
   begin
      Put (Image (A));
      Put (" * ");
      Put (Image (B));
      Put (" = ");
      Put (Image (A * B));
      New_Line;
   exception
      when Constraint_Error =>
         Put_Line ("Constraint_Error");
   end Multiply;

begin
   Multiply (A => (0 => 1, others => 0),
             B => (others => Big_Integer.Digit'Last));

   Multiply (A => (0 => Big_Integer.Digit'Last, others => 0),
             B => (0 => Big_Integer.Digit'Last, others => 0));

   Multiply (A => (0 => 2, others => 0),
             B => (others => Big_Integer.Digit'Last));

   Multiply (A => (2 => 0, 1 => 1, 0 => 2),
             B => (2 => 0, 1 => 4, 0 => 5));

   Multiply (A => (2 => 0, 1 => 2, 0 => 2),
             B => (2 => 0, 1 => 4, 0 => 5));

   Multiply (A => (2 => 0, 1 => 2, 0 => 3),
             B => (2 => 0, 1 => 4, 0 => 5));
end Use_Big_Integers;

Answer 2

Это хороший стиль, чтобы обеспечить полное воспроизведение, но не берите в голову...

когда I будет использоваться в качестве индекса в Y, это хороший стиль, чтобы написать оператор цикла как for I in reverse Y'Range... end loop;, Аналогично для N,

Вы уверены, что N + I - 1 всегда является допустимым индексом для Product? Я почти уверен, что в текущей реализации вы можете получить как слишком большие, так и слишком маленькие индексы. Я подозреваю, что слишком маленькие индексы являются ошибкой при реализации алгоритма. Слишком большие индексы вызваны тем, что вы еще не задумались о том, как справиться с целочисленным переполнением (традиционный способ в Аде - повысить Constraint_Error).

Вы не должны проверить значение Carry в конце функции?