No account? Create an account
 I also sampled everything in the medicine cabinet for comparison. - Lindsey Kuper [entries|archive|friends|userinfo]
Lindsey Kuper

 [ website | composition.al ] [ userinfo | livejournal userinfo ] [ archive | journal archive ]

I also sampled everything in the medicine cabinet for comparison. [Jan. 16th, 2009|09:14 pm]
Lindsey Kuper
 [ Tags | programming ]

The new semester began this past Monday. Between classes, homework, AI-ing, and choir rehearsal, it really seems to be cutting into my blogging-breathlessly-about-Python time.

A couple weeks ago, Tony suggested that one way to whip my Python into shape might be to do some Project Euler problems, so I decided to try a few. When I sat down to start doing them, I wasn't feeling particularly confident. But when I read the first problem, "Find the sum of all the multiples of 3 or 5 that are below 1000", I astonished myself by barely even having to think about it:

`print sum(filter(lambda x : x % 3 = 0 or x % 5 = 0, range(1, 1000))`

One line. 20 seconds to write.1 And it worked!

I decided to double-check the answer by solving the same problem in Scheme. Oughta be a snap to port this one trivial line of code ov -- oh, wait, in Scheme I don't have `range`. And I don't have `sum`. And, oops, I always forget that `%` is spelled "R-E-M-A-I-N-D-E-R", and hmm, `filter` doesn't seem to be in the R5RS, although, oh, good, Chez Scheme has it, and I could use `reduce` instead of `sum`, except Chez doesn't have `reduce` -- although both `filter` and `reduce` are in SRFI-1, so I can use them in PLT by sticking a `(require srfi/1)` at the top of my file, which I am guaranteed to misspell as "sfri" the first time, but you can't use `require` in Chez, and, and, and, and.

Let me be clear: I love Scheme. It is my favorite programming language. But it's a batteries-not-included sort of programming language. In Scheme you get to make your own batteries. Here's what I wrote:

``````(define problem-1
(lambda (n)
(letrec ((kernel (lambda (x acc)
(cond [(= x 0) (display acc) (newline)]
[(or (= (remainder x 3) 0)
(= (remainder x 5) 0))
(kernel (- x 1) (+ acc x))]
[else (kernel (- x 1) acc)]))))
(kernel (- n 1) 0))))

(problem-1 1000)``````

So it's a single, monolithic procedure that does the summing, filtering, and ranging all at once. Well, what's wrong with that? It's probably more efficient! To me, though, the more interesting point is that as a moderately experienced Schemer, doing it that way actually felt more right than implementing each of the helpers which would have enabled me to write something like `(sum (filter (lambda ...) (range 1 1000))))`. I'm not sure how I should feel about that. I would have guessed that a lack of libraries would slow me down as a programmer, but I wouldn't have thought that it would have such a pronounced effect on my actual coding style. But it does. If something I want isn't immediately available, my subconscious knee-jerk reaction isn't to implement it myself -- it's to think, "Oh, then I must not be supposed to use it!" and to look for a workaround.

I moved on to Euler problem 2: "Find the sum of all the even-valued terms in the Fibonacci sequence which do not exceed four million." I had it in Python in about five minutes. Then I went to check my answer by doing it in Scheme. And it dawned on me that I didn't want to.

You guys, a Fibonacci problem. In Scheme. That I didn't want to do. I actually called Alex to tell him I was having a crisis of faith. I am entirely serious. That's what I did.

After talking to Alex, though, since I was on a roll and didn't want to think about my crisis of faith, I moved on to Euler 3. "What is the largest prime factor of the number 600851475143?" Now we're talkin'! Hey, I bet I can use one of those crazy generator things! Better find out what that's all about, huh?

Then I hit a brick wall. I stared and stared at Guido's example of a generator in the Python tutorial, but it didn't seem apropos -- it seemed like, well, like the sort of thing that I could do just as easily without a generator, anyway. More to the point, though, I couldn't figure out how to generate an infinite stream! And I'm not just talking about the primes -- I'm saying I couldn't figure out how to do any infinite stream.

I went and got my SICP off the shelf and flipped it open to section 3.5.2. Oh, yes. A stream of the integers. A stream of the integers not divisible by 7. A stream of the Fibonacci numbers. And -- yes! -- a beautiful sieve of Eratosthenes! And, you know, it's SICP, so it's a hardened little pearl of a program, wrapped around a grain of sand they introduced back 20 or 50 or 100 pages ago, and moreover, you've been able to do this kind of thing in Scheme since before Python was ever thought of, because Scheme can be anything you want it to be!2

But I called Alex back, and Alex put Mark on, and I said, "How do I generate the integers?" and Mark explained, and I did like he said, and wait, what? It just goes back to where it left off when you call `next()`? Nah, too easy. But -- but -- it worked! And then I did it for the not-divisible-by-sevens, and for the Fibonacci numbers, and I'm just not believing it and I'm not believing it and no way. No. Way. This is cheating. It's cheating it's cheating it's cheating it's cheating it's cheating it's cheating it's cheating

``````def sieve():
i = 2
while True:
yield i
n = i + 1
for k in range (2, i):
if n % k == 0:
n = n + 1
i = n``````

"Python is cheating!" I told Will and Dan after class on Tuesday. They laughed.

2. Actually, maybe what I want to say is: The only thing that Scheme can't be is a language that can't be everything.

 From: 2009-01-17 08:13 am (UTC) (Link)
cheating? maybe... your function tells me that 27 and 35 are prime.

also: somewhat faster:

