Tiny computers vs. Big Languages

[Wolfgang Strobl]

[Subject changed from Re: Dr. Dobb's Python-URL! - weekly Python news
and links (Aug 12)]

Greg Ewing wrote:

>Andreas Leitgeb wrote:
>
>> The only language, that is not at all a nanny is machine language 
>> (not assembler, but really the raw bytes), and no human would actually 
>> *want* to write that.
>
>
>I did, at one stage of my life. Not much choice when
>you've only got 256 bytes of memory...

256 Bytes? That's plenty! :-)

Well, even the cheap handy in my pocket has much more memory than the
mainframe I ran my first program with. That IBM 7090 had 128 K memory.
Hundred of users used Fortran IV for various scientific programs.

On the other hand, there are still computers selling well today which
have much less than 256 Bytes of RAM, and aren't necessarily programmed
in assembler or in machine language. Take for example a late evening
project I did a while ago. It was based on a tiny 8 bit microcontroller
having only 68 bytes of RAM plus 1024 K words (1792 bytes) of ROM.
(For the obligatory connection to Python see down below.) I usually
program these beasts in some strange dialects of C or Basic, and only
switch to assembler when necessary.

68 bytes of RAM, that's enough memory to implement a device which plays
mastermind (aka jotto aka bulls and cows). Mastermind is a game where
somebody (in this case the computer) has to find a hidden combination
of objects or colors, by offering a series of guesses.  For a
description of the device and algorithm(and a Java applet written by my
son Jan simulating the devices operation) see
http://www.mystrobl.de/ws/pic/mm47/index.htm

Even for computers as tiny as these, assember language usually isn't
the best choice to write a program in. IMHO, writing the application in
some medium level language, and coding only the time critical parts in
assembly language is a better choice. In the example above, I used a
mixture of a Basic like language and inline assembler. 

Implementing a general mastermind solver isn't that hard, but it's an
interesting algorithmic problem, nevertheless, espescially when
learning a new language or a new architecture. 

An obvious solution for an algorithm is to start with a random
question, to compute the set of combinations which are still consistent
with the answers qiven so far, and to ask a question from this set each
time.   My first version of such an algorithm tried to do better, by
computing the optimal question each time, optimal being defined as
guaranteeing a maximal reduction of the search space in the next step.
Implemented in Z80 assembler it used about 4 K of program memory, about
4 K of RAM and wasn*t fast, but fast enough.

Much later I learned that a much simpler algorithm, which just selects
some question at random is about as good in guessing as the optimal
algorithm. :-/ For a discussion see
http://www.math.niu.edu/~rusin/uses-math/games/mastermind/mastermind

Well, this gave me an opportunity to try the aforementioned
hard+software project of implementing a "mastermind calculator".  A
tiny microcontroller like the 16F84 from Microchip neither has the
memory nor the speed for the original algorithm, but it's more than
fast enough to compute the search space in fractions of a second on the
fly, and so making it possible to never store the search space (that's
2401 combinations in a 4x7 game initially), but a series of questions
and answers only. 

Now comes the funny part, related to Python.  Later I implemented the
basic algorithm in Python too, of course, but found the speed somewhat
unsatisfying.  My mastermind calculator calculates the first computed
guess in about 0,5 s realtime, when using a 8MHz clock.   The very same
algorithm on a ~500 MHz Laptop, using Python 2.2.1 needs 0.18 s.  Sure,
its faster, but it's in the same order of magnitude.  So doing my
original algorithm (see above) in pure Python is out of question,
because computing a guess consumes three and a half minute, on my
laptop. That's not useable.

The hot spot in this computation is a simple function "compare", which
compares two combinations (say, (1,2,3,4) and (2,1,3,5), yielding a
pair (say, (1,2)) of correct places ("3") and values ("1" and "2").
My 16F84 performs this computation with 146 cycles, that amounts to 73
µs when using a 8MHz clock. Running the python program shown below
tells that my 500 MHz Laptop does a single comparison in about 50 µs.
Oh well.

Recoding the compare function as a C extension reduces the time for a
single comparison from 50 µs to 9 µs. That's faster, but still not fast
enough to implement the original algorithm in Python. One would have to
implement the outer loop in a C extension, too.

Two final remarks:

 - I tried to optimize the straightforward implementation of compare,
but every single variant I tried was both longer, more difficult to
understand, and slower.  

- To my surprise, the Python version of compare is noticeably faster
with Python 2.3 (cvs version from friday) than with 2.2.1:  42 µs
instead of 50 µs for a single call.


# building blocks for mastermind calculations
# W.Strobl 2002-08-25
# see http://www.mystrobl.de/ws/pic/mm47/index.htm

def compare(a,b):
    """
    >>> compare((1,2,3,4),(2,1,3,5))
    (1, 2)
    >>> compare((1,2,3,4),(2,1,2,2))
    (0, 2)
    >>> compare((0,1,1,0),(0,1,0,1))
    (2, 2)
    >>> compare((1,0,0),(1,0,0))
    (3, 0)
    """
    s,w=0,0
    al=[]
    bl={}

    for i in range(len(a)):
        if a[i]==b[i]:
            s += 1
        else:
            al.append(a[i])
            bl[b[i]]=1
    for x in al:
        if bl.has_key(x):
            w +=1
            del bl[x]
    return (s,w)

def gen(places,colors):
    """
    >>> len(gen(4,7))
    2401
    >>> gen(3,2)
    [(1, 1, 1), (2, 1, 1), (1, 2, 1), (2, 2, 1), (1, 1, 2), (2, 1, 2),
(1, 2, 2), (2, 2, 2)]
    """
    s=[]
    ol=[]
    for i in range(places):
        s.append(1)
    ol.append(tuple(s))
    while 1:
        for j in range(places):
            s[j] += 1
            if s[j]>colors:
                s[j]=1
            else:
                break
        else:
            return ol
        ol.append(tuple(s))

def reduc(space,question,answer):
    """
    compare extension only works with tuples of size four!
    #>> reduc(gen(3,2),(1,2,2),(3,0))
    [(1, 0, 0)]
    #>> reduc(gen(3,2),(1,2,2),(1,2))
    [(0, 1, 0), (0, 0, 1)]
    >>> len(reduc(gen(4,7),(4,1,2,3),(2,1)))
    60
    >>> len(reduc(gen(4,7),(1,2,4,4),(3,0)))
    24
    """
    ol=[]
    for t in space:
        if compare(t,question)==answer:
            ol.append(t)
    return ol
    

def messe():
    import time
    start=time.clock()
    for i in range(10000):
        pass
    slack=time.clock()-start

    start=time.clock()
    for i in range(10000):
        compare((1,2,3,4),(2,1,3,5))
    t=time.clock()-start
    print "compare  takes       %6.3f microseconds"%((t-slack)*100)

    
    start=time.clock()
    for i in range(1):
        len(reduc(gen(4,7),(6,7,7,8),(0,2)))
    t=time.clock()-start
    print "reduc    takes       %6.3f seconds"%((t)/1)

def _test():
    import doctest, mmesse
    return doctest.testmod(mmesse)

def main(args,optdict):
    import sys
    if optdict.has_key("--test"):
        _test()
    else:
        messe()
        

if __name__ == "__main__":
    import getopt,sys
    optlist,args=getopt.getopt(sys.argv[1:],"v",
        ["test", "messe"])
    optdict=dict(optlist)
    main(args,optdict)
       
-- 
Thank you for observing all safety precautions