[原创]大整数的开方

ysr · 发表于 2011-2-26 15:13

[watermark]如下方法如何编称，希望指导：
大整数用竖式开方,我觉得比迭代法好,不知是否可编称,用到公式:（a+b+c+d+……）^2=a^2+b(b+2a)+c(c+2a+2b)+d(d+2a+2b+2c)+……
举例：12345671 11111111 11111111先分段，每段必须是偶数位，最高位开方是3513（取整数），余数为4502（也可两位两位开），最后的余数与下一段并在一起得450211111111，除以3513*20000=70260000，商=6047，取余时减数为6047*（6047+3513*20000），余数为14241462，再和下一段并一起1424146211111111，除以35136047*20000，商=2026，则方根整数部分为351360472026，注意商的位数必须全满，不够则在高位添零，如商若为7，则写作0007，
[/watermark][br][br]-=-=-=-=- 以下内容由 ysr 在时添加 -=-=-=-=-
当商值和余数超过1个段位，要分段试除，法见“大整数的除法”

ysr · 发表于 2011-2-27 18:12

都是高手，希望俺的题也与沟通指导，谢谢！

ysr · 发表于 2011-2-27 18:18

大整数的乘除开平方运算，分段位数是，每段小于等于计算机处理位数的1/3，开平方每段必须是偶数位数，加减运算段位位数可以是小于等于计算机处理位数的1/2，这样不会溢出。

ysr · 发表于 2011-4-28 12:39

顶1下,被有用者查阅方便!

ysr · 发表于 2011-4-29 14:23

我的问题希望朋友探讨,顶一下!

ysr · 发表于 2011-12-27 15:19

最新补充版
大整数用竖式开方,比迭代法好,不知是否可编称,用到公式:（a+b+c+d+……）^2=a^2+b(b+2a)+c(c+2a+2b)+d(d+2a+2b+2c)+……
举例：12345671 11111111 11111111先分段，每段必须是偶数位，最高位开方是3513（取整数），余数为4502（也可两位两位开），最后的余数与下一段并在一起得450211111111，除以3513*20000=70260000，商=6047，取余时减数为6047*（6047+3513*20000），余数为14241462，再和下一段并一起1424146211111111，除以35136047*20000，商=2026，则方根整数部分为351360472026，注意商的位数必须全满，不够则在高位添零，如商若为7，则写作0007，
如果余数段位多，可以按大整数的除法算，继续分段，
  由于商为整段的(商若超过1段,说明前面的计算错了,商小了)，除数和被除数可同时去掉相同位数再算，这样的商也是正确的,
  余数过大是商小了，商+1=商，再试，商大了，被除数不够减，商-1=商再试，商过小的判断，余数>方根的2倍则商小了,余数>=方根的2倍是对的,商小了还有可能是商位数没写够,如0007写做7,中间段和末尾均可补0,均须补整段的0,没有半段的,半段的是商末尾为0造成的,如8000等,
