xyaoy
发表于 2021-10-25 17:33
ysr 发表于 2021-10-25 17:31
谢谢沟通指导!我不会VC,用VB程序的确速度太慢。
你这个平方根是用的迭代法吗?据说是迭代法计算速度快 ...
二分法,找一个数n n*n<m<n&(n+1) 这个算法是在网上查的
ysr
发表于 2021-10-25 17:35
xyaoy 发表于 2021-10-25 09:33
二分法,找一个数n n*n
额,二分可以,谢谢沟通探讨!可惜我不会VC,需要学习一下,欢迎指导!
xyaoy
发表于 2021-10-26 08:04
ysr 发表于 2021-10-25 17:35
额,二分可以,谢谢沟通探讨!可惜我不会VC,需要学习一下,欢迎指导!
二分是很快的,对于1024位数字,找它最近的整数平方根大概需要不到1秒
xyaoy
发表于 2021-10-26 08:07
ysr 发表于 2021-10-25 17:35
额,二分可以,谢谢沟通探讨!可惜我不会VC,需要学习一下,欢迎指导!
我研究rsa私钥的获取,感觉余数问题很难,想到的每一个想法都效率低下,对于小数可行的方法,到了大数之后效率就急剧下降,因数太多
ysr
发表于 2021-10-26 08:39
xyaoy 发表于 2021-10-26 00:07
我研究rsa私钥的获取,感觉余数问题很难,想到的每一个想法都效率低下,对于小数可行的方法,到了大数之 ...
是的大数位数太多,如果方法正确需要提高精确度,比如整数部分仅仅末尾5位数字与实际不同,那就可以分解大数了,如果仅仅最高位等于或者接近实际,那就是差距太大。
余数的变化是波动的非线性的,如何按线性计算呢?方法是大致可以认为余数r改做余数为p+r或者np+r。
当然这是短距离内适用。并不是严格的线性,得到的数值接近实际,需要其它方法修正,我前面的方法就是这样的。
修正公式虽然准确但前提是前一步必须接近实际,二者必须结合起来才能更接近实际。我的方法仅仅供参考。
ysr
发表于 2021-10-26 08:43
xyaoy 发表于 2021-10-26 00:04
二分是很快的,对于1024位数字,找它最近的整数平方根大概需要不到1秒
是吗?我不会用需要学习,我用的是模仿手工开平方根的方法,效率低速度太慢,结果是准确可靠的。
xyaoy
发表于 2021-10-26 08:43
ysr 发表于 2021-10-26 08:39
是的大数位数太多,如果方法正确需要提高精确度,比如整数部分仅仅末尾5位数字与实际不同,那就可以分解 ...
p是什么?较小素数么?这种假定不能成立啊?
ysr
发表于 2021-10-26 08:48
本帖最后由 ysr 于 2021-10-26 00:53 编辑
xyaoy 发表于 2021-10-26 00:43
p是什么?较小素数么?这种假定不能成立啊?
p是试除因子,当然,p也是通过前面的方法求出来的估计值,是接近实际的。
大致是线性变化的,不是严格的线性变化,这样处理后余数大致上不波动了,而是递增的增量不是严格的等差但大致上可以认为是等差。
xyaoy
发表于 2021-10-26 08:48
ysr 发表于 2021-10-26 08:43
是吗?我不会用需要学习,我用的是模仿手工开平方根的方法,效率低速度太慢,结果是准确可靠的。
二分的结果也很可靠,毕竟他找到的数字满足了不等式就必然是整数的平方根,并且把除法转成了乘法,速度很快
xyaoy
发表于 2021-10-26 08:53
ysr 发表于 2021-10-26 08:48
p是试除因子,当然,p也是通过前面的方法求出来的估计值,是接近实际的。
我这个数字:
141200934203348100398237203092056603810497665953866503938436185453188653157534841542476799951117838232625775007972565407157639296613520419503480411605352582268797113156766586228582255481135809096970885597928003710586870460226020496368765994413857405308613414568674463104615847526186185331402709548604450804313
试除因子是多少?这个数字是309位,它的试除因子位数是多少位?
页:
1
2
3
4
5
6
7
8
9
[10]
11
12
13
14
15
16