271 lines
7.7 KiB
Python
271 lines
7.7 KiB
Python
#!/usr/bin/env python3
|
|
# -*- coding: UTF-8 -*-
|
|
#
|
|
# License: GLP3+
|
|
# Copyright 2017 meagtan
|
|
# Copyright 2022 Beat Jäckle <beat@git.jdmweb2.ch>
|
|
|
|
|
|
from fractions import Fraction
|
|
from sys import maxsize
|
|
from modp import ModP
|
|
|
|
|
|
class PAdic:
|
|
def __init__(self, p, printInvers=False):
|
|
self.p = p
|
|
|
|
# current known value
|
|
self.digitP = [] # digitP[0]=c_0; digitP[i]=c_i
|
|
self.digitN = [] # digitN[0]=c_-1; digitN[i]=c_-1-i
|
|
self.prec = 0 # current known precision, not containing trailing zeros
|
|
|
|
self.order = 0 # order/valuation of number
|
|
self.printInvers = printInvers
|
|
return None
|
|
|
|
def calc(self, prec):
|
|
# First calculation
|
|
if len(self.digitN) + len(self.digitP) == 0:
|
|
if self.value == 0:
|
|
self.zero = True
|
|
self.digitP = [0]
|
|
return None
|
|
if self.order < 0:
|
|
absorder = abs(self.order)
|
|
self.digitN = [None]*absorder
|
|
for i in range(absorder):
|
|
self.digitN[absorder-i-1] = self._nextdigit()
|
|
if absorder >= prec:
|
|
self.prec = absorder
|
|
self.digitP.append(self._nextdigit())
|
|
elif self.order > 0:
|
|
self.digitP = [0]*self.order
|
|
while len(self.digitN) + len(self.digitP) < prec:
|
|
if self.value == 0:
|
|
break
|
|
self.digitP.append(self._nextdigit())
|
|
return None
|
|
|
|
def get(self, prec, decimal=True):
|
|
self.calc(prec)
|
|
'Return value of number with given precision.'
|
|
s = ''
|
|
for d in self.digitP[::-1]:
|
|
s += str(d)
|
|
if self.digitN:
|
|
if decimal:
|
|
s += '.'
|
|
for d in self.digitN:
|
|
s += str(d)
|
|
return s
|
|
|
|
def _nextdigit(self):
|
|
'Calculate next digit of p-adic number.'
|
|
raise NotImplementedError
|
|
|
|
def getdigit(self, index):
|
|
if index < self.order:
|
|
# print('not relevant 0')
|
|
return 0
|
|
|
|
# be sure to calculate the digits
|
|
prec = index+1
|
|
if self.order < 0:
|
|
prec += abs(self.order)
|
|
self.calc(prec)
|
|
|
|
# negative index
|
|
if index < 0:
|
|
try:
|
|
return self.digitN[abs(index)-1]
|
|
except IndexError:
|
|
print('Should not happen', index)
|
|
print('__dict__', self.__dict__())
|
|
raise IndexError(
|
|
f"Digit not Found\n"
|
|
f"index: {index}\n"
|
|
f"dict: {self.__dict__()}"
|
|
)
|
|
|
|
# positive index
|
|
else:
|
|
try:
|
|
return self.digitP[index]
|
|
except IndexError:
|
|
if self.value == 0:
|
|
# print('not significant',0)
|
|
return 0
|
|
else:
|
|
print('Logical Error')
|
|
print(f'Index = {index}')
|
|
print(f'pAdic = {self.__dict__()}')
|
|
raise ValueError('Logical Error')
|
|
|
|
# return value with precision up to 32 bits
|
|
def __int__(self):
|
|
return int(self.get(32), self.p)
|
|
|
|
def __getitem__(self, index):
|
|
return self.getdigit(index)
|
|
|
|
def __str__(self):
|
|
if self.printInvers:
|
|
return self.get(32)[::-1]
|
|
return self.get(32)
|
|
|
|
def __repr__(self):
|
|
return str(self)
|
|
|
|
# arithmetic operations
|
|
def __neg__(self):
|
|
return PAdicNeg(self.p, self)
|
|
|
|
def __add__(self, other):
|
|
return PAdicAdd(self.p, self, other)
|
|
|
|
def __radd__(self, other):
|
|
return PAdicAdd(self.p, other, self)
|
|
|
|
def __sub__(self, other):
|
|
return PAdicAdd(self.p, self, PAdicNeg(self.p, other))
|
|
|
|
def __rsub__(self, other):
|
|
return PAdicAdd(self.p, other, PAdicNeg(self.p, self))
|
|
|
|
def __mul__(self, other):
|
|
return PAdicMul(self.p, self, other)
|
|
|
|
def __rmul__(self, other):
|
|
return PAdicMul(self.p, other, self)
|
|
|
|
# p-adic norm
|
|
def __abs__(self):
|
|
if self.order == maxsize:
|
|
return 0
|
|
numer = denom = 1
|
|
if self.order > 0:
|
|
numer = self.p ** self.order
|
|
if self.order < 0:
|
|
denom = self.p ** self.order
|
|
return Fraction(numer, denom)
|
|
|
|
# determines the p-value of an p-adic number
|
|
def pValue(self):
|
|
return self.order
|
|
|
|
def fractionvalue(self):
|
|
self.calc(1)
|
|
s = Fraction(0)
|
|
for (i, d) in enumerate([self.digitP[0]]+self.digitN):
|
|
s += Fraction(d, self.p**i)
|
|
return s
|
|
|
|
def getOffset(self):
|
|
if self.order >= 0:
|
|
return 0
|
|
else:
|
|
return -self.order
|
|
|
|
|
|
class PAdicConst(PAdic):
|
|
def __init__(self, p, value, printInvers=False):
|
|
super().__init__(p, printInvers)
|
|
value = Fraction(value)
|
|
|
|
# calculate valuation
|
|
if value == 0:
|
|
self.value = value
|
|
self.order = float('inf')
|
|
self.zero = True
|
|
return None
|
|
|
|
while not value.numerator % self.p:
|
|
self.order += 1
|
|
value /= self.p
|
|
while not value.denominator % self.p:
|
|
self.order -= 1
|
|
value *= self.p
|
|
self.value = value
|
|
return None
|
|
|
|
def get(self, prec, decimal=True):
|
|
if self.zero:
|
|
return '0' * prec
|
|
return PAdic.get(self, prec, decimal)
|
|
|
|
def _nextdigit(self):
|
|
'Calculate next digit of p-adic number.'
|
|
rem = int(
|
|
ModP(self.p, self.value.numerator) *
|
|
ModP(self.p, self.value.denominator)._inv()
|
|
)
|
|
self.value -= rem
|
|
self.value /= self.p
|
|
return rem
|
|
|
|
|
|
class PAdicAdd(PAdic):
|
|
'Sum of two p-adic numbers.'
|
|
def __init__(self, p, arg1, arg2, printInvers=False):
|
|
super.__init__(self, p, printInvers)
|
|
self.carry = 0
|
|
_nextdigitCache = []
|
|
self.arg1 = arg1
|
|
self.arg2 = arg2
|
|
# might be larger than this
|
|
self.order = self.prec = min(arg1.order, arg2.order)
|
|
arg1.order -= self.order
|
|
arg2.order -= self.order
|
|
# loop until first nonzero digit is found
|
|
self.index = self.order
|
|
digit = self._nextdigit()
|
|
while digit == 0:
|
|
self.index += 1
|
|
digit = self._nextdigit()
|
|
self.order = self.index
|
|
_nextdigitCache.append(digit)
|
|
|
|
def _nextdigit(self):
|
|
if _nextdigitCache:
|
|
return _nextdigitCache.pop()
|
|
s = self.arg1.getdigit(self.index) + \
|
|
self.arg2.getdigit(self.index) + self.carry
|
|
self.carry = s // self.p
|
|
self.index += 1
|
|
return s % self.p
|
|
|
|
|
|
class PAdicNeg(PAdic):
|
|
'Negation of a p-adic number.'
|
|
def __init__(self, p, arg, printInvers=False):
|
|
super.__init__(self, p, printInvers)
|
|
self.arg = arg
|
|
self.order = arg.order
|
|
|
|
def _nextdigit(self):
|
|
if self.prec == 0:
|
|
# cannot be p, 0th digit of arg must be nonzero
|
|
return self.p - self.arg.getdigit(0 - self.getOffset())
|
|
return self.p - 1 - self.arg.getdigit(self.prec - self.getOffset())
|
|
|
|
|
|
class PAdicMul(PAdic):
|
|
'Product of two p-adic numbers.'
|
|
def __init__(self, p, arg1, arg2):
|
|
PAdic.__init__(self, p)
|
|
self.carry = 0
|
|
self.arg1 = arg1
|
|
self.arg2 = arg2
|
|
self.order = arg1.order + arg2.order
|
|
self.arg1.order = self.arg2.order = 0 # TODO requires copy
|
|
self.index = 0
|
|
|
|
def _nextdigit(self):
|
|
s = sum(
|
|
self.arg1.getdigit(i) * self.arg2.getdigit(self.index - i)
|
|
for i in xrange(self.index + 1)
|
|
) + self.carry
|
|
self.carry = s // self.p
|
|
self.index += 1
|
|
return s % self.p
|