判断方根是否正确：最后余数应该小于或等于方根的整数部分的2倍，且方根（取整数）的平方小于原数，方根（取整数）加1的平方大于原数。
例,求6958000001674999998647的方根?
令M=6958 000001 674999 998647,是22位,6位1段分段,最高段方根为83,余数为6958-83*83=6958-6889=69,
83*2000=166000,69 000001/166000=415,166415*415=69062225,大于被除数,所以用69000001-166414*414=69000001-68895396=104605为余数,
83 414*2000=166828000,104605 674999/166828000,数据过长,被除数和除数末尾同时去掉3位,104605674/166828=627,104605 674999-166828627*627=104605674999-104601549129=4125870,
83 414 627*2000=166829254,4125870 998647/166829254000,数据过长,被除数和除数末尾同时去掉3位,4125870 998/166829254=24,(注意商的位数不够补0为024），余数4125870 998647-24*166829254024=121968902071，所以方根为83 414 627 024，要检验是否正确，
数据过长,被除数和除数末尾去掉的位数不能太多，计算机不溢出就行，太多了商会不准确，一般会稍大，如：
104605 674999/166828000,数据过长,被除数和除数末尾同时去掉3位,104605674/166828=627,
被除数和除数末尾同时去掉6位,104605/166=630，过大，要用条件语句，和”商=商-1“循环试商，
也可以这样处理，除数=除数+1，再试商，166+1=167，104605/167=626.3772，上取整得626+1=627，有的还要小，要用条件语句和”商=商+1“循环试商，
例：14585113/997=14629，1458511/99=14732，过大14732-14629=103，1458511/100=14585，过小14629-14585=44，平均（14732+14585）/2=14658，
                                       145851/9=16205，过大16205-14629=1576，145851/10=14585，过小14629-14585=44，平均（16205+14585）/2=15395，
104605674/166828=627，10460/16=653，过大653-627=26，10460/17=615，过小627-615=12，平均（653+615）/2=634，
还可以参考《大整数的除法及求余》的作法，这样做：104605/166=630，104605-630*166=25，25674-630*828=-495966，-495966/828=598，（630+599）/2=614，
可见，去掉位数过多，不易找到准确的商，为了程序简便，可以直接用条件语句，商=商-1，或商=商+1，循环试商，循环次数不能过多，一般不超过商的1/2，如630/2=315，
超过次数就是前面程序出错，商必为1段，超过1段就是前面程序出错，要找出错误重新编程，

还可以这样：把最高位段开方，后被开方数增加1个段位，商加1个段位的9，把商的两个段位的平方，与被开方数的前2个段位比较，若大了，把商的末尾段位减小1/2，就是迭代法，若小了再加剩下的1/2，大了再减剩下的1/2，依次1段段向后算，直到算完！除了最高段，中间的段位必须数字占满，可以写0007这样的数，由于每次必须把方根所有位数乘方，计算量大，浪费资源，大数据不行，用竖式法好。

大整数的乘除开平方运算，分段位数是，每段小于等于计算机处理位数的1/3，开平方每段必须是偶数位数，加减运算段位位数可以是小于等于计算机处理位数的1/2，这样不会溢出。

ysr · 发表于 2011-12-29 11:52

条件语句：余数若大于方根的2倍则商太小，用商=商+1，再试，
商*（除数+商）=积，若大于被除数，则商太大，用商=商-1，再试，可循环试商，直到余数为正值小于或等于方根的2倍，且商*（除数+商）=积小于被除数，

ysr · 发表于 2012-2-9 14:53

收到退稿:
ysr先生/女士：您好！
首先，感谢您对本栏目的关注！
经审阅，认为本文提出的问题不宜作为科学研究的问题，因此予以退稿。

                                                                  此致
敬礼！
                                                                              《科学智慧火花》编辑组
                                                                                          2012年02月08日

这说明对此问题不重视,我不否认还有更好的方法,我的方法虽然简单不是没有技术含量的,细节和技巧不好,也不能编程成功的,速度越快程序越简单越好,是最实际的问题,
怎么说不宜作为科学研究的问题呢?
这是对基础的轻视,对科学不负责,是对科学精神的亵渎!

ysr · 发表于 2012-2-9 15:00

编号标题类型稿件附件投稿时间稿件状态
1 哥德巴赫猜想的1个必要条件（修订版）原稿  无 2012-01-07 13:49:05 处理中
2 哥德巴赫猜想的1个必要条件原稿  无 2012-01-07 13:40:49 已删除
3 大整数的乘法及开方（替代版）原稿  无 2011-12-24 13:06:08 退稿
4 修改：费尔马定理的初等证明（修改版... 修改稿  无 2011-12-20 13:38:54 退稿
5 修改：费尔马定理的初等证明（在线版... 修改稿  无 2011-12-19 22:10:19 退稿
6 RSA公钥密码的破解(完整版) 原稿  无 2011-11-27 18:30:35 退稿
7 RSA公钥密码的破解（补充调整版）原稿  无 2011-11-24 18:14:44 退稿
8 RSA公钥密码的破解(补充举例版的再补... 原稿  无 2011-11-21 17:10:11 处理中
9 RSA公钥密码的破解(补充举例版) 原稿  无 2011-11-20 16:47:18 处理中
10 费尔马定理的初等证明的几何插图原稿  无 2011-11-17 17:54:01 退稿
11 费尔马定理的初等证明(第3页) 原稿  无 2011-11-17 15:13:06 退改已修改
12 RSA公钥密码的破解原稿  无 2011-11-17 14:23:13 退改未修改
13 费而马定理的初等证明(第4页) 原稿  无 2011-11-17 14:03:28 退改未修改
14 费尔马定理的插图原稿  无 2011-11-17 13:43:23 退改未修改
15 费尔马定理的初等证明（在线版）原稿  无 2011-11-17 13:32:40 退改已修改
16 大整数的乘法及开方原稿  无 2011-11-14 12:03:56 处理中
17 大整数的除法及求余原稿  无 2011-11-12 18:24:06 处理中
18 RSA公钥密码的破解原稿  无 2011-11-11 16:21:57 退稿
19 费尔马定理的初等证明原稿  无 2011-11-08 10:36:22 退稿
我要投稿
查看投稿情况
个人资料修改
修改密码

ysr · 发表于 2012-3-25 11:17

刚收到火花的再次退稿信:
ysr先生/女士：您好！
   首先，感谢您对本栏目的关注！
   经专家审阅，认为本稿件的内容比较浅显，可以看作作者的体会，不宜作为科学意义上的文章，不符合本栏目的定位和要求，因此予以退稿。

                                                                  此致
敬礼！
                                                                              《科学智慧火花》编辑组
                                                                                          2012年03月23日

		自动登录	找回密码
密码			注册