带32位溢出处理的斐波那契数列算法名称咨询

实现场景与代码 #

在RISC-V32I架构下，利用32位内存实现可计算至第60项的斐波那契数列，通过拆分高低位处理数值溢出，先完成C语言实现：

#include <stdint.h>
#include <stdio.h>
#include <inttypes.h>

int main() {
    uint32_t n1 = 0;        // first pre number  (n - 2)
    uint32_t n2 = 1;        // second pre number (n - 1)
    uint32_t add = 0;       // current number

    uint32_t store_hi = 0;  
    uint32_t store_lo = 0; 
    uint32_t result;        // result
    uint32_t carry;         // carry bit

    for (int i = 2; i < 61; i++) {
        carry = 0;                              // reset carry bit
        add = (uint32_t)(n2 + n1);              // calculate current fib number
        
        if (add < n1) {                         // if overflow  
            carry = 1;                          // set carry bit
        }

        result = store_hi + store_lo;           // keeping track of higher bits
        result = result + carry;                // add carry bit

        store_lo = store_hi;                    // 
        n1 = n2;                                // update first pre number
        store_hi = result;                      // 
        n2 = add;                               // update second pre number
    }

    printf("Result32: 0x%08" PRIx32 " 0x%08" PRIx32 "\n", result, add);
    uint64_t result64 = ((uint64_t)result << 32) | add;
    printf("Result64: 0x%016" PRIx64 " -> %" PRId64 "\n", result64, result64);
}

运行结果 #

Result32: 0x00000168 0x6c8312d0
Result64: 0x000001686c8312d0 -> 1548008755920

算法核心与演示 #

该算法核心是将超32位数值拆分为高低位存储，通过检测加法溢出产生的carry bit维护高位数值，以下是4位内存空间的算法演示：

Loop 1:
     add = 4 # (10 + 10 = 20, but overflow, so 20 % 16 = 4)
     carry = 1
     result = 1
     store_lo = 0
     store_hi = 1
     n1 = 10
     n2 = 4
     # output: 0x14, 0x1 hi bit, 0x4 lo bit, which is 10 + 10 = 20
Loop 2:
     add = 14
     carry = 0
     result = 1
     store_lo = 1
     store_hi = 1
     n1 = 4
     n2 = 14
     # output: 0x1e, 0x1 hi bit, 0xe or 14, lo bit, which is 10 + 20 = 30
loop 3:
     add = 2 (14 + 4 = 18, but overflow, so 18 % 16, 2)
     carry = 1
     result = 3
     store_lo = 1
     store_hi = 2
     n1 = 14
     n2 = 2
     #output: 0x32, 0x3 hi bit, 0x2 low bit, which is  20 + 30 = 50
.... and so on.

该算法可适配任意基数，现咨询其是否有标准名称，或是仅与模运算、幂运算相关？

回答 #

这个算法本质上是多精度整数加法的简化实现，属于多精度计算（大数计算）的基础范畴，没有单独的专属标准名称，但核心逻辑完全基于模运算与进位传递的原理：

• 用固定字长（32位/4位）变量存储数值低阶部分，本质是对2^字长取模的运算，溢出产生的carry就是模运算商的最低位
• 通过维护高位变量累加进位，等价于把完整数值拆分为高位 * 基数 + 低位的形式，这里的基数就是2^字长，属于幂运算的应用场景

简单来说，它是多精度加法在斐波那契数列计算中的针对性应用，核心依赖模运算（处理低位溢出）和幂运算（定义高低位基数）实现超字长数值的逐步计算。

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