Solution to SICP Exercise 1.28

Structure and Interpretation of Computer Programs

Solution to Exercise 1.28:

(define (square x)
(* x x))

(define (expmod-with-trivial-sqrt-check base exp m)
(cond ((= exp 0) 1)
((even? exp)
(let* ((intermediate (expmod-with-trivial-sqrt-check base (/ exp 2) m))
(squared-mod (remainder (square intermediate) m)))
(if (and (not (or (= intermediate 1) (= intermediate (- m 1))))
(= squared-mod 1))
0
squared-mod)))
(else
(remainder (* base (expmod-with-trivial-sqrt-check base (- exp 1) m))
m))))

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

Request for comments: Online charity raffle

It’s been a while since I announced on this blog that I’m planning to walk in the Weekend to End Breast Cancer. I still haven’t raised many funds. I haven’t done very much either, which entirely explains it. Anyways, it’s about time I give this event some attention and start raising some money. So here goes nothing…

I’ve been giving some thought to one particular way I might solicit some donations and I’d would like to get your thoughts on it.

I’ve been toying with the idea of running an online raffle to raise money for the event. It is an idea inspired by John Chow’s link-building contests, but in my case, I’m more interested in raising money for breast cancer research than I am in promoting this blog.

I’m thinking of making the prize an iPod nano — a pink one, in keeping with the pink ribbons associated with the cause. If I had to guess the first rule about running a raffle, it would be that the prize has to be worth winning. Those iPods seem to be universally adored, so I think I’d be safe with one of those.

Here’s how I’m thinking it would work.

The raffle would be open to anybody and there would be several ways to enter:

  1. Make a donation – I’m thinking there would have to be some minimal donation for entry in the contest. An amount of $10 comes to mind.
  2. Spread the word by blog – A blogger could enter the contest by writing post about the raffle. As long as the post met some minimal criteria, like including a link to the contest page and another to my donation page, the blogger would be entered into the contest. I would supply some boilerplate text to make this easy to do.
  3. Spread the word by email – Non-bloggers could spread the word and enter the contest by forwarding an email about the contest to at least X others and copying me on it. I’m thinking 5 might be a good number for X. I’m feeling a little hesitant about this part of the contest because it kinda feels like spam, but I want to give people who don’t have websites a chance to enter. What do you think?

One of my biggest fears is that I’d have plenty of people the word (since it’s essentially free) and nobody making donations. To make the donation option more attractive, I’m thinking I’d have donations count for two ballots in the raffle and word-spreading entries only count for one. I recognize that there is a built-in disincentive to spreading the word, since it opens the possibility to more ballots entering the contest and reduces the likelihood that the spreader will win, but I’m not sure that it will be enough.

Another problem that I worry about is that email word-spreaders will try to beat the system by forwarding email to garbage addresses. I thought I might reduce this problem by warning people up front that I intend to check any potential winner by writing to the email addresses to which the message was forwarded and confirming that there is a human (or something that sounds human) on the other end. Of course, this doesn’t stop scammers from forwarding all the copies of the email to themselves, using a different alias for each copy.

One of my other concerns is that by turning my fund-raising into a contest for personal gain, I might be robbing potential donors of feeling they are good people. It seems to be setting up a perfect situation for an internal moral conflict: am I good person for giving to a worthy cause or a bad one because I want to win an iPod? I’m afraid it could backfire and paralyze people from doing anything.

Comments?

What are your impressions? Would you participate? How?

Any suggestions for how to set up the numbers for the contest? How many ballots would you enter for donations versus word-spreading? How big of a donation would require? How many emails would you require to forward?

Finally, are you interested in donating an iPod for the raffle? I’d make sure to have your name (or the name of your company) gratuitously plastered on all the related material. It could make for a good promotional tool you or your company. Email me if you’re interested: kd@kendyck.com.

Bird Lives!

charlieparker

charlieparker

Originally uploaded by hablando del asunto.

I recently finished reading Ross Russell’s Bird Lives!, a biography of Charlie Parker, the legendary jazz saxophonist who revolutionized the world of jazz in the early 1940s.

One of the things that surprised me on reading the book is just how unremarkable Parker was as a young musician.

We all hear stories of young Mozart; how audiences were astounded by his musical talents as a child. Mozart seemed to have some inexplicable innate musical from the moment of his birth.

Not Parker.

He was relatively late coming to music. He didn’t pick up an instrument until he was in high school. When he did, all accounts indicate that he was awful. For years he was considered a joke amongst his local Kansas City musicians, if they noticed him at all. His tone was terrible. He didn’t have any real understanding of music theory or harmony. He just plain sucked.

But what he might have lacked in raw talent, he more than made up in dedication. He spent every spare minute practicing. Despite several demoralizing incidents at local jam sessions — all of his early attempts to solo in public ended badly; one with the drummer throwing a cymbal to the floor to get him off the stage — he continued practicing. He was determined to master the alto sax.

