| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2717 人关注过本帖, 1 人收藏
标题:请教各位大师,怎么解决超大数的除法?
只看楼主 加入收藏
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
大数运算通常用字符串或数组形式,虽然运算效率低,但可以突破数值类型的限制。
加减乘除,除法相对比较复杂低效,对运算效率要求高的话,应尽量避免使用除法。
如:
b/a = b * 1/a
1/a 可用牛顿迭代求得:
X=1/a
Xn+1 = (2-a*Xn)*Xn
设:
n=5
b=123123
a=123
x=0.01
FOR i=1 TO n
    x = (2-a*x)*x
ENDFOR
?b*x
2017-04-02 21:47
zyxxzhyg
Rank: 3Rank: 3
来 自:江西
等 级:论坛游侠
威 望:5
帖 子:58
专家分:134
注 册:2014-6-26
收藏
得分:0 
回复 11楼 吹水佬
我用乘减方式完成,在个别应用中还行,效率因为字符串运算的关系肯定不会很高
图片附件: 游客没有浏览图片的权限,请 登录注册


[此贴子已经被作者于2017-4-5 08:45编辑过]

2017-04-05 08:44
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
回复 12楼 zyxxzhyg
用乘法较好,减法效率太低。
用牛顿迭代法,初始x值很重要(求a的倒数初始x值与a的位数相关),并同时考虑精度要求和迭代次数。
2017-04-05 09:25
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
简单写了个,随机测试了一下,VFP精度有限,没做大数测试。
** test.prg
CLEAR
SET FIXED ON
SET DECIMALS TO 16
nDecPre = 20
nPre = 16
RAND(-1)
FOR i=1 TO 100
    Num1 = RAND()
    Num2 = RAND()
    IF i%2==0
        Num1 = -Num1
    ELSE
        IF i%3==0
            Num2 = -Num2
        ENDIF
    ENDIF
    v1 = LEFT(TRANSFORM(Num1 + Num2), nPre)
    v2 = LEFT(_add(TRANSFORM(Num1),TRANSFORM(Num2),nDecPre), nPre)
    IF v1 != v2
        ? TRANSFORM(Num1) + " + " + TRANSFORM(Num2)
        ? "v1 = "+v1
        ? "v2 = "+v2
        ?
    ENDIF
    v1 = LEFT(TRANSFORM(Num1 - Num2), nPre)
    v2 = LEFT(_sub(TRANSFORM(Num1),TRANSFORM(Num2),nDecPre), nPre)
    IF v1 != v2
        ? TRANSFORM(Num1) + " - " + TRANSFORM(Num2)
        ? "v1 = "+v1
        ? "v2 = "+v2
        ?
    ENDIF
    v1 = LEFT(TRANSFORM(Num1 * Num2), nPre)
    v2 = LEFT(_mul(TRANSFORM(Num1),TRANSFORM(Num2),nDecPre), nPre)
    IF v1 != v2
        ? TRANSFORM(Num1) + " * " + TRANSFORM(Num2)
        ? "v1 = "+v1
        ? "v2 = "+v2
        ?
    ENDIF
    v1 = LEFT(TRANSFORM(Num1 / Num2), nPre)
    v2 = LEFT(_div(TRANSFORM(Num1), TRANSFORM(Num2), 10, 16), nPre)
    IF v1 != v2
        ? TRANSFORM(Num1) + " / " + TRANSFORM(Num2)
        ? "v1 = "+v1
        ? "v2 = "+v2
        ?
    ENDIF
ENDFOR
SET DECIMALS TO 2
SET FIXED OFF
RETURN


