Project Euler Problem 5 reads “What is the smallest number divisible by each of the numbers 1 to 20?” This is obviously a Least Common Multiple problem. There are 2 quick ways that come to mind to solve the problem. The first is that you can brute force it, checking all of the numbers until you find one that can be divided by all of the numbers.
After I arrived at my answer (by doing just that last year), I went into the Project Euler forums and found that quite a few people did it just the same way. Others actually attempted the prime factorization necessary to compute the least common multiple and had varying degrees of success.
With my recent foray into Scheme, I decided to hit the forums to see if anyone attempted problem 5 in Scheme. The first Scheme solution that I found was the following:
;; find the smallest number where n is
;; divisible by all numbers in given list
(let loop ((i 1))
(if (divisible-by i num-list)
(loop (+ i 1))))))
(lambda (n lst)
(if (null? lst)
(if (= (remainder n (car lst)) 0)
(divisible-by n (cdr lst))
;; generates a list of numbers between start and end
;; contract: number, number -> list
(lambda (start end)
(if (> start end)
(cons start (make-list-range (+ start 1) end)))))
(smallest-divisible-by (reverse (make-list-range 1 20)))
This was just a brute force method in Scheme. He created a list and then tried to find a number that was divisible by all of the numbers in the list. The bad news is that it took 97 seconds on my MacBook Pro with a Quad Core i5. That is completely unacceptable.
I got to thinking about it and I wondered if Scheme had a least common multiple function, as functional languages often have “neat math stuff” in their bag of tricks.
It turns out that it does. If I run this code:
(lcm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
It returns the answer as soon as I hit enter, computed almost instantly. It may be cheating to use a built-in function, but in real life, I don’t think so. I think you use the best tool for the job and if I can answer a problem with no development and an instant result, I think that that is the tool I should use.
Like any good nerd, I jumped on the Windows 8 download as soon as I could from The Windows Developer Page. I downloaded the 4.8 gig, 64 bit, full developer tool version (insert Tim Allen-style grunting here) and it took about 2 hours to arrive.
Once I had the .iso, I tried to install it in VMware on my MacBook Pro, but VMware kept complaining about some stupid error or another when it was trying to boot from the .iso, so I decided to move on. I fired up Virtual Box and this time got no complaints. The install was pretty quick and painless and took “maybe” a half hour, I didn’t time it. I created the virtual machine with 2 processors and 2 gigs of RAM and plenty of hard disk space.
My “artsy” install screen.
I also had to accept a license (it seems pretty lax):
Once I got all situated and into the OS, I was presented with a kind of confusing “totally green” screen. I was moving my mouse around and when I got to the “Start Button Corner”, some things popped up on the screen.
When I clicked “Start”, I got my first big time look at the new Metro UI.
If I scroll to the right a little, there is more.
But don’t worry, though, if too much change isn’t your thing. If you click “Desktop”, you get to see “Old Faithful”.
My first order of business – of course – was to check and make sure my blog was still okay. I mean, a man has to have priorities.
This version came with a Twitter client called Tweet@rama. It definitely is built in the Metro UI style that those of us with Windows Phone 7s are used to. It seems to have a panorama view and familiar styling on all of the icons and buttons.
All in all, Windows 8 is a good-looking operating system. If you can get behind the Metro UI on the Windows Phone, you will be at home here. The tiles can be moved around and they dip and slide out of each other’s way as you are doing any housekeeping or clicking. Also, there are Live Tiles – like WP7 – that update with current information.
If I was using this on a touch device, I would call this a definite home run. The problem is that the side scrolling was a little clunky to me using a mouse. It could be a VM issue, but my scroll wheel on the mouse that normally lets me press and slide up-down-left-right on a page did not work, so I had to go down and grab and move the horizontal scrollbar. Those of us who develop for the web know that people really hate doing that.
It is possible that Microsoft is betting on a huge move to touch devices being front and center for most business users in the future. I’m sure there is a happy story for developers and people who do a lot of data entry, but after an hour of playing, I don’t know what it is yet 😉
Do you have it installed yet? What do you think?
The last two posts just covered a basic overview of how Scheme’s syntax works and was kind of a way to just expose people to the language. This post is going to cover how you can use recursion in Scheme.
There are two very common mathematical examples that are always used when talking about recursion in programming. The first is computing a Factorial and the other is the Fibonacci sequence. Who am I to buck tradition?
First, we’ll look at the Fibonacci sequence. The first 10 numbers of the sequence are 1 1 2 3 5 8 13 21 34 55.
Here is how we would implement that in Scheme.
(define (fib n)
(if (< n 2)
(+ (fib (- n 1))(fib (- n 2)))
That function calls itself recursively to figure out what the nth digit of the Fibonacci sequence is. So, if we'd like to see it print out in a chain, we can just call that function in a loop.
(let loop ((n 1))
(if (<= n 10)
(display (fib n))(newline)
(loop (+ n 1))
That looks like this:
A factorial (ex: 5! = 5 * 4 * 3 * 2 * 1 = 120) in Scheme would be coded simply like this:
(if (= n 0)
(* n (factorial (- n 1)))
Here is something interesting. Because Scheme is dynamic with its type system and this function can return anything, I can actually work with really large numbers. For example, here I call the function twice, once with 5 to return 120 and the second time with 50 to return 30414093201713378043612608166064768844377641568960512000000000000. That is obviously WAY too big to be returned with any native .Net data type. Also, both of those calls returned as quickly as I hit Enter.
Up until now, there isn't much special about these recursive functions. However, Scheme does allow something that C# doesn't allow (well, it can in very special circumstances) and that is tail recursion. This is also (sometimes controversially) called tail optimization and is something of a hallmark of functional languages.
Traditionally, for every method/function/procedure call you are making in a language, you are building on the stack until that method/function/procedure returns. You see this all the time when you look at a stack trace while you are debugging. However, when you recursively call the same method over and over and over again, you risk a stack overflow. Imagine I wanted to find out what 50000! was. I would be putting 50000 function calls (all to the same function) on the stack and depending on the architecture I was on, I could overflow the stack (on my Macbook Pro, it did return after a few minutes with a VERY large number - pages and pages of scrolling).
What tail call optimization does is "discard" the stack up to the point when it calls itself again because the function will just be returning itself, so it doesn't need to keep track. If that sounds wayyy insane, let's think about our terms. First "tail position" refers to the last thing that happens in a function before it returns. In the case of tail recursion, the last thing that occurs is a call to the function itself. Even though it looks like my factorial example from earlier might be tail recursive, it really isn't. Here it is again.
(if (= n 0)
(* n (factorial (- n 1)))
Take notice of the last line: (* n (factorial (- n 1))). You see how the last thing the function does is multiply the number passed in (n) against the result of the function called again with "n minus 1". So, we can't just jump ahead to the new function and only return its results because those need to bubble up the stack, being multiplied against the function's original n all the way up.
What we need to do is track our own progress, so that the function doesn't need to be multiplied by anything outside of itself. One thing we could do is just take the accumulation as a second parameter, but that is relying on the caller of the function to kind of do something unnatural and not obvious when calling the function. What we'll do instead is declare a local function inside of our function and call this local function with our parameter and a variable that accumulates and tracks our state.
The factorial function in full tail-recursive glory could look something like this
(please note: this isn't formatted the "Scheme-Way" because I was trying to make it as readable as possible)
(define pete_factorial ; our function
(letrec ; defining something here with local scope
(inner_factorial ; a locally scoped function
; local function is a lambda taking 2 params
(lambda (the_number our_accumulator)
(if (= the_number 0) ; if the number passed in is 0
; return the current accumulation
; else call the local function again with the decremented
;number and an up-to-date accumulator
(inner_factorial (- the_number 1) (* our_accumulator the_number))
) ;closing the if
) ; closing the lambda
) ; closing the inner function def
) ; closing the letrec body
; actual pete_factorial definition is a lambda
; lambda body that calls the local function with the param and
; an initial accumulator of 1
(inner_factorial actual_parameter_passed_in_to_pete_factorial 1)
) ; close lambda
) ; close pete_factorial body
) ; close define statement
Hopefully, that is fairly clear. I've actually had this post in the hopper for some time while I wrapped my head around exactly what we were accomplishing here. Then, when I thought I had it and it was time to write, I still wasn't prepared to explain it clearly. I hope that the combination of the formatting, comments, and verbose variable names helps you to understand it. I know that it helped me out a great deal.
As I've said, our basic goal here is to keep the stack from having to keep track of our state. In the original one, it worked out to be something like
In my severely-commented tail recursive case, it doesn't have to do that. It loads the function onto the stack and it keeps it there. Every definition describes that it basically does a GOTO and just keeps calling back to the top of the function (the inner function) over and over again. Because we keep our own state, the last thing to evaluate is just returned because the last value of the function is the answer.
This time, it is:
replace arguments with (5 1), goto "inner_factorial"
replace arguments with (4 5), goto "inner_factorial"
replace arguments with (3 20), goto "inner_factorial"
replace arguments with (2 60), goto "inner_factorial"
replace arguments with (1 120), goto "inner_factorial"
replace arguments with (0 120), goto "inner_factorial"
I know we've covered a lot here, but this is good solid computer science stuff. It definitely doesn't hurt to think about it from time to time and really understand what is going on with the computer and within our languages when we write our code.
If you have any questions, or want me to try to clarify something, let me know in the comments and I'll do the best I can.