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 millerrabin 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 MillerRabin 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 n1st power is congruent to 1 modulo n. To test the primality of a number n by the MillerRabin test, we pick a random number a < n and raise a to the n1st 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 n1 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^n1 in this way will reveal a nontrivial square root of 1 modulo n. (This is why the MillerRabin 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 MillerRabin test with a procedure analogous to fermattest. Check your procedure by testing various known primes and nonprime . 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 (millerrabintest n)
(define (tryit a)
(= (expmod a ( n 1) n) 1))
(tryit (+ 1 (random ( n 1)))))
(define (fastprime? n times)
(cond ((= times 0) true)
((millerrabintest n)
(fastprime? 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/sicpexercise128millerrabinprimalitytest/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 millerrabin 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 millerrabin 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 (COBOLLike).
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 19867.
> 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 19820327 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)
Servizio di avviso nuovi messaggi
Ricevi direttamente nella tua mail i nuovi messaggi per
SICP  exercise 1.28 code review
Inserendo la tua email nella casella sotto, riceverai un avviso tramite posta elettronica ogni volta che il motore di ricerca troverà un nuovo messaggio per te
Il servizio è completamente GRATUITO!
x
Login to ForumsZone
Login with Google
Login with EMail & Password