Python의 유리수를 계산하는 p발 전개

15276 단어 parigpPython

구현 준비


이것은 이번에 설치된 알고리즘이다.
$\alpha =\displaystyle\frac{1}{15},\p = 5$
(1) $p$와 $p$인자가 없는 부분으로 나뉜다
$\displaystyle\alpha =\frac{1}{3}\cdot 5^{-1}$
(2) ${\rmmod}\p$로 $p$인자가 없는 부분을 고려합니다
$\displaystyle\frac{1}{3}\equiv 2\({\rm mod}\5)$
(3) 공식 변형
$
\displaystyle\alpha =\frac{1}{3}\cdot 5^{-1}
= 2\cdot 5^{-1} +\left(\frac{1}{3} - 2\right)\cdot 5^{-1}\\
\displaystyle\\= 2\cdot 5^{-1} +\left(-\frac{5}{3}\right)\cdot 5^{-1}
= 2\cdot 5^{-1} +\left(-\frac{1}{3}\right)
$
(4) 반복(1)~(3)
$
\displaystyle\alpha =\frac{1}{3}\cdot 5^{-1}
= 2\cdot 5^{-1} +\left(\frac{1}{3} - 2\right)\cdot 5^{-1}\\
\displaystyle\\= 2\cdot 5^{-1} + (-\frac{5}{3})\cdot 5^{-1}
= 2\cdot 5^{-1} +\left(-\frac{1}{3}\right)\\
\displaystyle\\= 2\cdot 5^{-1} + (-\frac{1}{3})
= 2\cdot 5^{-1} + 3\cdot 5^0 +\left(-\frac{1}{3} - 3\right)\cdot 5^0\\
\displaystyle\\= 2\cdot 5^{-1} + 3\cdot 5^0 +\left(-\frac{2}{3}\right)\cdot 5^1
=\cdots
$

실시


여기 뒀어.
import math

def get_num_divisible(n, p):
    i = 1
    while n % p ** i == 0:
        i += 1
    return i - 1

def get_inv_elem(n, p):
    if n % p == 0:
        return False
    for i in range(1, p):
        if i * n % p == 1:
            return i

def get_p_adic(frac, p, prec=10):
    if frac[1] == 0:
        return False
    index_dict = {}
    p_pow = get_num_divisible(frac[0], p) - get_num_divisible(frac[1], p)
    i = p_pow
    while i < prec:
        if frac[0] == 0:
            index_dict[i] = 0
            i += 1
            continue
        p_pow = get_num_divisible(frac[0], p) - get_num_divisible(frac[1], p)
        if p_pow == i:
            if p_pow > 0:
                beta = [int(frac[0] / p ** p_pow), frac[1]]
            elif p_pow < 0:
                beta = [frac[0], int(frac[1] / p ** - p_pow)]
            else:
                beta = frac
            x = get_inv_elem(beta[1], p)
            a = beta[0] * x % p
            index_dict[i] = a
            frac = [int((beta[0] - a * beta[1]) * p ** p_pow), beta[1]]
        else:
            index_dict[i] = 0
        i += 1
    return index_dict

def convert_to_formula(index_dict, p):
    if not index_dict:
        return False
    f = ''
    for k, v in index_dict.items():
        if v > 1:
            f += str(v) + '*' + str(p) + '^' + str(k) + ' + '
        elif v == 1:
            f += str(p) + '^' + str(k) + ' + '
        elif v  == 0:
            pass
    f += f'O({p}^{list(index_dict.keys())[-1] + 1})'
    return f

if __name__ == '__main__':
    p = 3
    prec = 10
    frac = [2, 5]
    index_dict = get_p_adic(frac, p, prec)
    f = convert_to_formula(index_dict, p)
    print('p = {}, alpha = {}/{} のp進展開:\n  {}'.format(p, frac[0], frac[1], f))

실행 예


소수 $p$와 유리수 $\alpha$, $\alpha$의 $\mathbb {Q}_p$의 $p$진전을 찾으십시오.

실행 예1


$p = 3,\\alpha =\displaystyle\frac{2}{5}$
p = 3, alpha = 2/5 のp進展開:
  3^0 + 3^1 + 2*3^2 + 3^3 + 3^5 + 2*3^6 + 3^7 + 3^9 + O(3^10)
PARI/GP
gp > 2/5 + O(3^10)
%24 = 1 + 3 + 2*3^2 + 3^3 + 3^5 + 2*3^6 + 3^7 + 3^9 + O(3^10)

실행 예2


$p = 5,\\alpha =\displaystyle\frac{1}{15}$
p = 5, alpha = 1/15 のp進展開:
  2*5^-1 + 3*5^0 + 5^1 + 3*5^2 + 5^3 + 3*5^4 + 5^5 + 3*5^6 + 5^7 + 3*5^8 + 5^9 + 3*5^10 + 5^11 + O(5^12)
PARI/GP
gp > 1/15 + O(5^12)
%25 = 2*5^-1 + 3 + 5 + 3*5^2 + 5^3 + 3*5^4 + 5^5 + 3*5^6 + 5^7 + 3*5^8 + 5^9 + 3*5^10 + 5^11 + O(5^12)

실행 예3


$p = 7,\\alpha =\displaystyle\frac{49}{5}$
p = 7, alpha = 49/5 のp進展開:
  3*7^2 + 7^3 + 4*7^4 + 5*7^5 + 2*7^6 + 7^7 + 4*7^8 + 5*7^9 + 2*7^10 + O(7^11)
処理時間: 0.0
PARI/GP
gp > 49/5 + O(7^11)
%26 = 3*7^2 + 7^3 + 4*7^4 + 5*7^5 + 2*7^6 + 7^7 + 4*7^8 + 5*7^9 + 2*7^10 + O(7^11)

PARI/GP


이번에 비교적 사용된 PARI/GP는 수론의 계산 소프트웨어이다.x + O(p^k)에서 p진법의 근사치를 구할 수 있다.
gp > 1/15 + O(5^10)
%19 = 2*5^-1 + 3 + 5 + 3*5^2 + 5^3 + 3*5^4 + 5^5 + 3*5^6 + 5^7 + 3*5^8 + 5^9 + O(5^10)

위의 그림에서 보듯이 SageMath의 CoCalc를 사용하여 Python에서 PARI/GP를 사용할 수 있습니다.
다음 빨간색 상자에서 아이콘을 클릭합니다.

CoCalc Now 실행을 클릭합니다.

SageMath 를 클릭합니다.

참고 자료


PARI/GP 공식 사이트입니다.
이 슬라이드는 통속적이고 알기 쉽게 설명한다.
명령은 이곳의 참고에 요약되어 있다.
이 보도는 매우 세밀하고 꼼꼼하게 정리되었다.
나는 Qiita에도 자세한 설명이 있는 것을 발견했다.
여기에는 SageMath에 대한 내용이 자세히 나와 있습니다.
이것은 SageMath의 빠른 참조입니다.명령이 정리되어 쉽게 볼 수 있다.

좋은 웹페이지 즐겨찾기