**
** 大数加减乘除运算
**
**    _div(cNum1, cNum2, nIte, nDecPre) .................. 除法, nIte迭代次数, nDecPre小数精度
**    _mul(cNum1, cNum2, nDecPre) ........................ 乘法
**    _sub(cNum1, cNum2, nDecPre) ........................ 减法
**    _add(cNum1, cNum2, nDecPre) ........................ 加法
**    _addsub(@cNum1, @cNum2, @bSub) ..................... 无符号加减法
**    _RetSigDec(@cRet, @cSig, @nDecpla, @nDecPre) ....... 运算结果的符号、小数点处理
**    _NumCmp(@cNum1, @cNum2) ............................ 无符号比较大小
**    _GetNumAtt2(@cNum, @cSig, @nDecPla, @nLen) ......... 取数属性,乘除法使用
**    _GetNumAtt(@cNum1, @cNum2, @cSig1, @cSig2, @nDecPla) 取数属性:符号、小数位数,检测字符和对齐取整
**    _amov(@aNum, @cNum) ................................ 字串数传送到数字数组(逆序)
**    _ainit(@aNum, @value) .............................. 初始化数字数组
**    _DecAlign(@cNum1, @cNum2) .......................... 小数点对齐取整(0.0123 与 12.3 ==> 123 与 123000)
**    _DecOut(@cNum) ..................................... 去掉小数点, 0.0123 => 123
**    nDecPla = _DecPla(@cNum) ........................... 小数位数
**    _Signed(@cNum, @cSig) .............................. 符号, 检测字符
**    _isNum(@cNum) ...................................... 数字字符检测
**
    * 除法
    * _div(cNum1, cNum2, nIte, nDecPre) nIte迭代次数, nDecPre小数位数
    * 除法转乘法:b/a = b * 1/a,用牛顿迭代法求 a 的倒数。
    * 牛顿迭代法迭代关系式:Xn+1 = Xn - F(Xn)/F'(Xn)
    * 设 x = 1/a,则:a = 1/x, 即 a - 1/x = 0
    * 得方程: F(x) = a - 1/x
    * 一阶导数 F'(x) = 1/x^2
    * 则:
    * Xn+1 = Xn - F(Xn)/F'(Xn)
    * Xn+1 = Xn - (a - 1/Xn)/(1/Xn^2)
    * Xn+1 = 2*Xn - a*Xn^2)
    * Xn+1 = (2 - a*Xn)*Xn
    * 例:设 n=5, b=123123, a=123, 求b/a
    * 根据 a=123,求x=1/a,设初始值 x=0.01
    * FOR i=1 TO n
    *    x = (2 - a*x) * x
    * ENDFOR
    * ? b*x  &&结果 b/a = 1001
FUNCTION _div(cNum1, cNum2, nIte, nDecPre)
    LOCAL cSig1, cSig2
    IF !_Signed(@cNum1, @cSig1)
        RETURN ""
    ENDIF
    IF !_Signed(@cNum2, @cSig2)
        RETURN ""
    ENDIF
    _DecAlign(@cNum1, @cNum2)
    IF LEN(cNum1) == 0
        RETURN "0"
    ENDIF
    IF LEN(cNum1) == 0
        RETURN ""
    ENDIF
    LOCAL cSig, nDecPla
    cSig = IIF(cSig1==cSig2, "", "-")
    nDecPla = nDecPre * 2
        * 求cNum2的倒数 cRec = 1/cNum2
    LOCAL cRec, Xn, cRet
    cRec = "0." + REPLICATE("0", LEN(cNum2)-1) + "1"
    Xn = ""
    DO WHILE (Xn!=cRec) AND (nIte>0)
        Xn = LEFT(cRec, nDecPla)
        cRec = LEFT( _mul( _sub( "2",_mul( cNum2,cRec,nDecPla ),nDecPla ),cRec,nDecPla ), nDecPla )
        nIte = nIte - 1
    ENDDO
        * cNum1 * 1/cNum2
    cRet = _mul(cNum1, cRec, nDecPla)
    nDecPla = AT(".", cRet)
    RETURN cSig + IIF(nDecPla>0, LEFT(cRet, nDecPla+nDecPre), cRet)
ENDFUNC

    * 乘法
    * _mul(cNum1, cNum2, nDecPre)
FUNCTION _mul(cNum1, cNum2, nDecPre)
        * 取符号、小数位数和取整长度
    LOCAL cSig1, cSig2, nDecPla1, nDecPla2, nLen1, nLen2
    IF !_GetNumAtt2(@cNum1, @cSig1, @nDecPla1, @nLen1)
        RETURN ""
    ENDIF
    IF !_GetNumAtt2(@cNum2, @cSig2, @nDecPla2, @nLen2)
        RETURN ""
    ENDIF
    IF (nLen1==0) OR (nLen2==0)
        RETURN "0"
    ENDIF
        * 运算结果的符号、小数位数
    LOCAL cSig, nDecPla
    cSig = IIF(cSig1==cSig2, "","-")
    nDecPla = IIF(nDecPla1>0 and nDecPla2>0, nDecPla1+nDecPla2, ABS(nDecPla1-nDecPla2))
        * 运算
    LOCAL i, j, cRet, aNum[nLen1+nLen2], aNum1[nLen1], aNum2[nLen2]
    _ainit(@aNum, 0)
    _amov(@aNum1, @cNum1)
    _amov(@aNum2, @cNum2)
    FOR i=1 TO nLen1
        FOR j=1 TO nLen2
            aNum[i+j-1] = aNum[i+j-1] + aNum1[i]*aNum2[j]
        ENDFOR
    ENDFOR
        * 运算结果、符号和小数位数处理
    cRet = ""
    FOR i=1 TO nLen1+nLen2
        IF aNum[i] > 9
            aNum[i+1] = aNum[i+1] + INT(aNum[i]/10)
            aNum[i] = aNum[i] % 10
        ENDIF
        cRet = CHR(aNum[i]+48) + cRet
    ENDFOR
    cRet = LTRIM(cRet, "0")
    RETURN _RetSigDec(@cRet, @cSig, @nDecpla, @nDecPre)   
