Exponent (LISP - Scheme)

Exponent - Lisp

In this post we will discuss how to make a normal program using which we can calculate exponent of the given numbers. i.e. 2^3 or 52^40 etc. I mean google it and you won't get a precise answer for 52^40 but using lisp you can get a more accurate answer. So lets get started...

So basic approach to calculate b^n is multiply b n times. So if you have followed my previous posts you might know how to proceed further as its very similar to the methods we used earlier to solve the problems. 

So the function for exponent is like : 

Firstly we will start by defining the function which will take in 2 arguments b & n.

(define (expo b n)

After that we want to multiply b n times and till n becomes 0 and when that happens we will then return 1 i.e. b^0 = 1. So the code will do something like b*(b^(n-1)) till n-1 = = 0.

So in further code its like this :

(cond ((= n 0) 1)
           (else (* b (expo b (- n 1))))))

Written By,

Sarvesh Bhatnagar

Reverse of a number - LISP(SCHEME)

Reverse of a number - LISP(Scheme)

Reverse of a given number involves 2 main task , 

1. Finding what the last digit is
2. Finding the remains number aside from last digit

If we solve these tasks then we can easily find the reverse of a given number by simply recursively finding the last digit and trimming the original number. 

Aside from this , there is one other problem which we might face which is : the problem of storing the last digit obtained... We can solve that by the following method:

1. Intitalize a variable temp which will hold the reversed number with 0.
2. perform temp = (temp * 10 ) + last digit.

we initialise temp = 0 only once whereas 2nd step is done at every step, in second step we are actually creating a space for last digit by multiplying it with 10, after which we can simply add the last digit to it.

Now the code for finding out reverse of a given number can be written as :

Now, we basically solve the first problem of finding last digit by using modulo operator...
i.e (modulo number 10) , we solve the second problem by finding the quotient of the number, So our code turns out as keep finding the reverse until the original number becomes 0 , and when that happens return the reversed number.

Written By,

Sarvesh Bhatnagar

Factorial - LISP(Scheme)

A Program for finding factorial using Scheme

Factorials n or n! is defined as product of all positive integers upto n.  Simply n! 

for example : 

5! = 5 * 4 * 3 * 2 * 1

Now there are two ways to calculate factorials, one is if we go in a backward direction i.e  in a decremental manner in which we recursively multiply the factorial(n-1) with n or we can go in an incremental manner in which we start from one and progress towards n i.e. 1 * 2 * 3 * ... * n-1 * n.

Aside from that , another condition which we need to know is 0! = 1.

In this post we will look how to implement the same in scheme.

When going in backward direction our scheme code will look like :

(define (fact n)(cond ((= n 1) 1)

                                   ((= n 0) 1)

                                   (else (* n (fact (- n 1))))))

In the above code we simply handle the possible edge cases first and continue until we reach the edge case. i.e. n == 1 or n == 0

Similarly we can define for an incremental iterative approach as : 

(define (fact n t)(cond((> n 0) (fact (- n 1) (* t n)))
                                     ( else t)))

Benefit of the incremental iterative approach is that if we know the state values, we can start directly from that particular state for example :
2nd state of 5! is :  t = 5 , n = 4
3rd state of 5! is :   t = 20 , n = 3
and so on...

Written By,

Sarvesh Bhatnagar

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

Cube Root - LISP

Cube Root - LISP(Scheme)

Let us program similarly for finding the cube root of which just 1 thing changes. i.e, how the next improve guess is defined i.e: if we make a guess, g then the improved guess would be 

g' = (x/(y^2) + 2y)/3

So , we will mainly have to make changes in improve which would look as:

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

Now our other functions are similar, just in checking of good guess we need to check the difference between the cube of the guess and x instead of square of the guess and x. Hence the procedure goodGuess changes to:

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

Now we need to define something else, instead of the function square, i.e: cube. 

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

Now let us define the main function cuberoot, its much similar to square root function we defined earlier. 

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

Now our total code will look in interpreter like: 

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

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

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

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

Now let us see the code in action , 

>(cuberoot 1.0 8)

2.000004911675504

Written By,

Sarvesh Bhatnagar