Informatik I - Übung 4

Pascal Schärli

pascscha@student.ethz.ch

15.03.2019

Was gibts heute?

  • Nachbesprechung
  • Best-Of Vorlesung:
    • Floats
    • Funktionen
  • Vorbesprechung

Pascal Schärli 15.03.2019

Nachbesprechung

Pascal Schärli 15.03.2019

Pascal Schärli 15.03.2019

1. True or False?

  8 > 4  > 2  > 1
((8 > 4) > 2) > 1
( true   > 2) > 1
(   1    > 2) > 1
       false  > 1
         0    > 1
            false

Pascal Schärli 15.03.2019

2. True or False? (a ist int)

 2 < a  < 4
(2 < a) < 4
  true  < 4
   1    < 4
 false  < 4
   0    < 4
       true

Pascal Schärli 15.03.2019

Vergleich vs Zuweisung

Vergleich

==

Zuweisung

 =
  • Wird gebraucht um die Grösse zu vergleichen
  • Verändert die Variablen nicht
  • Wird gebraucht um Variablen neue Werte zuzuweisen
  • Der Wert vom rechten Operand wird im linken Operand gespeichert.
int a;
int b = 5;
a = b;
a = 7;
if(a==b){
    //...
}

Beispiel:

Beispiel:

Pascal Schärli 15.03.2019

Booleans

a == false || b == true)
!a || b

Pascal Schärli 15.03.2019

Layout Matters!

#include <iostream>

int main(){

    int n;
    std::cin >> n;

    for(int i = 0; i < n; i++){
        if(i % 2 == 0){
            std::cout << i / 2 << std::endl;
        }
        else{
            std::cout << i * 2 << std::endl;
        }
    }
    
    return 0;
}
#include <iostream>
int main(){
int n;
std::cin >> n; for(int i = 0; i < n; i++)
if(i % 2 == 0)

std::cout << i / 2 << std::endl;
	else

std::cout << i * 2 << std::endl;
return 0;}

Vorlesung

Pascal Schärli 15.03.2019

Warm-Up

Pascal Schärli 15.03.2019

Expression Dezimal Binär
a
b
a + b
4
7
11
0b100
0b111
0b1011

Floats als Binärzahlen

Pascal Schärli 15.03.2019

ab.cd => 2*a + 1*b + 1/2 * c + 1/4 * d
00.00 => 0
00.01 => 1/4
00.10 => 1/2
00.11 => 3/4
01.00 => 1
01.01 => 1 + 1/4
01.10 => 1 + 1/2
01.11 => 1 + 3/4
10.00 => 2
10.01 => 2 + 1/4
10.10 => 2 + 1/2
10.11 => 2 + 3/4
11.00 => 3
11.01 => 3 + 1/4
11.10 => 3 + 1/2
11.11 => 3 + 3/4

Floats als Binärzahlen

Pascal Schärli 15.03.2019

x_i
b_i
x - b_i
x_{i+1} = 2*(x-b_i)
1.9
1.2
0.4
0.8
1.6
1.8
1.6
1
1
0
0
1
1
1
1.2
1.2
0.4
0.8
1.6
1.8
1.6
0.9
0.2
0.4
0.8
0.6
0.8
0.6
1
.
1
1
1
1
0
0
1
1
1
1.9 \rightarrow

Floats als Binärzahlen

Pascal Schärli 15.03.2019

Warum kann man 0.1 als Binärzahl nicht endlich darstellen, aber als Dezimalzahl schon?

  • Um 0.1 oder \(\frac{1}{10}\) als endliche Zahl zu notieren, benötigt man die beiden Primzahlen 5 und 2 (weil \(10 = 5 * 2 \)).

 

  • Das Dezimale Zahlensystem ist genau auf diesen beiden Zahlen basiert, daher geht es.

 

  • Das Binäre Zahlensystem hat nur die Zahl 2, daher kann man sie damit nicht endlich darstellen.

Floats als Binärzahlen

Pascal Schärli 15.03.2019

Berechne die Binärdarstellung der folgenden Dezimalzahlen:

0.25
11.1
0.01
1011.00011

Algorithmus:

\(b_i \rightarrow\) Binärziffer

\(x_i \rightarrow \) Dezimalzahl

Zuerst binärzahl vor Komma normal ausrechnen.

Danach folgende Schritte wiederholen:

  1. \(b_i\) : Zahl vor Komma
  2. \(x_{i+1} = 2*(x_i - b_i)\)

FP - Systeme

Pascal Schärli 15.03.2019