ENDFUNC

    * 减法
    * _sub(cNum1, cNum2, nDecPre)
FUNCTION _sub(cNum1, cNum2, nDecPre)
    LOCAL cSig1, cSig2, nDecPla
    IF !_GetNumAtt(@cNum1, @cNum2, @cSig1, @cSig2, @nDecPla)
        RETURN ""
    ENDIF
   
    LOCAL cSig, nCmp, cRet
    nCmp = _NumCmp(@cNum1, @cNum2)
    cSig = ""
    cRet = ""
    IF cSig1 == cSig2    &&同号相减
        IF nCmp == 0
            RETURN "0"
        ENDIF
        IF nCmp > 0
            cSig = IIF(cSig1=="-", "-", "")
        ELSE
            cSig = IIF(cSig1=="-", "", "-")
        ENDIF
        cRet = _addsub(@cNum1, @cNum2, .T.)
    ELSE     &&异号相加
        cSig = cSig1
        cRet = _addsub(@cNum1, @cNum2)
    ENDIF
    RETURN _RetSigDec(@cRet, @cSig, @nDecpla, @nDecPre)
ENDFUNC

    * 加法
    * _add(cNum1, cNum2, nDecPre)
FUNCTION _add(cNum1, cNum2, nDecPre)
    LOCAL cSig1, cSig2, nDecPla
    IF !_GetNumAtt(@cNum1, @cNum2, @cSig1, @cSig2, @nDecPla)
        RETURN ""
    ENDIF
   
    LOCAL cSig, nCmp, cRet
    nCmp = _NumCmp(@cNum1, @cNum2)
    cSig = ""
    cRet = ""
    IF cSig1 == cSig2    &&同号相加
        cSig = cSig1
        cRet = _addsub(@cNum1, @cNum2)
    ELSE     &&异号相减
        IF nCmp == 0
            RETURN "0"
        ENDIF
        cSig = IIF(nCmp>0, cSig1, cSig2)
        cRet = _addsub(@cNum1, @cNum2, .T.)
    ENDIF
    RETURN _RetSigDec(@cRet, @cSig, @nDecpla, @nDecPre)
ENDFUNC
   
    * 无符号加减法
    * _addsub(@cNum1, @cNum2, @bSub)
FUNCTION _addsub(cNum1, cNum2, bSub)
    LOCAL i, nLen1, nLen2, nLen, cRet, aNum1[1], aNum2[1]
        * 初始化字符数组
        * aNum1为被加(减)数
        * aNum2为加(减)数
        * 较大的数作为被加(减)数
    nLen1 = LEN(cNum1)
    nLen2 = LEN(cNum2)
    nLen = nLen1
    IF (nLen1>nLen2) OR (nLen1==nLen2 AND cNum1>cNum2)
        DIMENSION aNum1[nLen1+1], aNum2[nLen2]
        _amov(@aNum1, @cNum1)
        _amov(@aNum2, @cNum2)
        nLen = nLen2            
    ELSE
        DIMENSION aNum1[nLen2+1], aNum2[nLen1]
        _amov(@aNum1, @cNum2)
        _amov(@aNum2, @cNum1)
    ENDIF
        * 加、减运算
    IF !bSub    &&加法运算
        FOR i=1 TO nLen
            aNum1[i] = aNum1[i] + aNum2[i]
        ENDFOR
        FOR i=1 TO ALEN(aNum1)
            IF aNum1[i] > 9
                aNum1[i] = aNum1[i] - 10
                aNum1[i+1] = aNum1[i+1] + 1
            ENDIF
        ENDFOR
    ELSE    &&减法运算
        FOR i=1 TO nLen
            aNum1[i] = aNum1[i] - aNum2[i]
        ENDFOR
        FOR i=1 TO ALEN(aNum1)
            IF aNum1[i] < 0
                aNum1[i] = aNum1[i] + 10
                aNum1[i+1] = aNum1[i+1] - 1
            ENDIF
        ENDFOR
    ENDIF
        * 运算结果字串、前导0和小数点处理
    cRet = ""
    FOR i=1 TO ALEN(aNum1)
        cRet = CHR(aNum1[i]+48) + cRet
    ENDFOR
    cRet = LTRIM(cRet, "0")
    RETURN IIF(!EMPTY(cRet), cRet, "0")
