Transcript On Hemachandra Numbers

Two-week ISTE workshop on
Effective teaching/learning of computer
programming
Dr Deepak B Phatak
Subrao Nilekani Chair Professor
Department of CSE, Kanwal Rekhi Building
IIT Bombay
Lecture 3, Fundamental programming concepts
(Iterative algorithms)
Tuesday 29 June 2010
OVERVIEW
 Need for repetitive execution of instructions
• Problem of finding maximum of given numbers
 Instructions for specifying iteration
• with ‘for’
• With ‘While’
 Problem of estimating value of log x
 General problem of finding roots of a polynomial
Revisiting problem to find Maximum
 We saw that if we have to find maximum of 5 numbers we
could write:
int a, b, c, d, e, max;
cin >>a >>b >>c >>d >e ;
max = a;
if (b > max) {max = b};
if (c > max) {max = c};
if (d > max) {max = d};
if (e > max) {max = e};
cout<<“Max is”<< max << "\n";
 What do we do if the number of numbers is very large
A possible strategy
 We notice a repetitive pattern in our program, which is
if (number > max) { max = number}
 If we could execute this instruction repeatedly, every time
with a different value of number, we will get the desired
result. To ensure that this comparison is made with a new
value every time, we consider repeating a modifying pattern
cin >> number;
if (number > max) { max = number}
Further analysis of the repetitive
strategy
 If we repeat this block five times, we will find the maximum
of five numbers. But we need an initial value for max.
 If we assume all the given numbers are positive, then we
could assign an arbitrary negative initial value to max
 Expanding our strategy in words,
we wish to say something like:
max = -999;
// repeat the following block 5 times
{cin >> number;
if (number > max) { max = number}
}
Repetitive execution
 We need some kind of a ‘counting mechanism’ which will
add 1 to the count every time we execute the block, and will
stop repeated execution of the block once the count reaches
5
 The ‘ for’ instruction provides such mechanism
max = -999;
for (count =1, count <=5; count ++)
{cin >> number;
if (number > max) { max = number}
}
Repetitive execution
 The artificial initial value for max in not a good idea (What if
we are given negative numbers also).
 A better thing would be to read the first given number
separately, assign it to max, and then repeat the block only
4 times
cin >> number;
max = number;
for (count =1, count <=4; count ++)
{cin >> number;
if (number > max) { max = number}
}
Finding maximum of N given numbers
// Program 4 (prog4.cpp)
#include <iostream>
using namespace std;
// To find maximum of N given numbers
int main() {
int count, number, N, max; cin >> N;
cin >> number; max = number;
for (count =1, count <=N-1; count ++){
cin >> number;
if (number > max) { max = number}
}
}
General format and semantics of the ‘for’
statement
for( xxx; yyy; zzz ) {
www;
}
0. Execute “xxx;”. Must be an assignment statement.
“loop initialization”
1. Evaluate condition yyy. “loop test”. If true, continue with
step 2; if false, execution of ‘for’ statement ends.
2. Execute www. “loop body”
3. Execute zzz.
“loop increment”
4. Go back and repeat from 1.
Sum of N natural numbers
---int main(){
int i, N, Sum = 0;
cin >> N
for(i=1; i < N; i=i+1){
sum = sum + i;
}
cout << “Sum of” << N < “numbers is”;
cout << sum << “\n”;
return 0;
}
Computing Natural Logarithm
 Natural Logarithm of a number a is defined as
a
1/ x dx
1
 A computer cannot integrate
• Must use arithmetic operations.
 Estimate area under the curve f(x) = 1/x from 1 to a.
 Area approximated by small rectangles.
Riemann Integral
calculate Sum of areas of all
rectangles between 1 and a.
1
a
Riemann Integral using n rectangles
Width w of i th Rectangle (same for all rectangles)
w = (a-1)/n)
1
a
Riemann Integral using n rectangles
x coordinate of i th Rectangle
x = 1 + (i-1)w
1
a
Riemann Integral using n rectangles
Height h of i th Rectangle
h=1/x
= 1/(1 + (i-1)w)
1
a
How many rectangles?




More the merrier! Say 1000.
Total width of rectangles = a - 1.
Width w of each rectangle= (a - 1)/1000
x coordinate of left side of ith rectangle
x = 1 + (i-1)w.
 Height of ith rectangle
1/x = 1/(1+(i-1)w)
Program to compute logarithm of a
given value
int main(){
int i;
float x, area=0, w;
cin >> x;
w = (x-1)/1000.0;
for(i=1; i <= 1000; i=i+1){
area = area + w*(1/(1+(i-1)*w));
}
cout << “Log of ” << x << “is ” << area;
return 0;
}
Factorial of a number
int nfactorial, n, i;
cin >> n;
nfactorial = 1;
for (i =1; i <= n, i++){
nfactorial = nfactorial * i;
};
cout << nfactorial;
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
....
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
l l
l s s l s l s s s l
ya shubh r vas tra vru ta
l l
s l
l s s
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
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|
= |7 beat patterns| + |6 beat patterns|
Algebraically..
 Hn = number of patterns with n beats
H8 = H7 + H6
In general Hn = Hn-1 + Hn-2
 Does this help us to compute H8?
We need to know H7, H6, for which we need H5, ...
Algorithm Idea








H1 = number of patterns with 1 beat = 1 {S}
H2 = Number with 2 beats = 2 {SS, L}
H3 = H2 + H1 = 2 + 1 = 3 {SSS, SL, LS}
H4 = H3 + H2 = 3 + 2 = 5
H5 = H4 + H3 = 5 + 3 = 8
H6 = H5 + H4 = 8 + 5 = 13
H7 = H6 + H5 = 13 + 8 = 21
H8 = H7 + H6 = 21 + 13 = 34 ...
Program to compute Hn
int n;
cin >> n; // which number to compute
int hprev = 1, hcurrent = 2, hnext;
For (int i=3; i <= n; i++){
hnext = hprev + hcurrent;
// prepare for next iteration
hprev = hcurrent;
hcurrent = hnext;
}
cout << hnext;
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.
Newton Raphson method
 Method to find the root of f(x),
i.e. x such that f(x)=0.
 Method works if:
• f(x) and f '(x) can be easily calculated.
• and a good initial guess is available.
 Example: To find square root of k.
• use f(x) = x2 - k. f’ (x) = 2x.
• f(x), f’ (x) can be calculated easily.
• only 2 or 3 arithmetic operations needed
• Initial guess x0 = 1 always works! can be proved.
How to get better xi+1 given xi
Point A =(xi,0) known.
B
Point B=(xi,f(xi)) is known
Calculate f(xi ).
Approximate f by tangent
C= intercept on x axis
C=(xi+1,0)
f(x)
C
A
xi+1
xi
f’ (xi) = AB/AC = f(xi)/(xi - xi+1)  xi+1 = (xi- f(xi)/f’ (xi))
Square root of k
 xi+1 = (xi- f(xi)/f’ (xi))
 f(x) = x2 - k,
f’ (x) = 2x
 xi+1 = xi - (xi2 - k)/(2xi) = (xi + k/xi)/2
 Starting with x0=1, we compute x1, then x2, then...
 We can get as close to sqrt(k) as required.
Program segment
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;
}
cout << xi;
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;
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;
While statement
while (condition)
{ loop body};
 check condition, if true then execute loop body. 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.
for and 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.
THANK YOU