Matt Bowcock // mbowcock.com

Since I’m working my way through SICP I ended up using some of the code from the examples in section 1.2.6 to search for prime numbers. Six of the eight functions below are used to test if a number is prime. (next-prime …) just starts at the current prime number and iterate upward until it finds the next prime number. (search-for-factors …) does the actual searching for prime factors.

(define (smallest-divisor n)
  (find-divisor n 2))

(define (divides? a b)
  (= (remainder b a) 0))

(define (square n)
  (* n n))

(define (next-divisor n)
  (if (= n 2)
      3
      (+ n 2)))

(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (next-divisor test-divisor)))))

(define (prime? n)
  (= n (smallest-divisor n)))

(define (next-prime n)
  (let ((m (+ n 1)))
    (if (prime? m)
         m
         (next-prime m))))

(define (search-for-factors n factor)
  (cond ((= (/ n factor) 1) (display factor)
                                    (newline))
        ((divides? factor n) (display factor)
                                   (newline)
                                   (search-for-factors (/ n factor) factor))
        (else (search-for-factors n (next-prime factor)))))

(search-for-factors 600851475143 2)

The code below is exercises 1.16 and 1.17. I’ll finish up 1.18 and 1.19 some time in the future. I’ve created a repository on github to store the code I write while working through SICP – if you’re interested it can be found at
http://github.com/mbowcock/SICP.

Exercise 1.16 -

(define (square n)
  (* n n))

(define (fast-expt-iter b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt-iter b (- n 2) (* a (square b))))
        (else (fast-expt-iter b (- n 1) (* a b)))))

(define (fast-expt-new b n)
  (fast-expt-iter b n 1))

Exercise 1.17 –

(define (double n)
  (* n 2))

(define (halve n)
  (/ n 2))

(define (*. a b)
  (cond ((= b 0) 0)
        ((even? b) (*. (double a) (halve b)))
        (else (+ a (*. a (- b 1))))))

Had a little time and got it done quicker than I expected. Problem 1.12 was to write a procedure to calculate elements of pascals triangle. I took that to mean calculate the value at position n of a given row. Take a look -

(define (pascal row n)
  (cond ((> n row) 0)
        ((or (= n 1) (= n row)) 1)
        (else (+ (pascal (- row 1) n) (pascal (- row 1) (- n 1))))))

As I said in a post earlier this week I’ve begun reading and working on the problems in SICP. I just read chapter 1 section 2.2 on tree recursion and completed problem 1.11 and plan to do 1.12 and 1.13. Problem 1.11 was creating recursive and iterative procedures to calculate the following function:

The recursive function was straight-forward:

(define (f n)
  (if (< n 3)
      n
      (+ (f (- n 1)) (* 2 (f (- n 2))) (* 3 (f (- n 3))))))

Writing the procedure as an iterative process wasn’t as trivial. I initially expected it would be easy and sat down to write the code without really thinking about the problem, but wrapping my head around how to maintain the state needed for 3 function calls didn’t compute. So I resorted to pencil and paper – I wrote out the iterations of the function for n=0 through n=5 and the solution became clear:

(define (f-iter a b c count n)
  (cond ((< n 3) n)
    ((= count n) c)
      (else (f-iter b c (+ c (* 2 b) (* 3 a)) (+ count 1) n))))
     
(define (f2 n)
  (f-iter 0 1 2 2 n))

As a quick comparison of run-time for the 2 procedures I ran them with the same n value (n=30). For f(30) (recursive) the procedure took approximately 16 seconds to finish. For f2(30) (iterative) the procedure finished in less than a second. I tried higher numbers but the recursive process just takes to long – I killed the process at 3 minutes when running it for n=35. I’ve run the iterative process with n up to 150 and it completes in less than 1 second.

This one was relatively straight forward.

(define (fib-iter last-one last-two total max)
  (if (or (> (+ last-one last-two) max) (= (+ last-one last-two) max))
      total
      (fib-iter (+ last-one last-two)
                last-one
                (if (= (modulo (+ last-one last-two) 2) 0)
                    (+ total last-one last-two)
                    total)
                max)))

(fib-iter 1 0 0 4000000)

Working my way through SICP has a goal I’ve had for a while but never seemed to get to.  However – this past week I started reading the book and working on the exercises and am looking forward to the challenge.  I skipped a couple of exercises in the first section but came up with the following to exercise 1.8:

(define (cube x)
  (* x x x))

(define (abs-val x)
  (cond ((> x 0) x)
    ((= x 0) 0)
    ((< x 0) (- x))))

(define (improve guess x)
  (/ (+ (/ x (* guess guess)) (* 2 guess)) 3))

