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

Bild: look again by corpus delicti from the Noun Project

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:

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

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.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.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:

$b_i$ : Zahl vor Komma
$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:

Beide Zahlen auf den selben Exponenten bringen
Binärzahlen addieren (wie schriftliche Addition)
Summe re-Normalisieren ($1.\ldots$)
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:

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

Algorithmus:

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

Algorithmus:

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

Algorithmus:

Beide Zahlen auf den selben Exponenten bringen
Binärzahlen addieren (wie schriftliche Addition)
Summe re-Normalisieren ($1.\ldots$)
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

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

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

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

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;
}

«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

1: Float Representation

Gegeben ein binäres Float-System:

$\beta = 2$ (binär)
$p = 4$ (präzision)
$e \in [-3;3]$ (Exponent range)

Schreibe das System in der Notation $F^* (b, p, e_{min} , e_{max} )$
Stelle ${3.1416}_{10}$ dar in diesem System
Wandelt eurer Resultat von 2. wieder in Dezimal und bestimmt den Fehler
${Berechnet 2.718}_{10} + 3.1416 10 + 0.11 10 {in diesem System}$

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

Pascal Schärli 15.03.2019

2: Point on Parabola ?

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

3: Rounding

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

Tipp:

Serie 1 Aufgabe 3

4: Binary Expansion

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:

Algorithmus:

$b_i \rightarrow$ Binärziffer

$x_i \rightarrow $ Dezimalzahl

Folgende Schritte wiederholen:

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

Pascal Schärli 15.03.2019

5: Fixing Functions

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