•Hemachandra Numbers

CS 101

Computer Programming and Utilization

Dr Deepak B Phatak

Subrao Nilekani Chair Professor

Department of CSE, Kanwal Rekhi Building IIT Bombay

Lecture 5, More Numerical computing

IIT BOMBAY

IIT BOMBAY

Overview

• Review of CPP Dumbo

• Iterative Numerical computations

•Factorial of a given integer

•Hemachandra Numbers

•Finding roots of an equation

• Course and Lab organization

IIT BOMBAY

C++ program structure

#include <iostream>

using namespace std;

int main(){

---

--- statements/instructions;

---

return(0);

}

• We will learn later what each of these lines

IIT BOMBAY

C++ Data types

• We have seen numerical and string data 7.45, 12.3E-12, “Ranade”, “\n”,

• Constant values are written like this by us C++ stores these in an internal format

• Numerical values have an associated type int, long, float, double

• Memory location names, called variables, must be predefined with associated data type

IIT BOMBAY

C++ statements

• Each instruction of our program can ordinarily convey any one of the 3 actions

•Assignment, input, output

• Assignement

sum = a + b;

area = (x-1.0)*(1/(x-1.0);

m = m + x/2.5

•The last one is to be seen as

“reassignment”

IIT BOMBAY

C++ statements ...

• “increment” is special form of reassignment count = count + 1;

or count += 1;

or, more simply, ++count or count++

• Input

cin >> x >> maxvalue;

• Output

cout << “Value of y is “ << y << “\n”;

IIT BOMBAY

Conditional execution

• Program instructions are normally executed in the given sequence

• C++ can examine conditions, and based on the result, can execute conditions out of sequence if (condition)

{ statement group 1};

else

{ statement group 2};

IIT BOMBAY

Conditional execution ...

• Based on the age of a passenger, the ticket cost is different. Let us say, it is Rs 25.50 for an adult, and Rs 12.75 for a child (< 12 Years)

cin >> age;

ticket = 12.75;

ticket = 25.50;

cout << “Rs. “ << ticket << endl;

IIT BOMBAY

Conditional execution ...

• Suppose we alter the sequence of assigning a value to ticket

cin >> age;

ticket = 25.50;

ticket = 12.75;

cout << “Rs. “ << ticket << endl;

• The assignment to variable ticket will always be the last assigned value

irrespective of age!

IIT BOMBAY

Conditional execution …

• Use of the if – else statements will permit us to correctly evaluate the ticket

cin >> age;

if (age > 12)

{ticket = 25.50};

else

{ticket = 12.75};

cout << “Rs. “ << ticket << endl;

• What if elders are charged Rs 20?

IIT BOMBAY

If – else if ladder

cin >> age;

if (age > 60){

ticket = 20.00;}

else if (age > 12){

ticket = 25.50;}

else {

ticket = 12.75;}

cout << “Rs. “ << ticket << endl;

IIT BOMBAY

Repetitive actions

int nfactorial, n, i cin >> n

nafactorial = 1;

for (i =1; i <= n, i++){

nfactorial = nfactorial * i;

};

cout << “factorial ” << n << “ is ” << nfactorial;

IIT BOMBAY

Complete program for n!

#include <iostream>

using namespace std;

int main() {

int nfactorial, n, i;

cout << “ Give value of n” << endl;

cin >> n;

IIT BOMBAY

Complete program for n! …

nafactorial = 1;

for (i =1; i <= n, i++){

nfactorial = nfactorial * i;

};

cout <<“factorial ”<<n<< “is ”<<nfactorial<< endl;

Return(0);

}

IIT BOMBAY

Hemachandra’s Problem (12th century AD) Suppose I have to build a wall of length 8

feet. I have bricks 2 feet long and also 1 foot long. In how many ways I can lay the bricks so that I fill the 8 feet?

Possibilities:

2,2,2,2;

1,1,1,1,1,1,1,1;

2,2,2,1,1 ....

IIT BOMBAY

Hemachandra’s Actual Problem

Suppose I am designing a poetic meter with 8 beats. The meter is made of short syllables and long syllables.

Short syllable (s) = 1 beat, Long syllable (l) = 2 beats.

How many ways are there of filling 8 beats?

Example of a poetic meter

ya kun den du tu sha r ha r dha va la ya shubh r vas tra vru ta l l l s s l s l s s s l l l s l l s s

IIT BOMBAY

Hemachandra’s Solution

“By the method of Pingala, it is enough to observe that the last beat is long or short”

Pingala: mathematician/poet from 500 A.D.

Hemachandra is giving credit to someone who lived hundreds of years before him!!

Copy if necessary and if permitted, but always give credit

IIT BOMBAY

Hemachandra’s solution contd.

S : Class of 8 beat patterns with short last beat.

L : Class of 8 beat patterns with long last beat.

Each 8 beat pattern is in class L or class S

S = all 7 beat patterns + short beat appended.

L = all 6 beat patterns + long beat appended

| class S | = Number of patterns with 7 beats

| class L | = Number of patterns with 6 beats

|8 beat patterns| = |class S| + |class L|

IIT BOMBAY

Algebraically..

H_n = number of patterns with n beats H₈ = H₇ + H₆

In general H_n = H_n-1 + H_n-2

Does this help us to compute H₈?

We need to know H₇, H₆, for which we need H₅, ...

IIT BOMBAY

Algorithm Idea

H₁ = number of patterns with 1 beat = 1 {S}

H₂ = Number with 2 beats = 2 {SS, L}

H₃ = H₂ + H₁ = 2 + 1 = 3 {SSS, SL, LS}

H₄ = H₃ + H₂ = 3 + 2 = 5 H₅ = H₄ + H₃ = 5 + 3 = 8 H₆ = H₅ + H₄ = 8 + 5 = 13

H₇ = H₆ + H₅ = 13 + 8 = 21 H₈ = H₇ + H₆ = 21 + 13 = 34 ...

IIT BOMBAY

Program to compute H_n

int n; cin >> n; // which number to compute int hprev = 1, hcurrent = 2;

for(int i=3; i <= n; i++){

hnext = hprev + hcurrent;

// prepare for next iteration hprev = hcurrent;

hcurrent = hnext; } cout << hnext;

IIT BOMBAY

Code is tricky!

Need a comment:

/* At the begining of an iteration

hcurrent = H_i-1 write ith term if you like.

hprev = H_i-2

where i is the value of variable i */

Can you prove this?

Will mathematical induction help?

Proving this is enough

-- hnext = hprev + hcurrent –

hence correct answer will be generated.

IIT BOMBAY

Proof by induction

Base case: At the beginning of the first iteration is this true? Yes, i will have value 3, and hprev = 1 = H₁, hcurrent = 2 = H₂

Suppose it is true at some later iteration, when i has value v >= 3. By induction hypothesis, hprev and hcurrent have values H_v-1, H_v-2 respectively

The first statement hnext = hprev + hcurrent makes hnext = H_v-1 + H_v-2 = H_v. After this the statement hprev = hcurrent makes hprev = H_v-1. The next statement hcurrent = hnext makes hcurrent=H_v. In the next iteration i will have value v+1. But

hprev,hcurrent will have exactly the right values!

IIT BOMBAY

On Hemachandra Numbers Mathematics from poetry!

Series is very interesting.

- Number of petals in many flowers.

- Ratio of consecutive terms tends to a limit.

What are these numbers more commonly known as?

Fibonacci numbers!!

Hemachandra lived before Fibonacci.

IIT BOMBAY

Newton Raphson method

Method to find the root of f(x), i.e. x s.t. f(x)=0.

Method works if:

f(x) and f '(x) can be easily calculated.

A good initial guess is available.

Example: To find square root of k.

use f(x) = x² - k. f’ (x) = 2x.

f(x), f’ (x) can be calculated easily.

2,3 arithmetic operations

IIT BOMBAY

How to get better x_i+1 given x_i

f(x)

x_i x_i+1

Point A =(x_i,0) known.

A B

C

Calculate f(x_i ).

Point B=(x_i,f(x_i)) known Approximate f by tangent C= intercept on x axis C=(x_i+1,0)

IIT BOMBAY

Square root of k

x_i+1 = (x_i- f(x_i)/f’ (x_i))

f(x) = x² - k, f’ (x) = 2x

x_i+1 = x_i - (x_i² - k)/(2x_i) = (x_i + k/x_i)/2

Starting with x₀=1, we compute x₁, then x₂, then...

We can get as close to sqrt(k) as required.

Proof not part of the course.

IIT BOMBAY

Code

float k;

cin >> k;

float xi=1; // Initial guess. Known to work.

for(int i=0; i < 10; i++){

// 10 iterations xi = (xi + k/xi)/2;

}

IIT BOMBAY

Another way

float xi, k; cin >> k;

for( xi = 1 ;

// Initial guess. Known to work.

xi*xi – k > 0.001 || k - xi*xi > 0.001 ;

// until error in the square is at most 0.001 xi = (xi + k/xi)/2);

cout << xi;

IIT BOMBAY

Yet Another way

float k; cin >> k;

float xi=1;

while(xi*xi – k > 0.001 || k - xi*xi > 0.001){

xi = (xi + k/xi)/2 ; }

cout << xi;

}

IIT BOMBAY

While statement

while (condition) { loop body}

check condition, then execute loop body if true.

Repeat.

If loop body is a single statement, then need not use { }. Always putting braces is recommended;

if you insert a statement, you may forget to put them, so do it at the beginning.

True for other statements also: for/repeat/if.

IIT BOMBAY

For vs. while

If there is a “control” variable with initial value, update rule, and whose value distinctly defines each loop iteration, use for.

If loop executes fixed number of times, use for.

IIT BOMBAY

Homework

Write a program to calculate the cube root using Newton Raphson method.

Check how many iterations are needed to get good answers. Should be very few.

IIT BOMBAY

evaluation approach for CS101 Quizzes 10%

Assignments 10%

Course Project 30%

Mid-semester exam 20%

End Semester Exam 30%

Minimum passing grade (DD) at >= 40% marks

IIT BOMBAY

Consulting support

Monday 13:30 to 17:30 Tuesday 13:30 to 17:30

TAs will be available to help you with

your queries regarding lectures/labs and with programming problems

Additional hours for lab access on both these days

//possibly also Thursday 13:30 to 17:30 // will be announced tomorrow