Fibonacci Series - LISP(Scheme)

Fibonacci Series - LISP(Scheme)

Now in coding for different problems , you might have certainly found the problem to find nth  number in a fibonacci series... First of all what is a fibonacci series ? 

Well fibonacci series is a series starts with 0 and 1 then further series is evaluated as sum of two previous numbers i.e 0, 1, 1, 2, 3, 5, 8, 13, and so on... One can find good detail on fibonacci series at 

Fibonacci Series.

Now let us see how we might implement the above problem in lisp...

We want to be able to find nth number , so suppose we want to find 4th number in the series, how will we go about it... 

first of all we know that we need to find fibonacci at 4th and for finding Fibonacci number at 4th place we need to add Fibonacci number at 3rd and Fibonacci number at 2nd place, similarly for 3rd place fibonacci number we need to know The Fibonacci number at 2nd and 1st place and similarly for 2nd we need to know The Fibonacci number at 0th and 1st place which we know and so we can see a series being formed following the pattern fib(n) = fib(n-1) + fib(n-2) which looks like:

 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ...

So first of all we need to create a procedure taking n, and if we want value of fib 0 or fib 1, we should be able to return it, otherwise we need to calculate (fib n-1) + (fib n-2).

(define (fib n)(cond((= n 0) 0)
                                ((= n 1) 1)
                                (else(+ (fib (- n 1)) (fib (- n 2))))))

In the above code we simply start by stating the values of n = 0 and n = 1, other than those values we simply ask it to recursively compute two thing's
1. fib(- n 1)
2. fib(- n 2)
and add those up.


The above code will look like :
>(define (fib n)(cond((= n 0) 0)
                        ((= n 1) 1)
                        (else(+ (fib (- n 1)) (fib (- n 2))))))
in the interpreter.
Lets run the procedure we just created:
>(fib 5)
5

We can write the same program using an iterative approach which helps in a better memory management.

For Iterative approach we simply don't want to store much so we start from what we know and calculate what we don't know rather than keeping track of what we need to calculate...

(define fib-iter a b n)(cond ((= n 1) b)
                                           (else(fib-iter b (+ a b ) (- n 1)))))

a b are initially 0 & 1 respectively and n is the nth fibonacci term we wish to find.

Written By,

Sarvesh Bhatnagar

Block Structure for Cube-Root (Scheme)

Cube Root - LISP(Scheme)

Using Block Structure

Let us try the same we did for finding out cube root using block structure in LISP(Scheme dialect). 

First we should define some common functions which can be safely named globally such as cube:

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

Now let us start by defining cuberoot function:

(define (cuberoot guess x)

  (define (goodGuess)(<(abs (- (cube guess) x)) 0.001))

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

  (if(goodGuess) guess (cuberoot (improve) x)))

1. (define (cuberoot guess x)

in this step we simply define a block for cuberoot block ( main block ) and we know that we will require goodGuess procedure and an improve procedure both taking guess and x as a parameter but since both are already in lexical scope we can safely omit the parameters since we already know its value.

hence following (define (cuberoot guess x) we define goodGuess and improve : 

  (define (goodGuess)(<(abs (- (cube guess) x)) 0.001))

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

inside the main block.

Then we implement the actual cuberoot function by checking if the current guess is a good one, if it is a goodGuess then we simply output the guess else we improve it and call cuberoot again.

So now in interpreter , the function's will look like: 

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

>(define (cuberoot guess x)

  (define (goodGuess)(<(abs (- (cube guess) x)) 0.001))

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

  (if(goodGuess) guess (cuberoot (improve) x)))

Now let us test the made program by running it in interpreter, it will look like: 

>(cuberoot 1.0 8)

2.000004911675504

where 1.0 is the initial guess and 8 is the number of which we are interested to find cuberoot of.

Written By,

Sarvesh Bhatnagar

Block Structure (Square Root) - LISP

Block Structure - LISP

Now the style in which we have been coding until now , is a bit dangerous if we are talking about large and complex program as our coding style may lead to ambiguity between different programmer's function nomenclature. suppose one programmer name's  a function 'addup' which add's 2 numbers and then add's it with the multiplication of two numbers : (x + y) + (x * y) and suppose another function similarly names some other routine 'addup' which adds 2 numbers two times like (x + y) + (x + y) or 2* (x + y) now during execution , there may occur some ambiguity which may lead to unintended consequences , so we use block structures in which the not so common functions are defined inside the main function which we are using , like in previous square-root and cube-root example good enough?  and improve are not common functions so we can use the block structure as follows: 

First defining the common functions, square of a number and average of 2 numbers...

(define (square x)(* x x))

(define (average x y)(/ (+ x y) 2))

Now defining the square-root function in a block structure method : -

(define (sqr-root guess x)
    (define (good-guess)(<(abs(- (square guess) x)) 0.001))
    (define (improve)(average guess (/ x guess)))
    (if(good-guess) guess (sqr-root (improve) x)))

In above code, we first know that we need to pass the guess and the number of which we want the square root : so we started by:
(define (sqr-root guess x)

Now we know from original method that sqr-root function looks like this :
(define (sqr-root guess x)(if (good-guess guess x) guess (sqr-root (improve guess x) x))

So we know that we will require good-guess and an improve function ,  so we define good-guess function as:
(define (good-guess) (<(abs(-(square guess) x))0.001))

we didn't passed the parameters guess and x to the good-guess function as we are defining the good-guess function inside of sqr-root function so we don't need to pass the parameters since inside the function sqr-root we already know the value of guess and x.
similarly , we defined improve inside the sqr-root function as :

(define (improve) (average guess (/x guess)))

Now let us see how the program will look like in the terminal :

>(define (square x)(* x x))
>(define (average x y)(/ (+ x y) 2))
>(define (sqr-root guess x)
    (define (good-guess)(<(abs(- (square guess) x)) 0.001))
    (define (improve)(average guess (/ x guess)))
    (if(good-guess) guess (sqr-root (improve) x)))

Lets run the program and try the function sqr-root out:
>(sqr-root 1.0 4)
2.0000000929222947

Written By,

Sarvesh Bhatnagar