He did eventually, of course. He spent a summer learning to play the solos off some Lester Young records and learning music theory from other trained musicians. Slowly he became competent. Then he became good. He kept working at it until he became the great player that history remembers him for.

While reading the biography, I was reminded of an article Kathy Sierra wrote about becoming an expert:

The only thing standing between you-as-amateur and you-as-expert is dedication. All that talk about prodigies? We could all be prodigies (or nearly so) if we just put in the time and focused. At least that’s what the brain guys are saying. Best of all–it’s almost never too late.

I’m not suggesting you can consider Charlie Parker a typical example of anything, but his experience does seem to support what Kathy is saying.

Dedication makes a difference.

I find that encouraging.

5 Things

The Mighty Sally tagged me, so here are five things you probably don’t know about me.

  1. I was shot in the head with a BB gun when I was four years old by an older kid next door. I don’t remember much about the event itself but I remember the doctor yanking the shot out with a pair of pliers afterwards and showing it to me. I thought it was neat-o.
  2. I wore a mullet in a pony tail in high school. I attribute this lapse in judgment to my childhood head wound.
  3. I’ve never had a cavity. I’d thank my dentist father for training me in proper dental hygiene but The Mighty Sally had the same training when she was young and ended up with a mouthful. I’m just lucky, I guess.
  4. I can recite the Pythagorean theorem from memory on cue. Don’t think that I’m bragging. I’m aware this is nothing to be proud of.
  5. I’m a video game addict. If you are wondering why I’ve made so few posts lately, blame Final Fantasy XII.

Now to tag some more victims. Let’s see… how about Mandy, Larry, Kempton, and Michael?

New Year’s at Disney

Epcot Dome

Mandy and I rang in the New Year at Disney World in Florida. If you’re interested, check out the photo set.

One bit of advice if you are planning a trip to Disney World over the Christmas/New Year’s holidays: expect a crowd. The week between Chrismas and New Year’s is their busiest of the year. On New Year’s Eve, the Magic Kingdom was filled to capacity — over 70,000 people — and spent much of the day closed to visitors who weren’t staying on the resort.

The crowds practically disappear after New Year’s Day, though. The contrast was remarkable — especially with the Extra Magic Hours that we were able to take advantage of, being resort guests and all. In the days following New Year’s, we were able to made it on all the rides we wanted, usually with less than a 15 minute wait. That includes rides like Expedition Everest (highly recommended) and the Rock ‘n Rollercoaster (oh yeah!).

Books of 2006

As it’s coming to the end of the year, it seems appropriate to sound off on the books that I read this year.

The Wisdom of Crowds – Citing stock markets and sports betting odds Surowiecki contends that under the right conditions the collective guesses of a group of people are as good or better than that of any individual expert. It’s an interesting idea, but I came away unconvinced. The conditions that Surowiecki identifies under which collective wisdom wins seem awfully narrow. Worth a read, anyways.

The Long Emergency – This is the most pessimistic book I’ve ever read. Kunstler argues that the global supply of oil is nearing it’s peak in production while demand continues rising. The result will decimate the world’s economy. Poverty, starvation, war, disease, pestilence and lawlessness will follow. Technology can’t help us. Prepare for the end of civilization. This book is as gloomy as they come. On the other hand, it’s hard to take seriously if you’ve read any of the Singularity is Near.

The Singularity Is Near – This is the most optimistic book I’ve ever read. Kurzweil predicts that in the next 20-40 years, computer intelligence will surpass that of humans. When it does, us humans will be able to take a permanent vacation, leaving all the hard work to machines since they’ll be so much better than us at everything. Biological people will be able to enhance their abilities with all sorts of intelligent technology and even back-up their brains so they can practically live on eternally in cyberspace. Nanotechnology will render biological death a thing of the past. Immersive virtual reality will allow us to go anywhere with anyone as anyone. The future is a techno-utopia. Don’t worry. Be happy. It is hard to take this stuff seriously, but it is well-researched and hard to argue against, considering how history is littered with naysayers that were proven wrong.

Dizzy: The Life and Times of John Birks Gillespie – If you are at all interested in the origins of bebop or how one of its founding practitioners rose to prominence, this biography is well worth the read. It follows Dizzy from his earliest years in the churches of Cheraw, South Carolina, through the birth of bebop in the clubs of 52nd Street in New York, and on through the rest of his prodigious career. A little slow in spots, but highly recommended if you are a fan of jazz.

Freakonomics – This is a book that demonstrates what you can find if sit down and examine the numbers. Are sumo wrestlers throwing matches? If drug dealing is so lucrative, why do so many dealers live with their parents? Why did crime rates drop so precipitously in the 1990s? How does a child’s name affect his chances of success later in life? It’s an entertaining read and the results of Levitt’s work are interesting, but I wish Levitt and Dubner had spent a little more time showing how they came to their results than just stating what they found. Recommended.

