`
SavageGarden
  • 浏览: 223214 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

SICP学习笔记 1.2.6 实例:素数检测

    博客分类:
  • SICP
 
阅读更多

    练习1.22

;; runtime函数在stk、racket中都不支持,而GNU的Mit-Scheme十分难用,而且在Fedora16上编译安装后启动就报错,
;; 后来总算是在selinux的提示下让它能够正常启动了
;; grep scheme /var/log/audit/audit.log | audit2allow -M mypol
;; semodule -i mypol.pp

 (define (start-prime-test n start-time)
  (and (prime? n)
	  (report-prime n (- (runtime) start-time))))
	  
(define (prime? n)
  (= n (smallest-divisor n)))
  
(define (report-prime n elapsed-time)
  (display n)
  (display " *** ")
  (display elapsed-time)
  (newline))
  
(define (search-for-primes n)
  (if (even? n)
      (search-for-primes-iter (+ n 1) 3 (runtime))
      (search-for-primes-iter n 3 (runtime))))
      
(define (search-for-primes-iter n count start-time)
  (if (= count 0)
      ((newline) (display "search over"))
      (if (start-prime-test n start-time)
          (search-for-primes-iter (+ n 2) (- count 1) (runtime))
          (search-for-primes-iter (+ n 2) count (runtime)))))
          
;; 数据太小的话根本不能进行比较
(search-for-primes 10000000000)
10000000019 *** .23
10000000033 *** .23
10000000061 *** .24
search over

(search-for-primes 100000000000)
100000000003 *** .75
100000000019 *** .73
100000000057 *** .73
search over

(search-for-primes 1000000000000)
1000000000039 *** 2.34
1000000000061 *** 2.33
1000000000063 *** 2.33
search over

;; 耗时大概呈√10倍增长

 

    练习1.23

;; 修改如下
(define (next test)
  (if (= n 2)
      3
      (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
		((divides? test-divisor n) test-divisor)
		(else (find-divisor n (next test-divisor)))))
		
(search-for-primes 10000000000)
10000000019 *** .13
10000000033 *** .14
10000000061 *** .14
search over

(search-for-primes 100000000000)
100000000003 *** .45
100000000019 *** .45
100000000057 *** .44
search over

(search-for-primes 1000000000000)
1000000000039 *** 1.41
1000000000061 *** 1.39
1000000000063 *** 1.41
search over

;; 随着数据的增大,耗时大致呈2倍增长

 

    练习1.24

;; 1009 1013 1019
;; 1000003 1000033 1000037

timed-prime-test 1009)
1009 *** .39

(timed-prime-test 1013)
1013 *** .42

(timed-prime-test 1019)
1019 *** .44

(timed-prime-test 1000003)
1000003 *** .77

(timed-prime-test 1000033)
1000033 *** .76

(timed-prime-test 1000037)
1000037 *** .79

;; lg n^2 = 2 * lg n,对比以上结果,比较接近,预计测试数据增大后将更加接近

 

    练习1.25

    理论上可行,但是直接求base^exp的话可能会因为结果太大而出现溢出

 

    练习1.26

    修改后将对于base^2n进行如下方式的计算过程  -->  (base*base*base*...)*(base*base*base*...)

    而原来的方式将进行如下方式的计算过程   -->  (base^n)^2 => (base^(n/2)^2)^2 => ...
    因此原有方式为O(log n)而修改后为O(n)

 

    练习1.27

;; 561 1105 1729 2465 2821 6601

(define (expmod base exp m)
  (cond ((= exp 0) 1)
		((even? exp)
		 (remainder (square (expmod base (/ exp 2) m)) m))
		(else
		 (remainder (* base (expmod base (- exp 1) m)) m))))

(define (carmichael n)
  (carmichael-iter n 1))

(define (carmichael-iter n a)
  (cond ((= a n) true)
		((= (expmod a n n) a) (carmichael-iter n (+ a 1)))
		(else false)))
		
(carmichael 561)
;Value: #t

(carmichael 1105)
;Value: #t

(carmichael 1729)
;Value: #t

(carmichael 2465)
;Value: #t

(carmichael 2821)
;Value: #t

(carmichael 6601)
;Value: #t

 

    练习1.28

费马小定理:
如果n是素数, 其中1<a<n, 则有 a^n ≡ a (mod n)

变形过程为:
已知 a^n ≡ a (mod n)
-->     a^n = k*n + a  
-->     a^(n-1) = (k/a)*n + 1
-->     a^(n-1) = k'*n + 1
-->     a^(n-1) ≡ 1 (mod n)

设n是素数, 其中1<a<n-1, 假设 a^2 ≡ 1 (mod n)
-->     a^2 - 1 = k*n
-->     (a+1)*(a-1) = k*n
-->     (a+1)*(a-1) ≡ 0 (mod n)
-->     a+1 ≡ 0 (mod n)
        a-1 ≡ 0 (mod n)
-->     a = n-1
        a = 1
        而1<a<n-1,则n不为素数,或不存在1<a<n-1, a^2 ≡ 1 (mod n)
       
;; 561 1105 1729 2465 2821 6601

(define (miller-rabin n)
  (miller-rabin-iter n 1))

(define (miller-rabin-iter n a)
  (cond ((= a n) true)
		((= (expmod a (- n 1) n) 1) (miller-rabin-iter n (+ a 1)))
		(else false)))
		
(define (expmod base exp m)
  (cond ((= exp 0) 1)
		((even? exp)  
		 (nontrivial-square-root (expmod base (/ exp 2) m) m))
		(else
		 (remainder (* base (expmod base (- exp 1) m)) m))))
		 
(define (nontrivial-square-root a n)
  (define (try-it value)
    (if (and (> a 1) (< a (- n 1)) (= value 1))
        0
        value))
  (try-it (remainder (square a) n)))
  
(miller-rabin 561)
;Value: #f

(miller-rabin 1105)
;Value: #f

(miller-rabin 1729)
;Value: #f

(miller-rabin 2465)
;Value: #f

(miller-rabin 2821)
;Value: #f

(miller-rabin 6601)
;Value: #f	
0
1
分享到:
评论

相关推荐

    sicp-py-zh:[译] UCB CS61a SICP Python 描述 中文版

    UCB CS61a SICP Python 描述 原文: 译者: 协议: 前面是山,我们就爬山;前面是海,我们就渡海;前面是皇宫,我们就开炮!——《龙族前传》 ‍ 下载 Docker docker pull apachecn0/sicp-py-zh docker run -tid -p ...

    sicp-memo-ans:SICP笔记和答案

    请参考那些正在学习SICP的人。 笔记 如果你想在 gauch 中使用随机函数 (use math.mt-random) (define m (make &lt;mersenne&gt; :seed (sys-time))) (mt-random-integer m 1000) (define (random n) (mt-random-integer ...

    sicp-js-zh:【译】NUS CS1101s SICP JavaScript 描述

    NUS CS1101s SICP JavaScript 描述原文:协议:如果你交给某人一个程序,你将折磨他一整天;如果你教某人如何编写程序,你将折磨他一辈子。——David Leinweber贡献指南本项目需要校对,欢迎大家提交 Pull Request。...

    sicp-compiler-notes:有关SICP编译器的一些说明和演示

    在SICP上进行试用-&gt; WASM编译演示:SICP如何将机器代码注册为WASM 为阶乘翻译LISP代码(define (factorial n) (define (iter product counter) (if (&gt; counter n) product (iter (* counter product) (+ counter 1)))...

    sicp-py-zh:【译】UCB CS61a SICP Python

    - **操作符和表达式**:学习如何处理和操作符号,理解表达式的计算过程。 9. **动态类型**: - **类型检查**:Python是动态类型的,意味着在运行时确定变量类型。 - **类型转换**:如何在不同类型之间转换数据。...

    sicp_but_clojure:Clojure中的SICP示例和练习

    这些源代码文件扩展了./resources中的笔记内容,提供了解决SICP练习的实际实现。学习者可以通过阅读和修改这些代码,加深对Clojure语法和SICP概念的理解。 在Clojure中实现SICP的益处在于: - **函数式编程的思维...

    sicp和操作系统:精髓与设计原理第七版

    资源名称:sicp 和 操作系统:精髓与设计原理第七版资源截图: 资源太大,传百度网盘了,链接在附件中,有需要的同学自取。

    sicp-eg-ex:sicp课程视频示例,自己的笔记,习题题解

    本文将围绕"Sicp-eg-ex"这个项目,结合标题和描述,探讨在学习SICP过程中遇到的例子、笔记和习题解,特别是环境检查方案9.5的相关知识点。 首先,我们关注到的是"SICP课程视频示例"。SICP课程的核心在于通过实际的...

    sicp-study-group:一个研究计算机程序结构和解释(SICP)的研究小组

    1. **阅读材料**:可能是SICP书的章节摘要、笔记或者补充阅读材料,帮助学习者更好地理解和消化书中的概念。 2. **代码实现**:小组成员可能用JavaScript实现了SICP中的各种算法和解释器,这有助于实践和理解书中...

    sicp-to-z80:一台SICP寄存器机到TI-84 Z80编译器

    最终目标是完全支持SICP指令集,然后使用此编译器将Scheme编译为Z80,或直接将Scheme编写为Z80。 无论哪种方式,该项目对我来说也意味着可以在TI-84(不是最好的语言)上探索Z80装配中的编程。特征显示字符串和数字...

    sicp 和 操作系统:精髓与设计原理第七版打包

    《SICP》(Structure and Interpretation of Computer Programs)是一本经典的计算机科学教材,由Harold Abelson和Gerald Jay Sussman合著,MIT出版社出版。这本书主要探讨了程序设计语言的基础,以及如何构建和理解...

    SICP(计算机体系结构)

    - **1.2.6 示例:素性测试**: 介绍一种高效判断素数的方法。 - **1.3 使用高阶过程形成抽象** - **1.3.1 作为参数的过程**: 如何将过程作为其他过程的参数。 - **1.3.2 使用lambda构造过程**: 学习lambda表达式...

    sicp_notes:SICP笔记和练习

    《SICP笔记和练习》是一份详尽的资源,主要涵盖了由MIT教授们编写的经典计算机科学教材《Structure and Interpretation of Computer Programs》(简称SICP)的学习笔记和练习解答。这份资料以HTML格式呈现,便于在线...

    SICP:SICP解决方案

    《SICP:SICP解决方案》是针对结构与解释程序设计(Structure and Interpretation of Computer Programs,简称SICP)这本书的详细解答和实践指南。SICP是一本经典的计算机科学教材,由Harold Abelson和Gerald Jay ...

    sicp in python 中文版 sicp

    sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 download : https://github.com/wizardforcel/sicp-py-zh

    sicp in python 中文 sicp 中文

    sicp in python 中文版 sicp in python 中文版 sicp in python 中文版 !!!download&gt;&gt;&gt;https://github.com/wizardforcel/sicp-py-zh

    sicp 2016 from

    - **素性测试 (Example: Testing for Primality)**:讨论了如何检测一个数是否为素数。 - **使用高阶过程建立抽象 (Formulating Abstractions with Higher-Order Procedures)** - **作为参数的过程 (Procedures ...

    Learn_sicp:学习sicp的一些代码

    《学习SICP:探索Racket编程的艺术》 SICP,全称为《Structure and Interpretation of Computer Programs》(计算机程序的结构与解释),是一本经典的计算机科学教材,由Harold Abelson和Gerald Jay Sussman合著,...

Global site tag (gtag.js) - Google Analytics