Chinaunix首页 | 论坛 | 博客
  • 博客访问: 586527
  • 博文数量: 197
  • 博客积分: 7001
  • 博客等级: 大校
  • 技术积分: 2155
  • 用 户 组: 普通用户
  • 注册时间: 2005-02-24 00:29
文章分类

全部博文(197)

文章存档

2022年(1)

2019年(2)

2015年(1)

2012年(100)

2011年(69)

2010年(14)

2007年(3)

2005年(7)

分类: C/C++

2012-02-28 21:25:11

 最近几次碰到乘法溢出,



情况一:
下面是修订后的版本
void dfs(int pos, int lim, int val, int div)
{
    int i,j;
    if(pos>prime[0]||prime[pos]>lim) return;
    int t=prime[pos];
    for(i=1,j=1; i<=lim/t;j++){
        i*=t;
        divisor[val*i]=div*(j+1);
        dfs(pos+1,lim/i,val*i,div*(j+1));
    }
    dfs(pos+1,lim,val,div);
}
原来的版本是for(i=1,j=1; i*t<=lim;j++),结果i*t溢出变成负数导致divisor[val*i]的下标为负


情况二多一个乘法,导致顾此失彼: LIMIT 是500000,在下面的for循环
for(t=prime[ob.ind];t<=LIM/ob.cur;t*=prime[ob.ind])
t是第4793个质数46349,ob.cur为8,导致t*=prime[ob.ind]会产生乘法溢出(超过2^31-1),其实t<=LIM/ob.cur已经是为了避免乘法溢出的做法,结果还是没有考虑到后面的乘法。
程序运行最终产生了access violation(VC),因为divs[t*ob.cur]的下标出现了一个大负数。

解决的办法:因为这是都不超过int的范围,将相关类型扩展成long long就解决了。当然也可以采用上面的方式。

struct frame{
        int ind,cur,cur_div;
        frame(int i,int c, int d):ind(i),cur(c),cur_div(d){}
    };

void dfs(int ind, int cur, int cur_div)
{
   
    stack st;
    st.push(frame(ind,cur,cur_div));
   
    while(!st.empty()){
        frame ob=st.top();
        st.pop();
        if(ob.ind==prime[0]+1 || ob.cur>LIM/prime[ob.ind]) continue;
        st.push(frame(ob.ind+1,ob.cur,ob.cur_div));
        int t,tot=1;
        for(t=prime[ob.ind];t<=LIM/ob.cur;t*=prime[ob.ind]){
            tot+=t;
            divs[t*ob.cur]=ob.cur_div*tot;
            st.push(frame(ob.ind+1,ob.cur*t,ob.cur_div*tot));
        }
    }
}

最新的情况
要求 prime[i]^p * prime[i+k]^(p+t)<=10^9  prime[i+k]^(p+t)本身可能超过10^9,对数取整也许可以解除所有溢出烦恼,唯一不确定的就是浮点类型精度是损失是否会带来不可接受的误差

p*log10((double)prime[i])+(p+t)*log10((double)prime[i+k])<=9.0
阅读(2828) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~