因為一個整數(shù)p，若檢測為合數(shù)，這永遠是真命題；而檢測為素數(shù)，這命題只以較大概率成立。 可構(gòu)造一種NP檢測算法，步驟如下：
1. 猜測p（位長度n）的因子列表｛p1,p2,…pi｝，這是非確定的，每個分支耗時O(n)
2. 驗證p1*p2*…pi？=p-1，耗時不超過O(n^2)
3. 若各因子乘積等于p-1，則用當前算法遞歸驗證每個因子都是素數(shù)
4. 隨機選擇p最小剩余系內(nèi)的一個數(shù)x，計算x^((p-1)/q) （q遍歷上述列表經(jīng)過步驟3驗證過的素因子）是否都不同余于1模p，若是則必有x^(p-1)同余于1模p，則由指數(shù)整除p的歐拉數(shù)及費馬小定理，知p為素數(shù)，考慮到有少量的合數(shù)也滿足費馬小定理，故需多次選擇x重復(fù)驗證，選擇個數(shù)最多為log(p)
分析：本算法涉及的數(shù)論定理——設(shè)p是奇素數(shù)，p-1的所有素因子是q1,q2,…qs，那么g為原根的充要條件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
結(jié)論：第3步可以看成遞歸調(diào)用樹，每個頂點為待檢測整數(shù)，其每個子結(jié)點為一個因子，則最多n層，每層至多耗時O(n^4)，所以每個路徑即檢測p是否素數(shù)的非確定任一分支中，總耗時O(n^5)。 2002年，印度科學(xué)家發(fā)現(xiàn)素檢測確定性多項式時間算法，于是從NP前進到了P
posted @
2023-09-09 08:07 春秋十二月 閱讀(695) |
評論 (0) |
編輯 收藏為什么命題邏輯有效性是可判定的，而謂詞邏輯有效性是不可判定的？
因為命題邏輯由有限個合式公式及原子命題構(gòu)成，且原子命題的取值只有真、假兩種，簡單的判定方法是真值表窮舉，其復(fù)雜度為指數(shù)級：2^N，N為原子命題數(shù)量。快速的方法是先轉(zhuǎn)成合取范式（輸入是由否定、而且、或者、蘊含四種連接詞構(gòu)成的語法正確的命題邏輯公式，經(jīng)過對公式結(jié)構(gòu)歸納作蘊含釋放、否定原子、分配律變換三步處理，同時運用DAG優(yōu)化：共享終止即葉子結(jié)點、刪除冗余的測試結(jié)點、刪除重復(fù)的有相同子圖結(jié)構(gòu)的內(nèi)部結(jié)點，輸出等價最小的合取范式），再檢測合取范式的有效性（檢查所有子句，若每個子句包含至少一個原子及其否定形式，則有效，否則因為存在一種真值指派使其為假而導(dǎo)致整個合取范式無效），其復(fù)雜度為多項式級：N*logN+N，N為公式長度。謂詞邏輯基于命題邏輯擴展，添加了變元、函數(shù)、量詞“所有”與“存在”，如果量詞沒有約束變元范圍即定義域無限，那么函數(shù)值域也是無限的，另外可能引入的自由變元不受限制，這導(dǎo)致了解空間是無限的，所以不存在通用算法去判定任意謂詞邏輯公式是否有效，具體證明可以用pcp歸約，即構(gòu)造一組特定的謂詞邏輯公式，它是有效的當且僅當pcp實例有解，又已知pcp是不可判定的，故該特定謂詞邏輯有效性是不可判定的，由于任意包括特定，所以謂詞邏輯有效性是不可判定的
posted @
2023-09-09 08:05 春秋十二月 閱讀(100) |
評論 (0) |
編輯 收藏設(shè)程序片段S=if C then S1 else S2，S1和S2可以是由賦值、條件、循環(huán)構(gòu)成的復(fù)雜語句，S不為當前程序最后語句或某個循環(huán)主體最后語句，則S對應(yīng)的流圖生成的深度優(yōu)先生成樹T有3條樹邊，有S1的出口數(shù)+S2出口數(shù)-1條交叉邊。為什么是3條樹邊？C到S1、C到S2、S1或S2到S3（S3是S后繼結(jié)點，下同）。為什么交叉邊數(shù)是S1出口數(shù)+S2出口數(shù)-1？因為流圖中S1出口及S2出口到S3的邊，在生成T的過程中，只有1個出口比S3先訪問，這對應(yīng)形成1條樹邊，訪問S3后再訪問其它出口，這對應(yīng)形成其它出口到S3的交叉邊，注意這里沒有前向邊，因為較晚訪問的出口在T中不可能是S3的祖先。如果把S改為if C then S1，情況會怎樣？結(jié)果取決于生成T的過程中先訪問S3還是S1。若先訪問S3，則有樹邊2條：C到S3、C到S1，交叉邊數(shù)等于S1的出口數(shù)：S1的每個出口到S3各一條邊，沒有前向邊。若先訪問S2，則有樹邊1條：C到S2，前向邊1條：C到S3，交叉邊數(shù)等于S1出口數(shù)-1。
總結(jié)此類問題分析的基本思路是對程序控制結(jié)構(gòu)先構(gòu)建流圖，再構(gòu)建深度優(yōu)先生成樹，辨別其中的前向邊、交叉邊、后退邊
posted @
2023-09-07 06:50 春秋十二月 閱讀(74) |
評論 (0) |
編輯 收藏1.閉包記錄分配：若逃逸分析能識別哪些閉包記錄在創(chuàng)建它們的函數(shù)中是出口不活躍的，則這些閉包記錄可分配在棧幀中（不再是堆中）
2.內(nèi)聯(lián)擴展：由于小函數(shù)較多，因此內(nèi)聯(lián)可以免去調(diào)用開銷而提高性能，對于遞歸函數(shù)，需先用循環(huán)前置頭轉(zhuǎn)換再內(nèi)聯(lián)，如果是尾遞歸函數(shù)，可先使用尾調(diào)用優(yōu)化刪除遞歸。如果一個函數(shù)的所有調(diào)用都被內(nèi)聯(lián)擴展，并且該函數(shù)沒有作為參數(shù)傳遞或其它方式被引用，那么可以刪除這個函數(shù)本身即函數(shù)定義。內(nèi)聯(lián)擴展可以繼續(xù)作用于擴展后的函數(shù)體，只要存在函數(shù)調(diào)用，這也叫層疊式內(nèi)聯(lián)
3.循環(huán)不變量參數(shù)外提：遞歸函數(shù)經(jīng)過循環(huán)前置頭轉(zhuǎn)換后，若每次遞歸調(diào)用頭函數(shù)，傳入的某些參數(shù)值總不變，則可以將它們從函數(shù)參數(shù)中刪除，函數(shù)體中的每次使用出現(xiàn)用序曲函數(shù)對應(yīng)的參數(shù)名替換
4.解開嵌套的let：將嵌套的多層let中的代碼合并為一個let中的代碼，in中的代碼不變
5.避免代碼膨脹：由于內(nèi)聯(lián)復(fù)制函數(shù)體，通常使程序體積變大，且層疊式內(nèi)聯(lián)可無限擴展下去，因此為避免代碼膨脹，有如下啟發(fā)式策略對內(nèi)聯(lián)進行控制
a) 只內(nèi)聯(lián)執(zhí)行很頻繁的函數(shù)調(diào)用，可根據(jù)靜態(tài)估計比如循環(huán)嵌套深度、迭代次數(shù)，或根據(jù)執(zhí)行剖面分析反饋，計算函數(shù)的執(zhí)行頻率
b) 內(nèi)聯(lián)很小的函數(shù)，其函數(shù)體不會比直接調(diào)用多出較多指令
c) 內(nèi)聯(lián)只調(diào)用一次的函數(shù)，然后刪除原來的函數(shù)定義
posted @
2023-09-07 06:47 春秋十二月 閱讀(74) |
評論 (0) |
編輯 收藏1. 整數(shù)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
?注：用最大公約數(shù)定義、整除性質(zhì)、反證法，也可以得出(x, y)=1，(y, z)=1。本法則直接從最大公約數(shù)定理推導(dǎo)
2. u^2+3v^2=2p不可能成立，u、v為整數(shù)，p為奇素數(shù)
證明：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。得出這個中間結(jié)論，再由它可得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. 若四個正整數(shù)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. 假設(shè)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
證明：先論證中間結(jié)論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。由以上中間結(jié)論得等價形式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。假設(shè)2|z，則2|a^2+b^2=(a+b)^2-2ab或(a-b)^2+2ab =>2|a+b, 2|a-b。因題設(shè)是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。
綜上兩式結(jié)果得(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。
綜上三式結(jié)果得(18v, 3v^2+w^2)=1
###############################
從1、5和6問題的證明過程可得，如果一個數(shù)由兩個或多個因子相乘，那么求證是否互素可以逐一求每個因子與另一個數(shù)是否都互素
posted @
2023-09-07 06:43 春秋十二月 閱讀(629) |
評論 (0) |
編輯 收藏周知aes有限域同構(gòu)于系數(shù)為F2域一元多項式環(huán)的商環(huán)，其理想由不可約多項式m(x)=x^8+x^4+x^3+x+1生成，即F2^8≌F2[x]/(m(x))。這次進一步用域擴張的觀點分析，可以得知F2[x]/(m(x))正是包涵m(x)零點的擴域，設(shè)為K。那么如何理解？
令I(lǐng)=(m(x))，則K=F2[x]/I，理解關(guān)鍵是找出m(x)在K上的零點，以及K怎樣包涵F2？
1. 零點為~x。這里用~g(x)表示多項式在K中的陪集，即~g(x)=g(x)+I，所以~x=x+I。把~x代入m(x)，根據(jù)商環(huán)定義的加乘運算，代換結(jié)果為m(x)+I=~m(x)=~0（~0是K的零元）。那么還有嗎？比如~(x+a)（a非0），~x^2，代入這些得到的陪集代表不等于m(x)，所以不是零點。因此零點是唯一的一次多項式x之陪集
2. 構(gòu)造映射σ，把0對到K中的零多項式即~0，1對到K中的常數(shù)多項式即~1，且σ(0+1)=~1=~0+~1=σ(0)+σ(1)，σ(0*1)=~0=~0*~1=σ(0)*σ(1)，又依多項式比較法則得~0不等于~1，故σ是單同態(tài)，K包涵F2
小結(jié)：商群、商環(huán)、商域類似模同余之剩余系，理解這些結(jié)構(gòu)的關(guān)鍵是深入理解等價類、陪集，進而可理解正規(guī)子群、理想，最后就是商X之類的東西
posted @
2023-09-07 06:39 春秋十二月 閱讀(116) |
評論 (0) |
編輯 收藏1. 輸入：前者是二進制可執(zhí)行程序，后者是高級語言源程序
2. 優(yōu)化對象：前者主要是直線型代碼區(qū)域比如蹤跡或超塊（熱點路徑代碼），超塊類似后者中的擴展塊；后者是控制流圖，即所有代碼塊，不限于熱點路徑代碼。超塊構(gòu)造類似后者中的基本塊放置和過程放置
3. 優(yōu)化方法：前者要運行時采集剖析數(shù)據(jù)比如結(jié)點剖析和邊剖析，再基于剖析數(shù)據(jù)形成有利于指令cache局部性的超塊，然后在超塊上作常量傳播、常量折疊、強度削弱、復(fù)寫傳播、死代碼消除、公共表達式消除等基本優(yōu)化，也會作指令重排，但考慮到陷阱處理要恢復(fù)精確的客戶進程狀態(tài)，因此比較受限，沒有后者中的指令重排自由。后者如果基于剖析作優(yōu)化，那么效果和前者差不多
4. 寄存器分配：都是基于活躍范圍的沖突圖著色算法，但前者考慮到陷阱處理會延長相關(guān)寄存器的活躍范圍，而后者不用
————————————————————————
總結(jié)：二進制優(yōu)化所用的技術(shù)和編譯優(yōu)化其實相同，不同的是為陷阱處理所作的改變調(diào)整，以及運用在熱點代碼塊而非所有塊
posted @
2023-09-06 23:44 春秋十二月 閱讀(84) |
評論 (0) |
編輯 收藏1. NFA到DFA：設(shè)NFA的狀態(tài)數(shù)為n，根據(jù)子集構(gòu)造法，則至多有2^n個狀態(tài)轉(zhuǎn)移，對每個狀態(tài)轉(zhuǎn)移，其狀態(tài)分量至多有n個狀態(tài)，每個狀態(tài)計算它的可達狀態(tài)集合耗時為O(n^2)，另可達狀態(tài)集合的并耗時為O(n^2)，故一個轉(zhuǎn)移耗時為n*O(n^2)=O(n^3)，則所有轉(zhuǎn)移總耗時為O(n^3*2^n)。由于實際產(chǎn)生的狀態(tài)數(shù)遠小于2^n（通常為n），因此耗時為O(n^3*s)，s為DFA實際具有的狀態(tài)數(shù)
2. DFA到NFA：轉(zhuǎn)化方法是修改轉(zhuǎn)移表，對每個狀態(tài)轉(zhuǎn)移的目標狀態(tài)加上集合括號（因NFA對特定輸入可能有多個目標狀態(tài)，故為集合），若轉(zhuǎn)為£-DFA，則還需對每個狀態(tài)增加對£的轉(zhuǎn)移為空集。該方法耗時為O(n)，n為DFA的狀態(tài)數(shù)
3. DFA到正則表達式：設(shè)DFA狀態(tài)數(shù)為n，根據(jù)遞推公式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）來逐步構(gòu)造表達式，最終的表達式就是所有R(1,j,n)的并，其中j為可接受狀態(tài)。該過程會產(chǎn)生總共n^3+n^2個表達式，每次k遞增導(dǎo)致表達式長度增為4倍，故總耗時為O(n^3*4^n)。另一種更快的方法是消除所有除初始和接受狀態(tài)外的中間狀態(tài)，每次消除一個，就合并其前驅(qū)經(jīng)過它到其后繼的正則表達式和前驅(qū)直接到后繼的正則表達式，因前驅(qū)或后繼至多n-2個，則共有(n-2)^2個前驅(qū)到后繼的直通邊，且中間狀態(tài)至多n-2個，故耗時為O(n^3)；最后合并各接受狀態(tài)的正則表達式，因接受狀態(tài)至多n-1個，故耗時為O(n)。故總耗時為O(n^3)
4. 正則表達式到£-NFA：作詞法分析，對每個終結(jié)符號構(gòu)建狀態(tài)結(jié)點及轉(zhuǎn)移邊，即子£-NFA，特定符號對應(yīng)用并、連接、閉包、結(jié)合之一聯(lián)合已構(gòu)建的子£-NFA，耗時為O(n)，n為正則表達式的長度
posted @
2023-09-06 23:42 春秋十二月 閱讀(88) |
評論 (0) |
編輯 收藏1. 三條定律：交換律、結(jié)合律、吸收律（對于半格是冪等律），吸收律包含了冪等律
2. 上下界：交半格每對元素都有唯一最大下界，并半格每對元素都有唯一最小上界，格每對元素都有唯一最大下界和唯一最小上界
3. 格定義一個偏序，偏序有三個性質(zhì)：自反性、反對稱性、傳遞性
4. 格與偏序的關(guān)系：每個格對應(yīng)一個偏序，但不是所有偏序都對應(yīng)一個格，要滿足每對元素都有唯一最小上界和（或，對于半格）唯一最大下界。如果集合中的任何一個子集（包括空集）均存在最小上界和最大下界，那么對應(yīng)一個完備格
5. 任何元素有限的格都是完備格，格中的交運算和并運算對于其定義的偏序來說是單調(diào)的
6. 格的乘積、和、提升、映射仍然是格，利用這個性質(zhì)，可以在已有格的基礎(chǔ)上增量地構(gòu)造描述能力更豐富的格，這種技術(shù)稱為論域精化，是提高程序靜態(tài)分析精度的重要指導(dǎo)思想之一
posted @
2023-09-06 23:39 春秋十二月 閱讀(480) |
評論 (0) |
編輯 收藏周知cpu為方便亂序執(zhí)行，內(nèi)部會使用重命名寄存器技術(shù)消除數(shù)據(jù)依賴（war和waw）。編譯器在如下場景也會用到重命名
1. 靜態(tài)單賦值。過程內(nèi)的每個變量唯一定義一次，原有相同的則會重命名，包括phi結(jié)點的定值
2. bb表調(diào)度。為消除反相關(guān)依賴即war，可以重命名讀操作使用或?qū)懖僮鞫x的值，這樣能調(diào)度產(chǎn)生總時鐘周期更少的指令序列，但可能增加寄存器壓力導(dǎo)致溢出而新增了長延遲操作（內(nèi)存加載/存儲）并迫使另一輪調(diào)度
3. ebb表調(diào)度。對于某一ebb的一條路徑p，p存在過早退出路徑pe，p和pe的公共前綴是基本塊b，當調(diào)度p時，如果某個操作i向后移動到b，且i定義的值殺死了pe上的同名值，那么需要重命名i的定值。若i的定值被重命名，且其在p的出口處是活躍的，則調(diào)度器需要在出口處復(fù)制回原來的名字
4. trace表調(diào)度。蹤跡不同于ebb路徑，它允許中間存在多個前驅(qū)即入口的基本塊，而后者不能。當調(diào)度存在多入口的塊b的某蹤跡t時，t上的某操作i可能前向移動跨越b（t外的代碼路徑需作補償），若i殺死了一個活躍范圍跨越b的值，則需要重命名i的定值；同理，若i向后移動跨越b且殺死了t上的某值，則需重命名i的定值，這時t外的代碼路徑補償可以使用同一名字
posted @
2023-09-06 23:35 春秋十二月 閱讀(75) |
評論 (0) |
編輯 收藏