"""
n승근 루트k 계산기 ─ Nth Root Function 기반 개방법
======================================================
박찬우 프레임워크 핵심 공식
f_n(x, y) = Σ_{r=1}^{n} C(n,r)·(10x)^(n-r)·y^(r-1)
성질: (10x + y)^n − (10x)^n = f_n(x, y) × y
나머지 점화식:
M_{k+1} = M_k · 10^n − f_n(현재몫, y) × y ≥ 0
특수값:
n=2 : f_2(x,y) = 20x + y
n=3 : f_3(x,y) = 300x² + 30xy + y²
"""
try:
from math import comb # Python 3.8+
except ImportError:
from functools import reduce # Python 3.7 fallback
def comb(n, k):
"""이항계수 C(n, k) — math.comb 없는 환경용 (Python 3.7)"""
if k < 0 or k > n:
return 0
k = min(k, n - k)
num = reduce(lambda a, b: a * b, range(n, n - k, -1), 1)
den = reduce(lambda a, b: a * b, range(1, k + 1), 1)
return num // den
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 핵심 함수
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
def f_n(x: int, y: int, n: int) -> int:
"""
Nth Root Function
f_n(x, y) = Σ_{r=1}^{n} C(n,r)·(10x)^(n-r)·y^(r-1)
성질
· f_n(x,y)×y = (10x+y)^n − (10x)^n
· f_n(0,z) = z^(n-1)
"""
return sum(
comb(n, r) * (10 * x) ** (n - r) * y ** (r - 1)
for r in range(1, n + 1)
)
def nth_root(k: int, n: int, decimal_digits: int = 10,
verbose: bool = True) -> str:
"""
ⁿ√k 를 decimal_digits 소수점 자리까지 계산.
알고리즘
1. K = k·10^(n·d) 로 스케일링 (d = decimal_digits)
2. K 를 n 자리씩 묶어 왼쪽부터 처리
3. 각 단계: f_n(현재몫, y)×y ≤ 나머지 인 최대 y(0~9) 선택
4. M_{k+1} = M_k·10^n − f_n(·,y)×y
Returns
결과 문자열 예) "2.449489"
"""
if k <= 0 or n < 2 or decimal_digits < 0:
raise ValueError("k>0, n≥2, decimal_digits≥0 이어야 합니다.")
# ── 1. 스케일링 ────────────────────────────────────────
# ⁿ√(k·10^(n·d)) = ⁿ√k · 10^d
# → 정수 n제곱근을 구하면 소수점 d자리를 포함한 정수를 얻는다
K = k * (10 ** (n * decimal_digits))
# ── 2. n자리 그룹 분할 ─────────────────────────────────
K_str = str(K)
pad = (-len(K_str)) % n # 왼쪽 0 패딩 (n의 배수 맞추기)
K_str = '0' * pad + K_str
groups = [int(K_str[i:i + n]) for i in range(0, len(K_str), n)]
# ── 3. 자릿수별 처리 ───────────────────────────────────
quotient = 0 # 현재까지 구한 몫 q
remainder = 0 # 현재 나머지 M
BAR = '─' * 62
if verbose:
print(f"\n{'━'*62}")
print(f" {n}√{k} (소수점 {decimal_digits}자리)")
print(f" f_{n}(x,y) = Σ C({n},r)·(10x)^({n}-r)·y^(r-1)")
print(f"{'━'*62}")
for step, g in enumerate(groups):
# 다음 그룹 내려받기
remainder = remainder * (10 ** n) + g
base = 10 * quotient
target = base ** n + remainder # (10q)^n + M
# 최대 y 탐색: (base+y)^n ≤ target
y = 0
for cand in range(9, -1, -1):
if (base + cand) ** n <= target:
y = cand
break
# Nth Root Function 계산 및 나머지 갱신
fval = f_n(quotient, y, n)
fval_y = fval * y # = (base+y)^n − base^n
new_rem = remainder - fval_y # M_{k+1}
if verbose:
label = f"z={y}" if step == 0 else f"y={y}"
print(f"\n Step {step+1:>2} 그룹[{g:0{n}d}] 나머지={remainder}")
print(f" 현재 몫 x={quotient} → {label}")
print(f" f_{n}({quotient},{y}) = {fval}")
print(f" f·y = {fval}×{y} = {fval_y}")
print(f" 새 나머지 M = {remainder}−{fval_y} = {new_rem}")
print(f" {BAR}")
remainder = new_rem
quotient = quotient * 10 + y
# ── 4. 결과 포매팅 ─────────────────────────────────────
int_part = quotient // (10 ** decimal_digits)
frac_part = quotient % (10 ** decimal_digits)
result = (f"{int_part}.{str(frac_part).zfill(decimal_digits)}"
if decimal_digits > 0 else str(int_part))
if verbose:
from decimal import Decimal, getcontext
getcontext().prec = decimal_digits + 30
check = Decimal(result) ** n
print(f"\n 결 과 : {n}√{k} ≈ {result}")
print(f" 검 증 : ({result})^{n} = {str(check)[:decimal_digits + 8]}")
print(f" 최종 M : {remainder}")
print(f"{'━'*62}\n")
return result
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 유틸리티
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
def print_fn_formula(n: int) -> None:
"""n에 대한 f_n(x,y) 전개식 출력"""
terms = []
for r in range(1, n + 1):
c = comb(n, r)
exp_x = n - r
exp_y = r - 1
t = ""
if c != 1:
t += str(c)
if exp_x > 1:
t += f"(10x)^{exp_x}"
elif exp_x == 1:
t += "(10x)"
if exp_y > 1:
t += f"y^{exp_y}"
elif exp_y == 1:
t += "y"
if not t:
t = "1"
terms.append(t)
print(f" f_{n}(x,y) = {' + '.join(terms)}")
def print_fn_table(n: int, x_range: range = range(6)) -> None:
"""f_n(x, y) 값 테이블 (x 행, y 열)"""
header = "x\\y"
print(f"\n f_{n}(x, y) 값 테이블")
print(f" {header:>5}", end="")
for y in range(10):
print(f"{y:>14}", end="")
print()
print(" " + "─" * (5 + 14 * 10))
for x in x_range:
print(f" {x:>5}", end="")
for y in range(10):
print(f"{f_n(x, y, n):>14}", end="")
print()
print()
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 메인
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
def run_examples() -> None:
"""사전 예제 실행"""
# f_n 전개식 확인
print("\n ■ f_n(x,y) 전개식")
for n in [2, 3, 4, 5]:
print_fn_formula(n)
# 예제 1: √6 (책에 나온 예제)
nth_root(6, 2, decimal_digits=4)
# 예제 2: √2
nth_root(2, 2, decimal_digits=6)
# 예제 3: ∛2
nth_root(2, 3, decimal_digits=5)
# 예제 4: ⁴√625 (= 5)
nth_root(625, 4, decimal_digits=4)
# 고정밀도
print(" ■ 고정밀도: √2 (50자리)")
r = nth_root(2, 2, decimal_digits=50, verbose=False)
print(f" √2 ≈ {r}\n")
print(" ■ 고정밀도: ∛10 (30자리)")
r = nth_root(10, 3, decimal_digits=30, verbose=False)
print(f" ∛10 ≈ {r}\n")
def interactive() -> None:
"""대화형 입력"""
print("\n" + "━" * 62)
print(" n승근 루트k 계산기 (종료: Ctrl+C)")
print("━" * 62)
while True:
try:
k = int(input("\n k (양의 정수) : "))
n = int(input(" n (2 이상) : "))
d = int(input(" 소수점 자릿수 : "))
v = input(" 단계별 출력? (y/n, 기본 y) : ").strip().lower()
nth_root(k, n, decimal_digits=d, verbose=(v != 'n'))
except ValueError as e:
print(f" 입력 오류: {e}")
except KeyboardInterrupt:
print("\n 종료합니다.")
break
if __name__ == "__main__":
run_examples()
interactive()
n승근 루트k 계산기 ─ Nth Root Function 기반 개방법
======================================================
박찬우 프레임워크 핵심 공식
f_n(x, y) = Σ_{r=1}^{n} C(n,r)·(10x)^(n-r)·y^(r-1)
성질: (10x + y)^n − (10x)^n = f_n(x, y) × y
나머지 점화식:
M_{k+1} = M_k · 10^n − f_n(현재몫, y) × y ≥ 0
특수값:
n=2 : f_2(x,y) = 20x + y
n=3 : f_3(x,y) = 300x² + 30xy + y²
"""
try:
from math import comb # Python 3.8+
except ImportError:
from functools import reduce # Python 3.7 fallback
def comb(n, k):
"""이항계수 C(n, k) — math.comb 없는 환경용 (Python 3.7)"""
if k < 0 or k > n:
return 0
k = min(k, n - k)
num = reduce(lambda a, b: a * b, range(n, n - k, -1), 1)
den = reduce(lambda a, b: a * b, range(1, k + 1), 1)
return num // den
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 핵심 함수
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
def f_n(x: int, y: int, n: int) -> int:
"""
Nth Root Function
f_n(x, y) = Σ_{r=1}^{n} C(n,r)·(10x)^(n-r)·y^(r-1)
성질
· f_n(x,y)×y = (10x+y)^n − (10x)^n
· f_n(0,z) = z^(n-1)
"""
return sum(
comb(n, r) * (10 * x) ** (n - r) * y ** (r - 1)
for r in range(1, n + 1)
)
def nth_root(k: int, n: int, decimal_digits: int = 10,
verbose: bool = True) -> str:
"""
ⁿ√k 를 decimal_digits 소수점 자리까지 계산.
알고리즘
1. K = k·10^(n·d) 로 스케일링 (d = decimal_digits)
2. K 를 n 자리씩 묶어 왼쪽부터 처리
3. 각 단계: f_n(현재몫, y)×y ≤ 나머지 인 최대 y(0~9) 선택
4. M_{k+1} = M_k·10^n − f_n(·,y)×y
Returns
결과 문자열 예) "2.449489"
"""
if k <= 0 or n < 2 or decimal_digits < 0:
raise ValueError("k>0, n≥2, decimal_digits≥0 이어야 합니다.")
# ── 1. 스케일링 ────────────────────────────────────────
# ⁿ√(k·10^(n·d)) = ⁿ√k · 10^d
# → 정수 n제곱근을 구하면 소수점 d자리를 포함한 정수를 얻는다
K = k * (10 ** (n * decimal_digits))
# ── 2. n자리 그룹 분할 ─────────────────────────────────
K_str = str(K)
pad = (-len(K_str)) % n # 왼쪽 0 패딩 (n의 배수 맞추기)
K_str = '0' * pad + K_str
groups = [int(K_str[i:i + n]) for i in range(0, len(K_str), n)]
# ── 3. 자릿수별 처리 ───────────────────────────────────
quotient = 0 # 현재까지 구한 몫 q
remainder = 0 # 현재 나머지 M
BAR = '─' * 62
if verbose:
print(f"\n{'━'*62}")
print(f" {n}√{k} (소수점 {decimal_digits}자리)")
print(f" f_{n}(x,y) = Σ C({n},r)·(10x)^({n}-r)·y^(r-1)")
print(f"{'━'*62}")
for step, g in enumerate(groups):
# 다음 그룹 내려받기
remainder = remainder * (10 ** n) + g
base = 10 * quotient
target = base ** n + remainder # (10q)^n + M
# 최대 y 탐색: (base+y)^n ≤ target
y = 0
for cand in range(9, -1, -1):
if (base + cand) ** n <= target:
y = cand
break
# Nth Root Function 계산 및 나머지 갱신
fval = f_n(quotient, y, n)
fval_y = fval * y # = (base+y)^n − base^n
new_rem = remainder - fval_y # M_{k+1}
if verbose:
label = f"z={y}" if step == 0 else f"y={y}"
print(f"\n Step {step+1:>2} 그룹[{g:0{n}d}] 나머지={remainder}")
print(f" 현재 몫 x={quotient} → {label}")
print(f" f_{n}({quotient},{y}) = {fval}")
print(f" f·y = {fval}×{y} = {fval_y}")
print(f" 새 나머지 M = {remainder}−{fval_y} = {new_rem}")
print(f" {BAR}")
remainder = new_rem
quotient = quotient * 10 + y
# ── 4. 결과 포매팅 ─────────────────────────────────────
int_part = quotient // (10 ** decimal_digits)
frac_part = quotient % (10 ** decimal_digits)
result = (f"{int_part}.{str(frac_part).zfill(decimal_digits)}"
if decimal_digits > 0 else str(int_part))
if verbose:
from decimal import Decimal, getcontext
getcontext().prec = decimal_digits + 30
check = Decimal(result) ** n
print(f"\n 결 과 : {n}√{k} ≈ {result}")
print(f" 검 증 : ({result})^{n} = {str(check)[:decimal_digits + 8]}")
print(f" 최종 M : {remainder}")
print(f"{'━'*62}\n")
return result
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 유틸리티
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
def print_fn_formula(n: int) -> None:
"""n에 대한 f_n(x,y) 전개식 출력"""
terms = []
for r in range(1, n + 1):
c = comb(n, r)
exp_x = n - r
exp_y = r - 1
t = ""
if c != 1:
t += str(c)
if exp_x > 1:
t += f"(10x)^{exp_x}"
elif exp_x == 1:
t += "(10x)"
if exp_y > 1:
t += f"y^{exp_y}"
elif exp_y == 1:
t += "y"
if not t:
t = "1"
terms.append(t)
print(f" f_{n}(x,y) = {' + '.join(terms)}")
def print_fn_table(n: int, x_range: range = range(6)) -> None:
"""f_n(x, y) 값 테이블 (x 행, y 열)"""
header = "x\\y"
print(f"\n f_{n}(x, y) 값 테이블")
print(f" {header:>5}", end="")
for y in range(10):
print(f"{y:>14}", end="")
print()
print(" " + "─" * (5 + 14 * 10))
for x in x_range:
print(f" {x:>5}", end="")
for y in range(10):
print(f"{f_n(x, y, n):>14}", end="")
print()
print()
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
# 메인
# ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
def run_examples() -> None:
"""사전 예제 실행"""
# f_n 전개식 확인
print("\n ■ f_n(x,y) 전개식")
for n in [2, 3, 4, 5]:
print_fn_formula(n)
# 예제 1: √6 (책에 나온 예제)
nth_root(6, 2, decimal_digits=4)
# 예제 2: √2
nth_root(2, 2, decimal_digits=6)
# 예제 3: ∛2
nth_root(2, 3, decimal_digits=5)
# 예제 4: ⁴√625 (= 5)
nth_root(625, 4, decimal_digits=4)
# 고정밀도
print(" ■ 고정밀도: √2 (50자리)")
r = nth_root(2, 2, decimal_digits=50, verbose=False)
print(f" √2 ≈ {r}\n")
print(" ■ 고정밀도: ∛10 (30자리)")
r = nth_root(10, 3, decimal_digits=30, verbose=False)
print(f" ∛10 ≈ {r}\n")
def interactive() -> None:
"""대화형 입력"""
print("\n" + "━" * 62)
print(" n승근 루트k 계산기 (종료: Ctrl+C)")
print("━" * 62)
while True:
try:
k = int(input("\n k (양의 정수) : "))
n = int(input(" n (2 이상) : "))
d = int(input(" 소수점 자릿수 : "))
v = input(" 단계별 출력? (y/n, 기본 y) : ").strip().lower()
nth_root(k, n, decimal_digits=d, verbose=(v != 'n'))
except ValueError as e:
print(f" 입력 오류: {e}")
except KeyboardInterrupt:
print("\n 종료합니다.")
break
if __name__ == "__main__":
run_examples()
interactive()
개평법, 개립법 더 나아가 일반 개방법들은 모두 f(x, y)를 알면 구하는 방법이 동일하다.