My other blog …

04/10/2013

I have not been posting on here as much lately as I have set up another blog.

cscresources

This is a one-page blog on which I put links for you to download sample code with notes in .pdf form on a range of topics.

Today I have just added an article (plus sample programs) exploring four classic methods of enciphering messages.

Please check it out!

Knuth TAOCP, 1.4.2, ex. 7

13/06/2013

I have been reading Knuth’s classic work The Art of Computer Programming. I have been doing some of the exercises in a machine language (ARM assembly code for the Raspberry Pi). You can find those resources on a one-page blog I have created. It’s here.

This exercise, I chose to do in Python!

Simple Encode & Decode (Python)
Knuth, TAOCP, vol. 1, 1.4.2 ex. 7

The Task

This simple exercise in encoding and decoding comes in a section on coroutines, but works quite nicely using plain old Python functions. The idea is that we provide a string of characters which can contain only letters and numbers and which is terminated with a full stop.

For each character of the input, if the character is a digit (let’s call it i), then we write the following character i + 1 times (whether it is a digit or a letter). If the character is a letter, we just write it to the output once. Here’s a sample input (not the same as given by Knuth).

Knuth TAOCP 1.4.2
String: 2A0B345CDE67F1G1H0I5JK.

The output is arranged into groups of three characters separated by a space:

AAA B44 44C CCC CCD E77 777 77F GGH HIJ JJJ JJK.

The task Knuth sets is to write a program that will reverse the process. But first it makes sense to write one that performs the encoding.  I’ll start with the nuts and bolts part:

# encoder.py
# from Knuth vol. 1, 1.4.2 (p195)

def main():
    print("Knuth TAOCP 1.4.2")
    a = input("String: ")
    print(prepare(process(a)))

if __name__ == "__main__":
    main()

The main work happens in two functions, process() and prepare():

def prepare(string):
    output = ''
    count = 0
    for ch in string:
        if count == 3:
            output += ' '
            count = 0
        output += ch
        count += 1
    return output + '.'

This is very simple, it takes the output from process() and adds the spacing, plus the final full-stop. It’s important to add the spacing before adding the character, or you could end up with an unneeded space at the end.

Process() itself is fairly simple.

def process(string):
    output = ''
    i = 0
    temp = string[i]
    while temp != '.':
        temp1 = string[i+1]
        if temp.isalpha():
            output += temp
            i += 1
        elif temp.isdigit():
            output += temp1 * (int(temp)+1)
            i += 2
        temp = string[i]
    return output

First we set things up before we enter a loop. Then, in the while loop we add characters to the output string according to the rules of the encoding.

A Possible Solution

Once again, I’ll give you the boring bits first.

# decoder.py
# Knuth 1.4.2, ex. 7

def main():
    print("Knuth 1.4.2, ex. 7")
    a = input("String: ").replace(' ', '')
    print(process(a))

if __name__ == "__main__":
    main()

I’ve taken advantage of the handy Python replace() function to strip out the spaces. This program only has one other function, which I have called “process()”.

def process(string):
    i = 0
    output = ''
    temp = string[i]
    while temp != '.':
        i += 1
        count = 0
        while temp == string[i+count]:
            count += 1
        if count:
            output += str(count) + temp
            i += count
        else:
            output += temp
        temp = string[i]
    return output + '.'

Once again, I place the first character into a variable called temp before entering the while loop. I update temp with the next character at the end of the loop and this makes it easy to check for when we have finished.  Nested within the main while loop is another while loop that counts how many times a character appears in the input string. Knuth specifies that he doesn’t want zeroes to appear in the final string, so we only add a number to the output if it is over 1.

Conclusion

This is one of Knuth’s simpler examples, but it’s quite a nice one.

RSA Algorithm

16/01/2013

I have put together some short articles with sample code, all based on mathematical algorithms in Python.

Series One

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

Series Two

1. Newton’s method for nth roots.
2. Primes revisited
a) faster Miller-Rabin
b) Lucas-Lehmer number
3. A Little Number Theory
a) Ramanujan’s Highly Composite Numbers
b) Ramanujan and Hardy – roundness
c) Pythagoras – perfect numbers
d) Pythagoras – friendly numbers
4. Pi
a) Euler’s method for calculating Pi
b) Cesaro / Monte Carlo method
5. The RSA algorithm

The .zip file is here.

As a little taster, here is the code of my RSA algorithm program. You can copy and paste it and have a play and download the .zip file to read my notes in the pdf file.

# rsa.py - demo of the RSA algorithm

def main():
    n = e = d = 0
    while 1:
        print("""
    1. Set Public Key
    2. Encode
    3. Decode
    0. Quit
    Your choice? """, end = "")
        choice = int(input())
        if not choice:
            return
        if choice == 1:
            n, e, d = set_keys()
        if choice == 2:
            if not n:
                n = int(input("Public Key: "))
                e = int(input("e: "))
            encode(n, e)
        if choice == 3:
            if not d:
                n, e, d = set_keys()
            decode(d, n)

def set_keys():
    """This fuction asks for 2 primes.
    It sets a public key and an encoding number, 'e'."""
    p = int(input("p: "))
    q = int(input("q: "))
    n = p * q
    m = (p - 1) * (q - 1)
    e = get_e(m)
    print("N = ", n, "\ne = ", e)
    d = get_d(e, m)
    while d < 0:
         d += m
     return [n, e, d]

     def encode(n, e):
     """This function asks for a number and encodes it using 'n' and 'e'."""
     while 1:
         c = int(input("Number to encode: "))
         if not c:
             return
         print(pow(c, e, n))

 def decode(d, n):
     """This function asks for a number and decodes it using 'd' and 'n'."""
     while 1:
         c = int(input("Number to decode: "))
         if not c:
             return
         else:
             print(pow(c, d, n))
     
  def even(x):
     """True if x is even."""
     return x % 2 == 0

  def get_e(m):
     """Finds an e coprime with m."""
     e = 2
     while gcd(e, m) != 1:
         e += 1
     return e

 def gcd(a,b):
     """Euclid's Algorithm: Takes two integers and returns gcd."""
     while b > 0:
        a, b = b, a % b
    return a

def get_d(e, m):
    """Takes encoding number, 'e' and the value for 'm' (p-1) * (q-1).
    Returns a decoding number."""
    x = lasty = 0
    lastx = y = 1
    while m != 0:
        q = e // m
        e, m = m, e % m
        x, lastx = lastx - q*x, x
        y, lasty = lasty - q*y, y
    return lastx

if __name__ == "__main__":
    main()

You can download a .zip file with the other short articles and programs here.

Enjoy!

Latest Python tutorial. System arguments and stuff.

27/09/2012

Watch “Python Tutorial 13: print() and strings” on YouTube

11/08/2012

Watch “Python Tutorial 12: Turtle Graphics” on YouTube

11/08/2012

Watch “Python Tutorial 11: Peano Addition” on YouTube

11/08/2012

Video 10. Finding Square Roots.

10/08/2012

Video 0

09/08/2012

Simple one on for loops, while, if, else.
Plus a factorial program.
Made from the Pi (via VNC)

Bubble Sort

08/08/2012