A Dictionary-Based Polynomial Class
class Polynomial:
def __init__(self, coeffs):
if type(coeffs) == type({0:1}):
self.coeffs = coeffs
elif type(coeffs) == type([]):
out = {}
for k in range(len(coeffs)):
out[k] = coeffs[k]
self.coeffs = out
#print(self.coeffs)
@staticmethod
def descending(n, k):
out = 1
for j in range(n, n - k, -1):
out *= j
return out
def __str__(self):
k = list(self.coeffs.keys())
k.sort()
out = ""
for j in k:
if j == 0:
out += str(self.coeffs[j])
elif j == 1:
out += " + " + str(self.coeffs[j]) + "x"
else:
out += " + " + str(self.coeffs[j]) + "x^" + str(j)
return out
def __add__(self, other):
s = set()
for k in self.coeffs.keys():
s.add(k)
for k in other.coeffs.keys():
s.add(k)
l = list(s)
l.sort()
out = {}
for k in range(len(l)):
if k in self.coeffs.keys() and k in other.coeffs.keys():
out[k] = self.coeffs[k] + other.coeffs[k]
elif k in self.coeffs.keys():
out[k] = self.coeffs[k]
elif k in other.coeffs.keys():
out[k] = other.coeffs[k]
return Polynomial(out)
def __sub__(self, other):
s = set()
for k in self.coeffs.keys():
s.add(k)
for k in other.coeffs.keys():
s.add(k)
l = list(s)
l.sort()
out = {}
for k in range(len(l)):
if k in self.coeffs.keys() and k in other.coeffs.keys():
out[k] = self.coeffs[k] - other.coeffs[k]
elif k in self.coeffs.keys():
out[k] = self.coeffs[k]
elif k in other.coeffs.keys():
out[k] = -other.coeffs[k]
return Polynomial(out)
def __mul__(self, other):
coefficients = {}
d = self.deg() + other.deg()
for k in range(d, -1, -1):
total = 0
for j in range(0, k + 1):
total += self.coeff(j)*other.coeff(k - j)
if total != 0:
coefficients[k] = total
return Polynomial(coefficients)
def __pow__(self, n):
if n < 0:
raise ValueError
if n == 0:
return Polynomial({0:1})
if n % 2 == 0:
return (self*self)**(n//2)
return self*(self*self)**(n//2)
def __call__(self, x):
n = self.deg()
out = self.coeff(n)
for k in range(n, 0, -1):
out = out*x + self.coeff(k - 1)
return out
def deg(self):
return max(self.coeffs.keys())
def derivative(self, n = 1):
if self.deg() < n:
return Polynomial({0:0})
d = dict()
l = list(self.coeffs.keys())
l = [k for k in l if k >= n]
l.sort()
for k in l:
d[k - n] = Polynomial.descending(k, n)*self.coeffs[k]
#print("descending({}, {}) = {}".format(k, n, Polynomial.descending(n,k)))
return Polynomial(d)
def coeff(self, k):
if k not in self.coeffs.keys():
return 0
return self.coeffs[k]
def is_root(self, x):
return self(x) == 0
def reduceOrder(self, x):
if not self.is_root(x):
raise ValueError
if __name__ == "__main__":
f = Polynomial({0:1, 1:3, 2:2})
print(f)
print(f"f(2) = {f(2)}")
p = Polynomial({0:3, 1:4, 2:5})
q = Polynomial({0:5, 1:7, 2:1, 3:1})
print(p)
print(p.derivative())
print(p.derivative(2))
print(p(1))
print(q)
print(q(1))
print(p + q)
print(p - q)
p = Polynomial({1:5, 3:6, 5:10, 100:1})
print(p)
print(p(2))
p = Polynomial([1,1,1,1,1])
print(p)
print(p(2))
a = Polynomial([1, 1])
b = Polynomial([2, 1])
c = Polynomial([3, 1])
print(a)
print(b)
c = b**100
print(c(3))
print(f"a*b*c = {a*b*c}")
print(f"b**100 = {b**100}")
Extended-Precison Rational Arithmetic in Python
Dependency You need this module to make the BigFraction class work.
"""This module provides some basic number-theoretic
functions."""
def gcd(a,b):
"""
a:int
b:int
returns: The greatest common divisor of a and b
throws: ValueError if a == 0 && b == 0
"""
if a == 0 and b == 0:
raise ValueError
if a < 0:
a = -a
if b < 0:
b = -b
if a == 0:
return abs(b)
if b == 0:
return abs(a)
while b%a > 0:
b, a = a, b%a
return a
def smallest_factor(n):
"""
n:int n should satisfy n >= 2
returns: the smallest factor of n that is at least 2.
"""
if n%2 == 0:
return 2
k = 3
while k*k <= n:
if n%k == 0:
return k
k += 2
return n
def prime_factorization(n):
"""
n: int n should satisfy n >= 2
returns: a list containing the prime factors of
n in ascending order
"""
out = []
while n > 1:
d = smallest_factor(n)
print(d)
n = n//d
out.append(d)
return out
def is_prime(n):
"""
n: int n should satisfy n >= 2
returns: True if n is a prime number
"""
if n%2 == 0:
return 2
k = 3
while k*k <= n:
if n%k == 0:
return False
k += 2
return True
def primes_to(n):
out = [2]
k = 3
while k <= n:
j = 0
while out[j]*out[j] <= k and k%out[j] != 0:
j += 1
if out[j]*out[j] > k:
out.append(k)
k += 2
return out
if __name__ == "__main__":
print(gcd(7776, 1048576))
print(gcd(95238908341908231432498324980875, 34904249809812494329625))
print(prime_factorization(1048575))
print(is_prime(1000009))
print(prime_factorization(1000009))
BigFraction.py
from number_theory import gcd
class BigFraction:
"""This is a class for performing extended-precision rational
arithmetic. It includes a full suite of operators for arithmetic
and it produces a sortable objects, ordered by their numerical
values.
All BigFractions are stored in a canonical form: they are fully
reduced and any negative is stored in the numerator.
This class has three static constants
ZERO, the BigFraction representing 0
ONE, the BigFraction representing 1
HALF, the BigFraction representing 1/2
"""
ZERO = None
ONE = None
HALF = None
def __init__(self, num, denom):
"""This accepts two integer argments, a numerator
and a denominator. A zero denominator will trigger a ValueError."""
if denom == 0:
raise ValueError
if denom < 0:
num = -num
denom = -denom
d = gcd(num, denom)
self.num = num//d
self.denom = denom//d
def __str__(self):
"""This returns a string represenation for this
BigFraction of the form numerator/denominator."""
return f"{self.num}/{self.denom}"
def __repr__(self):
"""This returns a string representation of the form
BigFraction(numerator, denominator) suitable for the Python
REPL"""
return f"BigFraction({self.num}, {self.denom})"
def __add__(self, other):
"""This defines + and returns the sum of two BigFractions."""
top = self.num*other.denom + self.denom*other.num
bottom = self.denom*other.denom
return BigFraction(top, bottom)
def __sub__(self, other):
"""This defines - and returns the difference of two BigFractions."""
top = self.num*other.denom - self.denom*other.num
bottom = self.denom*other.denom
return BigFraction(top, bottom)
def __mul__(self, other):
"""This defines * and returns the product of two BigFractions."""
top = self.num*other.num
bottom = self.denom*other.denom
return BigFraction(top, bottom)
def __truediv__(self, other):
"""This defines / and returns the quotient of two BigFractions."""
top = self.num*other.denom
bottom = self.denom*other.num
return BigFraction(top, bottom)
def __pow__(self, n):
"""This defines ** and returns this BigFraction raised to the
nth power. This works for both positive and negative integers."""
if n == 0:
return BigFraction(1,1)
if n > 0:
return BigFraction(self.num**n, self.denom**n)
n = -n
return BigFraction(self.denom**n, self.num**n)
@staticmethod
def init_static():
"""initializes the static constants ZERO, HALF, and ONE."""
BigFraction.ZERO = BigFraction(0,1)
"""The Big Fraction 0/1"""
BigFraction.ONE = BigFraction(1,1)
"""The Big Fraction 1/1"""
BigFraction.HALF = BigFraction(1,2)
"""The Big Fraction 1/2"""
BigFraction.init_static()
Extended-Precison Rational Arithmetic in Java
import java.math.BigInteger;
public class BigFraction
{
public static final BigFraction ZERO;
public static final BigFraction HALF;
public static final BigFraction ONE;
static
{
ZERO = BigFraction.valueOf(0,1);
HALF = BigFraction.valueOf(1,2);
ONE = BigFraction.valueOf(1,1);
}
private final BigInteger num;
private final BigInteger denom;
public BigFraction(BigInteger num, BigInteger denom)
{
if(denom.equals(BigInteger.ZERO))
{
throw new IllegalArgumentException();
}
if(denom.compareTo(BigInteger.ZERO) < 0)
{
num = num.negate();
denom = denom.negate();
}
BigInteger d = num.gcd(denom);
this.num = num.divide(d);
this.denom = denom.divide(d);
}
@Override
public String toString()
{
return String.format("%s/%s", num, denom);
}
public static BigFraction valueOf(long num, long denom)
{
return new BigFraction(BigInteger.valueOf(num),
BigInteger.valueOf(denom));
}
public BigFraction add(BigFraction that)
{
BigInteger top = num.multiply(that.denom).add(
denom.multiply(that.num));
BigInteger bottom = denom.multiply(that.denom);
return new BigFraction(top, bottom);
}
public BigFraction subtract(BigFraction that)
{
BigInteger top = num.multiply(that.denom).subtract(
denom.multiply(that.num));
BigInteger bottom = denom.multiply(that.denom);
return new BigFraction(top, bottom);
}
public BigFraction multiply(BigFraction that)
{
BigInteger top = num.multiply(that.num);
BigInteger bottom = denom.multiply(that.denom);
return new BigFraction(top, bottom);
}
public BigFraction divide(BigFraction that)
{
BigInteger top = num.multiply(that.denom);
BigInteger bottom = denom.multiply(that.num);
return new BigFraction(top, bottom);
}
public BigFraction pow(int n)
{
if n == 0:
{
return BigFraction.valueOf(1,1);
}
if n > 0:
{
return BigFraction(num.pow(n), denom.pow(n));
}
n = -n;
return BigFraction(denom.pow(n), num.pow(n));
}
}