• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        

            
	
            
		
			

            

            
	
            
		
			
            CG@CPPBLOG
            
			/*=========================================*/
		            		
	
            

            

            

            

            隨筆 - 76, 文章 - 39, 評(píng)論 - 137, 引用 - 0
            

            


            		
	
            

            

            
	
            
		
			
            
				數(shù)據(jù)加載中……
			
            
		            		
		
			
            
				
					
	
            
		
            
			我的SICP習(xí)題答案（1.24~1.28）
		
            
		
            
		1.24
            對(duì)于Fermat檢查，因?yàn)榫哂衛(wèi)og n 的增長(zhǎng)階，所以對(duì)于 n^2 和 n 的檢查的時(shí)間比 理論上應(yīng)該是 2：1， 實(shí)際上，經(jīng)過(guò)測(cè)試也比較接近，當(dāng)n比較大時(shí)。
            若與預(yù)計(jì)不符，可能因?yàn)?n 比較小，或者字長(zhǎng)發(fā)生變化，比如 n > 2^32 （參見(jiàn)下題）

            1.25
            僅從理論分析，Alyssa 的改動(dòng)不會(huì)引起增長(zhǎng)階的變化，但實(shí)際上當(dāng) Fermat 檢查的 n 稍微大一點(diǎn)，速度就會(huì)很慢。主要原因 就是 base^exp 是一個(gè)非常大的數(shù)，可能遠(yuǎn)遠(yuǎn)超過(guò) 一個(gè)32位機(jī)字的表示范圍 2^32 ，在 scheme 里可能用若干個(gè) 32-bit 靠軟件實(shí)現(xiàn)運(yùn)算，這將導(dǎo)致計(jì)算急速增長(zhǎng)。無(wú)論是傳遞、運(yùn)算還是求模。
            實(shí)際上 1.22、1.23、1.24 的幾個(gè)題目可能都會(huì)遇到字長(zhǎng)變化引起的計(jì)算速度突變。

            1.26
            Fermat 檢查正是因?yàn)?連續(xù)求平方的求冪方法，使得的增長(zhǎng)階變?yōu)?log n， 而這均來(lái)源于 b^(2n) = (b^n)^2，            Louis 的方法讓求冪又變成了連乘，b^(2n) = b^n*b^n = (b*b*...*b)*(b*b*...*b)，求冪的增長(zhǎng)階變成了 O(n)，F(xiàn)ermat 檢查的增長(zhǎng)階自然也變成了 O(n)。

            1.27
            

            (define (fermat-test n)
              (fermat-iter (- n             1) n))

            (define (fermat-iter a n)
              (cond ((            = a 0) #t)
                    ((            = (expmod a n n) a) (fermat-iter (- a 1) n))
                    (else #f)))
            

            1.28
            首先來(lái)看，F(xiàn)ermat 小定理的一個(gè)變形：

            p 是素?cái)?shù), 1<a<p, 有 a^p % p = a
            ==> a^p = kp + a ==> a^p - a = kp ==> a(a^(p-1)-1) = kp ==> a^(p-1) -1 = k'p
            ==> a^(p-1) % p = 1

            這個(gè)變形就是題目中提到的，這個(gè)形式和費(fèi)馬小定理是等價(jià)的（但是奇怪的是，我沒(méi)有發(fā)現(xiàn)已知的幾個(gè)Carmichael數(shù)能夠躲過(guò)這個(gè)變形的檢查，有待研究①）

            再來(lái)看，miller-rabin 素性測(cè)試的原理：

            p 是素?cái)?shù)， 1<a<p, 且 a^2 % p = 1
            ==> (a^2-1) % p = 0 ==> (a+1)(a-1) % p =0
            那么 a+1 % p = 0 或者 a-1 % p =0,
            又 a<p 且 p 是素?cái)?shù)，所以
            a = 1 或者 a = p-1 （這兩個(gè)叫做 1模n的平凡平方根）

            代碼如下：
            

            (define (check-nontrivial-sqrt-of-one a n)
              (define (check-            1? t)
                (if (and (> a 1            )
                         (< a (- n             1))
                         (            = t 1))
                                0 t))
              (check-            1? (remainder (square a) n)))

            (define (expmod base exp m)
              (cond ((            = exp 0) 1)
                    ((even? exp)
                                 ;(remainder (square (expmod base (/ exp 2) m)) m))
                     (check-nontrivial-sqrt-of-one (expmod base (/ exp 2) m) m))
                    (else
                     (remainder (* base (expmod base (- exp             1) m)) m))))

            (define (miller-rabin-test n)
              (define (iter x n)
                (cond ((            = x 0) #t)
                      ((            = (expmod x (- n 1) n) 1) (iter (- x 1) n))
                      (else #f)))
              (iter (- n             1) n))
            

            ① 對(duì)于             Carmichael 數(shù) n ，實(shí)際上不能完全通過(guò) a^(n-1)%n = 1 的檢查，除非 a 與 n 互素，當(dāng) a 為 n 的素因子時(shí)，不能通過(guò)，比如 Carmichael 第一個(gè) 561 = 3*11*17， 而 3^560%561 = 375 ≠ 1 。可以程序驗(yàn)證這個(gè)。 所以我認(rèn)為，a^(n-1)%n = 1 的檢查比 a^n%n = a 的檢查更嚴(yán)格，是不是不存在合數(shù)通過(guò)完全的 a^(n-1)%n = 1 的檢查呢？我不敢說(shuō)。但把這個(gè)結(jié)論暫時(shí)記在這里，希望能得到幫助或者反駁。2008-04-02 23:56


              
		
            
		
            
			posted on 2008-03-31 00:21 cuigang 閱讀(1555) 評(píng)論(2)  編輯 收藏 引用  所屬分類: Lisp/Scheme 、我的SICP答案 
		
            
	
            
	
	


	


            
	    
    


            

            評(píng)論
            
	
	
			
            
				
            
					# re: 我的SICP習(xí)題答案（1.24~1.28）  回復(fù)  更多評(píng)論
					  
				
            
				a^(n-1)%n = 1 跟 a^n%n = a 應(yīng)該是完全等價(jià)的吧？
				
            
					2009-03-25 21:10 | pgw
				
            
			
            
		
			
            
				
            
					# re: 我的SICP習(xí)題答案（1.24~1.28）  回復(fù)  更多評(píng)論
					  
				
            
				@pgw

            

            好吧。。 我錯(cuò)了
				
            
					2009-03-25 21:42 | pgw
				
            
			
            
		

            





            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



色诱久久久久综合网ywww|
国产成人精品久久二区二区|
精品久久综合1区2区3区激情|
精品久久久久久中文字幕|
国产精品久久久久…|
久久久精品波多野结衣|
一本色道久久88综合日韩精品
|
久久久久亚洲爆乳少妇无|
久久人人爽人人澡人人高潮AV|
亚洲欧美伊人久久综合一区二区|
亚洲综合伊人久久综合|
色综合久久精品中文字幕首页|
久久久精品日本一区二区三区|
国产亚洲精久久久久久无码77777|
国产成人久久精品激情|
欧美日韩精品久久久免费观看
|
久久综合九色综合精品|
久久无码精品一区二区三区|
久久精品一本到99热免费|
大美女久久久久久j久久|
亚洲中文久久精品无码|
久久久久人妻精品一区三寸蜜桃|
亚洲av伊人久久综合密臀性色|
久久99久久无码毛片一区二区|
久久亚洲春色中文字幕久久久|
久久久精品人妻无码专区不卡|
国产精品久久久久久福利漫画
|
久久精品麻豆日日躁夜夜躁|
国内精品久久久久影院网站|
久久久久久国产精品无码超碰|
日韩欧美亚洲综合久久影院Ds|
AV色综合久久天堂AV色综合在|
国产99久久久国产精品小说|
国产成人99久久亚洲综合精品
|
久久久这里有精品中文字幕|
久久婷婷国产麻豆91天堂|
久久精品99久久香蕉国产色戒
|
无码日韩人妻精品久久蜜桃|
午夜精品久久久久久久无码|
久久精品国产亚洲5555|
久久激情五月丁香伊人|