ENDFUNC

    * 运算结果的符号、小数精度处理
    * _RetSigDec(@cRet, @cSig, @nDecpla, @nDecPre)
FUNCTION _RetSigDec(cRet, cSig, nDecpla, nDecPre)
    IF !(cRet=="0")
        IF nDecpla > 0
            LOCAL nLen
            nLen = LEN(cRet)
            cRet = IIF(nLen > nDecpla,;
                      LEFT(cRet, nLen-nDecpla) + "." + RIGHT(cRet, nDecpla),;
                      "0." + REPLICATE("0", nDecpla-nLen) + cRet)
            cRet = LEFT(cRet, AT(".", cRet)+nDecPre)
        ENDIF
        cRet = IIF(cSig=="-","-","") + cRet
    ENDIF
    RETURN cRet
ENDFUNC
   
    * 无符号比较大小
    * _NumCmp(@cNum1, @cNum2)
FUNCTION _NumCmp(cNum1, cNum2)
    LOCAL nLen1, nLen2
    nLen1 = LEN(cNum1)
    nLen2 = LEN(cNum2)
    IF nLen1>nLen2 OR nLen1<nLen2
        RETURN IIF((nLen1-nLen2)>0, 1, -1)
    ENDIF
    RETURN IIF(cNum1>cNum2, 1, IIF(cNum1<cNum2, -1, 0))
ENDFUNC

    * 取数属性:符号, 小数位数,检测字符和取整
    * _GetNumAtt2(@cNum, @cSig, @nDecPla, @nLen)
    * 乘除法使用
FUNCTION _GetNumAtt2(cNum, cSig, nDecPla, nLen)
    IF !_Signed(@cNum, @cSig)
        RETURN .F.
    ENDIF
    nDecPla = _DecPla(@cNum)
    _DecOut(@cNum)
    nLen = LEN(cNum)
    RETURN .T.
ENDFUNC

    * 取数属性:符号, 小数位数,检测字符和对齐取整
    * _GetNumAtt(@cNum1, @cNum2, @cSig1, @cSig2, @nDecPla)
    * 加减法使用
FUNCTION _GetNumAtt(cNum1, cNum2, cSig1, cSig2, nDecPla)
    IF !_Signed(@cNum1, @cSig1)
        RETURN .F.
    ENDIF
    IF !_Signed(@cNum2, @cSig2)
        RETURN .F.
    ENDIF
    nDecPla = MAX(_DecPla(@cNum1), _DecPla(@cNum2))
    _DecAlign(@cNum1, @cNum2)
    RETURN .T.
ENDFUNC

    * 字串数传送到数字数组(逆序)
    * _amov(@aNum, @cNum, @nLen)
FUNCTION _amov(aNum, cNum)
    _ainit(@aNum, 0)
    LOCAL i, nLen
    nLen = LEN(cNum)
    FOR i=1 TO nLen
        aNum[nLen-i+1] = ASC(SUBSTR(cNum,i,1))-48
    ENDFOR
ENDFUNC

    * 初始化数字数组
    * _ainit(@aNum, @value)
FUNCTION _ainit(aNum, Value)
    LOCAL i
    FOR i=1 TO ALEN(aNum)
        aNum[i] = Value
    ENDFOR
ENDFUNC

    * 小数点对齐取整(0.0123 与 12.3 ==> 123 与 123000)
    * _DecAlign(@cNum1, @cNum2)
FUNCTION _DecAlign(cNum1, cNum2)
    LOCAL nDecPla1, nDecPla2
    nDecPla1 = _DecPla(@cNum1)
    nDecPla2 = _DecPla(@cNum2)
    _DecOut(@cNum1)
    _DecOut(@cNum2)
    IF nDecPla1 > nDecPla2
        cNum2 = cNum2 + REPLICATE("0", nDecPla1-nDecPla2)
    ELSE
        IF nDecPla1 < nDecPla2
            cNum1 = cNum1 + REPLICATE("0", nDecPla2-nDecPla1)
        ENDIF
    ENDIF
ENDFUNC

    * 去掉小数点, 0.0123 => 123
    *_DecOut(@cNum)
