Saturday, March 15, 2008

Matrix

For my Linear Algebra class, I decided to write some stuff in Python to do matrix calculations. Unfortunately, I never got around to finishing it.

frac.py

#!/usr/bin/python
"""A library for simple fraction calculations."""
import re
import scanf
#import scanf as scanf


class fraction(object):
top = 1
bottom = 1
sign = True
def __init__(self, top = 1, bottom = 1, sign = '+'):
self.top = top
self.bottom = bottom
if(sign == '-'):
self.sign = True
else:
self.sign = False
def decimal(self):
ret = float(self.top) / float(self.bottom)
if(self.sign):
return -ret
else:
return ret
def add(self, rhs):
newbottom = self.bottom * rhs.bottom
nstop = self.top * rhs.bottom
if(self.sign):
nstop *= -1
nrtop = rhs.top * self.bottom
if(rhs.sign):
nrtop *= -1
newtop = nstop + nrtop
return fraction(top = (newtop < 0 and -newtop or newtop), bottom = newbottom, sign = (newtop < 0 and '-' or '+'))
def subtract(self, rhs):
newbottom = self.bottom * rhs.bottom
nstop = self.top * rhs.bottom
if(self.sign):
nstop *= -1
nrtop = rhs.top * self.bottom
if(rhs.sign):
nrtop *= -1
newtop = nstop - nrtop
return fraction(top = (newtop < 0 and -newtop or newtop), bottom = newbottom, sign = (newtop < 0 and '-' or '+'))
def multiply(self, rhs):
newsign = self.sign ^ rhs.sign
return fraction(top = self.top * rhs.top, bottom = self.bottom * rhs.bottom, sign = (newsign and '-' or '+'))
def inverse(self):
return fraction(top = self.bottom, bottom = self.top, sign = (self.sign and '-' or '+'))
def divide(self, rhs):
inv = rhs.inverse()
newsign = self.sign ^ inv.sign
return fraction(self.top * inv.top, self.bottom * inv.bottom, sign = (newsign and '-' or '+'))
def reduce(self):
reduced = False
if(not self.bottom):
self.bottom = 1
if(not self.top):
self.bottom = 1
self.sign = False
return
while(not reduced):
print 'Reducing'
reduced = True
while((not self.top % 2) and (not self.bottom % 2)):
#print 'Divisible by 2'
self.top /= 2
self.bottom /= 2
reduced = False
for div in range(3, (self.top < self.bottom and self.top or self.bottom) + 1):
#print 'div:', div
if((not self.top % div) and (not self.bottom % div)):
#print 'Divisible by', div
self.top /= div
self.bottom /= div
reduced = False
def sign(self):
return self.sign
def top(self):
return self.top
def bottom(self):
return self.top
def sprint(self):
if(self.bottom == 1):
return '%s%d' % (self.sign and '-' or '', self.top)
else:
return '%s%d/%d' % (self.sign and '-' or '', self.top, self.bottom)
def stripspaces(string):
words = string.split()
string = ''
for word in words:
string += word
return string
def fraction_fromdecimal(value = '0'):
if(value == int(value)):
return fraction(top = (value < 0 and -value or value), bottom = 1, sign = (value < 0 and '-' or '+'))
else:
top = (value < 0 and -value or value)
sign = (value < 0 and '-' or '+')
bottom = 1
for i in range(2, 9):
tmp = top * i
if(tmp == int(tmp)):
tmp = fraction(int(tmp), int(bottom * i), sign)
tmp.reduce()
return tmp
for i in range(1, 10):
tmp = top * 10 * i
if(tmp == int(tmp)):
tmp = fraction(int(tmp), int(bottom * 10 * i), sign)
tmp.reduce()
return tmp
def fraction_fromstring(string = '0'):
top = 0
bottom = 1
sign = '+'
valid = False
string = stripspaces(string)
if(string.rfind('/') != -1):
vals = string.partition('/')
if(vals[0].isdigit() and vals[2].isdigit()):
top = int(vals[0])
bottom = int(vals[2])
if(top < 0):
sign = '-'
top *= -1
valid = True
else:
valid = False
elif(string.isdigit()):
top = int(string)
bottom = 1
if(top < 0):
sign = '-'
top *= -1
valid = True
else:
try:
val = float(string)
except(ValueError):
pass
else:
valid = True
return fraction_fromdecimal(val)
if(valid):
return fraction(top, bottom, sign)
else:
print 'Not a valid fraction:', string
return None

vector.py

