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

Square Root

Lisp - Square Root

Lets take a look at the program to find square root of a number by newtons method

It involves 2 main steps : 

1. Check if current guess is a good one

2. If 1 returns false, improve the guess by guess + (x/guess) / 2 and re-apply the method to find square root.

so some basic functions which we might require are:

Average:

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

Improve Guess:

(define (improveGuess guess x) ( average guess (/ x guess )))

goodGuess? :

(define (goodGuess? guess x) (< (abs (- (square guess) x)) 0.001))

Average: Takes in 2 arguments x and y , adds them and then divides the sum by 2

 

Improve Guess: does what is mentioned in step 2

goodGuess: Calculates | guess^2 - x | and checks if the magnitude is more than 0.001, if it is then the guess needs to be improved , else the guess is good. 0.001 is the amount of error which is acceptable in calculation of square root.

now let us define square root:

(define (sqrt guess x) ( if(goodGuess? guess x) guess (sqrt (improveGuess guess x) x)))

Let us see total program in interpreter

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

>(define (improveGuess guess x) ( average guess (/ x guess )))

>(define (goodGuess? guess x) (< (abs (- (square guess) x)) 0.001))

>(define (sqrt guess x) ( if(goodGuess? guess x) guess (sqrt (improveGuess guess x) x)))

Now let us use our defined function sqrt in action, Note that the initial guess value is required to be seeded, in this case we are initializing it as 1.0

>(sqrt 1.0 4)

2.0000000929222947

Simple Procedures - LISP

Simple Procedures - LISP (Scheme)

In this post we will see how to define some procedures and use them.

Square:

Square of a number is the number time's number itself. Lets see how we can define the procedure to find a square of a number.

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

yes its that simple, and can be read as: define square which takes 1 argument x, and returns x * x. 

Now suppose we want to find the square of 4, we would simple type the following in the interpreter:

>(square 4)

>16

Now lets try and define a procedure to find larger number from the two given numbers:

(define (findMax x y) (cond (( > x y) x) (else y)))

cond is for condition, and in front of the condition we are placing the conditions and if it evaluates to true then we simply give the output we desire for that condition and at the end if none of the preceding condition evaluates to true then we return the desired output for that scenario by placing an else before the output.

Similarly we can define another procedure which finds the minimum of the two numbers:

(define (findMin x y)(cond ((< x y)x)(else y)))

Now let us define another procedure which takes in 3 inputs and returns the summation of square of two large numbers:

(define (largeSquareSum x y z)(cond((and (> x y) (> z y)) (+ (square x) (square z)))((and (> y x) (> z x)) (+ (square y) (square z)))((and (> x z) (> y z)) (+ (square x) (square y)))))

The same program can be written in a more neat way as follows:

(define (largeSquareSum x y z)(cond((and (> x y) (> z y)) (+ (square x) (square z)))

                                                              ((and (> y x) (> z x)) (+ (square y) (square z)))

                                                              ((and (> x z) (> y z)) (+ (square x) (square y)))))

The above program follows a very simple logic, it checks if x,z pair are larger than y, or if y,z pair are larger than x or if x,y pair is larger than z and returns the sum of square of the pairs whichever is larger.

If we pass the following to the interpreter we will get :

>(largeSquareSum 1 2 3)

>13

Written By,

Sarvesh Bhatnagar

Arithmetic Operations - Lisp

Arithmetic Operations - Lisp

Any operation in lisp follows a prefix notation. i.e. Operator is placed before the operand's.

e.g. 

Addition: 

>(+ 4  5)

>9

The above operation is evaluated as 4 + 5

Subtraction:

>(- 10 4)

>6

The above operation is evaluated as 10 - 4

Division:

>(/ 20 10)

>2

The above operation is evaluated as 20 / 10

Multiplication:

>(* 2 3)

>6

The above operation is evaluated as 2 * 3

Similarly if we want to perform some complex nested operations such as ((2+4)*(5-2)) / (10 + 2) * 4

The same can be done as making an operation tree as:

                   /

      *                     *  

  +      -             +       4

2   4  5   2    10    2

Hence by looking at the nested tree, we know that in total division appears first, then we divide up the operations into two parts further we know in those two parts multiplication is needed to be performed between 2+4 & 5-2 and multiplication between 10 + 2 and 4 ... so our prefix notation leads to the following steps.

1.(/ (*)(*))

2.(/ (*(+)(-))(*(+) 4))

3.(/ (* (+ 2 4) (- 5 2)) (* (+ 10 2) 4))

Giving the equation obtained in 3 to the interpreter:

>(/ (* (+ 2 4) (- 5 2)) (* (+ 10 2) 4))

>3/8

hence the result of the operation is 3/8.

Written By, 

Sarvesh Bhatnagar

Lisp

Lisp

Lisp is a family of computer languages with a long history and a distinctive fully parenthesized prefix notation. Lisp is second oldest high level programming language in widespread use today, there are various dialects of lisp and we will mainly be focusing on the dialect known as scheme.

Scheme is a dialect of lisp supporting multiple programming paradigms, including functional programming paradigm and imperative programming paradigm. Scheme was developed at MIT AI LABS during 1970's.

The reference book we will be using for learning Scheme will be : Structure and Interpretation of Computer Programs.

The interpreter we will be using for Scheme is DrRacket.