F^* (b, p, e_{min} , e_{max} )
\pm b_0.b_1 b_2 \cdots b_{p-1} * b^e
b_i \in \{0, \ldots b-1\}\\
b_0 != 0
e \in \{e_{min}, e_{min} + 1, \ldots, e_{max}\}\\

\(p \rightarrow\) Anzah Ziffern

(Basis des Zahlensystems)

(Bereich für Exponent)

(Normalisiert)

Pascal Schärli 15.03.2019

Sind diese Zahlen sind im folgenden Zahlensystem enthalten: \(F^* (2, 4, -2 , 2 )\)?

1.000 * 2^1
1.001 * 2^-1
1.111 * 2^2
0.000 * 2^1
1.0001 * 2^-1
1.111 * 2^5

normalisiert \(\rightarrow \) Zahl startet nicht mit 0

zu viele Nachkommastellen

Exponent ist nicht zwischen \(-2\) und \(2\).

\pm b_0.b_1 b_2 \cdots b_{p-1} * b^e

FP - Systeme

Pascal Schärli 15.03.2019

Was sind die folgenden Zahlen in \(F^* (2, 4, -2 , 2 )\)?

die kleinste nicht-negative.
die grösste
die kleinste
 1.111 * 2^2 ->  7.5
-1.111 * 2^2 -> -7.5
1.000 * 2^-2 -> 0.25
\pm b_0.b_1 b_2 \cdots b_{p-1} * b^e

FP - Systeme

Pascal Schärli 15.03.2019

Wie kann man Zahlen in einem FP-System addieren?

 

  • Beide Zahlen auf den selben Exponenten bringen

 

  • Binärzahlen addieren (wie schriftliche Addition)

 

  • Summe re-Normalisieren (\(1.\ldots\))

 

  • Runden falls nötig

Rechnen in FP-Systemen

Pascal Schärli 15.03.2019

Rechnen in FP-Systemen

Algorithmus:

  1. Beide Zahlen auf den selben Exponenten bringen
  2. Binärzahlen addieren (wie schriftliche Addition)
  3. Summe re-Normalisieren (\(1.\ldots\))
  4. Runden falls nötig
1.001 * 2^-1 + 1.111 * 2^-2
    1.001  * 2^-1
 +  0.1111 * 2^-1
    1.001  * 2^-1
 +  0.1111 * 2^-1
 -----------------
 = 10.0001 * 2^-1
    1.001  * 2^-1
 +  0.1111 * 2^-1
 -----------------
 = 10.0001 * 2^-1
 
 = 1.00001 * 2^0
    1.001  * 2^-1
 +  0.1111 * 2^-1
 -----------------
 = 10.0001 * 2^-1
 
 = 1.00001 * 2^0
 
=> 1.000   * 2^0

Algorithmus:

  1. Beide Zahlen auf den selben Exponenten bringen
  2. Binärzahlen addieren (wie schriftliche Addition)
  3. Summe re-Normalisieren (\(1.\ldots\))
  4. Runden falls nötig

Algorithmus:

  1. Beide Zahlen auf den selben Exponenten bringen
  2. Binärzahlen addieren (wie schriftliche Addition)
  3. Summe re-Normalisieren (\(1.\ldots\))
  4. Runden falls nötig

Algorithmus:

  1. Beide Zahlen auf den selben Exponenten bringen
  2. Binärzahlen addieren (wie schriftliche Addition)
  3. Summe re-Normalisieren (\(1.\ldots\))
  4. Runden falls nötig

Algorithmus:

  1. Beide Zahlen auf den selben Exponenten bringen
  2. Binärzahlen addieren (wie schriftliche Addition)
  3. Summe re-Normalisieren (\(1.\ldots\))
  4. Runden falls nötig

\(\rightarrow\) Resultat: \(1\) (Exakt: \(1.03125\))

\(F^* (2, 4, -2 , 2 )\)

Pascal Schärli 15.03.2019

Unser eigener Float-Datentyp

Wir haben \(10\) Bits zur Verfügung. Wie können wir damit einen eigenen Fliesskomma-Datentyp erstellen?

Pascal Schärli 15.03.2019

Unser eigener Float-Datentyp

X

X

X

X

X

X

X

X

X

X

0

1

2

3

4

5

6

7

8

9

Zahl vor dem Komma

Nachkomma Stellen

Exponent

Versuch 1

Wir versuchen die Wissenschaftliche Notation (e.g. \(2.73\cdot 10^{12}\)) zu imitieren

Einige Zahlen in unserem Sytem:

  • grösste Zahl: \(1.11111\cdot 2^{15} = 64512\)
  • kleinste Zahl: \(0.00000 * 2^0 = 0\)
  • kleinste Positive Zahl: \(0.00000 * 2^0 = 0\)