FUNCTION _DecOut(cNum)
    LOCAL i
    i = AT(".", cNum)
    IF i > 0
        cNum = LEFT(cNum, i-1) + SUBSTR(cNum, i+1)
    ENDIF
    cNum = LTRIM(cNum, "0")
ENDFUNC

    * 小数位数
    * nDecPla = _DecPla(@cNum)
FUNCTION _DecPla(cNum)
    LOCAL nDecPla
    nDecPla = AT(".", cNum)
    RETURN IIF(nDecPla>0, LEN(cNum)-nDecPla, 0)
ENDFUNC

    * 取符号, 检测字符
    * _Signed(@cNum, @cSig)
FUNCTION _Signed(cNum, cSig)
        * 检测字符
    IF !_isNum(cNum)
        RETURN .F.
    ENDIF
        * 符号
    cSig = ""
    IF LEFT(cNum,1) == "-"
        cSig = "-"
        cNum = SUBSTR(cNum, 2)
    ENDIF
    RETURN .T.
ENDFUNC

    * 数字字符检测
    * _isNum(@cNum)
FUNCTION _isNum(cNum)
    IF EMPTY(cNum)
        RETURN .F.
    ENDIF
    IF OCCURS(".", cNum) > 1
        MESSAGEBOX(cNum + 0h0D + "无效的数值串","提示")
        RETURN .F.
    ENDIF
    LOCAL i, ch, nLen
    nLen = LEN(cNum)
    FOR i=IIF(LEFT(cNum,1)=="-",2,1) TO nLen
        ch = SUBSTR(cNum, i, 1)
        IF !ISDIGIT(ch) AND !(ch==".")
            MESSAGEBOX(cNum + 0h0D + "无效的数值串","提示")
            RETURN .F.
        ENDIF
    ENDFOR
    RETURN .T.
ENDFUNC
2017-04-06 06:03
zyxxzhyg
Rank: 3Rank: 3
来 自:江西
等 级:论坛游侠
威 望:5
帖 子:58
专家分:134
注 册:2014-6-26
收藏
得分:0 
回复 14楼 吹水佬
学习了,用数组方式比我直接用字符速度快
2017-04-06 08:18
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
_div()发现这里有误:
    IF LEN(cNum1) == 0
        RETURN "0"
    ENDIF
    IF LEN(cNum1) == 0
        RETURN ""
    ENDIF
改为:
    IF LEN(cNum1) == 0
        RETURN "0"
    ENDIF
    IF LEN(cNum2) == 0
        RETURN ""
    ENDIF
2017-04-06 08:34
mywisdom88
Rank: 16Rank: 16Rank: 16Rank: 16
等 级:版主
威 望:191
帖 子:3147
专家分:8408
注 册:2015-3-25
收藏
得分:0 
吹版,有点问题,速度问题。
当 SET DECIMALS TO 16 时,大概 1.3 秒
当 SET DECIMALS TO 17 时,大概 1.8 秒
当 SET DECIMALS TO 18 时,大概 2.6 秒

当 SET DECIMALS TO 15 时,大概 1.2 秒
当 SET DECIMALS TO 14 时,大概 2.6 秒
当 SET DECIMALS TO 13 时,大概 5.6 秒
当 SET DECIMALS TO 12 时,大概 6.5 秒
当 SET DECIMALS TO 11 时,大概 6.1 秒
当 SET DECIMALS TO 10 时,大概 6.1 秒


2017-04-06 09:07
zyxxzhyg
Rank: 3Rank: 3
来 自:江西
等 级:论坛游侠
威 望:5
帖 子:58
专家分:134
注 册:2014-6-26
收藏
得分:0 
回复 17楼 mywisdom88
用了迭代,整除的情况就没办法了。
图片附件: 游客没有浏览图片的权限,请 登录注册
2017-04-06 09:17
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
回复 18楼 zyxxzhyg
整除问题,没做舍入处理,可按一定的精度舍入取整。
2017-04-06 09:51
吹水佬
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:451
帖 子:10607
专家分:43186
注 册:2014-5-20
收藏
得分:0 
回复 17楼 mywisdom88
SET DECIMALS TO 16 只是想取VFP运算最大有效精度,超过时VFP的一些命令函数运算结果会引起不准确或异常。
这个 test.prg 只是与VFP命令算法结果比对,有限度地检测大数算法有无错误,没有用大数去进行运算检测。


2017-04-06 10:04
快速回复:请教各位大师,怎么解决超大数的除法?
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.020976 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved