mysql做乘法运算溢出_乘法溢出及对策

最近几次碰到乘法溢出，

情况一：

下面是修订后的版本

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)

{

stackst;

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

阅读(1957) | 评论(0) | 转发(0) |

总结

以上是生活随笔为你收集整理的mysql做乘法运算溢出_乘法溢出及对策的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。