16/04/2013

Python

Algorithms – A series of articles on mathematical algorithms in Python.

1: A. M. Legendre, exponentiation by successive squaring.
2: Heron of Alexandria, square roots
3: Peano arithmetic
4: Zeller’s congruence
5: Factorial
6: Fibonacci numbers
7: Euclid’s GCD & prime factors
8: Eratosthenes’ sieve and the Miller-Rabin algorithm
9: Pascal’s triangle
10: Tau using Gregory and Euler’s equations

Mathematical Algorithms Part Two

1. Newton’s Method for finding nth roots.
2. A faster version of the Miller-Rabin test and Lucas-Lehmer numbers.
3. Ramanujan’s Highly Composite Numbers, plus Perfect and Friendly numbers.
4. Euler and Cesaro methods for Pi
5. RSA algorithm

Casesar Cipher – Implementation and notes in a .pdf.

Count Char  – A program to count the frequency of letters in a text file. Includes notes and sample texts. Can be used to break Caesar Cipher!

Substitution Cipher – Program plus notes, sample key and texts.

Caesar, Vigenere, Jigsaw and Playfair Ciphers  – Simple implemetations of the four ciphers with explanation.

Game of Life – Program plus notes.

Drawingpad – a turtle drawing program, with some notes on tkinter.

Recipe  – a simple program that lets you load & save recipes and scale quantities for different numbers of diners.

Basic OOP – simple program plus notes exporing OOP.

Hangman – With multiple manageable wordlists. Program and notes.

Simple Calculator – just does add and subtract.

Read / Write Cheat sheet – quick overview of reading & writing to text files, pickle and shelve.

Booth’s Algorithm – the multiplication algorithm, with notes and code in Python.

N Queens – explanation of the recursive approach to this problem, plus a small optimisation.

Pythagoras – how to prove Pythagoras’ theorem using only a turtle.

Decimal Periods – On binary fractions, decimal fractions and Gauss.

Harmonic Numbers – Python implementation of Knuth TAOCP, vol. 1, 1.3.2 ex. 16, plus notes.

Simple Encode / Decode – A very simple example based on Knuth TAOCP, vol.1, 1.4.2 ex. 7. Plus notes

Magic Squares – Python code plus notes, based on Knuth  TACOP, vol.1 3.3.2 ex.21.

RNG – Python implementation of random numbers (linear congruential) plus a simple dice game and notes.

The Dining Philosophers – Code and notes for the well-known threading problem.

Sequences – Python programs to generate and analyse polynomial sequences. Plus notes.

Giving Change – Recursive algorithm for counting the number of ways to give change.

Assembly Code

Getting Started   Hello World in ARM assembly code.

Greet –   A simple greeter program in ASM.

Using the GNU debugger – Sample code plus notes. This one may need a bit of redrafting.

Max / GCD – two simple programs. Greatest Common Denominator and Maximum.

First 500 Primes – Based on an exercise in Knuth’s TAOCP.

Num In – How to get a number from the keyboard in ARM asm.

Print Number – How to print a number out.

Exponentiation – A simple application that demonstrating successive squaring algorithm.

Easter – In response to Knuth’s exercise on the Easter algorithm (TAOCP, vol. 1, 159f)

Counting Change – A look at recursion using a program that counts ways to give change.

Scratch

[ resources coming soon]

General

Recursion – simple discussion of recursion with examples in Scratch and Python.

happy hacking,

antiloquax