#!/usr/local/bin/python
# coding: iso-8859-1
# Copyright © 2008 by Amos Newcombe
#
# This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
#
# This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
#
# You should have received a copy of the GNU General Public License along with this program. If not, see .
'''Command-line program to test running speed of greatest common divisor algorithms.
'''
import re, time
from random import getrandbits
from gcd import dfGcd
class CartesianIter:
'''Given a list n iterators, loop over the space of their cartesian product, with the last one on the list changing most frequently, and the first one least frequently.
Beware of feeding it iterators that are infinite, or length zero: it will fail.
'''
def __init__(self, *lit):
self.lit = lit
self.litWork = [iter(it) for it in lit]
self.lResult = []
def __iter__(self): return self
def next(self):
i = len(self.litWork) - 1
if not self.lResult:
self.lResult = [it.next() for it in self.litWork]
else:
while True:
try: self.lResult[i] = self.litWork[i].next()
except StopIteration:
self.litWork[i] = iter(self.lit[i])
self.lResult[i] = self.litWork[i].next()
i -= 1
if i < 0: raise
else: break
return tuple(self.lResult)
class ListPairIter:
def __init__(self, l):
self.l = l
self.i, self.j = 0, 0
self.c = len(l)
def __iter__(self): return self
def next(self):
self.j += 1
if self.c <= self.j:
self.i += 1
self.j = self.i + 1
if self.c <= self.j: raise StopIteration
return (self.l[self.i], self.l[self.j])
from commander.commander import commander
import sys
class gcdtest(commander):
# ¤ Metadata
sUsage = '''\
python %prog ...
run a timing test on the gcd routines\
'''
sVersion = '%prog 2008.08.05.0'
sAlgDefault = 'ENC'
slBitsDefault = '16'
sNDefault = '5'
# ¤ Creation
def __init__(self, lsLine):
commander.__init__(self, lsLine)
def options(self): # called by commander.__init__()
'populate the option parser (self.optParser) with options'
self.optParser.add_option('-a',
dest='sAlg', default=self.sAlgDefault, metavar='',
help='use the algorithms listed in by their one-letter code:' + \
''.join(dfGcd.keys()) + ' default ' + self.sAlgDefault
)
self.optParser.add_option('-b',
dest='slBits', default=self.slBitsDefault, metavar='b,b...',
help='use numbers of b bits, where b is from this ' + \
'punctuation-separated list, default ' + self.slBitsDefault
)
self.optParser.add_option('-n',
dest='sN', default=self.sNDefault, metavar='n',
help='use n random numbers for the test, default ' + self.sNDefault
)
def ResolveOptions(self):
'Interpret the command line options.'
try : self.sAlg = self.opt.sAlg
except AttributeError: self.sAlg = self.sAlgDefault
try : slBits = self.opt.slBits
except AttributeError: slBits = self.slBitsDefault
self.lnBits = [int(s) for s in re.split('\W+', slBits)]
try : sN = self.opt.sN
except AttributeError: sN = self.sNDefault
self.nN = nN = int(sN)
self.cPairs = nN * (nN-1) / 2
# ¤ Reporting
def texttable(self, dResult, nWidth=5):
print 'bits'.rjust(nWidth) + ' ' + \
' '.join([ch.center(nWidth) for ch in self.sAlg])
for nB in self.lnBits:
print str(nB).rjust(nWidth) + ' ' + \
' '.join([self.textresult(dResult[(ch, nB)], nWidth) for ch in self.sAlg])
def textresult(self, Value, nWidth=5):
if isinstance(Value, str):
try : sValue = '(%s)' % self.dnErrors[Value]
except KeyError: sValue = Value
sValue = sValue.center(nWidth)
else:
sValue = '%*.1f' % (nWidth, Value)
return sValue
# ¤ Operation
def main(self):
dResult = self.test()
self.texttable(dResult, 6)
def test(self):
# generate data for each bit size
self.dlData = dict([
(nB, [getrandbits(nB) for i in range(self.nN)])
for nB in self.lnBits
])
# run the test
dResult = {}
self.dnErrors, nFootnote = {}, 0
isError = False
for ch, nB in CartesianIter(self.sAlg, self.lnBits):
fGcd = dfGcd[ch]
itData = ListPairIter(self.dlData[nB])
xElapsed = -time.clock()
for n1, n2 in itData:
try: fGcd(n1, n2)
except RuntimeError, ex:
isError = True
# print 'RuntimeError:', str(ex)
if not self.dnErrors.has_key(str(ex)):
nFootnote += 1
self.dnErrors[str(ex)] = nFootnote
dResult[(ch, nB)] = str(ex)
break
xElapsed += time.clock()
if isError: isError = False
else : dResult[(ch, nB)] = 1e6 * xElapsed / self.cPairs
return dResult
if __name__ == '__main__':
gcdtest(sys.argv).main()