免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: substr函数
打印 上一主题 下一主题

[数值计算] 不支持 bignum 的语言, 不依赖外部模块, 如何实现 [ + - * ] 运算 [复制链接]

论坛徽章:
95
程序设计版块每日发帖之星
日期:2015-09-05 06:20:00程序设计版块每日发帖之星
日期:2015-09-17 06:20:00程序设计版块每日发帖之星
日期:2015-09-18 06:20:002015亚冠之阿尔艾因
日期:2015-09-18 10:35:08月度论坛发贴之星
日期:2015-09-30 22:25:002015亚冠之阿尔沙巴布
日期:2015-10-03 08:57:39程序设计版块每日发帖之星
日期:2015-10-05 06:20:00每日论坛发贴之星
日期:2015-10-05 06:20:002015年亚冠纪念徽章
日期:2015-10-06 10:06:482015亚冠之塔什干棉农
日期:2015-10-19 19:43:35程序设计版块每日发帖之星
日期:2015-10-21 06:20:00每日论坛发贴之星
日期:2015-09-14 06:20:00
21 [报告]
发表于 2015-12-30 20:32 |只看该作者
回复 1# substr函数


    你直接把 Python 的 bignum 实现找出来看看,再用其他语言实现就是了。

论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
22 [报告]
发表于 2016-01-02 11:37 |只看该作者
回复 21# MMMIX


Master: It is C: <all>

I am a small white..

[ ]

论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
23 [报告]
发表于 2016-01-02 11:38 |只看该作者
回复 21# MMMIX


    我是小白
small white

论坛徽章:
145
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
24 [报告]
发表于 2016-01-03 15:01 |只看该作者
回复 10# substr函数

除法
ex: 378 / 23

1. 初始
  bn1 = 378
  bn2 = 23
  len1 = length("378") = 3
  len2 = length("23") = 2
  len1 要大于等于 len2
  由378取出与23相同长度(2)
  bn1 = 378, dvn = 37, bn2 = 23


2. 用(相比)减法做除法

  37 >= 23 True, ==> 37 - 23 = 15 , 数组++ = 1
  15 >=23  False,
  换一下位
  158
  158 >= 23 True, ==> 158 - 23 = 135 , 数组++ = 11
  135 >= 23 True, ==> 135 - 23 = 112 , 数组++ = 12
  ...
   33 >= 23 True, ==>  33 -  23 =   10 , 数组++ = 16
   10 >= 23  False

3. 16

4. awk code (div function with unsigned only)
  xxx_bn for big number
  xxx_bs for big number with signed
  xxx_bu for big number with unsigned

function _div_bu(bu1, bu2, len1,len2,len,n,c1,c2,dvn){
    len1 = length(bu1)
    len2 = length(bu2)
    if(len1 < len2 || (len1 == len2) && (bu1"" < bu2"")) return "0"
    len  = len1 - len2 + 1
    delete _x
       dvn = substr(bu1, 1, len2)
    for(n=1; n<=len; n++){
         _x[n] = 0
         while(_GE(dvn, bu2)){
             _x[n]++
             dvn = _sub_bu(dvn, bu2)
         }
         dvn = dvn get1(bu1, n+len2)
    }
    return _get_ret(len,"x")
}

function _get_ret(len, x,  n,ret){
    for(n=1; n<=len; n++){
        if(x == ""){
            ret = _a[n]%10 ret
            _a[n+1] += int(_a[n]/10)
        }
        else{
            ret = ret _x[n]
        }
    }
    sub(/^0+/, "", ret)
    if(ret == "") ret = "0"
    return ret
}

5. 测试驱动开发 TDD
https://zh.wikipedia.org/zh-cn/%E6%B5%8B%E8%AF%95%E9%A9%B1%E5%8A%A8%E5%BC%80%E5%8F%91
$ awk -vTEST=1 -v TEST_LVL=2 -f bignum.awk
test  1 PASSED!!!
    normal: 2 > -3     = True
    bignum: 2 > -3     = True   (by _GT function)
test  2 PASSED!!!
    normal: 2 >= -3     = True
    bignum: 2 >= -3     = True   (by _GE function)
test  3 PASSED!!!
    normal: 2 < -3     = False
    bignum: 2 < -3     = False   (by _LT function)
test  4 PASSED!!!  
    normal: 2 <= -3     = False
    bignum: 2 <= -3     = False   (by _LE function)
