Square Root Continued Fraction Calculator (Scheme-Oriented)
Compute the continued fraction expansion of √n, inspect period length, generate convergents, and export output in Scheme-friendly formats.
Expert Guide: Calculating Square Root Continued Fractions in Scheme
Continued fractions are one of the most elegant ways to represent irrational numbers, and square roots of non-square integers are the most famous examples. If you are working in Scheme or any Lisp-style language, continued fractions are especially pleasant because the data naturally fits recursive lists and pairs. In this guide, you will learn what square root continued fractions are, why they are periodic, how to compute them correctly, how to encode them in Scheme, and how to validate your implementation with convergence statistics.
For a non-square integer n, the number √n is irrational, but it has a structured continued fraction: [a0; overline(a1, a2, …, ak)]. The bar indicates repetition, and this periodicity is not just a curiosity. It is central in algebraic number theory, Pell equations, and high-quality rational approximations.
1) Why continued fractions matter for square roots
- Best approximations: Convergents are among the best possible rational approximations for bounded denominator sizes.
- Guaranteed structure: For √n with n non-square, periodicity is guaranteed by Lagrange’s theorem.
- Pell equation links: Period length and convergents are directly tied to solutions of x² – ny² = 1.
- Implementation simplicity: The algorithm uses integer arithmetic in the recurrence, making it stable and deterministic in Scheme.
2) Core recurrence used in computation
Let a0 = floor(√n). If n is a perfect square, the continued fraction terminates immediately as [a0]. Otherwise, initialize:
- m0 = 0
- d0 = 1
- a0 = floor(√n)
Then iterate for i = 0,1,2,…:
- m(i+1) = d(i) * a(i) – m(i)
- d(i+1) = (n – m(i+1)²) / d(i)
- a(i+1) = floor((a0 + m(i+1)) / d(i+1))
For square roots, the period closes when a(i+1) = 2a0 (equivalently when the state repeats). This recurrence is ideal in Scheme because every step can be represented with exact integers.
3) Scheme-focused data modeling strategy
A practical Scheme representation is a pair of lists: one element for the non-repeating head and one list for the periodic block. Example for √23:
‘(4 (1 3 1 8))
This means √23 = [4; overline(1, 3, 1, 8)]. You can also wrap with a constructor or record-like structure for richer metadata:
(list ‘radicand 23 ‘a0 4 ‘period ‘(1 3 1 8) ‘period-length 4)
If you plan to compute convergents, store generated terms in a lazy stream or a finite list repeated from the period. Scheme’s recursion is expressive, but iterative loops with named let are often more efficient and easier to debug for this problem.
4) Real comparison data: period lengths for selected n
The following values are standard outcomes from the recurrence. They illustrate how period length can vary significantly even for nearby radicands.
| n | floor(√n) | Periodic block | Period length |
|---|---|---|---|
| 2 | 1 | (2) | 1 |
| 3 | 1 | (1 2) | 2 |
| 7 | 2 | (1 1 1 4) | 4 |
| 13 | 3 | (1 1 1 1 6) | 5 |
| 19 | 4 | (2 1 3 1 2 8) | 6 |
| 23 | 4 | (1 3 1 8) | 4 |
| 29 | 5 | (2 1 1 2 10) | 5 |
| 31 | 5 | (1 1 3 5 3 1 1 10) | 8 |
This table is useful for unit tests. If your Scheme function outputs different periods for these entries, your recurrence or stopping condition likely has a bug.
5) Convergents and measurable approximation quality
Convergents are generated from continued fraction coefficients via: p(k) = a(k)p(k-1) + p(k-2), and q(k) = a(k)q(k-1) + q(k-2), with initial values p(-2)=0, p(-1)=1, q(-2)=1, q(-1)=0. The ratio p(k)/q(k) is the k-th convergent.
Below is real numerical behavior for √2. Observe how quickly the absolute error shrinks.
| k | Convergent p/q | Decimal value | Absolute error vs √2 |
|---|---|---|---|
| 1 | 1/1 | 1.0000000000 | 0.4142135624 |
| 2 | 3/2 | 1.5000000000 | 0.0857864376 |
| 3 | 7/5 | 1.4000000000 | 0.0142135624 |
| 4 | 17/12 | 1.4166666667 | 0.0024531043 |
| 5 | 41/29 | 1.4137931034 | 0.0004204590 |
| 6 | 99/70 | 1.4142857143 | 0.0000721519 |
| 7 | 239/169 | 1.4142011834 | 0.0000123790 |
| 8 | 577/408 | 1.4142156863 | 0.0000021239 |
6) Common implementation mistakes in Scheme
- Using floating-point for recurrence states: m and d must remain exact integers.
- Wrong stopping criterion: terminating on repeated a values alone can fail; use known period closure condition for square roots.
- Off-by-one in term generation: ensure a0 is the head and periodic terms start at a1.
- Convergent seed errors: incorrect p(-2), p(-1), q(-2), q(-1) values distort all outputs.
- Perfect-square handling: if n = t², return [t] immediately with period length 0.
7) Suggested Scheme workflow for robust code
- Write a pure function to detect perfect squares.
- Write a function that returns (a0 period-list).
- Write a separate function to expand finite terms from repeating period.
- Write convergent function that accepts term list and returns list of (p q value error).
- Add test vectors (2, 3, 7, 13, 23, 31) and compare known periods.
- Benchmark with larger n to verify integer arithmetic performance.
8) How to interpret the calculator output
The calculator above returns four practical views: exact periodic form, generated finite term list, convergents, and charted convergence behavior. If you select Scheme format, you can paste the output directly into your interpreter or source file. The chart mode helps you verify whether your approximation sequence oscillates around √n (value mode) or contracts rapidly in magnitude (error mode).
Precision note: this tool uses JavaScript for decimal display, but period detection and recurrence logic are integer-based. For very large n and very long runs, a Scheme implementation with bignum support is recommended for production number-theory work.
9) Authoritative references for deeper study
- NIST Digital Library of Mathematical Functions: Continued Fractions (nist.gov)
- Stanford notes on Continued Fractions (stanford.edu)
- MIT OpenCourseWare: Theory of Numbers (mit.edu)
10) Final takeaways
Calculating square root continued fractions in Scheme is an ideal project because it combines elegant mathematics with clean functional programming patterns. The recurrence is compact, the structure is theoretically rich, and the outputs are directly useful for approximation, cryptographic intuition, Pell-equation exploration, and numeric reasoning. If you implement the integer recurrence carefully, validate against known periods, and monitor convergent errors, you will have a mathematically reliable toolchain that scales from classroom examples to advanced computation.
Use this calculator as both a practical assistant and a verification layer while building your Scheme version. Generate periods, compare convergents, export list syntax, and check visual convergence trends. Once your Scheme routines match these results across many n values, you can be confident that your implementation is correct and robust.