MATHEMATIK PROGRAMMIEREN MIT

PYTHON

Univ.–Prof. Dr. Stefan Muller-StachAG Zahlentheorie

27. September 2006

JOGU Mainz

PYTHON: Moglichkeiten einer Programmiersprache

PYTHON: Objektorientierte Sprache von Guido van Rossum [1]benannt nach der MONTY PYTHON TruppeGenutzt fur Content Management Systemewie PLONE/ZOPE und auch GOOGLE et.al.leicht erlernbar, geeignet fur Mathematik (longint)Plattformunabhangig (lauft auf Win, Mac, Linux etc.)Kostenlos erhaltlich, siehe http://python.org

JOGU Mainz

Starten von PYTHON

Man startet das Programm mit Hilfe einer Konsole, am bestensogar eine interaktive Version wie z.B. IPYTHON. In folgenderBeispielsitzung wird die Mathematik–Bibliothek math geladen:

>>> import math

>>> math.pi

3.1415926535897931

>>> math.e

2.7182818284590451

>>> 2**5

32

>>> math.cos(2*math.pi)

1.0

JOGU Mainz

>>> 221 % 17

0

>>> 4/3 (oder besser 4//3)

1

>>> from future import division

>>> 4/3

1.33333333333

>>> 2**190

1569275433846670190958947355801916604025588861116008628224L

>>> numbers=[i for i in range(1,8)]

>>> numbers

[1,2,3,4,5,6,7]

>>> [2**n for n in numbers]

[2,4,8,16,32,64,128]

>>> [x for x in range(-10,10) if (x**4-13*x**2+36==0)]

[-3, -2, 2, 3]

JOGU Mainz

Beispiel 1: Der ggT

Man kann kleine Programme wie hier den großten gemeinsamenTeiler von zwei ganzen Zahlen auch selbst auf der Konsoleprogrammieren:

>>> def ggt(a,b):

>>> while b:

>>> a,b=b,a%b

>>> return a

JOGU Mainz

Etwas allgemeiner kann man den erweiterten EuklidischenAlgorithmus programmieren, der auch noch eine Linearkombinationxa+ yb = ggt(a,b) ausgibt:

>>> def xggt(a,b):

>>> x1,x2,y1,y2=1,0,0,1

>>> while b:

>>> q=a//b

>>> x1,x2,y1,y2=x2,x1-q*x2,y2,y1-q*y2

>>> a,b=b,a%b

>>> return a,x1,y1

JOGU Mainz

Beispiel 2: Primzahlen

Mit PYTHON kann man auch Programme in Dateien schreibenund ausfuhren lassen. Schreiben Sie folgendes Programm in eineDatei z.B. mit dem Namen primzahltest.py:

from math import sqrt

def isprime(n):

if n % 2 == 0 and not n == 2:

return (0)

else:

limit = int(sqrt(n)) + 1

for l in range(3, limit, 2):

if n % l == 0:

return (0)

return (1)

JOGU Mainz

Jetzt kann man diese Datei laden und neu definierte Kommandoisprime benutzen:

>>> from primzahltest import isprime

>>> [i for i in range(1,30) if isprime(i)]

2,3,5,7,11,13,17,19,23,29

JOGU Mainz

Beispiel 3: Fibonacci Zahlen

def fibonacci(n):

a,b = 0,1

list=[1,1]

for x in range(1,n-1):

a,b=b,a+b

list.append(a+b)

return list

Das Kommando fibonacci(7) produziert nun die Liste der erstensieben Fibonaccizahlen [1,1,2,3,5,8,13].

JOGU Mainz

Beispiel 4: Fakultat

Rekursive Programmierung:

def factorial(n):

assert n>=0, "n nicht negativ!"

if n=1:

return 1

else:

return n*factorial(n-1)

Das Kommando factorial(5) ergibt das korrekte Ergebnis5! = 120.

JOGU Mainz

Beispiel 5: Binomialkoeffizenten

Die Binomialkoeffizienten tauchen im Pascalschen Dreieck auf undsind definiert durch

(

nk

)

:= n!k!(n−k)! = n(n−1)···(n−k+1)

1·2···k ∈ N.

def binomial(n,k):

out=1

for i in range(1,k+1):

out = (out*(n-i+1))//i

return out

Das Kommando binomial(5,3) ergibt das korrekte Ergebnis 10.

JOGU Mainz

Beispiel 6: Mersenne Primzahlen und Lucas–Lehmer Test

Der Lucas–Lehmer Test untersucht ob n = 2p−1 mit p prim eine

(Mersenne) Primzahl ist, die großten bekannten Primzahlen, z.B.derzeit die Zahl 232.582.657

−1 mit uber 9.8 Mio. Ziffern [6]. Dazukonstruiert man rekursiv eine Folge sn mit s1 = 4 und sn+1 = s2

n −2und testet, ob sp−1 durch n teilbar ist:

def lucas(p):

s=4

val=pow(2,p)-1

for i in range(3,p+1):

s=(s*s-2)%val

return not s

Die ersten funf Mersenne–Primzahlen sind 22−1 = 3, 23

−1 = 7,25

−1 = 31, 27−1 = 127 und 213

−1 = 8191.

JOGU Mainz

Beispiel 7: Sierpinski Grafik

1 1 1 1 1 1

1 3 5 7 9 · · ·

1 5 13 25 41 · · ·

1 7 25 63 129 · · ·

1 9 41 129 321 · · ·

1...

......

...

Bild wird durch PYTHON Imaging Library als JPEG–Bild erzeugt.

JOGU Mainz

PYTHON MATH LAB

PYTHON MATH LAB [3] ist eine Webseite, die zum Ziel hat,Mathematik mit PYTHON zu unterstutzen. Dort findet manBibliotheken fur viele mathematische Teilgebiete, wie z.B.Zahlentheorie, Geometrie, Kryptographie, Numerische Analysis.Ebenso findet man dort PYTHON–Programme, die aufSmartphones laufen (siehe unten).

JOGU Mainz

SAGE

SAGE [5] ist ein auf PYTHON aufgebautes freies und kostenlosesCAS. Es enthalt u.a. NTL, MWRANK, NUMERIC, SINGULAR,MAXIMA, GAP und PARI/GP.

sage: 2/3

2/3

sage: 2//3

0

sage: parent( )

Rational Field

sage: factor(232 +1)641 * 6700417

In der letzten Zeile sieht man, dass die 5–te Fermatzahl 232 +1nicht prim ist.

JOGU Mainz

NZMATH

NZMATH [7] ist ein eng auf die Zahlentheorie fokussiertes und inPYTHON geschriebenes CAS. Im Gegensatz zu SAGE sind alleAlgorithmen ausschließlich in PYTHON implementiert und bildendamit ein Lehrbeispiel fur die Programmierung in PYTHON.

JOGU Mainz

NOKIA PYTHON fur Series 60

Series 60 Telefone besitzen ein SYMBIAN Betriebssystem, fur daseine Opensource PYTHON Implementation von NOKIA existiert[2].

Features: 2D Grafik, BildbetrachtungKamera, Kalender und KontaktdatenbankzugangSoundaufnahme und PlaybackZugang zu Systeminformation (e.g. GSM Location)Telefon und SMS-NutzungGPRS, Webserver und Bluetooth ApplikationenStandalone Programme herstellbarAktives Developer Forum [2]

JOGU Mainz

Mathematik auf dem Telefon

Das kleine in PYTHON geschriebene CAS mathlab.py lauft aufSerie 60 Mobiltelefonen und lost viele kleine mathematischeProbleme der Zahlentheorie [3].

Features: Elementare ZahlentheorieAlgebraische Zahlentheorie (Klassenzahlen)Rationale Zahlen, Vektoren, Matrizen, GleichungenTaschenrechnerfunktionenElementare Kombinatorik

Eine Weiterentwicklung ist geplant. Gotz Schwandtner vomInstitut fur Informatik in Mainz hat z.B. einenspigot–Algorithmus zur Berechnung beliebig vieler Ziffern von πund e implementiert [13].

JOGU Mainz

Screenshots

JOGU Mainz

Andere PYTHON–Mathematik Links

In der numerischen Mathematik (Scientific Computing) werden oftextrem große Matrizen benutzt und manipuliert. Dazu gibt dieBibliothek NUMPY [4] (fruher NUMERIC oder NUMARRAY).Weitere Links: Kombinatorische Mathematik ALADIM [8],MATHGUIDE [9] (weiteres CAS), Kryptographische ToolsPYCRYPTO [9], 2D und 3D Visualierungs- und GeometrietoolsVPYTHON [10] und PYGEO [11].

JOGU Mainz

Bibliographie

[1 ] PYTHON, http://python.org

[2 ] NOKIA, http://opensource.nokia.com/projects/pythonfors60/

[3 ] PYTHON MATH LAB, http://hodge.mathematik.uni-mainz.de/∼stefan/python/index.html

[4 ] NUMPY, http://numeric.scipy.org/

[5 ] SAGE, http://modular.math.washington.edu/sage/

[6 ] GIMPS, http://www.mersenne.org

[7 ] NZMATH, http://sourceforge.net/projects/nzmath/

[8 ] ALADIM, http://www.math.uni-siegen.de/ring/aladim.html

[9 ] MATHGUIDE, http://www.math.uni-siegen.de/ring/mathGUIde/

[10 ] PYCRYPTO, http://www.amk.ca/python/code/crypto.html

[11 ] VPYTHON, http://vpython.org/

[12 ] PYGEO, http://home.netcom.com/∼ajs/index.html

[13 ] http://wombatz.informatik.uni-mainz.de/∼goetz/PyS60/

JOGU Mainz