test  5 PASSED!!!  
    normal: 2 == -3     = False
    bignum: 2 == -3     = False   (by _EQ function)
test  6 PASSED!!!  
    normal: 2 != -3     = True
    bignum: 2 != -3     = True   (by _NE function)
test  7 PASSED!!!  
    normal: 2 + -3     = -1
    bignum: 2 + -3     = -1   (by add_bn function)
test  8 PASSED!!!  
    normal: 2 - -3     = 5
    bignum: 2 - -3     = 5   (by sub_bn function)
...
test 134 PASSED!!!  
    normal: -1234567890 / -233     = 5298574
    bignum: -1234567890 / -233     = 5298574   (by div_bn function)
test 135 PASSED!!!  
    normal: 1234567890 / 233     = 5298574
    bignum: 1234567890 / 233     = 5298574   (by div_bn function)
test 136 PASSED!!!  
    normal: 1234567890*5537483*666699999999999999967777/12345671236789+667785412345-12345/233     = 369184220770065865283121625
    bignum: 1234567890*5537483*666699999999999999967777/12345671236789+667785412345-12345/233     = 369184220770065865283121625   (by bignum function)
test 137 PASSED!!!  
    normal: -1234567890*5537483*-666699999999999999967777/-12345671236789+667785412345-12345/233     = -369184220770064529712297039
    bignum: -1234567890*5537483*-666699999999999999967777/-12345671236789+667785412345-12345/233     = -369184220770064529712297039   (by bignum function)
test 138 PASSED!!!  
    normal: 1234567890*5537483*666699999999999999967777/1234567123     = 3691842209730830511335195117281
    bignum: 1234567890*5537483*666699999999999999967777/1234567123     = 3691842209730830511335195117281   (by bignum function)


论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
25 [报告]
发表于 2016-01-03 15:58 |只看该作者
回复 20# jason680


谢谢 J 神 [ ]
期待 i .. n .. g ..

论坛徽章:
145
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
26 [报告]
发表于 2016-01-03 16:58 |只看该作者
回复 25# substr函数

不知为什么24帖(我发的,不见了),再重发...   

除法 ex: 378 / 23

1. 初始
  bn1 = 378
  bn2 = 23
  len1 = length("378") = 3
  len2 = length("23") = 2
  len1须大于等于len2

  由bn1取出与bn2相同长度(2)
   bn1 = 378, dvn = 37, bn2=23

2. big number 使用比较(大于等于)与 减法 代替 除法

  37   >= 23 True, 37 - 23 = 14, _x数组++ = 1
  14   >= 23 False,  取下一个数 378
  148 >= 23 True, 148 - 23 = 125, _x数组++ = 11
  125 >= 23 True, 125 - 23 = 102, _x数组++ = 12
  105 >= 23 True, 102 - 23 =   79, _x数组++ = 13
  ...
  56   >= 23 True, 56   - 23 =   33, _x数组++ = 15
  33   >= 23 True, 33   - 23 =   10, _x数组++ = 16
  10   >= 23 False,
answer = 16

3. awk code ( div with unsigned only)
# xxx_bn for bing number
# xxx_bs for bing number with signed
# xxx_bu for bing number with unsigned

function _div_bu(bu1, bu2, len1,len2,len,n,c1,c2,dvn){
    len1 = length(bu1)
    len2 = length(bu2)
    if(len1 < len2 || (len1 == len2) && (bu1"" < bu2"")) return "0"
    len  = len1 - len2 + 1
    delete _x
    dvn = substr(bu1, 1, len2)   #由bn1取出与bn2相同长度
    for(n=1; n<=len; n++){
         _x[n] = 0
         while(_GE(dvn, bu2)){
             _x[n]++
             dvn = _sub_bu(dvn, bu2)
         }
         dvn = dvn get1(bu1, n+len2)
    }
    return _get_ret(len,"x")
}

4. 测试驱动开发(TDD, Test-driven development)
https://zh.wikipedia.org/zh-cn/%E6%B5%8B%E8%AF%95%E9%A9%B1%E5%8A%A8%E5%BC%80%E5%8F%91
测试驱动开发(Test-driven development)是极限编程中倡导的程序开发方法,以其倡导先写测试程序,然后编码实现其功能得名。...

$ awk -vTEST=1 -v TEST_LVL=2 -f bignum.awk
test  1 PASSED!!!
    normal: 2 > -3     = True
    bignum: 2 > -3     = True   (by _GT function)