Pascal Schärli 15.03.2019

Unser eigener Float-Datentyp

X

X

X

X

X

X

X

X

X

X

0

1

2

3

4

5

6

7

8

9

Vorzeichen

Nachkomma Stellen

Exponent

Versuch 2

Wir klassifizieren unser System als \(F^* (b, p, e_{min} , e_{max} )\) System. Da das erste Bit immer 1 ist, verwenden wir es als Vorzeichen.

Einige Zahlen in unserem Sytem:

  • grösste Zahl: \(1.11111\cdot 2^{15} = 64512\)
  • kleinste Zahl: \(-1.11111 * 2^{15} = -64512\)
  • kleinste Positive Zahl: \(1.00000 * 2^0 = 1\)

Pascal Schärli 15.03.2019

Unser eigener Float-Datentyp

X

X

X

X

X

X

X

X

X

X

0

1

2

3

4

5

6

7

8

9

Vorzeichen

Nachkomma Stellen

Exponent

Versuch 3

Um Fliesskommazahlen zu Erhalten müssen wir negative Nachkommazahlen haben. Wir ziehen daher dem Exponent jeweils 8 ab.

Einige Zahlen in unserem Sytem:

  • grösste Zahl: \(1.11111\cdot 2^{7} = 252\)
  • kleinste Zahl: \(-1.11111 * 2^{7} = -252\)
  • kleinste Positive Zahl: \(1.00000 * 2^{-8} = 0.00390625\)

Pascal Schärli 15.03.2019

Unser eigener Float-Datentyp

X

X

X

X

X

X

X

X

X

X

0

1

2

3

4

5

6

7

8

9

Vorzeichen

Nachkomma Stellen

Exponent

Versuch 4

Es gibt keine 0 in unserem System! Wir definieren also, dass wir beim Exponent \(-8\) eine Spezielle Zahl haben.

Einige Zahlen in unserem Sytem:

  • grösste Zahl: \(\infty\)
  • kleinste Zahl: \(-\infty\)
  • kleinste Positive Zahl: \(0\)

Bits 1-5:

  • \(0000 \rightarrow 0\)
  • \(0001 \rightarrow +\infty\)
  • \(0010 \rightarrow -\infty\)
  • \(0011 \rightarrow \) NaN

Pascal Schärli 15.03.2019

Floats: Guidelines

float a = 0.2f;
if (10*a == 2.0f){
	std::cout << "Equal" << std::endl;
}
else{
	std::cout << "Not Equal" << std::endl;	
}
Not Equal

«Prüft nie ob zwei Fliesskommazahlen gleich sind, wenn mindestens eine vorher gerundet wurde!»

Pascal Schärli 15.03.2019

Floats: Guidelines

float a = 67108864.0f + 1.0f;
if (a > 67108864.0f){
	std::cout << "Greater" << std::endl;
}
else{
	std::cout << "Not Greater" << std::endl;
}
Not Greater

«Vermeidet die Addition von Zahlen mit extremen Unterschieden in der Grösse

 

(Rundungsfehler)

   67108864 = 
         +1 = 
   67108864 = 1.000000000000000000000000   * 2^26
         +1 = 0.00000000000000000000000001 * 2^26
   67108864 = 1.000000000000000000000000   * 2^26
         +1 = 0.00000000000000000000000001 * 2^26
  -----------------------------------------------
 = 67108865 = 1.00000000000000000000000001 * 2^26
   67108864 = 1.000000000000000000000000   * 2^26
         +1 = 0.00000000000000000000000001 * 2^26
  -----------------------------------------------
 = 67108865 = 1.00000000000000000000000001 * 2^26
=> 67108864 = 1.000000000000000000000000   * 2^26

Pascal Schärli 15.03.2019

Floats: Guidelines

float a = .2f;
for(int i = 0; i < 20; i++){
    a = 6*a - 1;
    std::cout << a << std::endl;
}
0.2
0.2
0.200002
0.20001
0.200062
0.200371
0.202225
0.213348
0.28009
0.680542
3.08325

«Vermeidet die Subtraktion von Zahlen mit ähnlicher Grösse»

 

(Rundungsfehler)

Pascal Schärli 15.03.2019

Funktionen

Schreibe ein Programm, welches für drei Zaheln a, b und c die Summe a! + b! + c! zurückgibt.

 

  • Wir müssen drei mal den selben Code kopieren um die Fakultät zu berechnen
unsigned int a,b,c;
std::cin >> a >> b >> c;

