?

Log in

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|]

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 idealisms 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 oniugnip 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.


  1. And fewer to read.
  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.
LinkReply

Comments:
[User Picture]From: conform
2009-01-17 08:13 am (UTC)
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
(Reply) (Thread)
[User Picture]From: pmb
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
(Reply) (Parent) (Thread)
[User Picture]From: stereotype441
2009-01-17 03:13 pm (UTC)

Re: Woo pythoooon!

Whoa.
(Reply) (Parent) (Thread)
[User Picture]From: dlakelan
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.
(Reply) (Parent) (Thread)
[User Picture]From: conform
2009-01-17 10:33 pm (UTC)
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
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
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.
(Reply) (Parent) (Thread)
[User Picture]From: conform
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.
(Reply) (Parent) (Thread)
[User Picture]From: billings
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.
(Reply) (Parent) (Thread)
[User Picture]From: conform
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.
(Reply) (Parent) (Thread)
[User Picture]From: billings
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
(Reply) (Parent) (Thread)
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)))
(Reply) (Thread)
[User Picture]From: jes5199
2009-01-18 12:35 am (UTC)
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

and the sieve (from your google page, bug included:)
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
(Reply) (Thread)
[User Picture]From: jes5199
2009-01-18 12:47 am (UTC)
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
(Reply) (Parent) (Thread)
[User Picture]From: conform
2009-01-18 02:00 am (UTC)
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
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2009-01-18 01:39 am (UTC)
python generators in ruby, implementing using the terrifying callcc magic. http://pastie.org/363584
(Reply) (Parent) (Thread)
[User Picture]From: lindseykuper
2009-02-17 03:44 pm (UTC)
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.
(Reply) (Parent) (Thread)
[User Picture]From: jes5199
2009-01-18 12:50 am (UTC)
anyway, I'm proud that you're finally learning that programming doesn't have to be wracked with pain.
(Reply) (Thread)
[User Picture]From: dlakelan
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...

(Reply) (Thread)
[User Picture]From: idealisms
2009-01-24 05:11 am (UTC)
(catching up on LJ)

Python:
http://xkcd.com/353/
(Reply) (Thread)
[User Picture]From: lindseykuper
2009-01-25 01:10 am (UTC)
I know, man. That's what I'm quoting in the title.
(Reply) (Parent) (Thread)