求解模平方根的算法(答得完整我会再追加分数)

平方根真心听不懂 求解~

平方根就是一个数开根号，需要记住1~25的平方、就能自然地知道平方根
若平方根非整数 只需要外面加个根号
若一个数是一个整数平方*一个非整数平方 如125
则需要将25提取变成5根号5
一个数的平方根有两个 两个为相反数
大概就是这么点了

一、开平方的手动算法
此方法是在高一学万有引力和航天时，因需要大量开平方运算又不能用计算器，而被逼无奈研发的。
开平方的整个过程分为以下几步：
（一）分位
分位，意即将一个较长的被开方数分成几段。具体法则是：
1、分位的方向是从低位到高位；
2、每两个数字为一段；
3、分到最后，最高位上可以不满两个数字，但不能没有数字。
如：43046721分位后是43｜04｜67｜21
12321分位后是1｜23｜21
其中，每段中间的竖线在熟练了以后可不必写。
分位以后，其实就能看出开方后的结果是几位数了，如43046721分位后是四段，那么开方结果就是四位数。
（二）开方
开方的运算过程其实与做除法很类似，都有一个相乘以后再相减的过程。
这里以43046721为例。
分位后是43｜04｜67｜21
运算时从高位到低位，先看前两位43，由于62最接近43而不超过43，因而商（这里找不到合适的字眼，因而沿用除法时的字眼）6，然后做减法（如下图）：
6
———————————————
4 3｜0 4｜6 7｜2 1
3 6
————————
7 0 4
这里一次落两位，与除法不同。
下面的过程是整个算法中最复杂的部分，称为造数，之所以用这个词是因为算出最后要减掉的数的过程较为麻烦。
首先，将已商数6乘以2：6×2=12
这里的12不是真正的12，实际上是120，个位上的0之所以空出来是为了写下一个要商的数。
我们不妨假设下一个要商的数为A，我们下面要考虑的问题就是：从0-9中找一个A，使得：
12A×A最接近但不超过上面余下的数704。注意，A在这里代表一个数位，若A=6，那么12A的含义不是12×6，而是126。
以上过程与除法中的试商的过程很类似。
经验证，125×5=625符合要求，因此下一个要商的数就是5。（如下图）

往下依此类推：
65
×2
———
130


1306
× 6
————
7836

656
×2
———
1312


13121
× 1
————
13121



所以，43046721的算术平方根为6561
从开方的过程中我们可以看出，越到后面，计算量越大，因此，凭我们的计算量，再算一些开不尽的数时，如7的算术平方根，其精确程度是非常有限的。
以上就是开平方的一般方法，请列位指教。



二、开立方的手动算法
此方法是昨天刚刚研发成功的，为了应付在由体积求分子半径时产生的开立方的运算。
开立方的方法与开平方的方法很类似，但要复杂很多，如果不能熟练掌握，倒不如按大脸猫说的方法：凑！当然，熟练掌握以后，比凑的方法是快多了。
开立方的过程分以下几步：
（一）分位
与开平方基本一致，只有一点：这次是每三位为一段
（二）开方
这里以41063625为例
第一个要商的数的确定与开平方是类似，只是变成了要找一个数的立方（如下图）：
3
——————————————
4 1｜0 6 3｜6 2 5
2 7
————————
1 4 0 6 3
一次落三位！
下面的造数过程是最麻烦的，流程如下：

1、将已商数乘以3。3×3=9
2、将要商的数乘以3后，向后错一位加在第1步算出的数上：
4×3=12
9
+ 12
———
102
3、将第2步得出的数乘以已商数：102×3=306
4、将要商的数平方以后，向后错一位加在第3步算出的数上
42=16
306
+ 16
————
3076
5、将第4步中算出的数乘以要商的数，使它最接近又不超过余下来的数：
3076×4=12304
12304就是我们要造的数，将这个数代回原来的开方式减掉就可以了。



3 4
——————————————
4 1｜0 6 3｜6 2 5
2 7
————————
1 4 0 6 3
1 2 3 0 4
—————————————
1 7 5 9 6 2 5
有人肯定会问，你怎么知道要商的数就是4？的确，我一开始也不知道，确定要商的数的过程实际上就是类似开平方中的试商的过程，但这个过程比开平方是要繁琐得多。
当做完造数过程的第1步以后，得出了9这个数，由于不知道应该商几，所以，我们可以先假设商0，那么依据第2步，90×3=270。270错位加一个数，等于扩大了10倍还多，由于我们假设商0，由第3步，270变成了2700。这是我们就要看一看2700乘以一个什么数最接近且不超过14063，这个数可能（这里说“可能”的原因从下文可以看到）就是我们要商的数。乍一看5非常合适，但你要考虑到我们在假设商0时少加了多少东西，所以商5可能就超了。经验告诉我们，4和5都有可能，此时我们可先取5为要商的数，然后进行1-5各步，结果发现的数已经超过了14063，因此4就是我们要商的数。
注：这个试商的过程在熟练了以后是一眼就能看出来的。
下面的步骤可依此类推：
34
×3
————
102
+ 15 （3×5）
————
1035
× 34
————
4140
3105
————
35190
+ 25 52
————
351925
× 5
————
1759625



这里的5是怎么商出来的不用我再说一遍了吧？

整个流程相当繁琐，丢其中任何一步都可能导致前功尽弃，因此必须要求计算准确。熟练了以后，速度是可以保证的。我曾经把手动开方法和凑数法比较过，前者比后者至少快一倍。
另外，值得注意的是：如果已知结果是整数，那么结果最后一位的确定可不必用以上方式，直接根据立方数末位的特异性就可确定，但前提是对1-9的立方表非常熟悉。1-5的立方表同志们应该都很熟悉，以下几个是不常用的：
63=216 73=343 83=512 93=729


结语：这两种方法可用来准确地进行开平方及开立方的运算，只要有耐心，想算几位就算几位。但开立方的过程实在是很复杂，很可能还存在优化方案，但由于时间紧迫，我没有再考虑其他的方法。同志们谁要是有兴趣，可以使这优化这两个算法，我的方法仅供参考。

※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※
#!/usr/bin/python
#coding=gbk
import math
def quick_algorithm(a,b,c): #y=a^b%c,a的b次幂余除c
a = a % c
ans = 1
#这里我们不需要考虑b<0，因为分数没有取模运算
while b != 0: #费马小定理
if b & 1:
ans = (ans * a) % c
b>>=1
a = (a * a) % c
return ans
def IsHaveMoSqrt(x,P):#是否有模平方根y*y=x mod p，已知x，p，判断是否存在y
ret = quick_algorithm(x,(P-1)//2,P)
if ret==1:
return True
else:
return False
def GetMoSqrt(x,P):#求模平方根y*y=x mod p，已知x，p求y
if(IsHaveMoSqrt(x,P)==1):
t=0
s=P-1#P-1=(2^t)*s //s是奇数
while s%2==0:
s=s//2
t=t+1
if(t==1):
ret = quick_algorithm(x,(s+1)//2,P)
return (ret,P-ret)
elif (t>=2):
x_=quick_algorithm(x,P-2,P)
n=1
while(IsHaveMoSqrt(n,P)==1):
n=n+1
b=quick_algorithm(n,s,P)
print(b)
ret = quick_algorithm(x,(s+1)//2,P)#t-1
t_=0
while(t-1>0):
if(quick_algorithm(x_*ret*ret,2**(t-2),P)==1):
ret=ret
else:
ret=ret*(b**(2**t_))%P
t=t-1
t_=t_+1
return (ret,P-ret)
else:
return (-2,-2)
else:
return (-1,-1)
def Secp256k1GetYByX(x):#y^2=x^3+7 (mod p)根据x求y
a=(x*x*x+7)%0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
ret = GetMoSqrt(a,0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
return ret
if __name__ == "__main__":
if True:
x=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798#私钥为1,对应的公钥x
ret = Secp256k1GetYByX(x)#secp256k1，根据x求y
print("x=%x" % (x))
print("y=%x" % (ret[0]))
print("y=%x" % (ret[1]))
print("")
x=1#x最小值
ret = Secp256k1GetYByX(x)#secp256k1，根据x求y
print("x=%x" % (x))
print("y=%x" % (ret[0]))
print("y=%x" % (ret[1]))
print("")
x=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F-3#x最大值
ret = Secp256k1GetYByX(x)#secp256k1，根据x求y
print("x=%x" % (x))
print("y=%x" % (ret[0]))
print("y=%x" % (ret[1]))
print("")
input()
※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※

#include<stdio.h>

int main()
{
int a,n,i;
int x[10000],c=0;
scanf("%d%d",&a,&n);
a%=n;
for(i=0;i<n;i++)
{
if(i*i%n==a)
{
x[c++]=i;
}
}
for(i=0;i<c;i++)printf("%d ",x[i]);
puts("");
return 0;
}

---

清流县19618574316： 求解模平方根的算法(答得完整我会再追加分数) - ？
枝文枸櫞： ※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※※ #!/usr/bin/python #coding=gbk import math def quick_algorithm(a,b,c): #y=a^b%c,a的b次幂余除c a = a % c ans = 1 #这里我们不需要考虑b<0,因为分数没有取模运算 while ...

清流县19618574316： 求复数的模的公式是啥 - ？
枝文枸櫞： 假设其为a+bi,则它的模为a^2+b^2的算术平方根.参考资料:人教版高三数学2007年.

清流县19618574316： 虚数的模怎么算? - ？
枝文枸櫞： (1)复数形如:a+bi.模=√(a^2+b^2). 例如虚数:1+2i,求它的模就是直接代入公式:模=√(a^2+b^2)=√5(其中a=1,b=2). (2)虚数形如:bi.模=√(b^2)=丨b丨. 例如虚数2i,求它的模,就是丨2丨=2. 数学中的虚数的模.将虚数的实部与虚...

清流县19618574316： 平方根如何计算 - ？
枝文枸櫞： 把369从右往左每两位数分为一节,解3'69.用近似除法的方法.首先从左边看第一节的数3,大于1的平方,小于2的平方,所以商1.3-1=2.然后,把69写在2的后面,即269.把第一个商1乘以20,(20+a)*a.a是第二次的商,积小于等于269.可以商9,...

清流县19618574316： 求平方根立方根的算法 - ？
枝文枸櫞： 就是分解质因数,挑出完全平方数,开出来剩下的放根号里面 比如根号32,32=16*2,根号32=4根号2 根号18就可以分解为:根号下:9*2 9又是3的平方 那么根号2开不出来 就成了:3又根号2

清流县19618574316： 如何快速计算平方根 - ？
枝文枸櫞： 比如136161这个数字,首先找到一个和136161的平方根比较接近的数,任选一个,比方说300到400间的任何一个数,这里选350,作为代表. 先计算0.5(350+136161/350),结果为369.5.然后再计算0.5(369.5+136161/369.5)得到369.0003,...

清流县19618574316： 如何计算平方根? - ？
枝文枸櫞： 述求平方根的方法,称为笔算开平方法,用这个方法可以求出任何正数的算术平方根,它的计算步骤如下: 1.将被开方数的整数部分从个位起向左每隔两位划为一段,用撇号分开(竖式中的11'56),分成几段,表示所求平方根是几位数; 2.根...

清流县19618574316： 怎样求一个数的平方根? 越简单越好. - ？
枝文枸櫞： 用二分法求解,首先找到要求平方根的这个数在哪两个整数的平方之间,比如求47的平方根,6²不过如果你有计算器的话那另当别论了,直接用计算器算出来就好了

清流县19618574316： 平方根怎么求解 - ？
枝文枸櫞： 不用平方根表和计算器,可不可以求出一个数的平方根呢? 先一起来研究一下,怎样求,这里1156是四位数,所以它的算术平方根的整数部分是两位数,且易观察出其中的十位数是3.于是问题的关键在于;怎样求出它的个位数a?为此,我们从...

清流县19618574316： 怎样计算一个数的平方根? - ？
枝文枸櫞： 方法一,用计算器 方法二,用二分逼近法,比如计算5的平方根,那么2^2=4,3^2=9,可以知道√5在2和3之间,而后计算2.5^2=6.25>5,可以知道√5在2到2.5之间,不断重复这个过程可以计算出√5任意位小数.方法三,牛顿迭代法,参考任意计算方法教材 方法四,级数展开法法 ……