Overview MOSIM

Created by Ameyah Official

overview to the lectures on Modulation and Simulation

#Scientific computing, #computer arithmetics, #floating points

Whitehead

Prop b the deformation is trivial

ifdeformation

formal def

trivial deformation

g ss

BA

Formal Jacobi

Gerstenhaber Alg

Prop a ifdeform. the \zeta are cocycles in H(g,g)

find zetas

Gerstenhaber Prod

zetas in C(g,g)

def \delta

zetas are cocyclesZ(g,g)

cohomology group H(g,g)

zetas are coboundaries --> B(g,g))

Korrektur

Auf der 2. Tafel mit der Berechnung der Gewichte ist mir
beim Gewicht c_{2,2} ein eigentlich auffälliger Schreibfehlerunterlaufen, da der an der Tafel angegebene Wert 64/65 erstens
nicht > 1 ist, zweitens nicht das Produkt von 15 und 3 als
Nenner enthält und drittens nach der allgemeinen Formel für c_{m,m} größer als c_{1,1} = 4/3 sein müsste.

Kurzum: Der richtige Wert ist natürlich c_{2,2} = 64/45 .

Nur so ergibt auch die Summe der Gewichte c_{2,i} den Wert 1 : 1/45 - 4/9 + 64/45 = 1 .

Restglied

Euler_Macl Sum

Fehlerfolge& max. Extrapolgrad

Gewichte

Romberg Int

Def

Gewichtete Sum

Schema

Polynomauswertung Neville-Aitken

PA Neville-Aitken 2

PA-NA Proof_Pros

direkter Algo

Richardson Extrapol.

Polynomauswertung Neville-Aitken

Adaptiver Algo

Autom. Diff.

MOSIM

2

Quadraturverfahren

Srt 2 Division

Additional Information

step 1-3

Comp Arith. Summary

Scientific Computating Problems

1. Def prob. --> simplification
2. physical prob --> model error
3.Math.modeling --> approx error
4.math. approx --> rounding error
5.computation --> error  analysis

example: numerical differetiation

for small h, h>0
h-balance zw. rundungs und genauigkeit.

Exm?

Newton Cortes Formeln

Intro 1

Motivation für FPNs und integers

Zahlenformate

- single 32bit
- double 64bit
-extended 80bit
-quadruple 128bit --> Details später!

Num Func Real types by F95

1. Kind
2. Radix - base b rep.
3. Digits - # of digits in base b
4. minexp - Minimal possible exp
5. maxexp - Max. possible exp
6. huge - largest possible FPN in type
7. tiny - small. poss. FPN in type
8. epsilon - 
9. precision
10. range

example code for \epsilon

program test_epsilon
real :: x = 3.143
real(8) :: y = 2.33
print *, EPSILON(x)
print *, EPSILON(y)
end program test_epsilon

CompAirDemo-tool?

Math(Brain) vs ProgSw vs PC/Hw

Restglied

Num. Func for INT types by F95

1. Kind
2. Radix - base b
3. digits - # of b digits
4. largest val rep in type
5. decimal range r
6. smallest val?

Normalizing of FPN

Norm of x\neq 0:
mantissa digits um k-digits nach links schieben (k= anz. führender 0-Ziffern) und subtraktion von k von e_x, then e_xneu = e_x-k

step 4

Boolsche Algebra with True=T and False=F

FPN

x \neq 0!
x = (s_x, m_x,e_x,b)

1. s_x=sign bit
2. m_x = mantissa
3. e_x = exponent
4. b = base (b \neq 0,1)
5. b_max = b-1

normalized

ele. Operations

XOR(zusammengesetzt)

Symbols

Ziel

Intervallbasierende Räume mit FP und kompatibilität mit Funktionen.
also zb. \sin(X) = [\sin(x_min),\sin(x_min)], this probably changes the order? Periodicy

unnormalized

normalizing condition

Only possible if e_xneu = e_x - k \ge e_min

Anford an Prog-Lang