#!/usr/bin/python
from frac import fraction, fraction_fromstring, stripspaces
class vector(object):
elements = []
def __init__(self, elems = [0, 0]):
self.elements = []
for source in elems:
if(isinstance(source, fraction)):
self.elements.append(source)
else:
self.elements.append(fraction(top = source, bottom = 1, sign = (source < 0 and '-' or '+')))
def get(self, idx = 0):
return self.elements[idx]
def set(self, idx = 0, val = 0):
ret = self.elements[idx]
if(isinstance(fraction(), source)):
self.elements[idx] = source
else:
self.elements[idx] = fraction(top = source, bottom = 1, sign = (source < 0 and '-' or '+'))
return ret
def length(self):
return len(self.elements)
def reduce(self):
for i in self.elements:
i.reduce()
def add(self, rhs):
"""Adding an integer, fraction, or vector to a vector"""
if(isinstance(rhs, vector)):
if(rhs.length() == self.length()):
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).add(rhs.get(i)))
return vector(nelems)
else:
return None
elif(isinstance(rhs, fraction)):
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).add(rhs))
return vector(nelems)
else:
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).add(fraction(top = (rhs < 0 and -rhs or rhs), bottom = 1, sign = (rhs < 0 and '-' or '+'))))
return vector(nelems)
def subtract(self, rhs):
"""Subtracting an integer, fraction, or vector from a vector"""
if(isinstance(rhs, vector)):
if(rhs.length() == self.length()):
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).subtract(rhs.get(i)))
return vector(nelems)
else:
return None
elif(isinstance(rhs, fraction)):
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).subtract(rhs))
return vector(nelems)
else:
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).subtract(fraction(top = (rhs < 0 and -rhs or rhs), bottom = 1, sign = (rhs < 0 and '-' or '+'))))
return vector(nelems)
def multiply(self, rhs):
"""Multiplying a vector by either an integer or a fraction"""
if(isinstance(rhs, vector)):
print 'Unable to multiply vector by vector'
return None
elif(isinstance(rhs, fraction)):
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).multiply(rhs))
return vector(nelems)
else:
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).multiply(fraction(top = (rhs < 0 and -rhs or rhs), bottom = 1, sign = (rhs < 0 and '-' or '+'))))
return vector(nelems)
def divide(self, rhs):
"""Dividing a vector by either an integer or a fraction"""
if(isinstance(rhs, vector)):
print 'Unable to divide vector by vector'
return None
elif(isinstance(rhs, fraction)):
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).divide(rhs))
return vector(nelems)
else:
nelems = []
slen = self.length()
for i in range(0, slen):
nelems.append(self.get(i).multiply(fraction(top = 1, bottom = (rhs < 0 and -rhs or rhs), sign = (rhs < 0 and '-' or '+'))))
return vector(nelems)
def dotp(self, rhs):
slen = self.length()
if(slen != self.length()):
return 0
ret = fraction(0, 1, '+')
for i in range(0, slen):
ret = ret.add(self.get(i).multiply(rhs.get(i)))
ret.reduce()
return ret
def sprint(self, begin = '<', end = '>'):
ret = begin + ' '
slen = self.length()
for i in range(0, slen):
ret += self.get(i).sprint()
if(i < slen - 1):
ret += ', '
ret += ' ' + end
return ret
def vector_fromstring(string = '< 0 >', begin = '<', end = '>'):
valid = False
string = stripspaces(string)
values = []
if(string[0] == begin and string[-1] == end):
valid = True
string = string[1:-1]
if(valid and string.rfind(',') != -1):
vals = string.split(',')
for i in vals:
tfrac = fraction_fromstring(i)
if(tfrac != None):
values.append(tfrac)
valid = True
else:
valid = False
break
elif(valid):
tfrac = fraction_fromstring(string)
if(tfrac != None):
values.append(tfrac)
valid = True
else:
valid = False
if(valid):
return vector(values)
else:
print 'Not a valid vector:', string
return None

if __name__ == '__main__':
vectest = vector(elems = [1, 2, 3, 4])
print 'Vector1:', vectest.sprint()
vect2 = vector(elems = [5, 6, 7, 8])
print 'Vector2:', vect2.sprint()
print '%s + %s = %s' % (vectest.sprint(), vect2.sprint(), vectest.add(vect2).sprint())
print '%s - %s = %s' % (vectest.sprint(), vect2.sprint(), vectest.subtract(vect2).sprint())
print '%s dot %s = %s' % (vectest.sprint(), vect2.sprint(), vectest.dotp(vect2).sprint())



print fraction_fromstring('1/2').sprint()
print fraction_fromstring('3 / 4').sprint()
print vector_fromstring('< 0, 1, 2, 3, 4, 5 >').sprint('[', ']')
#fractest = fraction(top = 3, bottom = 2, sign = '+')
# print 'frac:', fractest.sprint()
# print 'Decimal:', fractest.decimal()
# inv = fractest.inverse()
# print 'Inverse:', inv.sprint()
# print 'Decimal:', inv.decimal()
# result = fractest.multiply(inv)
# result.reduce()
# print 'Together make:', result.sprint()
# fractest = fraction(top = 9, bottom = 5, sign = '-')
# print 'frac:', fractest.sprint()
# print 'Decimal:', fractest.decimal()
# fract2 = fraction(top = 6, bottom = 9, sign = '+')
# fracres = fractest.multiply(fract2)
# print '%s x %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()
# fracres = fractest.divide(fract2)
# print '%s / %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()
# fracres = fractest.add(fract2)
# print '%s + %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()
# fracres = fractest.subtract(fract2)
# print '%s - %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()

