Author: kjdyck

Taking the Digicam Plunge

For an embarrassingly long time, I’ve been promising Mandy that we would buy a digital camera. Last night, we finally took the plunge.

Our main criteria was price. We wanted to spend less than $300. After some surfing around TigerDirect, I found four Kodak cameras that worked: CX6445, CX7530, DX7440, and LS753.

The reviews of the DX7440 and LS753 on Imaging Resource and the dearth of reviews on the CX cameras convinced me that we were looking at a shootout between the DX7440 and the LS753.

Mandy and I compared the two. The LS753 is a 5 megapixel camera, but only has a 2.8x optical zoom. The DX7440 only has 4 megapixels, but a 4.0x optical zoom. We don’t expect that we’ll be printing out to many large (>5×7) photos, so the extra megapixel of resolution didn’t seem all that important. I wanted more than the 2.8x optical zoom of the LS753.

So the DX7440, it was. It should be arriving this week. Expect to see some shots on Flickr by the weekend.

Solution to SICP Exercise 1.20

Structure and Interpretation of Computer Programs

Solution to Exercise 1.20:

;;; Normal Order

; remainder count: 0
(gcd 206 40)

; rc: 0
(if (= 40 0)
206
(gcd 40 (remainder 206 40)))

; rc: 0
(gcd 40 (remainder 206 40))

; rc: 0
(if (= (remainder 206 40) 0)
40
(gcd (remainder 206 40)
(remainder 40 (remainder 206 40))))

; rc: 1
(if (= 6 0)
40
(gcd (remainder 206 40)
(remainder 40 (remainder 206 40))))

; rc: 1
(gcd (remainder 206 40)
(remainder 40 (remainder 206 40)))

; rc: 1
(if (= (remainder 40 (remainder 206 40)) 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))

; rc: 2
(if (= (remainder 40 6) 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))

; rc: 3
(if (= 4 0)
(remainder 206 40)
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))

; rc: 3
(gcd (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))

; rc: 3
(if (= (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
0)
(remainder 40 (remainder 206 40))
(gcd (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))))

; rc: 4
(if (= (remainder 6
(remainder 40
(remainder 206 40)))
0)
(remainder 40 (remainder 206 40))
(gcd (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))))

; rc: 5
(if (= (remainder 6
(remainder 40
6))
0)
(remainder 40 (remainder 206 40))
(gcd (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))))

; rc: 6
(if (= (remainder 6 4) 0)
(remainder 40 (remainder 206 40))
(gcd (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))))

; rc: 7
(if (= 2 0)
(remainder 40 (remainder 206 40))
(gcd (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40 (remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))))

; rc: 7
(gcd (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))

; rc: 7
(if (= (remainder (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))
0)
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(gcd (remainder (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))
(remainder (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))))

; rc: 14 (there were 7 calls to remainder in the = form above)
(if (= 0 0)
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(gcd (remainder (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40))))
(remainder (remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))
(remainder (remainder 40
(remainder 206 40))
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))))))

; rc: 14
(remainder (remainder 206 40)
(remainder 40
(remainder 206 40)))

; rc: 15
(remainder 6
(remainder 40
(remainder 206 40)))

; rc: 16
(remainder 6 (remainder 40 6))

; rc: 17
(remainder 6 4)

; rc: 18
2

For normal order, remainder is performed 18 times.

;;; Applicative Order

; rc: 0
(gcd 206 40)

; rc: 0
(if (= 40 0)
206
(gcd 40 (remainder 206 40)))

; rc: 0
(gcd 40 (remainder 206 40))

; rc: 1
(gcd 40 6)

; rc: 1
(if (= 6 0)
40
(gcd 6 (remainder 40 6)))

; rc: 1
(gcd 6 (remainder 40 6))

; rc: 2
(gcd 6 4)

; rc: 2
(if (= 4 0)
6
(gcd 4 (remainder 6 4)))

; rc: 2
(gcd 4 (remainder 6 4))

; rc: 3
(gcd 4 2)

; rc: 3
(if (= 2 0)
4
(gcd 2 (remainder 4 2)))

; rc: 3
(gcd 2 (remainder 4 2))

; rc: 4
(gcd 2 0)

; rc: 4
(if (= 0 0)
2
(gcd 0 (remainder 2 0)))

; rc: 4
2

For applicative order, remainder is only performed four times.

Solution to SICP Exercise 1.19

Structure and Interpretation of Computer Programs

Solution to Exercise 1.19:

Tqp is defined as:

a ← bq + aq + ap
b ← bp + aq

If we apply Tpq to itself, we get T2pq:

