因为一个整数p，若检测为合数，这永远是真命题；而检测为素数，这命题只以较大概率成立。 可构造一种NP检测算法，步骤如下：
1. 猜测p（位长度n）的因子列表｛p1,p2,…pi｝，这是非确定的，每个分支耗时O(n)
2. 验证p1*p2*…pi？=p-1，耗时不超过O(n^2)
3. 若各因子乘积等于p-1，则用当前算法递归验证每个因子都是素数
4. 随机选择p最小剩余系内的一个数x，计算x^((p-1)/q) （q遍历上述列表经过步骤3验证过的素因子）是否都不同余于1模p，若是则必有x^(p-1)同余于1模p，则由指数整除p的欧拉数及费马小定理，知p为素数，考虑到有少量的合数也满足费马小定理，故需多次选择x重复验证，选择个数最多为log(p)
分析：本算法涉及的数论定理——设p是奇素数，p-1的所有素因子是q1,q2,…qs，那么g为原根的充要条件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
结论：第3步可以看成递归调用树，每个顶点为待检测整数，其每个子结点为一个因子，则最多n层，每层至多耗时O(n^4)，所以每个路径即检测p是否素数的非确定任一分支中，总耗时O(n^5)。 2002年，印度科学家发现素检测确定性多项式时间算法，于是从NP前进到了P
posted @
2023-09-09 08:07 春秋十二月 阅读(695) |
评论 (0) |
编辑 收藏为什么命题逻辑有效性是可判定的，而谓词逻辑有效性是不可判定的？
因为命题逻辑由有限个合式公式及原子命题构成，且原子命题的取值只有真、假两种，简单的判定方法是真值表穷举，其复杂度为指数级：2^N，N为原子命题数量。快速的方法是先转成合取范式（输入是由否定、而且、或者、蕴含四种连接词构成的语法正确的命题逻辑公式，经过对公式结构归纳作蕴含释放、否定原子、分配律变换三步处理，同时运用DAG优化：共享终止即叶子结点、删除冗余的测试结点、删除重复的有相同子图结构的内部结点，输出等价最小的合取范式），再检测合取范式的有效性（检查所有子句，若每个子句包含至少一个原子及其否定形式，则有效，否则因为存在一种真值指派使其为假而导致整个合取范式无效），其复杂度为多项式级：N*logN+N，N为公式长度。谓词逻辑基于命题逻辑扩展，添加了变元、函数、量词“所有”与“存在”，如果量词没有约束变元范围即定义域无限，那么函数值域也是无限的，另外可能引入的自由变元不受限制，这导致了解空间是无限的，所以不存在通用算法去判定任意谓词逻辑公式是否有效，具体证明可以用pcp归约，即构造一组特定的谓词逻辑公式，它是有效的当且仅当pcp实例有解，又已知pcp是不可判定的，故该特定谓词逻辑有效性是不可判定的，由于任意包括特定，所以谓词逻辑有效性是不可判定的
posted @
2023-09-09 08:05 春秋十二月 阅读(104) |
评论 (0) |
编辑 收藏设程序片段S=if C then S1 else S2，S1和S2可以是由赋值、条件、循环构成的复杂语句，S不为当前程序最后语句或某个循环主体最后语句，则S对应的流图生成的深度优先生成树T有3条树边，有S1的出口数+S2出口数-1条交叉边。为什么是3条树边？C到S1、C到S2、S1或S2到S3（S3是S后继结点，下同）。为什么交叉边数是S1出口数+S2出口数-1？因为流图中S1出口及S2出口到S3的边，在生成T的过程中，只有1个出口比S3先访问，这对应形成1条树边，访问S3后再访问其它出口，这对应形成其它出口到S3的交叉边，注意这里没有前向边，因为较晚访问的出口在T中不可能是S3的祖先。如果把S改为if C then S1，情况会怎样？结果取决于生成T的过程中先访问S3还是S1。若先访问S3，则有树边2条：C到S3、C到S1，交叉边数等于S1的出口数：S1的每个出口到S3各一条边，没有前向边。若先访问S2，则有树边1条：C到S2，前向边1条：C到S3，交叉边数等于S1出口数-1。
总结此类问题分析的基本思路是对程序控制结构先构建流图，再构建深度优先生成树，辨别其中的前向边、交叉边、后退边
posted @
2023-09-07 06:50 春秋十二月 阅读(74) |
评论 (0) |
编辑 收藏1.闭包记录分配：若逃逸分析能识别哪些闭包记录在创建它们的函数中是出口不活跃的，则这些闭包记录可分配在栈帧中（不再是堆中）
2.内联扩展：由于小函数较多，因此内联可以免去调用开销而提高性能，对于递归函数，需先用循环前置头转换再内联，如果是尾递归函数，可先使用尾调用优化删除递归。如果一个函数的所有调用都被内联扩展，并且该函数没有作为参数传递或其它方式被引用，那么可以删除这个函数本身即函数定义。内联扩展可以继续作用于扩展后的函数体，只要存在函数调用，这也叫层叠式内联
3.循环不变量参数外提：递归函数经过循环前置头转换后，若每次递归调用头函数，传入的某些参数值总不变，则可以将它们从函数参数中删除，函数体中的每次使用出现用序曲函数对应的参数名替换
4.解开嵌套的let：将嵌套的多层let中的代码合并为一个let中的代码，in中的代码不变
5.避免代码膨胀：由于内联复制函数体，通常使程序体积变大，且层叠式内联可无限扩展下去，因此为避免代码膨胀，有如下启发式策略对内联进行控制
a) 只内联执行很频繁的函数调用，可根据静态估计比如循环嵌套深度、迭代次数，或根据执行剖面分析反馈，计算函数的执行频率
b) 内联很小的函数，其函数体不会比直接调用多出较多指令
c) 内联只调用一次的函数，然后删除原来的函数定义
posted @
2023-09-07 06:47 春秋十二月 阅读(74) |
评论 (0) |
编辑 收藏1. 整数r>s>0，(r, s)=1，2∤r+s，x=r^2-s^2, y=2rs, z=r^2+s^2，求证(x, y)=1，(y, z)=1
证明：由2∤r+s（r与s必一奇一偶）知2∤r-s，故2∤r^2-s^2，以及2∤(r+s)(r+s)。又1=(r, s)=(r+s, r)=(r+s, s)=(r+s, rs)。同理得1=(r, s)=(r-s, rs)，故1=((r+s)(r-s), rs)=(r^2-s^2, rs)，又1=(2, r^2-s^2)，故(r^2-s^2, 2rs)=1，即(x, y)=1。(y, z)=(2rs, r^2+s^2)=(2rs, r^2+s^2+2rs)=(2rs, (r+s)(r+s))=(rs, (r+s)(r+s))=(rs, r+s)=(r, r+s)=(r, s)=1
注：用最大公约数定义、整除性质、反证法，也可以得出(x, y)=1，(y, z)=1。本法则直接从最大公约数定理推导
2. u^2+3v^2=2p不可能成立，u、v为整数，p为奇素数
证明：u^2+3v^2=2p => u^2+v^2=2(p-v^2) => 2|u^2+v^2=(u+v)^2-2uv => 2|(u+v)^2 => 2|u+v。得出这个中间结论，再由它可得4|2(u+v)|2v(u+v)=2v^2+2uv，以及4|(u+v)^2=u^2+v^2+2uv，故得4|u^2+3v^2+4uv，继得4|u^2+3v^2=2p，即2|p，所以矛盾，证毕
3. 若四个正整数y1*x2=y2*x1，(x1,y1)=(x2,y2)=1，则x1=x2，y1=y2
证明：由y1*x2=y2*x1可得x1|y1*x2，又因(x1,y1)=1，故x1|x2；另得x2|y2*x1，又因(x2,y2)=1，故x2|x1；终得x1=x2，y1=y2
4. 假设2∤z，z^3=x^2+3y^2有解且满足(x, y)=1，其通解形式为x=a^3-9ab^2，y=3a^2b-3b^2，a、b满足z=a^2+3b^2，求证(-3/p)=1，p是z的任一素因子；(a, 3b)=1
证明：先论证中间结论3∤z，p>3且(p, xy)=1。若3|z，则3|x^2+3y^2=>3|x^2=>3|x=>9|x^2，另有9|x^2+3y^2=>9|3y^2=>3|y^2=>3|y，这与(x, y)=1矛盾，故3∤z。又2∤z，得p>3，由此若p|x，则p|3y^2得p|y，或若p|y，则p|x^2得p|x，都与(x, y)=1矛盾，故(p, xy)=1。
再论证勒让德符号(-3/p)=1。由以上中间结论得等价形式x^2+3y^2=(Z^3p^2)p，及p∤x^2、p∤y^2，推得1=(x^2/p)=(-3y^2/p)=(-3/p)。
最后论证(a, 3b)=1。假设2|z，则2|a^2+b^2=(a+b)^2-2ab或(a-b)^2+2ab =>2|a+b, 2|a-b。因题设是2∤z，故2∤a+b, 2∤a-b，由此推得2∤a^2-b^2, 4∤a^2-b^2，进而8∤a^2-b^2，即(8, a^2-b^2)=1。由1=(x, y)=(a^3-9ab^2, 3a^2b-3b^2)=(a(a^2-9b^2), 3b(a^2-b^2))。又(a^2-9b^2, a^2-b^2)=(8b^2, a^2-b^2)=(b^2, b^2-a^2)=(b^2, a^2)=(a, b)^2，于是令a^2-9b^2=(a, b)^2*A, a^2-b^2=(a, b)^2*B，则得1=(x, y)=(a, b)^2*(aA, 3bB)，故(a, 3b)=1
5. 已知2∤u+w，3∤u，(u, w)=1，求证(2u, u^2+3w^2)=1
证明：2∤u+w=>2∤u^2+w^2=>2∤u^2+3w^2，即(2, u^2+3w^2)=1。
由3∤u，(u, w)=1得(u, 3w)=(u, 3w^2)=(u, u^2+3w^2)=1。
综上两式结果得(2u, u^2+3w^2)=1
6. 已知(3v, w)=1，2∤3v+w，求证(18v, 3v^2+w^2)=1
证明：(3v, w)=1=>(3v, w^2)=(3v, 3v^2+w^2)=1。
(3v, w)=1=>(3, w)=1=>(3, w^2)=(3, 3v^2+w^2)=1。2∤3v+w=>2∤v+w=>2∤v^2+w^2=>2∤3v^2+w^2，即(2, 3v^2+w^2)=1。
综上三式结果得(18v, 3v^2+w^2)=1
###############################
从1、5和6问题的证明过程可得，如果一个数由两个或多个因子相乘，那么求证是否互素可以逐一求每个因子与另一个数是否都互素
posted @
2023-09-07 06:43 春秋十二月 阅读(630) |
评论 (0) |
编辑 收藏周知aes有限域同构于系数为F2域一元多项式环的商环，其理想由不可约多项式m(x)=x^8+x^4+x^3+x+1生成，即F2^8≌F2[x]/(m(x))。这次进一步用域扩张的观点分析，可以得知F2[x]/(m(x))正是包涵m(x)零点的扩域，设为K。那么如何理解？
令I=(m(x))，则K=F2[x]/I，理解关键是找出m(x)在K上的零点，以及K怎样包涵F2？
1. 零点为~x。这里用~g(x)表示多项式在K中的陪集，即~g(x)=g(x)+I，所以~x=x+I。把~x代入m(x)，根据商环定义的加乘运算，代换结果为m(x)+I=~m(x)=~0（~0是K的零元）。那么还有吗？比如~(x+a)（a非0），~x^2，代入这些得到的陪集代表不等于m(x)，所以不是零点。因此零点是唯一的一次多项式x之陪集
2. 构造映射σ，把0对到K中的零多项式即~0，1对到K中的常数多项式即~1，且σ(0+1)=~1=~0+~1=σ(0)+σ(1)，σ(0*1)=~0=~0*~1=σ(0)*σ(1)，又依多项式比较法则得~0不等于~1，故σ是单同态，K包涵F2
小结：商群、商环、商域类似模同余之剩余系，理解这些结构的关键是深入理解等价类、陪集，进而可理解正规子群、理想，最后就是商X之类的东西
posted @
2023-09-07 06:39 春秋十二月 阅读(117) |
评论 (0) |
编辑 收藏1. 输入：前者是二进制可执行程序，后者是高级语言源程序
2. 优化对象：前者主要是直线型代码区域比如踪迹或超块（热点路径代码），超块类似后者中的扩展块；后者是控制流图，即所有代码块，不限于热点路径代码。超块构造类似后者中的基本块放置和过程放置
3. 优化方法：前者要运行时采集剖析数据比如结点剖析和边剖析，再基于剖析数据形成有利于指令cache局部性的超块，然后在超块上作常量传播、常量折叠、强度削弱、复写传播、死代码消除、公共表达式消除等基本优化，也会作指令重排，但考虑到陷阱处理要恢复精确的客户进程状态，因此比较受限，没有后者中的指令重排自由。后者如果基于剖析作优化，那么效果和前者差不多
4. 寄存器分配：都是基于活跃范围的冲突图着色算法，但前者考虑到陷阱处理会延长相关寄存器的活跃范围，而后者不用
————————————————————————
总结：二进制优化所用的技术和编译优化其实相同，不同的是为陷阱处理所作的改变调整，以及运用在热点代码块而非所有块
posted @
2023-09-06 23:44 春秋十二月 阅读(84) |
评论 (0) |
编辑 收藏1. NFA到DFA：设NFA的状态数为n，根据子集构造法，则至多有2^n个状态转移，对每个状态转移，其状态分量至多有n个状态，每个状态计算它的可达状态集合耗时为O(n^2)，另可达状态集合的并耗时为O(n^2)，故一个转移耗时为n*O(n^2)=O(n^3)，则所有转移总耗时为O(n^3*2^n)。由于实际产生的状态数远小于2^n（通常为n），因此耗时为O(n^3*s)，s为DFA实际具有的状态数
2. DFA到NFA：转化方法是修改转移表，对每个状态转移的目标状态加上集合括号（因NFA对特定输入可能有多个目标状态，故为集合），若转为£-DFA，则还需对每个状态增加对£的转移为空集。该方法耗时为O(n)，n为DFA的状态数
3. DFA到正则表达式：设DFA状态数为n，根据递推公式R(i,j,k)=R(i,j,k-1)+R(i,k,k-1)R(k,k,k-1)^*R(k,j,k-1)（1<=i<=j<=n，0<=k<=n）来逐步构造表达式，最终的表达式就是所有R(1,j,n)的并，其中j为可接受状态。该过程会产生总共n^3+n^2个表达式，每次k递增导致表达式长度增为4倍，故总耗时为O(n^3*4^n)。另一种更快的方法是消除所有除初始和接受状态外的中间状态，每次消除一个，就合并其前驱经过它到其后继的正则表达式和前驱直接到后继的正则表达式，因前驱或后继至多n-2个，则共有(n-2)^2个前驱到后继的直通边，且中间状态至多n-2个，故耗时为O(n^3)；最后合并各接受状态的正则表达式，因接受状态至多n-1个，故耗时为O(n)。故总耗时为O(n^3)
4. 正则表达式到£-NFA：作词法分析，对每个终结符号构建状态结点及转移边，即子£-NFA，特定符号对应用并、连接、闭包、结合之一联合已构建的子£-NFA，耗时为O(n)，n为正则表达式的长度
posted @
2023-09-06 23:42 春秋十二月 阅读(88) |
评论 (0) |
编辑 收藏1. 三条定律：交换律、结合律、吸收律（对于半格是幂等律），吸收律包含了幂等律
2. 上下界：交半格每对元素都有唯一最大下界，并半格每对元素都有唯一最小上界，格每对元素都有唯一最大下界和唯一最小上界
3. 格定义一个偏序，偏序有三个性质：自反性、反对称性、传递性
4. 格与偏序的关系：每个格对应一个偏序，但不是所有偏序都对应一个格，要满足每对元素都有唯一最小上界和（或，对于半格）唯一最大下界。如果集合中的任何一个子集（包括空集）均存在最小上界和最大下界，那么对应一个完备格
5. 任何元素有限的格都是完备格，格中的交运算和并运算对于其定义的偏序来说是单调的
6. 格的乘积、和、提升、映射仍然是格，利用这个性质，可以在已有格的基础上增量地构造描述能力更丰富的格，这种技术称为论域精化，是提高程序静态分析精度的重要指导思想之一
posted @
2023-09-06 23:39 春秋十二月 阅读(480) |
评论 (0) |
编辑 收藏周知cpu为方便乱序执行，内部会使用重命名寄存器技术消除数据依赖（war和waw）。编译器在如下场景也会用到重命名
1. 静态单赋值。过程内的每个变量唯一定义一次，原有相同的则会重命名，包括phi结点的定值
2. bb表调度。为消除反相关依赖即war，可以重命名读操作使用或写操作定义的值，这样能调度产生总时钟周期更少的指令序列，但可能增加寄存器压力导致溢出而新增了长延迟操作（内存加载/存储）并迫使另一轮调度
3. ebb表调度。对于某一ebb的一条路径p，p存在过早退出路径pe，p和pe的公共前缀是基本块b，当调度p时，如果某个操作i向后移动到b，且i定义的值杀死了pe上的同名值，那么需要重命名i的定值。若i的定值被重命名，且其在p的出口处是活跃的，则调度器需要在出口处复制回原来的名字
4. trace表调度。踪迹不同于ebb路径，它允许中间存在多个前驱即入口的基本块，而后者不能。当调度存在多入口的块b的某踪迹t时，t上的某操作i可能前向移动跨越b（t外的代码路径需作补偿），若i杀死了一个活跃范围跨越b的值，则需要重命名i的定值；同理，若i向后移动跨越b且杀死了t上的某值，则需重命名i的定值，这时t外的代码路径补偿可以使用同一名字
posted @
2023-09-06 23:35 春秋十二月 阅读(75) |
评论 (0) |
编辑 收藏