Ada语言大整数小学乘法算法实现：索引越界问题求助

首先得说，小学乘法逻辑本身不难，但在Ada固定大小数组的约束下，索引越界大概率是有效位遍历范围没控制或者索引计算逻辑搞反了导致的。我帮你拆解问题，一步步修复：

先明确核心前提：BigNum的存储约定 #

先确认你的BigNum是怎么存数字的——这是索引计算的关键！我默认你用低位在索引0的常见存储方式（比如数字123存在数组里是[3,2,1,0,...0]），如果你的存储方向反过来（高位在0），后面的索引逻辑要对应调整。

常见的索引越界原因&修复方案 #

1. 遍历了整个数组的无效0位 #

如果你的循环是直接遍历0..Size-1的所有位，那i+j的最大值会达到2*(Size-1)，远远超过BigNum的最大索引Size-1，肯定越界。

解决方法：先获取两个数的有效最高位，只遍历有效位：

-- 先写个辅助函数，找到BigNum的最后一个非零位索引
FUNCTION Get_Last_Significant_Bit (Num : BigNum) RETURN Natural IS
BEGIN
   FOR I IN REVERSE Num'Range LOOP
      IF Num(I) /= 0 THEN
         RETURN I;
      END IF;
   END LOOP;
   RETURN 0; -- 全0的情况
END Get_Last_Significant_Bit;

2. 乘法位的索引计算&边界检查 #

在逐位相乘时，必须确保i+j不超过BigNum的最大索引，同时处理进位时也要检查边界：

FUNCTION "*" (X, Y : BigNum) RETURN BigNum IS
   Product : BigNum := Zero;
   Carry : Natural := 0;
   Base : CONSTANT Natural := 10; -- 假设你用十进制，替换成你的实际Base值
   X_Last : Natural := Get_Last_Significant_Bit(X);
   Y_Last : Natural := Get_Last_Significant_Bit(Y);
BEGIN
   -- 处理其中一个数是0的情况，直接返回0
   IF X_Last = 0 AND X(0) = 0 THEN
      RETURN Zero;
   ELSIF Y_Last = 0 AND Y(0) = 0 THEN
      RETURN Zero;
   END IF;

   -- 遍历X的每一位有效位
   FOR I IN 0 .. X_Last LOOP
      Carry := 0; -- 每处理X的一位，重置进位
      -- 遍历Y的每一位有效位
      FOR J IN 0 .. Y_Last LOOP
         -- 关键：先检查索引是否越界
         IF (I + J) > Product'Last THEN
            RAISE Constraint_Error WITH "BigNum overflow: product exceeds maximum size";
         END IF;

         DECLARE
            Temp : Natural := X(I) * Y(J) + Product(I+J) + Carry;
         BEGIN
            Product(I+J) := Temp MOD Base;
            Carry := Temp / Base;
         END;
      END LOOP;

      -- 处理当前X位遍历后的剩余进位
      DECLARE
         K : Natural := I + Y_Last + 1;
      BEGIN
         WHILE Carry > 0 AND K <= Product'Last LOOP
            DECLARE
               Temp : Natural := Product(K) + Carry;
            BEGIN
               Product(K) := Temp MOD Base;
               Carry := Temp / Base;
            END;
            K := K + 1;
         END LOOP;
      END;

      -- 如果进位还没处理完，说明数组不够大，抛出溢出异常
      IF Carry > 0 THEN
         RAISE Constraint_Error WITH "BigNum overflow: carry exceeds maximum size";
      END IF;
   END LOOP;

   RETURN Product;
END "*";

3. 存储方向搞反的修正 #

如果你的BigNum是高位在索引0（比如123存成[1,2,3,0,...0]），那索引计算要彻底调整：

• X的最低位索引是Size-1 - i，Y的最低位是Size-1 - j
• 乘积的对应位置索引是Size-1 - ((Size-1 -i) + (Size-1 -j)) = i + j - (Size-1)
• 这种存储方式容易搞混，非常建议改成低位在0的模式，能减少80%的索引错误

额外注意事项 #

• 确保Zero是全0的BigNum，初始化正确
• 如果需要支持更大的乘积，要保证BigNum的Size至少是两个输入数有效位数之和（比如两个n位数相乘，结果最多2n位）
• 可以给BigNumPkg加一个Max_Size常量，方便统一管理数组长度

内容的提问来源于stack exchange，提问作者Justiciar