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.
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/.