unsigned int a_fact = 1;
for(int i = 1; i <= a; i++){
	a_fact *= i;
}

unsigned int b_fact = 1;
for(int i = 1; i <= b; i++){
	b_fact *= i;
}

unsigned int c_fact = 1;
for(int i = 1; i <= c; i++){
	c_fact *= i;
}

std::cout << a_fact + b_fact + c_fact << std::endl;

Pascal Schärli 15.03.2019

Funktionen

Wie können wir verhindern, immer wieder den selben Code zu kopieren?

 

  • Wir können die Fakultät in eine "Funktion" packen, so dass wir den Algorithmus nur einmal schreiben müssen.
#include <iostream>

unsigned int fact(unsigned int n){
    unsigned int out = 1;
    for(int i = 0; i < n; i++){
	out *= i;
    }
    return out;
}


int main(){
    unsigned int a,b,c;
    std::cin >> a >> b >> c;
    
    std::cout << fact(a) + fact(b) + fact(c) << std::endl;
    return 0;
}

Pascal Schärli 15.03.2019

Funktionen

Eine Funktion hat die folgenden Komponenten:

int foo(int a, float b, bool c){
    if(c){
        a += b;
    }
    else{
        a-=b;
    }
    return a;
}

Datentyp vom Rückgabewert

Name der Funktion

Beliebig viele Übergabewerte

Funktions-Körper (Berechnung)

Rückgabe des Resultats

Pascal Schärli 15.03.2019

Funktionen

isPrime(n);{
    for(unsigned int i == 2; i < n/2, i+1){
        if(n % i = 0){
    	    return false
    	}
    }

}
bool isPrime(unsigned int n){
    for(unsigned int i = 2; i <= n/2; i++){
    	if(n % i == 0){
    		return false;
    	}
    }
    return true;
}

Findet die 10 Fehler!

Pascal Schärli 15.03.2019

Funktionen



bool inInterval(double x, double left, double right){
	return x >= left && x <= right;
}

Precondition:

  • Was muss bei Funktionsaufruf gelten?
  • Spezifiziert Definitionsbereich der Funktion.

 

//PRE:  left <= right
//POST: returns true iff x is in the Interval [left, right]
bool inInterval(double x, double left, double right){
	return x >= left && x <= right;
}

Postcondition:

  • Was gilt nach Funktionsaufruf?
  • Spezifiziert Wert und Effekt des Funktionsaufrufes.

Vorbesprechung

Pascal Schärli 15.03.2019

Pascal Schärli 15.03.2019

Gegeben ein binäres Float-System:

  • \(\beta = 2\) (binär)
  • \(p = 4\) (präzision)
  • \(e \in [-3;3]\) (Exponent range)
  1. Schreibe das System in der Notation \(F^* (b, p, e_{min} , e_{max} )\)
  2. Stelle 3.141610, 2.71810, 710 und 0.1110 dar in diesem System
  3. Wandelt eurer Resultat von 2. wieder in Dezimal und bestimmt den Fehler
  4. Berechnet 2.71810+3.141610+0.1110 in diesem System

 

Tipp:
Normalisiert \(\rightarrow\) Zahl vor Komma darf nicht 0 sein!

Pascal Schärli 15.03.2019

Schreibt ein Programm, welches bestimmt ob ein Punkt \((x, y)\) auf der Parabel \(g(x) = 0.9 \cdot x^2 + 1.3 \cdot x - 0.7\) liegt

Tipps:

  • Direkter Vergleich wird nicht funktionieren (Guidlines)
  • Baut eine Fehlertoleranz ein
a == b \rightarrow |a - b| \lt \epsilon

Pascal Schärli 15.03.2019

Schreibt eine Funktion, welche einen double auf den nächsten Integer runden kann.

Schreibt ein Programm, welches ein x mit \(0 \le x \le 2 \) als Binärzahl im folgenden Format schreiben kann: \(b_0.b_1b_2b_3...b_{15}\)

Tipp:

Wendet diesen Algorithmus an:

Pascal Schärli 15.03.2019

Pascal Schärli 15.03.2019

bool is_even (unsigned int i) {
    if (i % 2 == 0) return true;
}
double invert (double x) {
    double result;
    if (x != 0)
        result = 1 / x;
    return result;
}

Behebe alle Probleme welche diese Funktionen haben und füge passende pre- und post conditions.

Tipp:

  • Spielt selbst ein paar Eingabewerte durch und schaut was zurückkommt.

Program of the Week

Pascal Schärli 15.03.2019

Viel Spass!

Pascal Schärli 15.03.2019