Transcript CS 101: Numbers and assignment

CS 101: Numerical Computing
Abhiram Ranade
Representing Integers
• “int x;” : reserves one cell in memory for x.
• One cell: “One word” has 32 capacitors.
Each capacitor can have High/Low charge.
• Storing positive numbers only: Represent
number to be stored in binary, and store
High charge for 1, Low charge for 0.
• How to store negative numbers?
Sign magnitude representation
• Key idea: One of the capacitors determines sign.
L = “+”, H= “-”
• “x = 5;” : store L LLLL...LHLH
• “x = -5;” : store H LLLL...LHLH
• Max positive number: L H...H = + 231-1
• Min negative number: H H...H = - 231-1
• 231 is almost = 2 * 109
• Actual representation is slightly different.
How to store larger numbers?
• Use Long integers: “ long x;”
Reserves 2 words, with one sign bit. Max
magnitude 263-1, about 1019
• Use floating point representation.
Floating Point Representation
• “float y;” : reserve 1 word = 32 bits as before.
• 24 bits : mantissa. 8 bits: exponent. Each
includes a sign bit.
• Mantissa can only store 23 bit accuracy, about 7
decimal digits.
• Exponent can be between -100 and +100 (about).
• “double z;” : 53 bits of mantissa, 11 bits exponent.
Summary
• Cohoon gives exact details. Not important
in this course. Various other formats, e.g.
“unsigned int”, “short”.
• Circuits are more complex for floating
representation, sign...
“God made natural numbers, the rest is the
work of man.” -- Leopold Kronecker.
Floating Point Arithmetic
•
•
•
•
float w, y=1.5, avogadro=6.023 E 23 ;
w = avogadro + y;
What is the value of w?
Exact value of w and avogadro will differ in
the 23rd digit.
“float” stores only 7 digits. 23rd digit
ignored. -- “roundoff error”.
w = avogadro!
Mixed Arithmetic
• C++ converts from float to int and vice
versa as needed.
• “int x=10; float y=6.5;”
• “x=y;” : 6.5 is rounded down. x=6.
• “360/x” : integer result is calculated.
• “360.0/x” : float result is calculated.
• “360/y” : float result. Try out yourself!
Simple Numerical Program
#include <turtlesim.h>
procedure turtleMain(){
float c;
cout << “Centigrade temperature:” << endl;
cin >> c;
cout << “Fahrenheit:” << (c*9/5)+32;
}
Remarks on Arithmetic
• Multiplication: write explicitly using “*”.
• *, / have higher precedence than +, • *, / have equal precedence, evaluated in left
to right order. Similarly +, • “x = m % n;” % : mod. m=10,n=4, x=2.
• Same precedence as *, /
• Use () to override default precedence.
Comments
• Programs are read by compilers, but also by
other programmers.
• You should include extra description
(“comment”) to help other programmers
figure out the logic:
• Style 1: “// ......” to end of line
• Style 2: “/* .... */” Examples soon.
Important Idea: Reassignment
int m=5;
m = 3*m + 1;
// Reassignment
• Mathematically absurd: “simplify” to
0 = 2*m+1
• C++ interpretation: Calculate the value of rhs,
then store it in lhs. Above: m = 16.
• Important inside loops. Next..
Reassignment in Loops
int i=1;
repeat(5){
forward(i); right(90);
forward(i); right(90);
i = i + 1;
}
• What will be drawn?
Nested Squares
How will you draw this pattern? Can you avoid
writing 7 calls to procedure Polygon?
Side length: 2, 4, 6, ...
Homework: draw this
Number of times to spiral: read from cin
Make pattern go around a polygon/circle

Common Programming pattern
“Repeat n times with i taking different values”
• Cleanly specified using for statement:
for( xxx; yyy; zzz ) { www } // next..
• Useful in numerical computing also
Spiral using for
int i;
for(i=1; i < 6; i=i+1){
forward(i); right(90);
forward(i); right(90);
}
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, for statement
execution ends.
2. Execute www. “loop body”
3. Execute zzz.
“loop increment”
4. Continue from 1.
Condition
• “ a op b” where op is <, >, <=, >=, ==, !=
• == : is equal to
• != : is not equal to
• Conditions can be combined:
– (a > 0) && (a <= 9) : true if a is a positive digit.
• && : conjunction. “and”
• || : disjunction. “or”
More examples of for
• for(j=10; j>0 ; j=j-1){ cout << j*j << endl; }
What is printed?
• for(int i=1; i < 100; i=i*2){ cout << i << endl; }
What is printed?
i can be defined inside for – then i cannot be accessed
outside of loop body ( {cout... } )
{ ... } is the scope of i.
And one more..
int i=0,num;
for( cin >> num; num > 1; num = num/2){ }
cout << i << endl;
num=num/2 : integer part of the quotient.
What is printed?
Computing ln x
• Must use arithmetic operations.
• Estimate the area under f(x) = 1/x from 1 to
x.
• Area approximated by small rectangles.
Riemann Integral
1
x
How many rectangles?
•
•
•
•
More the merrier! Say 1000.
Total width of rectangles = x - 1.
Width w of each = (x - 1)/1000
x coordinate of left side of ith rectangle
1 + (i-1)w.
• Height of ith rectangle = 1/(1+(i-1)w)
Program to compute ln
procedure turtleMain(){
float x, area=0, w;
cin >> x; w = (x-1)/1000.0;
for(int i=1 ; i <= 1000 ; i=i+1){
area = area + w*(1/(1+(i-1)*w);
}
cout << “ln(” << x << “)=” << area << endl;
}
Notes
• ith iteration adds area of ith rectangle to
“area”.
• It is customary to count starting at 0, so
there is a zeroth rectangle, first rectangle..
• height of (new) ith rectangle = 1+ iw
• i++ : short form for i=i+1
• area += q : short form for area = area + q
New program
procedure turtleMain(){
float x, area=0, w;
cin >> x; w = (x-1)/1000.0;
for(int i=0; i < 1000; i++)
area += w/(1+i*w);
cout << “ln(”<< x << “)=”<< area << endl;
}
Homework
• Write a program that prints a conversion table
from centigrade to Fahrenheit; for i = 1 to 100 it
should print equivalent value in Fahrenheit. Use
above procedure.
• Write a program that integrates f(x)=x. Check
how much error it makes by doing a direct
calculation.
• Write a program that computes xn given x and n.
• Write a program that computes n! given n.