[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.lisp

SICP - exercise 1.28 code review

pyroclastic33

6/13/2016 10:13:00 AM

Can I have my implementation of SICP's exercise 1.28 - the miller-rabin primality test
(https://mitpress.mit.edu/sicp/chapter1/n...)
reviewed here?

Here's the description:

"Exercise 1.28: One variant of the Fermat test that cannot be fooled is called the Miller-Rabin test (Miller 1976; Rabin 1980). This starts from an alternate form of Fermat’s Little Theorem, which states that if n is a prime number and a is any positive integer less than n, then a raised to the n-1-st power is congruent to 1 modulo n. To test the primality of a number n by the Miller-Rabin test, we pick a random number a < n and raise a to the n-1-st power modulo n using the expmod procedure. However, whenever we perform the squaring step in expmod, we check to see if we have discovered a “nontrivial square root of 1 modulo n,” that is, a number not equal to 1 or n-1 whose square is equal to 1 modulo n. It is possible to prove that if such a nontrivial square root of 1 exists, then n is not prime. It is also possible to prove that if n is an odd number that is not prime, then, for at least half the numbers a < n, computing a^n-1 in this way will reveal a nontrivial square root of 1 modulo n. (This is why the Miller-Rabin test cannot be fooled.) Modify the expmod procedure to signal if it discovers a nontrivial square root of 1, and use this to implement the Miller-Rabin test with a procedure analogous to fermat-test. Check your procedure by testing various known primes and non-prime . Hint: One convenient way to make expmod signal is to have it return 0."

Here's my code:

;; modified expmod procedure
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(if (and (not (= base 1)) (not (= base (- m 1))) (not (= exp (- m 1))) (= (remainder base m) 1))
0
(remainder
(expmod (square base) (/ exp 2) m)
m)))
(else
(remainder
(* base (expmod base (- exp 1) m))
m))))

(define (miller-rabin-test n)
(define (try-it a)
(= (expmod a (- n 1) n) 1))
(try-it (+ 1 (random (- n 1)))))

(define (fast-prime? n times)
(cond ((= times 0) true)
((miller-rabin-test n)
(fast-prime? n (- times 1)))
(else false)))

What do you think? Is this correct?

Note: I've already received some feedback here:
http://codereview.stackexchange.com/questions/129964/sicp-exercise-1-28-miller-rabin-primality-test/129991?noredirect=1#comment243...
I'm just looking for more.
2 Answers

Pascal J. Bourguignon

6/13/2016 5:40:00 PM

0

pyroclastic33@gmail.com writes:

> Can I have my implementation of SICP's exercise 1.28 - the miller-rabin primality test
> (https://mitpress.mit.edu/sicp/chapter1/n...)
> reviewed here?

If you wrote it in Common Lisp, yes.

> What do you think? Is this correct?

But it's written in scheme, so it would be better to ask on
news:comp.lang.scheme instead.

--
__Pascal Bourguignon__ http://www.informat...
â??The factory of the future will have only two employees, a man and a
dog. The man will be there to feed the dog. The dog will be there to
keep the man from touching the equipment.� -- Carl Bass CEO Autodesk

William James

6/14/2016 9:42:00 AM

0

Pascal J. Bourguignon wrote:

> > Can I have my implementation of SICP's exercise 1.28 - the miller-rabin primality test
> > (https://mitpress.mit.edu/sicp/chapter1/n...)
> > reviewed here?
>
> If you wrote it in Common Lisp, yes.

You're lying.

This newsgroup is not devoted to CL (COBOL-Like).

In fact, CL is of so little importance that it has no newsgroup.


Thomas Bushnell wrote:

> > The first post to comp.lang.lisp was in November of 1986; _Common
> > Lisp, The Language_ was published in 1984.
>
> Oh, that's just an artifact of the Great Renaming, which was 1986-7.
> comp.lang.lisp is the new name of the old net.lang.lisp. The first
> message was there can be found at
> http://groups.google.com/groups?hl=en&group=net.lang.lisp&scoring=d&as_drr...
> _mind=1&as_minm=1&as_miny=1981&as_maxd=10&as_maxm=6&as_maxy=1982&selm=anews.Aucb
> arpa.997
>
> And is dated 1982-03-27 23:56:29 PST.
>
> It's by John Foderaro. The first sentence is:
>
> "The net.lang.lisp newsgroup is for the discussion of any and all lisp
> dialects."

--
The goal is to meet the EU challenge of interracial marriage. It's not a
choice. It's an obligation. If voluntarism does not work for the republic,
then the state will move in with more coercive measures.
--- the Jew Nicolas Sarkozy (www.youtube.com/watch?v=K0hD7IffTJs)