Newton's Method and Fixed-Point Iteration (Essential for StableSwap) TODO
Concept
Newton's method finds a root of a function f by repeatedly drawing the tangent line at the current point and moving to that tangent line's root — the update subtracts f(x)/f'(x) from x each step. Near the root, if f' is nonzero and the initial guess is close enough, the error shrinks quadratically each step — quadratic convergence. Fixed-point iteration is a more general form that rewrites the equation as x = g(x) and iterates it; if g is a contraction mapping it converges, typically at a linear rate. Newton's method is fast but can diverge or oscillate with a bad initial guess or a small derivative, so it needs an iteration cap and range safeguards. When implementing it in integer arithmetic, the convergence tolerance should be set around an absolute error of 1 unit, and the direction of any remaining rounding error must be decided explicitly.
Invariants with no closed-form solution — like StableSwap's D or y — can only be solved iteratively, and on-chain every one of those iterations costs gas and is a potential point of failure.
Code & Formula
# Day 31 — 뉴턴법/고정점 반복(StableSwap 필수)
# f(x) = x^2 - 2 의 근(sqrt(2))을 뉴턴법으로 찾고, 오차가 제곱으로 줄어드는 이차수렴을 확인한다.
import math
def f(x):
return x ** 2 - 2
def f_prime(x):
return 2 * x
x = 1.0 # 초기값
true_root = math.sqrt(2)
print(f"뉴턴법으로 sqrt(2) = {true_root:.10f} 근사:\n")
prev_error = None
for step in range(6):
error = abs(x - true_root)
ratio = error / (prev_error ** 2) if prev_error else float("nan")
print(f"step {step}: x = {x:.10f}, error = {error:.2e}, error/prev_error^2 = {ratio:.4f}")
prev_error = error
x = x - f(x) / f_prime(x)
print(f"\n최종 x = {x:.12f}")
print("오차/이전오차^2 값이 일정 상수로 수렴 -> 이차수렴(quadratic convergence)의 증거")
Exercise
Implement a function that solves for D in a StableSwap-style invariant using Newton's method with integer arithmetic, then check how many iterations it takes to converge under extremely imbalanced reserves, and whether any inputs cause it to diverge.
Practical Connection
Analyzing AMM invariants, inverting interest-rate models, and numerical solvers related to LMSR all use the same tool, and the iteration cap plus rounding direction become security properties in their own right.
Where it lands in Jayverse
- DeFi: hard-cap Newton iterations and pick the rounding direction explicitly. For any invariant with no closed form (a StableSwap-style pool, a rebasing index), round in the protocol's favor and write a test for the extremely-imbalanced-reserves case the exercise asks about.
- Verex: treat the iteration cap and tolerance as security parameters if the market maker ever needs an iterative solve. Document them in the contract instead of tuning purely for gas.
- CI: add a fuzz test that feeds extreme or imbalanced inputs to any on-chain Newton-method solver. Assert it either converges within the capped iterations or reverts cleanly, never loops or returns a stale value.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| tangent line | 접선 · 뉴턴법에서 현재 점에서 그은 직선을 말할 때. "drawing the tangent line at the current point" |
| quadratic convergence | 이차 수렴(오차가 제곱으로 줄어듦) · 근처에서 매우 빠르게 수렴하는 성질. "the error shrinks quadratically each step" |
| contraction mapping | 축소 사상 · 반복할수록 값들이 서로 가까워지는 함수를 말할 때. "if g is a contraction mapping it converges" |
| diverge or oscillate | 발산하거나 진동하다 · 반복 계산이 수렴하지 않고 불안정할 때. "can diverge or oscillate with a bad initial guess" |
| range safeguards | 범위 안전장치 · 값이 허용 범위를 벗어나지 않도록 막는 장치. "needs an iteration cap and range safeguards" |
| closed-form solution | 닫힌 형태의 해(공식으로 바로 구해지는 해) · 반복 계산 없이 수식으로 바로 풀리는 해가 없을 때. "Invariants with no closed-form solution" |
| point of failure | 실패 지점, 취약점 · 시스템에서 문제가 생길 수 있는 지점을 말할 때. "a potential point of failure" |
| LMSR | 로그마켓점수규칙(Logarithmic Market Scoring Rule) · 예측시장 가격을 자동으로 매기는 방식, Verex의 확률 계산에도 쓰임. "numerical solvers related to LMSR all use the same tool" |
| StableSwap | 커브(Curve)식 스테이블코인 AMM 불변식 · 폐형해가 없어 뉴턴법 등으로 반복적으로 풀어야 하는 유동성 곡선. "Newton's Method and Fixed-Point Iteration (Essential for StableSwap)" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/math-50-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.