具有 32 位溢出算法的斐波那契数列

Question

我目前正在 riscv32I 中实现运行斐波那契数列（最多第 60 个数字）的代码，这意味着我可以使用的内存地址只有 32 位。

我首先用 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 位内存地址中，因此我们必须将其拆分为 32 位内存地址，一个保存高位，一个保存低位。

让我们将上面的算法推广到 4 位内存空间，以便更容易理解该算法。这意味着最大int可以是16。让ss设置n1 = 10，n2 = 10。

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.

这应该适用于任何基础，但我很好奇这个算法被表示为什么，或者它是否仅仅与模块和权力相关？

谢谢！

Answer 1

它称为任意精度算术，您可以在此处阅读更多相关信息。

任意精度算术，也称为 bignum 算术、多精度算术，有时也称为无限精度算术，表示对精度位数仅受主机系统可用内存限制的数字执行计算。