```def smart_sieve():
yield 2
primes = [2]
i = 1
n = 2
while True:
n += 1
for k in range(len(primes)):
if n % primes[k] == 0:
break
else:
primes.append(n)
yield primes[i]
i += 1
```
From:
2009-01-17 11:43 am (UTC)

### Woo pythoooon!

Also, something that blew my mind about generating primes:
"The Genuine Sieve of Eratosthenes" - http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
From:
2009-01-17 03:13 pm (UTC)

### Re: Woo pythoooon!

Whoa.
From:
2009-01-18 06:10 am (UTC)

### Re: Woo pythoooon!

I remember programming a seive of eratosthenes at Chases' house in Pascal ca. 1991. Pretty sure with a little help from you we got it to do the first hundred thousand primes in less than 1 second on a 33mhz or so Mac LC

The real sieve is a thing of beauty.
 From: 2009-01-17 10:33 pm (UTC) (Link)
The fastest really simple sieve I've come up with:

```def smart_sieve():
yield 2
primes = []
n = 3
while True:
is_prime = True
for p in primes:
if n < p[1]:
break
if n % p[0] == 0:
is_prime = False
break
if is_prime:
primes.append([n, n * n])
yield n
n += 2
```
From:
2009-01-18 01:30 am (UTC)

### Re: Woo pythoooon!

Oof! Thanks, Seamus. Clearly, I didn't bother to test it much beyond "not giving me 9 and 15" (and apparently I just got lucky that it gave me the right answer for the Euler problem). I'll play with it some more. I'm interested in figuring out precisely why it is wrong.
From:
2009-01-18 02:13 am (UTC)

### Re: Woo pythoooon!

Here is a script that computes primes in rather too many ways: http://www.pastie.org/363603

run it with no arguments for the usage.

-ow is currently the fastest. on my laptop it'll crank out the millionth prime in about five minutes. -q is the most complicated, but to little avail: it's slower than everything but the naive approach. not sure if i've got the energy to find a data structure that will allow it to reach its full potential.
From:
2009-01-18 06:26 am (UTC)

### Re: Woo pythoooon!

Where are you getting the wheel stuff from?

Also: http://www.pastie.org/363716

Priority queue helps a lot but still gets whipped by the simple prime-only division method.
From:
2009-01-18 08:55 am (UTC)

### Re: Woo pythoooon!

the wheel stuff is basically an extension of "primes are always odd, so i can add two every time instead of one", for "primes are always p % 2 == 1 and p % 3 == 3," etc for 2, 3, 5, 7. it's the sequence of intervals of all the numbers starting with 11 that aren't % 0 for 2-7.
From:
2009-01-19 04:02 am (UTC)

### Re: Woo pythoooon!

I have no idea how to solve y = x / ln(x) in terms of y

I am a failure as a human being
From: (Anonymous)
2009-01-17 01:14 pm (UTC)

### Alternative Scheme solutions

Hi, I liked your post, and thought you might like to see alternative Scheme solutions. They are written in PLT Scheme, but are easy to port other Scheme implementations. #lang scheme (require srfi/42) (sum-ec (:range x 0 1000) (if (or (= (remainder x 3) 0) (= (remainder x 5) 0))) x) (apply + (filter (λ (x) (or (zero? (remainder x 3)) (zero? (remainder x 5)))) (build-list 1000 values)))
 From: 2009-01-18 12:35 am (UTC) (Link)
1) I am astounded that any scheme fails to have "reduce" or "filter". Those always near the top the list of "useful things we learned from LISP"

2) A programming language that discourages writing sub-functions is dangerous

3) Why doesn't ruby have generators? I guess we would write them inside out- pass your prime-eating code as a block:
``````def factor(n)
factors = []
my_sieve.each do |d|
break if n < d
if n % d == 0
factors.push(d)
n /= d
retry
end
end
return factors
end``````

``````def sieve
i = 2
loop do
yield i
n = i + 1
(2...i).each do |k|
if n % k == 0
n = n + 1
end
end
i = n
end
end``````
 From: 2009-01-18 12:47 am (UTC) (Link)
the bug seems to be
``````if n % k == 0
n = n + 1``````

n + 1 is never tested for factors in 2..k

I've got a fixed version for ruby, but it's not pretty:
``````def sieve
i = 2
loop do
yield i
n = i + 1

catch(:next) do
loop do
catch(:retry) do
(2...i).each do |k|
if n % k == 0
n = n + 1
throw :retry
end
end
throw :next
end
end
end

i = n
end
end``````
 From: 2009-01-18 02:00 am (UTC) (Link)
here's the version i had last night after i fixed the bug and started incrementing by twos:

```def sieve():
i = 2
n = 3
yield i
while True:
for k in range (3, n):
if n % k == 0:
break
else:
i = n
yield i
n += 2
```
 From: 2009-01-18 01:39 am (UTC) (Link)
python generators in ruby, implementing using the terrifying callcc magic. http://pastie.org/363584
 From: 2009-02-17 03:44 pm (UTC) (Link)
I am astounded that any scheme fails to have "reduce" or "filter". Those always near the top the list of "useful things we learned from LISP"

For what it's worth, Chez has `fold-left` and `fold-right`. And I'm not sure any actual Scheme doesn't have `filter`, despite it not being in the (old version of the) spec.
 From: 2009-01-18 12:50 am (UTC) (Link)
anyway, I'm proud that you're finally learning that programming doesn't have to be wracked with pain.
From:
2009-01-18 06:07 am (UTC)

### Re: Woo pythoooon!

It's not cheating, it's just half-assed implementing a special case of call/cc to do coroutines...

if only common lisp had call/cc life would be complete...