数学研发论坛

 找回密码
 欢迎注册
查看: 167|回复: 0

[原创] 大数(正整数)除法之多精除以单精

[复制链接]
发表于 2018-2-11 09:58:31 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
大数运算中会经常遇到多精除以单精的情况,有时也会把某些除法分解成多精除以单精加快运行速度,这里所说单精数是不超过cpu位长二分这一的数,32位机是65535,

在此以千进制数为例讲解一下具体实现,

       For i = 1 To 被除数数组长度

            运算结果(i) = 被除数(i) \ 单精数
            被除数(i + 1) = (被除数(i) Mod 单精数) * 1000 + 被除数(i + 1)
       Next

用实例演示一下:123 456 789 125 /234

运算结果(1)=123 \ 234=0                          '被除数(1) 中初始存放123,234为除数
被除数(2)=(123 mod 234) *1000+456=123456       ‘1000为千进制数的基,(123 mod 234) *1000的结果为123000,被除数(2)中初始存放456
运算结果(2)=123456\ 234=527                          '被除数(2) 中存放123456,234为除数
被除数(3)=(123456 mod 234) *1000+789=138789       ‘1000为千进制数的基,(123456 mod 234) *1000的结果为138000,被除数(3)中初始存放789


运算结果(3)=138789\ 234=593                        '被除数(3) 中存放138789,234为除数
被除数(4)=(138789 mod 234) *1000+125=027125      ‘1000为千进制数的基,(138789 mod 234) *1000的结果为027000,被除数(4)中初始存放125


运算结果(4)=027125\ 234=115                      '被除数(4) 中存放138789,234为除数
被除数(5)=(027125 mod 234) *1000+0=215000     ‘1000为千进制数的基,(027125 mod 234) *1000的结果为215000 ,被除数(5)中初始存放0

此时运算结果数组中依次存放000 527 593 115 为该除法的整数商,若要计算到小数后某某位,可以通过扩充被除数长度实现。

这段代码在提升落叶高精度表达式计算器1.2的速度中发挥出关键作用。


下面是网上收集的一段多精除以单精c代码:

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
using namespace std;  
int main()  
{  
    char a[510];  
    int c[510];   
    int b,l;  
    while (~scanf("%s%d",&a,&b))  
    {  
        memset(c,0,sizeof(c));   
        l=strlen(a);  
        int ys=0;  
        int t=0,temp,i;  
        for (i=0;i<l;i++)  
        {  
            temp=a[i]-'0'+10*ys;
            if (temp>=b)  
            {  
                c[t]=temp/b;  
                ys=temp % b ;  
                t++;  
            }  
            else ys=temp;  
        }  
        while (c[i]==0) i--;  
        for (int j=i;j>=0;j--)  
            printf("%d",c[j]);  
        if (ys) printf(" %d",ys);  
            printf("\n");  
    }  
    return 0;  
}  
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|Archiver|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2018-5-27 21:33 , Processed in 0.046328 second(s), 16 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表