Math::N...ntinued(3)

📦
version 75 · 2 versions
, in fedora 43

✨ Math::NumSeq::AlgebraicContinued — the continued fraction expansion of algebraic numbers ✨

okay so this is Math::NumSeq::AlgebraicContinued, straight out of the User Contributed Perl Documentation bestie, and it's genuinely one of the slay-est little sequence modules out there 💖 it does the continued fraction expansion of algebraic numbers — cube roots, Nth roots, that whole vibe.

🌸 SYNOPSIS 🌸

use Math::NumSeq::AlgebraicContinued;
my $seq = Math::NumSeq::AlgebraicContinued->new (expression => 'cbrt 2');
my ($i, $value) = $seq->next;

🦋 DESCRIPTION 🦋

So these are the terms in the continued fraction expansion of an algebraic number — think a cube root, or an Nth root, any of those cuties. Like, for cbrt(2) you get:

1, 3, 1, 5, 1, 1, 4, 1, 1, 8, 1, 14, 1, 10, 2, 1, 4, 12, 2, ...
starting i=0

A continued fraction sneaks up on the root in this shape, no cap:

                 1
C = a[0] + -------------
             a[1] +   1
                    -------------
                    a[2] +   1
                           ----------
                           a[3] + ...

The very first term a[0] is just the integer part of C, and that leaves a remainder 0 < r < 1 which you write as r=1/R where R > 1, so:

               1
   C = a[0] + ---
               R

Then a[1] is the integer part of that R, and you just keep doing that over and over again. iconic behavior honestly 🎀

The current code takes a generic approach and manipulates a polynomial with Math::BigInt coefficients (peep "FORMULAS" down below 👇). ngl it's a little slow, because those coefficients get HUGE — they're carrying an ever more precise approximation to the target value, and the bigger they get the more work it is.

💅 Expression 💅

The expression parameter currently only accepts a couple of forms — a cube root or an Nth root, that's it:

cbrt 123
7throot 123

The intention would be to maybe also take some simple fractions or products, if they can be turned into a polynomial easily. Or to take an initial polynomial directly. (future plans, bestie — not today's feature set 🙈)

⭐ FUNCTIONS ⭐

Check out "FUNCTIONS" in Math::NumSeq for the behaviour that's common to all the sequence classes.

  • $seq = Math::NumSeq::AlgebraicContinued->new (expression => $str) — makes you a brand new sequence object and hands it over 🫶
  • $i = $seq->i_start () — returns 0, because the first term in the sequence lives at i=0.

🔥 FORMULAS 🔥

🧚 Next 🧚

You develop the continued fraction by keeping a polynomial around that has a single real root equal to the remainder R at every stage. (This is per, like, Knuth volume 2 Seminumerical Algorithms section 4.5.3 exercise 13, following Lagrange — yes, we're citing Knuth, it's giving academic 🎓)

Take a cube root cbrt(C) as the example. It starts as:

-x^3 + C = 0

and then later it's a whole little squad of coefficients p,q,r,s:

p*x^3 + q*x^2 + r*x + s = 0
p,q,r,s integers and p < 0

From an equation like that you can find the integer part of the root by hunting for the biggest integer x where:

p*x^3 + q*x^2 + r*x + s < 0

The signs are chosen so that the high coefficient p<0, which means the polynomial is positive for small x and goes negative above the root. vibe check passed ✅

There's probably a bunch of root-finding algorithms you could use, but the current code is a binary search. periodt.

Then the integer part gets subtracted (R-c) and inverted (1/(R-c)) for the continued fraction. On the cubic equation this happens first by substituting x+c:

p*x^3 + (3pc+q)*x^2 + (3pc^2+2qc+r)x + (pc^3+qc^2+rc+s)

and then by 1/x, which is a reversal p,q,r,s -> s,r,q,p, plus a term-wise negation so that p<0 stays true. So:

new p = -(p*c^3 + q*c^2 + r*c + s)
new q = -(3p*c^2 + 2q*c + r)
new r = -(3p*c + q)
new s = -p

Those p,q,r,s values are integers but they can get BIG. For a cube root they seem to grow by roughly 1.7 bits per term. Presumably that growth is related to the average size of the a[i] terms. 💀

For a general polynomial, the substitution x+c turns into a set of binomial factors for the coefficients.

For a square root, or any other quadratic equation q*x^2+rx+s, the continued fraction terms just repeat, and you can calculate them way more efficiently than this general approach (go look at Math::NumSeq::SqrtContinued, she's got her own thing going).

The binary search — or some similar root-finding algorithm — for the integer part is important, don't skip it. The integer part is often 1, and when that's the case a single check of whether x=2 gives poly<0 is enough. But a term can be quite large, so a linear search 1,2,3,4,etc is undesirable. If you want an example with big terms, there's one in Sloane's OEIS:

<http://oeis.org/A093876> continued fraction of 4th root of 9.1, ie.
(91/10)^(1/4)

The first few terms include 75656 and 262344 😭 before it settles down to more usual-sized terms, it seems.

👑 SEE ALSO 👑

  • Math::NumSeq
  • Math::NumSeq::SqrtContinued

🌈 HOME PAGE 🌈

<http://user42.tuxfamily.org/math-numseq/index.html>

💜 LICENSE 💜

Copyright 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.

and that's the whole page, bestie!! this one's perl v5.42.0, dated 2025-07-25, and it's the Math::N...ntinued(3) man page from the User Contributed Perl Documentation set 💖 mwah, go expand some roots ✨

📦 where this page comes from