Introduction to A&D

Karatsuba multiplication

Karatsuba Multiplikation.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

n/2

n/2

n/2

n/2

n

n

a

b

c

d

Embedded Files

fa213f307a1e3140541e18a52caa012446662c51: $10^{n}ac+10^{n/2}+10^{n/2}bd+10^{n/2}(a-b)(d-c)+bd$

Link to original

$10^{n}ac+10^{n/2}(ad+bc)+bd$

NOTE

ONLY 3 multiplications needed the normal method is to calculate $(10^{n/2}a+b)(10^{n/2}c+d)$ and need 4 multiplications

This is called Divide and conquer

Time Complexity Analysis

$M(n)$: The number of digit multiplications needed to calculate the multiplication of two numbers which have n digits respectively.

• $M(2^0)=1$
• $M(2^k)=3\cdot M(2^{k-1})$ //Rekurrenz
• $M(2^k)=3^k$ // kein Beweis, für Beweis braucht man Induction $n=2^k⟹k={\log }_{2}n⟹3^k=3^{{\log }_{2}n}=n^{{\log }_{2}3}=n^{1.58}$ (See Algorithm Runtime Analysis)

one dimensional goal finding

Goal finding on a line.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

1

1

2

2

4

4

8

8

Link to original

Time Complexity Analysis (worst case)

k=distance between start and end Annahme: $2^{i-1}<k<2^i$

• $2\cdot 1+2\cdot 2^1+2\cdot 2^2+\cdots +2^i+k$
• $=2(2^{i+1}-1)+k$
• $2^{i+1}=4\cdot 2^{i-1}<4k$
• $⟹2(2^{i+1}-1)+k<9k$

Definition des Algorithmus

NOTE

Beschreibung einer Abfolge von elementaren Operationen zur Lösung eines Problems

A typical computer: $10^9$ Ops/sec

What to learn in A&D

• Entwurf und Analyse von Algorithmen
• algorithmische Denkweise
• wichtige Algorithmen kennenlernen