BigNum整数的加长(小学)乘法

Question

我正在尝试在Ada中实现小学乘法算法，目前我得到了一个索引越界错误。我非常感谢任何关于如何修复错误并成功实现算法的意见。提前感谢！

我有一个定义type BigNum is array(0..Size - 1) of Integer;的包BigNumPkg

我目前正在尝试实现的函数如下所示：

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的有效索引吗？我非常确定，在当前的实现中，索引既可以太大，也可以太小。我怀疑索引太小是算法实现过程中的一个偏差。索引太大是因为您没有清楚地考虑如何处理整数溢出( Ada中的传统方法是引发Constraint_Error)。

你不应该在函数的末尾检查Carry的值吗？