matrix.py

#!/usr/bin/python
from frac import fraction, fraction_fromstring, stripspaces, fraction_fromdecimal
from vector import vector, vector_fromstring
class matrix(object):
rows = []
width = 0
def __init__(self, nrows = [vector([0])]):
self.rows = []
width = nrows[0].length()
for i in nrows:
if(isinstance(i, vector) and i.length() == width):
self.rows.append(i)
def sprint(self):
ret = '['
slen = len(self.rows)
for i in range(0, slen):
ret += self.rows[i].sprint(begin = ((not i) and '[' or ' ['), end = (i == slen - 1 and ']' or ']\n'))
ret += ']'
return ret
def transpose(self):
return matrix_from_columns(self.rows)
def reduce(self):
for i in self.rows:
i.reduce()
def echelon(self):
trows = self.rows
rcount = len(trows)
ccount = trows[0].length()
reduced = False
p = 0
for i in range(0, rcount):
rdone = False
while(not rdone):
if(not trows[i].get(p)):
for q in range(i + 1, rcount):
if(trows[q].get(p)):
tmp = trows[i]
trows[i] = trows[q]
trows[q] = tmp
break
if(trows[i].get(p)):
nrow = trows[i].divide(trows[i].get(p))
print i, ':', trows[i].sprint(), '/', trows[i].get(p).sprint()
trows[i] = nrow
rdone = True
else:
p += 1
rdone = False
print 'Cascading'
for i2 in range(i + 1, rcount):
nrow = trows[i2].subtract(trows[i].multiply(trows[i2].get(p)))
print i2, ':', trows[i2].sprint(), '-', trows[i].sprint(), 'x', trows[i2].get(p).sprint()
trows[i2] = nrow
p += 1
tmp = matrix(trows)
print tmp.sprint()
tmp.reduce()
return tmp
def matrix_from_columns(ncols = [vector([0])]):
nrows = []
width = len(ncols)
height = ncols[0].length()
for i in range(0, height):
nrows.append([])
for i in range(0, height):
for q in range(0, width):
nrows[i].append(ncols[q].get(i))
nvecs = []
for i in nrows:
nvecs.append(vector(i))
return matrix(nvecs)
if __name__ == '__main__':
vectest = vector(elems = [1, 2, 3, 4])
print 'Vector1:', vectest.sprint()
vect2 = vector(elems = [5, 6, 7, 8])
print 'Vector2:', vect2.sprint()
mattest = matrix(nrows = [vectest, vect2])
print 'Matrix:'
print mattest.sprint()
matt2 = mattest.transpose()
print 'Transpose:'
print matt2.sprint()
matt2 = mattest.echelon()
print 'Echelon:'
print matt2.sprint()

# print '%s + %s = %s' % (vectest.sprint(), vect2.sprint(), vectest.add(vect2).sprint())
# print '%s - %s = %s' % (vectest.sprint(), vect2.sprint(), vectest.subtract(vect2).sprint())
# print '%s x 10 = %s' % (vectest.sprint(), vectest.multiply(10).sprint())
# print '%s / 10 = %s' % (vectest.sprint(), vectest.divide(10).sprint())
# print '%s dot %s = %s' % (vectest.sprint(), vect2.sprint(), vectest.dotp(vect2).sprint())
#
#
#
# print fraction_fromstring('1/2').sprint()
# print fraction_fromstring('3 / 4').sprint()
# print vector_fromstring('< 0, 1, 2, 3, 4, 5 >').sprint('[', ']')
# dec = 0.11111111111111111111111111;
# print 'Decimal:', dec
# print 'Fraction:', fraction_fromdecimal(dec).sprint()
#fractest = fraction(top = 3, bottom = 2, sign = '+')
# print 'frac:', fractest.sprint()
# print 'Decimal:', fractest.decimal()
# inv = fractest.inverse()
# print 'Inverse:', inv.sprint()
# print 'Decimal:', inv.decimal()
# result = fractest.multiply(inv)
# result.reduce()
# print 'Together make:', result.sprint()
# fractest = fraction(top = 9, bottom = 5, sign = '-')
# print 'frac:', fractest.sprint()
# print 'Decimal:', fractest.decimal()
# fract2 = fraction(top = 6, bottom = 9, sign = '+')
# fracres = fractest.multiply(fract2)
# print '%s x %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()
# fracres = fractest.divide(fract2)
# print '%s / %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()
# fracres = fractest.add(fract2)
# print '%s + %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()
# fracres = fractest.subtract(fract2)
# print '%s - %s = %s' % (fractest.sprint(), fract2.sprint(), fracres.sprint())
# fracres.reduce()
# print 'Reduced:', fracres.sprint()
Post a Comment