Exercise 1.22

Printer-friendly versionPrinter-friendly version

Most Lisp implementations include a primitive called runtime that returns an integer that specifies the amount of time the system has been running (measured, for example, in microseconds). The following timed-prime-test procedure, when called with an integer n, prints n and checks to see if n is prime. If n is prime, the procedure prints three asterisks followed by the amount of time used in performing the test.

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

Using this procedure, write a procedure search-for-primes that checks the primality of consecutive odd integers in a specified range. Use your procedure to find the three smallest primes larger than 1000; larger than 10,000; larger than 100,000; larger than 1,000,000. Note the time needed to test each prime. Since the testing algorithm has order of growth of Θ(√n), you should expect that testing for primes around 10,000 should take about √10 times as long as testing for primes around 1000. Do your timing data bear this out? How well do the data for 100,000 and 1,000,000 support the √n prediction? Is your result compatible with the notion that programs on your machine run in time proportional to the number of steps required for the computation?

Corresponding Section: 

Comments

Birkenstock over 200birkenstock outlet

Choose the one with Chaussures Birkenstockthick sole birkenstock pas cherto provide discount birkenstock sandals,birkenstock clogs cheap,birki clogs,shoe clogs,men s birkenstocks, even BMX cyclistsarmani watches are using eh same kind of shoes, since it sticks well in the pedals andarmani watches uk its thick flat shoes is utilized as a brake. Furthermore, the shoes are popular because of its strength. These kinds of shoes are very expensive because of having high quality materialbirkenstock outlet used and the additional features which provide the shoes the advantages as compared to other brands. Also these shoes should be manufactured and designed Unisex Birkenstockaccording to the safety features associated with the sports. The price of these shoes will be according on the features which the shoes have.

At 73 years old,Birkenstock outlet he is still busy birkenstock kairomaking people look good. Giorgio Armani is one of the preeminentBirkenstock UK Italian fashion designers in the world,birkenstock homme still goingbirkenstock france strong after 33 years in the birkenstock kairoindustry. Known for his classically tailored, sleek power suits and clean,armani watches high quality fabrics, everyone from the who’s who of Hollywood to the bankers onarmani watches uk Wall Street have fallen in love with the Armani brand. Now, with over $1.5 billion armani ceramicain revenue and a retail empire that extends to more than 35 countries, Armani himself continues to maintain full control over his business. However, it has been a long, uphill journey for the designer to get where he is today. 

The code snippet for exercise 1.22 does not match the book’s. Here’s the original:


(define (timed-prime-test n)
  (newline)
  (display n)
  (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
  (if (prime? n)
      (report-prime (- (runtime) start-time))))

(define (report-prime elapsed-time)
  (display " *** ")
  (display elasped-time))

I hope this does not get lost in spam.

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options