2

我正在为引用符号表示中的数字实现算术函数，这是p-adic numbers的一种形式。从本文中获取基本思想，我有一个结构和一个构造函数。

enum { base = 10 };

/*
   d[n+m-1] ... d[n+1] d[n] ' d[n-1] ... d[2] d[1] d[0]

   Sum(i=0..n d[i]*b^i) + Sum(i=n+1..n+m d[i]*b^i/(b^m-1))
 */
typedef struct q { 
    int b,n,m,d[];
} *q;

这与论文大致相同，但我稍微更改了索引。

/* nb. not defined for LONG_MIN */
q qlong(long i){ 
    if (i<0) return qneg(qlong(-i));
    int m=0;
    int n=i?ceil(log(i)/log(base)):0;
    q z=malloc(sizeof*z + (n+m)*sizeof*z->d);
        z->b=base; z->n=n; z->m=m;
    int j;
    for(j=0; j<n; j++){
        z->d[j] = i % base;
        i /= base;
    }   
    qprint(z);
    return z;
}

使用论文中提出的界限，我可以估计加法结果的位数。

q qadd(q x,q y){
    int m=lcm(x->m,y->m);
    int n=max(x->n,y->n)+m+2;
    int t,c=0;
    q z=malloc(sizeof*z + (n+m)*sizeof*z->d);
        z->b=base; z->n=n; z->m=m;
    int k;
    for(k=0; k<n+m; k++){
        t = qdig(x,k) + qdig(y,k) + c;
        z->d[k] = t % base;
        c = t / base;
    }

    findrepetition(z);
    return z;
}

但是一旦达到重复状态，这可能会执行不必​​要的计算。标准化步骤中的计算甚至更多。

在他早期的论文中，Hehner 提出了一种检测重复的算法。

Hehner 终止算法

void findrepetition(q z){
    int i;
    int j;
    qprint(z);
    for(i=1; i<z->n+z->m-1; i*=2) {
        for(j=i+1; j<2*i; j++) {
            if (z->d[j-1]==z->d[i-1]) {
                z->n=i;
                z->m=j-i;
                return;
            }
        }
    }
}

但是我可以将它合并到我现有的计算循环中而不是进行第二次传递吗？我已经避免了 i 和 j inqadd所以它们在这些循环中的使用不会与我的使用冲突。

其中一些材料之前已发布到comp.lang.c，并且有一个链接视频，它是对整个主题的极好介绍。

4

0 回答 0