2. 处理器的字长和同余总计,1.当m是素数的时候

对于(a/b)%m==?

2.2.1 注明加法结合律:对擅自的自然数a,b,c,(a+b)+c = a+(b+c).
用数学归咎法注脚:
c=0时,(a+b)+0 = a+b (根据引理2.2.2)
a+(b+0) = a+b
一旦当c=n时,等式(a+b)+n= a+(b+n)创设,现在表达c=n++时,等式(a+b)+(n++)=
a+(b+(n++))也树立
(a+b)+(n++)=(n++)+(a+b)=(n+(a+b))++=((a+b)+n)++
a+(b+(n++))=a+((n+b)++))=a+((b+n)++))=
((b+n)++))+a=((b+n)+a)++=(a+(b+n))++
由于(a+b)+n= a+(b+n)
所以((a+b)+n)++=(a+(b+n))++,即(a+b)+(n++)= a+(b+(n++))

1. 问题

1.当m是素数的时候,依据费马小定理,直接出口b^(n-2)即可

2.2.2 若a是正数,注明恰存在一个理所当然数b,使得b++=a.
行使数学归咎法
当a=1时(是那般么?),1=0++,按照公理4,仅存在b=0
假使a=n时,恰存在自然数b使b++=n
当a=n++时,n++=(b++)++,同样基于公理4,仅设有自然数b++使等式成立。
(也就是说,任何一个不为0的自然数一定是某个自然数的后继。只依照公理3能查获倘若一个数不是其余自然数的后继它就是0啊?)

俺们领悟,在处理器中是用补码来存放在实际的正负数的,那么总结机为什么要用补码来存放数据,计算机教材中,那多少个补码
= 反码 + 1的公式又是怎么来的?

2.否则,伸张欧几里得exgcd(b,m,x,y)

2.2.3 自然数的序的基本特性
(a) 序是自反的:a>=a.
证实:a = a + 0,即存在自然数n = 0使 a = a + n

要精晓那个问题的答案,大家先要通晓部分基本的知识,最宗旨的同余公式那里就不讲了,看本帖在此之前要求去离散数学或数论中询问下中央的同余运算即可。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int a,b,m;
 7 int x,y;
 8 int exgcd(int a,int b,int &x,int &y)
 9 {
10     if(b==0)
11     {
12         x=1;
13         y=0;
14         return a;
15     }
16     int r=exgcd(b,a%b,x,y);
17     int tmp=x;
18     x=y;
19     y=tmp-a/b*y;
20     return r;
21 }
22 int fastpow(int a,int p)
23 {
24     int base=a;int ans=1;
25     while(p!=0)
26     {
27         if(p%2==1)ans=ans*base;
28         base=base*base;
29         p=p/2;
30     }
31     return ans;
32 }
33 int main()
34 {
35     scanf("%d%d%d",&a,&b,&m);
36     for(int i=1;i<=sqrt(m);i++)
37     {
38         if(m%i==0)
39         {
40             int ans=exgcd(b,m,x,y);
41             printf("%d",(a*ans)%m);
42             return 0;    
43         }
44     }
45     printf("%d",fastpow(b,m-2));
46 }

(b) 序是传递的: 若 a>=b 且 b>=c, 则 a>=c
表明: a>=b, 那么存在自然数m使得 a = b + m
b>=c, 那么存在自然数n使得 b = c + n
a = b + m = c + n + m = c + (n + m) , n + m 为自然数(按照加法的定
义),即 a >= c
(c)序是置之度外称的: 若a>=b 且 b>=a, 则 a=b
证明: a = b + m
b = a + n
a = a + n + m = a + (n + m)
a = a + 0 = a + (n + m )
基于加法结合律和命题2.2.6有 n + m = 0
若 n != 0, m = 0, 则 n + m = n + 0 = n != 0, 与 n + m = 0矛盾
若 n = 0, m != 0, 则 n + m = 0 + m = m != 0, 与 n + m = 0矛盾
若 n != 0, m != 0,则基于加法的概念,n + m 必为某个自然数的后继,而
n + m = 0 不为任何自然数的后继,所以依然龃龉
所以 n = 0, m = 0
即 a = b
(d) 加法保序: a >= b 当且仅当 a + c >= b + c
证明:(1) 先证 a >= b时, a + c >= b + c
留存自然数 m 使a = b + m, a + c = b + m + c = b + c + m
即 a + c >= b + c
(2) 再证 a + c >= b + c时, a >= b
留存自然数n 使得 a + c = b + c + n, 按照命题2.2.6有
a = b + n, 即 a >= b
(e) a < b 当且仅当 a++ <= b.
证实: (1) a < b ,则 存在自然数m , b = a + m且 b != a, 由反正法知 m
!= 0,
那就是说 m 必为 某一自然数n 的后继 即 m = n++ (按照习题2.2.2)
则有 b = a + (n++) ,依据推测 n++ = n + 1 可得到
b = a + (n + 1) = a + (1 + n) = ( a + 1) + n = (a++) + n,即 a++ <=
b
(2) a++<=b, 则 存在自然数m使b = (a++) + m
b = (a++) + m = a + 1 + m = a + (m++)
基于英里3有 m++ != 0, 则 b != a 也就是 a < b
(f) a < b 当且仅当对于某正数d,b = a + d
表达: (1)a < b, 存在自然数m 使得 b = a + m且b != a, 由反正法知 m
!= 0
也就是m是正数,则存在正数d 使得 b = a + d
(2) b = a + d ,若d 为某正数即 d != 0,也就是说 b != a, 那么 a < b

 

 

2. 电脑的字长和同余计算

