Archive for the ‘notebook’ Category
Project Euler Problem 3 in Scheme
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)
SICP Section 1.2.4
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))))))
SICP Problem 1.12
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))))))
SICP Problem 1.11
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.
Project Euler Problem 2 in Scheme
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)
SICP and Project Euler
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)
MIT Scheme on Arch Linux Issue
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 -
Networking for Non-Network Engineers – Part 1
This post is a work in progress and will be expanded on in the future.
I work with developers, DBAs, etc. all the time who have no practical knowledge of computer networking. I’m going to try to shed a little light on the magic that happens behind the scenes. Initially this will be really basic but will become more technical.
A computer network can be broken up into two distinct pieces – the edge and the core. The network edge is made of things we are all familiar with – client PCs, servers, network attached storage, etc. The network core is what connects the systems on the edge to each other. The core is made up of routers, switches, hubs, etc.
Network Edge
Systems on the edge are sometimes referred to as hosts and hosts can be further broken down into clients and servers. Clients are typically desktop PCs, thin clients, IP enabled phones and servers are typically more powerful systems such as web & database servers. In general software terms – a client is a program running on one edge system that requests a service from a program running on another edge system. So – essentially one computer requests a service from another computer- AKA Client/Server architecture.