sicp

sicp sandbox.
git clone git://git.ricketyspace.net/sicp.git
Log | Files | Refs

commit b51382f42a102146ffdf42497fd9fd2cbf914980
parent 52afc19f43872517e443a948cc19abbad1afdbdf
Author: rsiddharth <s@ricketyspace.net>
Date:   Sat, 12 Aug 2017 18:54:32 +0000

Add (net ricketyspace sicp one twentyseven).

* net/ricketyspace/sicp/one/twentyseven.scm: New file.

Diffstat:
net/ricketyspace/sicp/one/twentyseven.scm | 37+++++++++++++++++++++++++++++++++++++
1 file changed, 37 insertions(+), 0 deletions(-)

diff --git a/net/ricketyspace/sicp/one/twentyseven.scm b/net/ricketyspace/sicp/one/twentyseven.scm @@ -0,0 +1,37 @@ +;;;; Under Creative Commons Attribution-ShareAlike 4.0 +;;;; International. See +;;;; <https://creativecommons.org/licenses/by-sa/4.0/>. + +(define-module (net ricketyspace sicp one twentyseven) + #:use-module (srfi srfi-1) + #:export (carmichael-numers-fool-fermat-test?)) + +(define carmichael-numbers '(561 1105 1729 2465 2821 6601)) + +(define (square x) (* x x)) + +(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 (fermat-test n) + (define (try-it a) + (= (expmod a n n) a)) + (try-it (+ 1 (random (- n 1))))) + +(define (fast-prime? n times) + (cond ((= times 0) #t) + ((fermat-test n) (fast-prime? n (- times 1))) + (else #f))) + +(define (carmichael-numers-fool-fermat-test?) + "Returns #t if all `carmichael-numbers` pass (fool) the fermat test." + (let* ((fooled-test? (lambda (n) (fast-prime? n 100000))) + (fooled? (lambda (result) (eq? result #t))) + (results (map fooled-test? carmichael-numbers))) + (every fooled? results)))