# -*- coding: utf-8 -*-
import sys
from sage.all import *
import datetime
import os
import os.path
from benchmark import *
###
# This file will usually not need any alteration. Create subclasses of FactorizationFunction.
###
class FactorizationFunctionCharacteristics(object):
def __init__(self):
self.canFactorizePrimes = False
self.canFactorizeNonPrimes = False
def __str__(self):
return "Factorization Function Characteristics <Can factorize primes: %c, Can factorize non-primes: %c>"%(self.canFactorizePrimes, self.canFactorizeNonPrimes)
def __repr__(self):
return "Factorization Function Characteristics <Can factorize primes: %c, Can factorize non-primes: %c>"%(self.canFactorizePrimes, self.canFactorizeNonPrimes)
# FactorizationFunction is inherited to create benchmarkable, testable factorization functions
class FactorizationFunction(object):
@classmethod
# Return characteristics of the specific algorithm
def getCharacteristics(self):
return None
@classmethod
# Run factorization
# n: number to factor
# returnBenchmark: return factors if False, tuple of (factors, benchmark) if True
def factorize(self, n, returnBenchmark=False):
return (None, None)
@classmethod
# Runs benchmark on the factorization function
# iterations: number of times to run the function
# numberOfFactors: number of factors included in factorized number
# factorLowerLimit: lower limit from which primes are generated
# factorUpperLimit: upper limit from which primes are generated
# Returns tuple (times, iterations)
def benchmark(self, numberSuite, iterations=10, optionalArgs={}, start=2, end=None, skipFactors=None, mode="factors"):
benchmarks = []
description, suite = numberSuite
modeLine = "Unknown"
if mode == "factors":
modeLine = "Number of factors"
elif mode == "bits":
modeLine = "Number of bits"
now = datetime.datetime.now()
name = str(self)
name = name[name.rfind(".")+1:-2]
filename = "./benchmarks/%s_%s.txt"%(name, now.strftime('%Y-%m-%d_%H:%M:%S'))
originalFilename = filename[:-4]
serial = 1
while os.path.isfile(filename):
filename = "%s_%d.txt"%(originalFilename, serial)
serial += 1
def writeToFile(line):
mode = "a" if os.path.exists(filename) else "w"
handle = open(filename, mode)
handle.write(line + "\n")
handle.close()
# Write header and description to file
def formatParameter(parameter):
string = str(parameter)
if "<function" in string:
string = string.split(" ")[1]
return string
def formatParameters(parameters):
if isinstance(parameters, list):
return "[%s]"%', '.join(map(formatParameter, parameters))
return str(parameters)
writeToFile("# %s"%name + (" (%s)"%",".join("%s: %s"%(pair[0], formatParameters(pair[1])) for pair in optionalArgs.items()) if len(optionalArgs) > 0 else ""))
writeToFile("# %s"%description)
writeToFile("%s:Number to factorize:Time taken:Iterations taken"%modeLine)
for numberOfFactors, numbers in suite:
if numberOfFactors < start:
continue
if end is not None and numberOfFactors > end:
continue
if skipFactors is not None:
if callable(skipFactors) and skipFactors(numberOfFactors):
continue
bs = []
for i in range(iterations):
for n, factors in numbers:
resultingFactors, b = self.factorize(n, true, **optionalArgs)
# Only take into account correct factorizations
if sorted(resultingFactors) == sorted(factors):
bs.append(b)
formattedTime = ",".join("%s-%f"%pair for pair in b.totalTime.items())
formattedIterations = ",".join("%s-%d"%pair for pair in b.iterations.items())
writeToFile("%d:%d:%s:%s"%(numberOfFactors, n, formattedTime, formattedIterations))
benchmarks.append((numberOfFactors, bs))
# Result, one tuple per number of factors:
# (numberOfFactors, minimum benchmark, maximum benchmark, average benchmark)
res = [(bs[0], Benchmark.min(bs[1]), Benchmark.max(bs[1]), Benchmark.average(bs[1])) for bs in benchmarks]
return res
@classmethod
def testFactorization(self, cases, truths, optionalArgs):
passed = True
for i in range(len(cases)):
n = cases[i]
truth = sorted(truths[i])
result = sorted(self.factorize(n, **optionalArgs))
factorString = "*".join(str(x) for x in truth)
def togglePassed(passed):
if passed:
print u"✘"
passed = False
return passed
if result is None:
passed = togglePassed(passed)
print "Can factorize %d=%s: ✘"%(n, factorString)
print "\t Expected: ", truth
print "\t Got: None. Most likely means that the function does not support the given input"
elif result != truth:
passed = togglePassed(passed)
print u"Can correctly factor %d=%s: ✘"%(n, factorString)
print "\t Expected: ", truth
print "\t Got: ", result
if passed:
print u"✓"
@classmethod
# Runs test on the factorization function
# optionalArgs is expected to be a map and is passed to factorize function
def test(self, optionalArgs={}):
testFunctions = filter(lambda x : x.find("test") == 0 and x != "test" and x != "testFactorization", dir(self))
if len(testFunctions) > 0:
print "=== Common Tests ==="
print "Can run factorization function: ",
try:
self.factorize(15)
print u"✓"
except:
print u"✘"
print "Will abort tests due to error in factorization function"
return
c = self.getCharacteristics()
if c.canFactorizePrimeComposites:
print "Can factorize one or more primes: ",
cases = [2, 3, 5, 7, 11, 15, 21, 25, 45, 77, 121, 169, 21853]
truths = [[1, 2], [1, 3], [1, 5], [1, 7], [1, 11], [1, 3, 5], [1, 3, 7], [1, 5, 5], [1, 3, 3, 5], [1, 7, 11], [1, 11, 11], [1, 13, 13], [1, 13, 41, 41]]
self.testFactorization(cases, truths, optionalArgs)
else:
print u"Can factorize one or more primes: ✘ (Not supported)"
if c.canFactorizeEvenComposites:
print "Can factorize one or more non-primes: ",
cases = [2, 4, 12, 20, 30]
truths = [[1, 2], [1, 2, 2], [1, 2, 2, 3], [1, 2, 2, 5], [1, 2, 3, 5]]
self.testFactorization(cases, truths, optionalArgs)
else:
print u"Can factorize one or more non-primes: ✘ (Not supported)"
# Run class specific tests
if len(testFunctions) > 0:
print "\n=== Algorithm Specific Tests ==="
for func in testFunctions:
method = getattr(self, func)
method()