1. math. Notation (prog einfach, klar, recycling, überladung, einfache formeln)
2. Datenabstraktion (neue datenobj/Oper aus existierenden möglich, zusammensetzen)
3. auto. memory management (dynam. objects )
4. Genuaigkeit und Einschließung

Ausleseprob

Parallelisierung:

Bitvector B(x) of a number x

x is a number in R or \R?
B(x) = [x_n-1 x_n-2, ..., x_1, x_0]_2
Value: |B(x)|=\sum_{i=0}^{n-1}x_i \cdot 2ⁱ = usigned value of x

Laws, props AND first, then OR

Bin. Rep. of numbers

https://i.imgur.com/sNO6vIS.jpg                                                                                                                                         

FPN-format

R = R(b,l,e_min,e_max, denorm)

denorm para.

denorm = true, if denorm. FPN are allowed or false otherwise

FP-interv. over R

IR = {X = [x_min,x_max], x_min \le x_max, x_min,x_max \in R}

Interv mit FP Grenzen

Wilkinson ep

e = b^(1-l) = 1/b^{l-1
with l = mantissa length
größte rel. Abstand zw. zwei benachbarten normalisierten FPN ~ größter rel. Fehler bei Rundung}

IntervallMA

denorm FPN

e_x = e_min and mantissa not normalized/normalizable

1er complement

|B(x)|+ |B(-x)| = 2ⁿ-1

2er complement

|B(x)| +|B(-x)| = 2ⁿ
Value in 2er complement of num. a
a = (-) a_n-1 \cdot 2^n-1 + \sum_{i=0}^{n-2} a_i \cdot 2ⁱ
with (-) wirkliches negative: 1--> -1

Full Adder

Adders

2 ganze Zahlen mit je n bit add/sub.

exact result - in \R

z * = x+/* y with x,y \in I_n (integer with n-bits with incl. Vorzeichen)

ulp(x)

ulp(x) = \begin{cases}
b^e_x-l falls x normal\\
b^{e_min - l} falls x denorm oder 0
\end{cases}
unit in the last place at the mantissa of x = Einheit in letzter Stelle

Zahlenstrahl

jede ziffernpos can have 3 behaviours

Half Adder

Menge beschränkt abgeschl. reellen Interv over \R

I\R = {X = [x_min,x_max] x_min \le x_max, x_min,x_max \in R}

erzeugtes result in R (Raster)

z := ((z *  2^n-1)mod 2ⁿ)* 2^n-1 \in I_n

Nachfolger succ(x)/Vorgänger pred(x)

Improved HA

Interv-Rundung

&: \R \to  \R mit &X = [&x_min,&x_max] \superseteq X =[x_min,x_max]
the rounded interval is always a subset of the 
original Interv X?-verify?

Def Rounding

Op %: \R \to R (FP raster) with 3 properties
R1: %x = x for all c \in R (projection)
R2:x,y\in \R : x \le y \implies %x \le %y (monotonie)
R3: %(-x) = -%x \forall x \in \R (antisym)

Simpler Adder

John Von Neumann Adder JVNA

Serial Adder

Props &X

R1 &X = X for all X \in IR
R2 X,Y \in IR: X \subseteq Y => &X \subseteq & Y
R3 &(-X) = -&X, cos  \triangle (-x) = -\nabla x, \nabla(-x) = -\triangle x \in \R!!!

to R3 remember: -X = [-x_max,-x_min]
X=[a,b] => -X=[-b,-a]!!!

Carry-Select-Adder

Ripple-Carry-Adder

CSA (2)

diam(X\pm Y) in IR

X + Y = [x_min + y_min, x_max+y_max] and 
X - Y = [x_min - y_max, x_max - y_min]
equal  to
              diam(X\pm Y) = \diam X + \diam Y

Beispiele Rundungen, \nabla and \triangle

Grundop auf I\R (1)

Combination CLA+RCA

Grop auf I\R (2)

Intervstandardfcts

Inclusionsprop/overestimation

Complete CLA

Carry Lookahead Adder (CLA) Curcuit

Carry-Skip Adder (CSA)

2nd part CLA tree

1st part CLA tree

Div Algos

restor Div

nonrestor Div

SRTX Div