test  2 PASSED!!!
    normal: 2 >= -3     = True
    bignum: 2 >= -3     = True   (by _GE function)
test  3 PASSED!!!
    normal: 2 < -3     = False
    bignum: 2 < -3     = False   (by _LT function)
test  4 PASSED!!!
    normal: 2 <= -3     = False
    bignum: 2 <= -3     = False   (by _LE function)
test  5 PASSED!!!
    normal: 2 == -3     = False
    bignum: 2 == -3     = False   (by _EQ function)
test  6 PASSED!!!
    normal: 2 != -3     = True
    bignum: 2 != -3     = True   (by _NE function)
test  7 PASSED!!!
    normal: 2 + -3     = -1
    bignum: 2 + -3     = -1   (by add_bn function)
test  8 PASSED!!!
    normal: 2 - -3     = 5
    bignum: 2 - -3     = 5   (by sub_bn function)
...
test 134 PASSED!!!
    normal: -1234567890 / -233     = 5298574
    bignum: -1234567890 / -233     = 5298574   (by div_bn function)
test 135 PASSED!!!
    normal: 1234567890 / 233     = 5298574
    bignum: 1234567890 / 233     = 5298574   (by div_bn function)
test 136 PASSED!!!
    normal: 1234567890*5537483*666699999999999999967777/12345671236789+667785412345-12345/233     = 369184220770065865283121625
    bignum: 1234567890*5537483*666699999999999999967777/12345671236789+667785412345-12345/233     = 369184220770065865283121625   (by bignum function)
test 137 PASSED!!!
    normal: -1234567890*5537483*-666699999999999999967777/-12345671236789+667785412345-12345/233     = -369184220770064529712297039
    bignum: -1234567890*5537483*-666699999999999999967777/-12345671236789+667785412345-12345/233     = -369184220770064529712297039   (by bignum function)
test 138 PASSED!!!
    normal: 1234567890*5537483*666699999999999999967777/1234567123     = 3691842209730830511335195117281
    bignum: 1234567890*5537483*666699999999999999967777/1234567123     = 3691842209730830511335195117281   (by bignum function)


论坛徽章:
145
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
27 [报告]
发表于 2016-01-03 17:08 |只看该作者
本帖最后由 jason680 于 2016-01-03 17:31 编辑

回复 25# substr函数

两次回帖,都看不到......
先回后改...

big number 除法  
ex: 378 / 23

1. 初始
  bn1 = 378  
  bn2 = 23  
  len1 = length("378") = 3
  len2 = length("23") = 2
  len1 须大于等于 len2
  由bn1取出与bn2相同长度
  bn1= 378, dvn=37, bn2=23

2. 先 ==> 除法
  37   >= 23  True, 37 - 23 = 14, _x数组(第一位)加1 = 1
  14   >= 23  False, 取一下位
  148 >= 23  True, 148 - 23 = 125, _x数组(第二位)加1 = 11
  125 >= 23  True, 125 - 23 = 102, _x数组(第二位)加1 = 12
  ...
  56   >= 23  True, 56  - 23 =  33, _x数组(第二位)加1 = 15
  33   >= 23  True, 33  - 23 =  10, _x数组(第二位)加1 = 16
  14   >= 23  False
Answer = 16

3. awk code ( div with unsigned only)
function _div_bu(bu1, bu2, len1,len2,len,n,dvn){
    len1 = length(bu1)
    len2 = length(bu2)
    if(len1 < len2 || (len1 == len2) && (bu1"" < bu2"")) return "0"
    len  = len1 - len2 + 1
    delete _x
    dvn = substr(bu1, 1, len2)
    for(n=1; n<=len; n++){
         _x[n] = 0
         while(_GE(dvn, bu2)){
             _x[n]++
             dvn = _sub_bu(dvn, bu2)
         }
         dvn = dvn get1(bu1, n+len2)
    }
    return _get_ret(len,"x")
}



论坛徽章:
26
2015亚冠之胡齐斯坦钢铁
日期:2015-06-25 21:40:202015亚冠之柏斯波利斯
日期:2015-08-31 17:03:192015亚冠之柏斯波利斯
日期:2015-11-07 13:10:00程序设计版块每日发帖之星
日期:2015-11-10 06:20:00每日论坛发贴之星
日期:2015-11-10 06:20:00程序设计版块每日发帖之星
日期:2015-11-26 06:20:00程序设计版块每日发帖之星
日期:2015-12-02 06:20:00黄金圣斗士
日期:2015-12-07 17:57:4615-16赛季CBA联赛之天津
日期:2015-12-23 18:34:14程序设计版块每日发帖之星
日期:2016-01-02 06:20:00程序设计版块每日发帖之星
日期:2016-01-06 06:20:00每日论坛发贴之星
日期:2016-01-06 06:20:00
28 [报告]
发表于 2016-01-03 17:11 |只看该作者
回复 27# jason680