What Should I Do with My Life? – This is an excellent book. Po Bronson tells the stories of real people who have struggled with their purpose in life. Not everybody finds an answer. Even when one does, it often takes a major disruption in one’s life, such as a layoff or separation, before one even thinks of pursuing it. People are more often forced into major life changes than they choose to pursue them. Ultimately, some people do figure it out and are happier for it. For some the happiness doesn’t come. This book is an honest, touching look at life. Highly recommended.

Pattern Recognition – A logo-sensitive ad consultant tracks down the creators of underground online video. I could take it or leave it.

A Short History of Progress – History is replete with civilizations that have over-consumed and consequently collapsed. Wright argues that technology hasn’t made us any smarter. It’s only enabled us to carry out our unsustainable practices at a grander scale.

Metamorphosis and Other Stories – The tragic story a man who wakes up one morning finding himself transformed into a massive bug. Some of the other stories are quite fascinating, too. Recommended.

On Bullshit – A somewhat serious philosophical examination of the nature of bullshit. This is a fun and illuminating read. Recommended.

Opening Skinner’s Box – Slater examines ten experiments in psychology that have changed the what we understand of ourselves. Slater’s writing is excellent: engaging, thoughtful, fun. You might not expect a book about psychology to be especially interesting. I think this one might surprise you. Highly recommended.

Influence: The Psychology of Persuasion – This covers a lot of the same ground as Opening Skinner’s Box, but does so with an eye on how compliance professionals (marketers, salesmen, con men, etc.) apply what we know about psychology to influencing people. It isn’t written as a how-to book, but the lessons are definitely there for those eager to exploit them; as are some tips for defending yourself against the classic tricks. This is powerful stuff. Highly recommended.

A Million Little Pieces – A junkie goes through rehab. This is a captivating story of a young man putting his life back together. It is an embellishment on a true story, which is part of the reason it is so compelling. Highly recommended.

Life of Pi – The fantastic story of a boy trapped on a lifeboat with a tiger. It’s by no means a life-changer, but it definitely is a page-turner. Highly recommended.

Big Book of Drawing – I still suck pretty bad at drawing, but if it weren’t for this book, I’d be drawing stick figures. Lessons on drawing portraits, figures, and animals. In graphite and colour. Highly recommended.

It’s Not Funny If I Have to Explain It: A Dilbert Treasury – A collection of Dilbert cartoons with commentary from Scott Adams. Typical Scott Adams hilariousness. Highly recommended.

Concepts, Techniques, and Models of Computer Programming – From declarative computation through object-oriented, shared-state concurrency, relational, distributed, and constraint programming, this book surveys the vast field of programming paradigms and demonstrates them using the Mozart/Oz language. Good stuff. Recommended.

SCJP Sun Certified Programmer for Java 5 Study Guide – This book is an excellent book for what it does: prepare its readers for the SCJP exam.  I found the subject matter somewhat disheartening, though, as the exam seems to be set up more to test the student’s ability to parse java code for syntax errors than to understand the semantics of the language itself. Can’t hold that against the study guide, though. If you have to take the SCJP exam, I’d recommend it.

Back from Las Vegas

Eiffel Tower

Eiffel Tower

Originally uploaded by Ken Dyck.

We returned from Las Vegas yesterday. Photos here and here.
The highlights:

  1. Love, the Cirque de Soleil show based on the music of the Beatles, was one of the most magical experiences of my life. Highly recommended.
  2. I wasn’t expecting much, but the Fountains of Bellagio impressed me.
  3. The Cheesecake Factory makes a great sandwich. Wish they’d come to Canada.
  4. Red Rock Canyon is a landscape unlike anything in southwestern Ontario. Check out our photos.
  5. All the architecture along the strip is over the top. Check out our photos.

The lowlights:

  1. There are four things to do in Vegas: drink, gamble, pay for sex, or shop. If you aren’t especially interested in any of them, you are likely to get pretty bored pretty fast.
  2. Sirens of TI, the free live show put on by Treasure Island, was far and away the cheesiest thing we saw in Vegas. And that’s coming from somebody who saw the Fall of Atlantis.
  3. Timeshare hucksters were everywhere; the scourge of Vegas.

Leaving for Las Vegas

Mandy and I are heading to Vegas for the weekend. Neither of us have ever been there.

Neither of us are much on gambling. Mandy doesn’t expect to spend any time in the casinos at all. If I happen to do any wagering at all, it’ll be solely for the entertainment value. I expect anything I bet to go directly into the pockets of the casino operators. You might as well tatoo the word ‘fish’ on my forehead.

The main reason for going is to catch a Cirque du Soleil show: Love. It is set to the music of the Beatles, and in our household the combination of Cirque du Soleil and Beatles music is simply irresistible.
This will be the first time I’ve seen a live performance by the company. If the video clips I’ve seen are any indication it should be spectacular.

Expect some photos when we return.