(define (good-enough? guess x)
  (< (abs-val (- (cube guess) x)) 0.001))

(define (cube-root-iter guess x)
  (if (good-enough? guess x)
    guess
    (cube-root-iter (improve guess x) x)))

(define (cube-root x)
  (cube-root-iter 1.0 x))

Along with the exercises in SICP I plan to also apply my new found knowledge to some of the problems from Project Euler.  The solution I came up with for exercise 1 was probably overkill but it worked and should work for larger sets of numbers:

(define (calc-iter total count limit)
  (if (= count limit)
    total
    (calc-iter
        (+ (if (or (= (modulo count 3) 0) (= (modulo count 5) 0)) count 0) total)
        (+ count 1)
        limit)))

(define (calc x)
  (calc-iter 0 0 x))

(calc 1000)

I installed the latest MIT/GNU Scheme version and ran into an issue with a missing dependency.  When attempting to start scheme I would get the following message -

This ended up being an easy fix -

I ran into an issue last night where I changed the boot options for XP using MSCONFIG (foolishly) to enter safemode.  After doing this the computer would blue screen when booting and then attempt to boot back into safe mode.  I didn’t have a XP disc to enter recovery mode so I ended at google trying to find some sort of boot/recovery disc and found – ERD Commander from Micrsoft (30 day eval) – which has some great tools on it.  I ended up making an ERD boot disc and restored to a restore point to fix the BSOD issue.  After the restore I rebooted and found the computer booted correctly but I couldn’t log into the Admin account.  (This is a company laptop and the admins changed the admin password to something new – so I thought I was screwed.)  I tried booting the different boot options -  ‘Last known good configuration’, ‘Windows XP Normally’, etc. but no luck.

I tried resetting the admin password with the ‘locksmith’ utility in ERD but for whatever reason I couldn’t get it to work.  Back to Google – I tried to find a way to reset the admin password – and found plenty of tools to reset the account but none seemed to work.

At this point the system was booting fine so I didn’t care about getting into safe mode but I since I set the options in MSCONFIG (won’t do that again) I couldn’t get around them.  I tried running MSCONFIG when I booting using the ERD Commander boot disc but it didn’t work – I could get the app to run – but it wouldn’t save the changes.  Next I try running bootcfg from the command line – using this I can remove all options from the boot config except for /SAFEBOOT:MINIMAL – WTF?  So then I figure why not just edit the boot config by hand?  I don’t know why it took me so long to get to that point – I could have done that initially and saved myself a lot of time .  After booting using the ERD Commander CD – I went to the file explorer and navigated to the root (C:\) and changed the properties of boot.ini to writable (uncheck ‘Read-Only’).  I then edited to remove the /SAFEBOOT:MINIMAL switch, saved the file, and rebooted – back to Windows as normal.

All in all this was a pain in the ass (and a little embarrassing but I’m sharing it here so it wasn’t that bad).

I got into programming about a year before Future Crew released Panic in 1992 and absolutely loved it.  I thought it was the most amazing thing – the music was great, loved the mandelbrot set.  Anyway – I was browsing the Interweb and found a couple of sites worth checking out -

pouet.net – online demoscene resource 

pouet.net Future Crew Page

scene.org  

Also worth checking out is this demoscene documentary on youtube.

I’ve been playing with Chrome since I downloaded it yesterday and have a couple of observations -

Its fast – much faster to start than Firefox, Opera, or IE7 – and pages start loading quicker

As far as memory usage is concerned for 1 page (1 tab) Chrome uses less memory.  As you add tabs Chrome utilizes more memory per tab than Firefox, Opera, or IE7.  I assume this is a result of the tabs being contianed in their own process – for 7 tabs I had 10 Chrome processes running.  The overhead to create each process certainly contributes to the greater memory usage.  That said – as I use the other 3 browsers the memory usage creeps up significantly whereas Chrome’s memory usage creeps much more slowly.

Due to each tab running in its own independent process I was able to kill one of the processes without closing the other tabs.  I assume the same works when a process crashes due to a problem with a plugin, or some other error.  When the process does crash you’re tab will remain with the image below -

Chrome Error - Aw Snap!

I’m not sure how well flash is working – I’ve been to a couple of flash heavy sites that load with content missing but other sites have loaded flash content correctly.  I’m not sure if its flash related or something unrelated.  

There are very few plugins available for Chrome – even the Google toolbar isn’t available – but there are some and there does appear to be support for themes.  So far though its a nice piece of software – I’m not sure what it brings for the average user who gets similar or more functionality in IE or Firefox (or Opera).