a ← (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p
b ← (bp + aq)p + (bq + aq + ap)q

With some manipulation, this can be rewritten as:

a ← b(2pq + q2) + a(2pq + q2) + a(p2 + q2)
b ← b(p2 + q2) + a(2pq + q2)

As we are looking for a transformation of the form

a ← bq′ + aq′ + ap′
b ← bp′ + aq′

It should be fairly obvious that

p′ = p2 + q2
q′ = 2pq + q2

Now we can modify our program:
(define (fib n)
(fib-iter 1 0 0 1 n))

(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(sum-of-squares p q) ; compute p'
(+ (* 2 p q) (square q)) ; compute q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))

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

(define (sum-of-squares x y)
(+ (square x) (square y)))

27,000 Concurrent Erlang Poker Games

In the past six weeks, Joel Reymont has rewritten a large part of his online poker software engine in Erlang, with some impressive results:

I have a PowerBook G4 1.25Ghz with 512Mb of memory. Running 27K games consumes about 600Mb of memory and takes around 15 minutes per 10K games due to heavy swapping. I gave “top” a cursory look so this is a probably reason. Each game runs in about 0.02 to 0.07 seconds, depending on the number of games running.

Erlang has long been on my list of languages to learn, but I don’t expect to get to it any time soon. SICP first, then CTM. If I haven’t died of old age by then (given my current pace, I’d put the odds around 50:50), I might just take up Concurrent Programming in ERLANG.

FYI, Joel’s engine was formerly programmed in Common Lisp. (via Chris Double)

Cosmic Radiation and the BSOD

Space is full of cosmic radiation. Computer chips that go into satellites and other space gear need special shielding to protect them from the single-event effects, or SEEs, of cosmic radiation, but here on Earth, chip designers haven’t had to worry about it too much because the atmosphere reflects most of it away.

According to an article in EDN, with the increased densities of modern computer chips, SEEs are becoming the dominant reliability-failure mechanism here on Earth.

Paul Dodd, another foremost expert on SEEs and acting manager for the radiation-effects department at Sandia National Laboratories (Albuquerque, NM), says that commercial designs are also more frequently encountering SEEs but that designers are commonly missing or misidentifying them as other failures. “It could be happening on everyone’s PC, but instead everyone curses Microsoft,” says Dodd. “Software bugs probably cause a lot of those blue-screen problems, but you can trace some of them back to radiation effects.” And designers cannot yet quantify the breadth of the problem because, as IC-design and EDA consultant Pallab Chatterjee points out, “It is something companies don’t brag about.”

As chip densities and clock speeds continue to increase, it seems chips will become more susceptible to SEEs. It will be interesting to see how this affects Moore’s Law.

Marburg Outbreak in Angola

According to this New Scientist story, the Marburg virus outbreak in Angola that started in March has now spread into all age groups. Prior to this the virus was mainly infecting children. The virus has killed 271 of 311 reported cases.

Should I be surprised that this story isn’t getting the same kind of coverage in the mainstream media that, say, the SARS outbreak received?

Challenging the Education Leviathan

Robert Nagle blogs about John Taylor Gatto’s online book, An Underground History of American Education. From the prologue:

The new dumbness is particularly deadly to middle- and upper-middle-class kids already made shallow by multiple pressures to conform imposed by the outside world on their usually lightly rooted parents. When they come of age, they are certain they must know something because their degrees and licenses say they do. They remain so convinced until an unexpectedly brutal divorce, a corporate downsizing in midlife, or panic attacks of meaninglessness upset the precarious balance of their incomplete humanity, their stillborn adult lives. Alan Bullock, the English historian, said Evil was a state of incompetence. If true, our school adventure has filled the twentieth century with evil.

The way he rails against the public education system, you might never guess Gatto was once New York State Teacher of the Year.

Miniature Motors

New Scale Technologies makes miniature piezoelectric motors:

Piezoelectric actuators in the SQUIGGLE motor ultrasonically vibrate a threaded nut, producing an orbital motion. The nut vibration directly rotates a mating threaded screw to create precise linear motion — with no parasitic drag, no backlash, and very high stiffness. The motor holds its position with the power off.

This simple, robust piezo motor generates no magnetic fields, is vacuum compatible, and can be made from non-ferrous metals for use in MRI, scanning electron microscopy and focused ion microscopy applications.

Combine some of these with a miniature low-power DSP, and you have the makings of one tiny robot. What on earth you’d want a miniature robot for is beyond me, but it comforts me to know its possible.

Asynchronous Digital Design by Fulcrum

Fulcrum Microsystems developed a clockless semiconductor design methodology. Which allows them to design processors that run much faster than clocked chips and with lower power.

Back in 1994, near the end of the digital design course I took in university, the professor introduced the class to asynchronous design. Our professor showed us some tricks for solving simple problem with asynchronous logic, but told us that the technique wasn’t feasible for large scale design at the time, because it was terribly complicated with race conditions. It seems Fulcrum has solved the problem, and even designed some rather complex chips with it.

They raised $20 million on Monday.