电脑的字长是指统计机运算时,能存放的最大数字的的位长,如我辈常说的32位机,字长就是32位的,寄存器唯有32bit,最多能放32个1,能发布的最大数字就是232

  • 1

当跨越这些数字后,由于不可以储存,会被电脑放任,同时会安装CPU的溢出标志位,那就是所谓的溢出

为了不难,大家用8位机来做示范,即最大能表示的数字是28 – 1

记m = 28

故而,统计机的统计 (a + b)时,实际上计算的是 (a + b) % m (mod
m),超越m的局地都会被甩掉,只取余数的局地,即计算机中的计算实际都是一个模m的同余计算

如 1000 0000 + 1000 0001 = 1 0000
0001

是因为最高位胜出最大可以代表的数,多出的位将溢出屏弃,所以最后的结果为
0000 0001 = 1

 

3. 补码的概念和计算

设m > b >= 0,b为整数

则b的补 b = m – b
(注意,那里定义的是补,而不是补码,不要弄混了)

鉴于有正负数,总计机中对正负数的补码举行了差异定义:

1>
正整数b的补码为自己,即b的补码仍为b

2> 负整数-b的补码为b的补,即b

我们理解,a – b即可转接为 a + (-b),如果用补码来运算

a – b = a + (-b)  (mod m) 在电脑中计算的是 a + b  (mod m)

那就是说她们的同余吗(即他们模m后的值分外吗)?

∵ b = m – b

∴ a + b = a + (m – b)

          ≡ a – b (mod m)

∴ 将负数转化为补码进行统计后,如故是确立的

之所以,统计机中用补码来储存所有的数后,就不须要充实减法器了,用加法器就可以代替总计减法,那样能节约电路设计,当然,那还只是中间的一个利益之一

 

4. 负数的意味和运算

面前讲了统计机中用补码来囤积数字,大家领悟,在8位机中,-1的补码为 1111
1111 =
255,那么在8位机中,这么些数字即可以表示是-1的补码,也得以象征是255的补码,那就发出一个冲突了。

为了缓解那种争执,总计机中,从可用的8位中挪用了一个最高位来差异正负数,即当最高位为1时,该数为负数,为0则代表正数

诸如此类,由于最高位被挪用,8位机在代表正负数时,就唯有7位有效数字了,设m2
= 27 = 1000 0000 = 28 / 2 = m/2

正负数仍用低7位的补码来表示,此时的模要换成m2了。

如-1,1模m2的补码为 (m2-1) = 0111
1111,然后将最高地方为1,最终在微机中意味为: 1111 1111(即oxFF)

图片 1

图片 2

 

那儿,大家面前定义的补码还有用呢?运算的规律还须要改变吧?

1> a + b

当 a + b 小于 m2时,不会向符号位进位,所以结果就是 a +
b,没问题

当2个正整数相加大于或等于m2时,就会向最高位进位,那时相对m2来说是溢出了,最高位会变为1,即(a+b)最终会获取一个负的结果,那些结果是抽象的,所以计算时要留意结果是不是溢出

测试代码:

图片 3

设置带符号和10进制显示:

图片 4

测试结果:

从图中得以见见,100 + 100 = 200 = 0xC8 =1100 1000 = –56

由于计算溢出,明显-56不是大家想要的结果

 

2> a + (–b)

当加上一个负数时,-b在总结机中的带符号的补码表示为: m2 +
(m2 – b) = 2m2 – b = m – b   (m2 =
1000 0000,任何低于m2的数拉长m2就一定于将其标志位变为1)

∴ a – b = a + (m – b)

         ≡ a – b (mod m)

即带符号的补码在负数运算中,依然有效

但有个问题,若是 a > b, a-b 为正数,计算甘休后符号位应该是0,当a
< b时,a-b 为负数, 符号位应该是1,景况是那样的吗?

4.2.1 当 a > b时

∵ a < m2

∴ a – b < m2 – b < m2

∴ (a – b)不会当先m2,即不会溢出到符号位,符号位仍会为0

4.2.2 当  a < b时

a – b ≡ m + a – b  (mod m)

       ≡ 2m2 + a – b   (mod m)

       ≡ (m2 – b) + m2  + a   (mod m)

∵ m2 >  b

∴ (m2 – b) > 0

m > (m2 – b) + m2  + a > m2 

∴ a < b时,一定会向符号位溢出,即符号为一定会变成1

同时,a –
b ≡ a – b (mod m2)

∴ 溢出后,低7位的数与a-b仍是同余的

于是,带符号位的补码运算,仍和不带符号位的补码运算规则一样,总计时将标志位带入总计,结果依旧依然一如既往,那样补码的第三个好处就出来了,即意味着带符号的统计时,不用关切符号位。

 

4.2.3 当 a == b时,以及a和b中有0的情况

那么些情景很简短了,就不表达了

 

5. 补码和反码

这就是说怎样求一个数的补码呢,正数没问题,就是自身,但负数呢,下面已有大约的公式
–b → b = m – b,
但这里需求用到减法计算,而为了节约电路设计,大家用补码是为着省去减法器的,那就龃龉了,怎么办?

看过书的同班早已知晓,用反码来统计 : 补码 = 反码 + 1

本条公式怎么样来的:

1> 反码的概念

咱俩精晓,反码即是讲原来为0的位变为1, 为1的位变为0,

俺们也知道一个会聚加上其反,就极度全集

即b + ~b = 1111 1111 = 28 – 1 =
m – 1

∴ m = b + ~b + 1

∴ b = m – b = (b + ~b + 1) – b =
~b + 1

那就是补码运算的大名鼎鼎公式的源点

相关文章