谢谢 J 神
期待 i .. n .. g .. [   ]

论坛徽章:
145
技术图书徽章
日期:2013-10-01 15:32:13戌狗
日期:2013-10-25 13:31:35金牛座
日期:2013-11-04 16:22:07子鼠
日期:2013-11-18 18:48:57白羊座
日期:2013-11-29 10:09:11狮子座
日期:2013-12-12 09:57:42白羊座
日期:2013-12-24 16:24:46辰龙
日期:2014-01-08 15:26:12技术图书徽章
日期:2014-01-17 13:24:40巳蛇
日期:2014-02-18 14:32:59未羊
日期:2014-02-20 14:12:13白羊座
日期:2014-02-26 12:06:59
29 [报告]
发表于 2016-01-03 21:34 |只看该作者
回复 28# substr函数

测试驱动开发(TDD,Test-driven development)
测试驱动开发(Test-driven development)是极限编程中倡导的程序开发方法,以其倡导先写测试程序,然后编码实现其功能得名。...

$ awk -vTEST=1 -v TEST_LVL=2 -f bignum.awk
test  1 PASSED!!!
    normal: 2 > -3     = True
    bignum: 2 > -3     = True   (by _GT function)
test  2 PASSED!!!
    normal: 2 >= -3     = True
    bignum: 2 >= -3     = True   (by _GE function)
test  3 PASSED!!!
    normal: 2 < -3     = False
    bignum: 2 < -3     = False   (by _LT function)
test  4 PASSED!!!
    normal: 2 <= -3     = False
    bignum: 2 <= -3     = False   (by _LE function)
test  5 PASSED!!!
    normal: 2 == -3     = False
    bignum: 2 == -3     = False   (by _EQ function)
test  6 PASSED!!!
    normal: 2 != -3     = True
    bignum: 2 != -3     = True   (by _NE function)
test  7 PASSED!!!
    normal: 2 + -3     = -1
    bignum: 2 + -3     = -1   (by add_bn function)
test  8 PASSED!!!
    normal: 2 - -3     = 5
    bignum: 2 - -3     = 5   (by sub_bn function)
...
test 134 PASSED!!!
    normal: -1234567890 / -233     = 5298574
    bignum: -1234567890 / -233     = 5298574   (by div_bn function)
test 135 PASSED!!!
    normal: 1234567890 / 233     = 5298574
    bignum: 1234567890 / 233     = 5298574   (by div_bn function)
test 136 PASSED!!!
    normal: 1234567890*5537483*666699999999999999967777/12345671236789+667785412345-12345/233     = 369184220770065865283121625
    bignum: 1234567890*5537483*666699999999999999967777/12345671236789+667785412345-12345/233     = 369184220770065865283121625   (by bignum function)
test 137 PASSED!!!
    normal: -1234567890*5537483*-666699999999999999967777/-12345671236789+667785412345-12345/233     = -369184220770064529712297039
    bignum: -1234567890*5537483*-666699999999999999967777/-12345671236789+667785412345-12345/233     = -369184220770064529712297039   (by bignum function)
test 138 PASSED!!!
    normal: 1234567890*5537483*666699999999999999967777/1234567123     = 3691842209730830511335195117281
    bignum: 1234567890*5537483*666699999999999999967777/1234567123     = 3691842209730830511335195117281   (by bignum function)

   

论坛徽章:
1
技术图书徽章
日期:2016-02-03 16:35:25
30 [报告]
发表于 2016-01-04 14:47 |只看该作者
J神~
在get_num函数中
    if(abs(pos) > len || pos == 0)
        return(0)
这两行有什么作用呢?去掉它不会影响任何东西
感谢~

function get_num(num, pos){
    len = length(num)
    if(abs(pos) > len || pos == 0)
        return(0)
    pos = (pos>0) ? pos : len+pos+1
    return substr(num, pos, 1)
}

回复 8# jason680


   
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年举报专区
中国互联网协会会员  联系我们:huangweiwei@itpub.net
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP