Let \(p_1=2,p_2=3,p_3=5,\dots\) be the prime numbers, and define
$$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots].$$
So the partial quotients of \(x\) begin
$$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots.$$
The implementations then study the transformed number
$$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots],$$
and the goal is to evaluate
$$S=\sum_{k=0}^{10^8-1}\beta_k.$$
The difficulty is that neither \(x\) nor \(y\) should be approximated by enormous convergents. Instead, the continued fraction of \(y\) is generated directly from the continued fraction of \(x\) in a single streaming process.
The central idea is to keep track of how the unread tail of \(x\) is transformed, rather than to rebuild the whole number after every new coefficient.
After the leading \(2\), the input coefficients come in a very rigid pattern: for each prime \(p_j\), there are exactly \(p_j\) copies of \(1\), followed by another \(2\). The beginning of the stream is therefore
$$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots.$$
This matters because the algorithm never forms \(x\) itself. It only requests the next partial quotient when the transformation state cannot yet determine the next output digit of \(y\).
Let \(z\) denote the unread tail of the original continued fraction. At any moment the remaining task can be written as
$$T(z)=\frac{Az+B}{Cz+D},$$
with positive integers \(A,B,C,D\). Initially, before any input has been read,
$$T(z)=\frac{2z+3}{3z+2},$$
so the starting matrix is \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\).
If the next input coefficient is \(n\), then the current tail becomes \([n;z]=n+\frac1z\). Substituting this into \(T\) gives
$$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}.$$
Therefore one input step updates the matrix by
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix}. $$
This recurrence is exact; no approximation is introduced at any stage.
Because every unread continued-fraction tail is positive, \(z>0\). For the current state \(T(z)=\frac{Az+B}{Cz+D}\), compare \(T(z)\) with the two rational endpoints \(\frac{A}{C}\) and \(\frac{B}{D}\):
$$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$$
These two differences always have opposite signs, so \(T(z)\) lies between \(\frac{A}{C}\) and \(\frac{B}{D}\) for every admissible tail \(z\). Hence, if
$$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a,$$
then the next continued-fraction coefficient of \(y\) is forced to be \(a\), regardless of what the rest of the prime-driven input will be.
After removing that integer part and inverting the remainder,
$$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}.$$
So one output step becomes
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix}. $$
This is the mechanism that turns the input continued fraction into the output continued fraction one coefficient at a time.
The determinant starts at
$$AD-BC=2\cdot2-3\cdot3=-5.$$
Every input step multiplies the matrix on the right by \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\), whose determinant is \(-1\), and every output step also flips the sign of the determinant. Therefore
$$|AD-BC|=5$$
for the entire run. This is not the main source of speed, but it is a useful invariant that confirms the transformation remains exact.
Start from
$$T(z)=\frac{2z+3}{3z+2}.$$
The first input coefficient is \(2\). After one input update,
$$T_1(z)=\frac{7z+2}{8z+3}.$$
Now
$$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0,$$
so the first output coefficient is \(\beta_0=0\). Removing that digit gives
$$T_2(z)=\frac{8z+3}{7z+2}.$$
Again the two bounds have the same floor, because
$$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
so \(\beta_1=1\). The next unread input digits are \(1,1,2\). Reading those three digits yields
$$T_3(z)=\frac{41z+16}{8z+3},$$
and now
$$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5.$$
Hence \(\beta_2=5\). Continuing in the same manner produces the checked prefix
$$0,1,5,6,16,9,1,10,16,11,\dots.$$
The C++, Python, and Java implementations generate primes incrementally by trial division against the primes already discovered. Those primes determine the input continued fraction of \(x\): one initial \(2\), then prime-length runs of \(1\)'s, each run followed by another \(2\).
The implementation keeps only four integers for the current linear-fractional state, plus a counter for how many output coefficients have been produced and a running total for their sum. Whenever the two rational bounds \(\frac{A}{C}\) and \(\frac{B}{D}\) have the same floor, that floor is appended to the continued fraction of \(y\) and added to the sum. Otherwise the next input coefficient of \(x\) is read and the input recurrence is applied.
This means the continued fraction of \(y=\frac{2x+3}{3x+2}\) is generated directly from the prime-driven input, without reconstructing \(x\) from convergents. The implementations also verify the short prefix \(0,1,5,6,16,9,1,10,16,11\), whose first ten terms sum to \(75\), before processing the full target of \(10^8\) output coefficients.
Let \(M\) be the number of requested output coefficients and let \(N\) be the number of input coefficients that must be read before those \(M\) outputs become determined. The linear-fractional transducer performs \(O(M+N)\) fixed-width arithmetic updates, because every loop iteration is exactly one input update or one output update.
The only auxiliary structure that grows is the list of primes needed to delimit the blocks of ones. With the straightforward trial-division prime generator used here, prime production has the usual incremental primality-testing cost up to the largest prime block encountered. Memory usage is therefore \(O(\pi(P))\) for the cached primes up to the largest generated prime \(P\), plus \(O(1)\) for the four-state transducer, the counters, and the running sum.
Seien \(p_1=2,p_2=3,p_3=5,\dots\) die Primzahlen, und definiere
$$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots].$$
Damit beginnen die Partialquotienten von \(x\) als
$$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots.$$
Die Implementierungen untersuchen dann die transformierte Zahl
$$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots],$$
und gesucht ist
$$S=\sum_{k=0}^{10^8-1}\beta_k.$$
Der entscheidende Punkt ist, dass weder \(x\) noch \(y\) über riesige Konvergenten aufgebaut werden sollen. Stattdessen wird der Kettenbruch von \(y\) direkt aus dem Kettenbruch von \(x\) als Strom berechnet.
Die zentrale Idee ist, nicht den gesamten Wert neu zu berechnen, sondern nur festzuhalten, wie der noch ungelesene Rest von \(x\) gerade transformiert wird.
Nach der führenden \(2\) kommen die Eingabekoeffizienten in einem starren Muster: Für jede Primzahl \(p_j\) erscheinen genau \(p_j\) Einsen, gefolgt von einer weiteren \(2\). Der Beginn des Stroms ist also
$$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots.$$
Das ist wichtig, weil der Algorithmus \(x\) nie vollständig materialisiert. Er fordert den nächsten Partialquotienten nur dann an, wenn der aktuelle Transformationszustand den nächsten Ausgabedigit von \(y\) noch nicht erzwingt.
Bezeichne den noch ungelesenen Rest des ursprünglichen Kettenbruchs mit \(z\). Zu jedem Zeitpunkt lässt sich die verbleibende Aufgabe in der Form
$$T(z)=\frac{Az+B}{Cz+D}$$
schreiben, mit positiven ganzen Zahlen \(A,B,C,D\). Zu Beginn, bevor irgendein Eingabewert gelesen wurde, gilt
$$T(z)=\frac{2z+3}{3z+2},$$
also startet man mit der Matrix \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\).
Ist der nächste Eingabekoeffizient \(n\), dann wird der aktuelle Rest zu \([n;z]=n+\frac1z\). Einsetzen in \(T\) ergibt
$$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}.$$
Ein Eingabeschritt aktualisiert die Matrix daher nach
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix}. $$
Diese Rekurrenz ist exakt; es wird an keiner Stelle numerisch approximiert.
Jeder ungelesene Kettenbruchrest ist positiv, also \(z>0\). Für den aktuellen Zustand \(T(z)=\frac{Az+B}{Cz+D}\) vergleicht man \(T(z)\) mit den beiden rationalen Werten \(\frac{A}{C}\) und \(\frac{B}{D}\):
$$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$$
Diese beiden Differenzen haben stets entgegengesetzte Vorzeichen. Also liegt \(T(z)\) für jeden zulässigen Rest \(z\) zwischen \(\frac{A}{C}\) und \(\frac{B}{D}\). Gilt daher
$$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a,$$
dann ist der nächste Kettenbruchkoeffizient von \(y\) zwangsläufig \(a\), ganz unabhängig vom restlichen primzahlgesteuerten Eingang.
Nach dem Entfernen dieses Ganzteils und dem Invertieren des Restes erhält man
$$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}.$$
Damit wird ein Ausgabeschritt zu
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix}. $$
Genau dieser Mechanismus wandelt den Eingabekettenbruch Koeffizient für Koeffizient in den Ausgabekettenbruch um.
Die Determinante startet mit
$$AD-BC=2\cdot2-3\cdot3=-5.$$
Jeder Eingabeschritt multipliziert rechts mit \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\), dessen Determinante \(-1\) ist, und jeder Ausgabeschritt dreht ebenfalls nur das Vorzeichen um. Deshalb gilt während des gesamten Laufs
$$|AD-BC|=5.$$
Das ist nicht der eigentliche Geschwindigkeitsgewinn, aber eine nützliche Invariante: Die Transformation bleibt stets exakt dieselbe linear-fractionale Abbildung eines späteren Restes.
Man startet mit
$$T(z)=\frac{2z+3}{3z+2}.$$
Der erste Eingabekoeffizient ist \(2\). Nach einem Eingabeschritt erhält man
$$T_1(z)=\frac{7z+2}{8z+3}.$$
Nun gilt
$$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0,$$
also ist der erste Ausgabekoeffizient \(\beta_0=0\). Nach dem Entfernen dieses Digits folgt
$$T_2(z)=\frac{8z+3}{7z+2}.$$
Auch jetzt stimmen die Ganzteile überein, denn
$$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
also ist \(\beta_1=1\). Die nächsten ungelesenen Eingabedigits sind \(1,1,2\). Nach diesen drei Leseschritten erhält man
$$T_3(z)=\frac{41z+16}{8z+3},$$
und nun
$$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5.$$
Daher ist \(\beta_2=5\). So entsteht weiter der überprüfte Präfix
$$0,1,5,6,16,9,1,10,16,11,\dots.$$
Die C++-, Python- und Java-Implementierungen erzeugen Primzahlen inkrementell per Probedivision durch die bereits gefundenen Primzahlen. Diese Primzahlen steuern den Eingabekettenbruch von \(x\): eine anfängliche \(2\), danach Primzahlblöcke aus Einsen, jeweils abgeschlossen durch eine weitere \(2\).
Die Implementierung speichert nur vier ganze Zahlen für den aktuellen linear-fractionalen Zustand, dazu einen Zähler für die bereits erzeugten Ausgabekoeffizienten und die laufende Summe. Immer wenn die beiden rationalen Schranken \(\frac{A}{C}\) und \(\frac{B}{D}\) denselben Ganzteil haben, wird genau dieser Ganzteil an den Kettenbruch von \(y\) angehängt und zur Summe addiert. Andernfalls wird der nächste Eingabekoeffizient von \(x\) gelesen und die Eingaberekurrenz angewendet.
So wird der Kettenbruch von \(y=\frac{2x+3}{3x+2}\) direkt aus dem primzahlgesteuerten Eingang erzeugt, ohne \(x\) über Konvergenten zu rekonstruieren. Zusätzlich prüfen die Implementierungen den kurzen Präfix \(0,1,5,6,16,9,1,10,16,11\), dessen erste zehn Terme die Summe \(75\) haben, bevor das volle Ziel mit \(10^8\) Ausgabekoeffizienten verarbeitet wird.
Sei \(M\) die Anzahl der gewünschten Ausgabekoeffizienten und \(N\) die Anzahl der Eingabekoeffizienten, die gelesen werden müssen, bevor diese \(M\) Ausgaben feststehen. Der linear-fractionale Transducer benötigt \(O(M+N)\) Aktualisierungen mit Maschinenarithmetik, weil jede Schleifeniteration genau ein Lese- oder ein Ausgabeschritt ist.
Die einzige wachsende Hilfsstruktur ist die Liste der Primzahlen, die für die Einsblöcke gebraucht wird. Mit dem hier verwendeten einfachen Primzahlgenerator per Probedivision entstehen die üblichen inkrementellen Kosten der Primzahltests bis zur größten verwendeten Primzahl \(P\). Der Speicherbedarf ist also \(O(\pi(P))\) für die zwischengespeicherten Primzahlen plus \(O(1)\) für den Vier-Zustands-Transducer, die Zähler und die laufende Summe.
\(p_1=2,p_2=3,p_3=5,\dots\) asal sayılar olsun ve
$$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots]$$
şeklinde tanımlansın. Böylece \(x\)'in zincir kesir katsayıları
$$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots$$
diye başlar. Uygulamalar daha sonra
$$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots]$$
sayısını ele alır ve hedef
$$S=\sum_{k=0}^{10^8-1}\beta_k$$
toplamını bulmaktır. Esas zorluk, ne \(x\)'i ne de \(y\)'yi dev yakınsaklar üzerinden açıkça kurmak istemememizdir. Bunun yerine \(y\)'nin zincir kesri, \(x\)'in zincir kesrinden doğrudan akış halinde üretilir.
Temel fikir, her yeni katsayıdan sonra bütün değeri yeniden hesaplamak yerine, \(x\)'in henüz okunmamış kuyruğunun nasıl dönüştüğünü izlemektir.
Baştaki \(2\)'den sonra giriş katsayıları çok katı bir desene sahiptir: her asal \(p_j\) için tam \(p_j\) tane \(1\) gelir, ardından bir \(2\) daha gelir. Akışın başlangıcı bu yüzden
$$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots$$
şeklindedir. Bu yapı önemlidir; çünkü algoritma \(x\)'i hiçbir zaman tam olarak kurmaz. Dönüşüm durumu bir sonraki çıktı katsayısını belirleyemediğinde ancak o zaman yeni bir giriş katsayısı ister.
Orijinal zincir kesrin henüz okunmamış kuyruğunu \(z\) ile gösterelim. Her anda geriye kalan görev
$$T(z)=\frac{Az+B}{Cz+D}$$
biçiminde yazılabilir; burada \(A,B,C,D\) pozitif tam sayılardır. Başlangıçta, henüz hiçbir giriş katsayısı okunmadan önce,
$$T(z)=\frac{2z+3}{3z+2}$$
olduğundan başlangıç matrisi \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\) olur.
Sıradaki giriş katsayısı \(n\) ise mevcut kuyruk \([n;z]=n+\frac1z\) haline gelir. Bunu \(T\)'ye yerleştirince
$$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}$$
elde edilir. Dolayısıyla bir giriş adımı matrisi
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix} $$
şeklinde günceller. Bu bağıntı tamdır; hiçbir yerde yaklaşık hesap yoktur.
Okunmamış her zincir kesir kuyruğu pozitiftir; yani \(z>0\). Mevcut durumda \(T(z)=\frac{Az+B}{Cz+D}\) için \(T(z)\)'yi \(\frac{A}{C}\) ve \(\frac{B}{D}\) ile karşılaştıralım:
$$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$$
Bu iki fark her zaman zıt işaretlidir. Demek ki \(T(z)\), izin verilen her \(z\) için \(\frac{A}{C}\) ile \(\frac{B}{D}\) arasındadır. O halde
$$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a$$
ise \(y\)'nin bir sonraki zincir kesir katsayısı, kuyruğun geri kalanı ne olursa olsun, kesin olarak \(a\) olur.
Bu tam kısmı çıkarıp kalanı ters çevirdiğimizde
$$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}$$
olur. Yani bir çıktı adımı
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix} $$
güncellemesine karşılık gelir. Giriş zincir kesrini çıktı zincir kesrine katsayı katsayı çeviren mekanizma tam olarak budur.
Determinant başlangıçta
$$AD-BC=2\cdot2-3\cdot3=-5$$
değerindedir. Her giriş adımı sağdan \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\) ile çarpmaya karşılık gelir ve bu matrisin determinantı \(-1\)'dir. Her çıktı adımı da determinantın sadece işaretini çevirir. Bu yüzden tüm çalışma boyunca
$$|AD-BC|=5$$
kalır. Bu özellik hızın ana kaynağı değildir, ama dönüşümün her an tam kaldığını doğrulayan yararlı bir değişmezdir.
Başlangıçta
$$T(z)=\frac{2z+3}{3z+2}$$
vardır. İlk giriş katsayısı \(2\)'dir. Bir giriş güncellemesinden sonra
$$T_1(z)=\frac{7z+2}{8z+3}$$
elde edilir. Şimdi
$$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0$$
olduğundan ilk çıktı katsayısı \(\beta_0=0\) olur. Bu katsayıyı çıkarınca
$$T_2(z)=\frac{8z+3}{7z+2}$$
elde edilir. Yine tabanlar aynıdır; çünkü
$$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
dolayısıyla \(\beta_1=1\). Bir sonraki okunmamış giriş katsayıları \(1,1,2\)'dir. Bu üç katsayı okunduğunda
$$T_3(z)=\frac{41z+16}{8z+3}$$
olur ve artık
$$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5$$
eşitliği vardır. Böylece \(\beta_2=5\) bulunur. Aynı süreç devam ettirildiğinde doğrulanan başlangıç parçası
$$0,1,5,6,16,9,1,10,16,11,\dots$$
elde edilir.
C++, Python ve Java uygulamaları asalları, daha önce bulunmuş asallarla yapılan artımlı bölme testleriyle üretir. Bu asallar \(x\)'in giriş zincir kesrini belirler: başta bir \(2\), sonra asal uzunluklu \(1\) blokları ve her bloğun sonunda bir \(2\).
Uygulama yalnızca mevcut doğrusal kesirsel durum için dört tam sayı, üretilmiş çıktı katsayılarının sayacı ve koşan toplamı tutar. Ne zaman \(\frac{A}{C}\) ile \(\frac{B}{D}\) rasyonellerinin tabanları eşitse, o taban \(y\)'nin zincir kesrine eklenir ve toplama katılır. Tabanlar eşit değilse \(x\)'in bir sonraki giriş katsayısı okunur ve giriş bağıntısı uygulanır.
Böylece \(y=\frac{2x+3}{3x+2}\) sayısının zincir kesri, \(x\)'i yakınsaklardan yeniden kurmadan doğrudan üretilmiş olur. Uygulamalar ayrıca kısa doğrulama ön eki olan \(0,1,5,6,16,9,1,10,16,11\) dizisini ve bu ilk on terimin toplamı olan \(75\)'i kontrol eder; ardından tam hedef olan \(10^8\) çıktı katsayısına geçer.
\(M\) istenen çıktı katsayısı sayısı, \(N\) ise bu \(M\) çıktının belirlenmesi için okunması gereken giriş katsayısı sayısı olsun. Doğrusal kesirsel dönüştürücü \(O(M+N)\) adet sabit genişlikli aritmetik güncelleme yapar; çünkü her döngü turu ya bir giriş güncellemesi ya da bir çıktı güncellemesidir.
Büyüyen tek yardımcı yapı, \(1\) bloklarının sınırlarını belirleyen asal listesidir. Burada kullanılan basit deneme bölmeli asal üreticiyle, asal üretimin maliyeti kullanılan en büyük asal \(P\)'ye kadar olağan artımlı asallık testleri maliyetidir. Bu nedenle bellek kullanımı, önbelleğe alınan asallar için \(O(\pi(P))\), dört durumlu dönüştürücü, sayaçlar ve koşan toplam için ise \(O(1)\) olur.
Sea \(p_1=2,p_2=3,p_3=5,\dots\) la sucesión de primos, y defínase
$$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots].$$
Por tanto, los cocientes parciales de \(x\) empiezan como
$$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots.$$
Las implementaciones estudian luego el número transformado
$$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots],$$
y el objetivo es calcular
$$S=\sum_{k=0}^{10^8-1}\beta_k.$$
La dificultad real es que no conviene construir ni \(x\) ni \(y\) mediante convergentes enormes. En lugar de eso, la fracción continua de \(y\) se produce directamente a partir de la de \(x\) en un solo flujo.
La idea central consiste en seguir la transformación aplicada a la cola aún no leída de \(x\), en vez de recomputar el número completo cada vez que aparece un nuevo coeficiente.
Después del \(2\) inicial, los coeficientes de entrada siguen un patrón rígido: para cada primo \(p_j\) aparecen exactamente \(p_j\) unos, seguidos de otro \(2\). El comienzo del flujo es entonces
$$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots.$$
Esto importa porque el algoritmo nunca materializa \(x\) por completo. Solo pide el siguiente cociente parcial cuando el estado de la transformación todavía no puede fijar el siguiente dígito de salida de \(y\).
Sea \(z\) la cola no leída de la fracción continua original. En cualquier instante, la tarea restante puede escribirse como
$$T(z)=\frac{Az+B}{Cz+D},$$
con \(A,B,C,D\) enteros positivos. Al principio, antes de leer ninguna entrada,
$$T(z)=\frac{2z+3}{3z+2},$$
de modo que la matriz inicial es \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\).
Si el siguiente coeficiente de entrada es \(n\), la cola actual pasa a ser \([n;z]=n+\frac1z\). Sustituyendo en \(T\) se obtiene
$$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}.$$
Por tanto, un paso de lectura actualiza la matriz según
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix}. $$
Esta recurrencia es exacta; no hay aproximación numérica en ningún momento.
Toda cola no leída de una fracción continua regular es positiva, así que \(z>0\). Para el estado actual \(T(z)=\frac{Az+B}{Cz+D}\), comparemos \(T(z)\) con los racionales \(\frac{A}{C}\) y \(\frac{B}{D}\):
$$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$$
Estas dos diferencias siempre tienen signos opuestos, de modo que \(T(z)\) queda entre \(\frac{A}{C}\) y \(\frac{B}{D}\) para toda cola admisible. Si entonces
$$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a,$$
el siguiente coeficiente de la fracción continua de \(y\) queda fijado como \(a\), sin importar cuál sea el resto de la entrada gobernada por primos.
Después de retirar esa parte entera e invertir el resto,
$$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}.$$
Así, un paso de salida corresponde a
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix}. $$
Ese es el mecanismo que convierte la fracción continua de entrada en la de salida, coeficiente a coeficiente.
El determinante inicial es
$$AD-BC=2\cdot2-3\cdot3=-5.$$
Cada paso de lectura multiplica por la derecha por \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\), cuyo determinante es \(-1\), y cada paso de salida también cambia solo el signo del determinante. Por ello, durante toda la ejecución se mantiene
$$|AD-BC|=5.$$
No es la fuente principal de eficiencia, pero sí un invariante útil para comprobar que la transformación sigue siendo exacta.
Se empieza con
$$T(z)=\frac{2z+3}{3z+2}.$$
El primer coeficiente de entrada es \(2\). Tras un paso de lectura,
$$T_1(z)=\frac{7z+2}{8z+3}.$$
Ahora
$$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0,$$
así que el primer coeficiente de salida es \(\beta_0=0\). Al retirar ese dígito queda
$$T_2(z)=\frac{8z+3}{7z+2}.$$
Otra vez los dos pisos coinciden, porque
$$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
y por tanto \(\beta_1=1\). Los siguientes dígitos de entrada aún no leídos son \(1,1,2\). Tras leerlos se obtiene
$$T_3(z)=\frac{41z+16}{8z+3},$$
y entonces
$$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5.$$
Así, \(\beta_2=5\). Continuando del mismo modo se obtiene el prefijo comprobado
$$0,1,5,6,16,9,1,10,16,11,\dots.$$
Las implementaciones en C++, Python y Java generan primos de forma incremental mediante división por prueba contra los primos ya encontrados. Esos primos determinan la fracción continua de entrada de \(x\): un \(2\) inicial, luego bloques de \(1\)'s de longitud prima, y después otro \(2\).
La implementación conserva solo cuatro enteros para el estado lineal-fraccionario actual, un contador de cuántos coeficientes de salida ya se han producido y la suma acumulada. Siempre que las dos cotas racionales \(\frac{A}{C}\) y \(\frac{B}{D}\) tienen el mismo piso, ese piso se añade a la fracción continua de \(y\) y también a la suma. Si no coinciden, se lee el siguiente coeficiente de entrada de \(x\) y se aplica la recurrencia de lectura.
De esta forma, la fracción continua de \(y=\frac{2x+3}{3x+2}\) se genera directamente desde la entrada, sin reconstruir \(x\) a partir de convergentes. Las implementaciones también verifican el prefijo corto \(0,1,5,6,16,9,1,10,16,11\), cuyos diez primeros términos suman \(75\), antes de procesar el objetivo completo de \(10^8\) coeficientes de salida.
Sea \(M\) el número de coeficientes de salida solicitados y \(N\) el número de coeficientes de entrada que deben leerse antes de que esos \(M\) valores queden determinados. El transductor lineal-fraccionario realiza \(O(M+N)\) actualizaciones aritméticas de tamaño fijo, porque cada iteración del bucle es exactamente una lectura o una emisión.
La única estructura auxiliar que crece es la lista de primos necesaria para delimitar los bloques de unos. Con el generador elemental por división de prueba usado aquí, la producción de primos tiene el coste incremental habitual hasta el mayor primo \(P\) alcanzado. Por tanto, la memoria es \(O(\pi(P))\) para los primos almacenados, más \(O(1)\) para el estado de cuatro enteros, los contadores y la suma acumulada.
设 \(p_1=2,p_2=3,p_3=5,\dots\) 为素数序列，并定义
$$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots].$$
因此，\(x\) 的连分数系数开头是
$$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots.$$
实现随后研究变换后的数
$$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots],$$
目标是计算
$$S=\sum_{k=0}^{10^8-1}\beta_k.$$
难点在于不能先把 \(x\) 或 \(y\) 展开成巨大的收敛分数再处理。正确做法是把 \(x\) 的连分数按流式方式直接转换成 \(y\) 的连分数，并在生成过程中累计前 \(10^8\) 项的和。
核心思想不是反复重建整个数值，而是始终维护“尚未读入的尾部在当前变换下会变成什么”的精确描述。
首项 \(2\) 之后，输入系数具有非常刚性的结构：对每个素数 \(p_j\)，先出现恰好 \(p_j\) 个 \(1\)，然后再出现一个 \(2\)。因此输入流开头为
$$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots.$$
这一点非常重要，因为算法从不显式构造整个 \(x\)。只有当当前状态还不足以确定 \(y\) 的下一个连分数系数时，程序才会向前读取一个新的输入系数。
设原始连分数尚未读入的尾部为 \(z\)。在任意时刻，剩余任务都可以写成
$$T(z)=\frac{Az+B}{Cz+D},$$
其中 \(A,B,C,D\) 为正整数。初始时，在尚未读取任何输入之前，
$$T(z)=\frac{2z+3}{3z+2},$$
所以起始矩阵就是 \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\)。
如果下一个输入系数是 \(n\)，那么当前尾部会变成 \([n;z]=n+\frac1z\)。将其代入 \(T\) 得到
$$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}.$$
因此，读取一个输入系数时，矩阵按照
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix} $$
更新。这个递推完全精确，中间没有任何近似。
任何尚未读入的正规连分数尾部都满足 \(z>0\)。对当前状态 \(T(z)=\frac{Az+B}{Cz+D}\)，比较 \(T(z)\) 与两个有理数 \(\frac{A}{C}\) 和 \(\frac{B}{D}\)：
$$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$$
这两个差的符号永远相反，所以对所有允许的尾部 \(z\)，\(T(z)\) 总落在 \(\frac{A}{C}\) 与 \(\frac{B}{D}\) 之间。因此如果
$$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a,$$
那么无论后面还隐藏着怎样的素数驱动输入，\(y\) 的下一个连分数系数都已经被唯一确定为 \(a\)。
输出这个整数部分后，需要去掉它并把剩余部分取倒数，于是
$$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}.$$
所以一次输出更新就是
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix}. $$
这正是把输入连分数逐项转换成输出连分数的关键步骤。
初始行列式为
$$AD-BC=2\cdot2-3\cdot3=-5.$$
每次读取输入，相当于在右侧乘上 \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\)，其行列式是 \(-1\)；每次输出也只会把行列式改号。因此整个过程中始终有
$$|AD-BC|=5.$$
它不是主要的加速来源，但却是一个很好的正确性信号：当前状态始终精确表示同一个固定线性分式变换作用在某个更短尾部上的结果。
从
$$T(z)=\frac{2z+3}{3z+2}$$
开始。第一个输入系数是 \(2\)。做一次输入更新后，得到
$$T_1(z)=\frac{7z+2}{8z+3}.$$
此时
$$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0,$$
所以第一个输出系数就是 \(\beta_0=0\)。去掉这一项后，状态变为
$$T_2(z)=\frac{8z+3}{7z+2}.$$
再次检查可见两个地板函数仍然相同，因为
$$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
于是 \(\beta_1=1\)。接下来尚未读入的输入系数是 \(1,1,2\)。连续读入这 3 项后得到
$$T_3(z)=\frac{41z+16}{8z+3},$$
并且此时
$$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5.$$
因此 \(\beta_2=5\)。继续相同过程，就会得到已经在实现中验证过的前缀
$$0,1,5,6,16,9,1,10,16,11,\dots.$$
C++、Python 和 Java 实现都会用逐步试除的方式生成素数，只拿已经找到的素数去测试新的候选数。这些素数决定了 \(x\) 的输入连分数结构：先是一个 \(2\)，然后是长度为素数的 \(1\) 块，每个块后面跟一个 \(2\)。
实现只保存 4 个整数来表示当前线性分式状态，再加上已经输出了多少项以及当前累计和。每当两个有理上界 \(\frac{A}{C}\) 与 \(\frac{B}{D}\) 的整数部分相同，这个整数部分就可以立即作为 \(y\) 的下一个连分数系数，同时加进总和；如果两者还不同，就继续读取 \(x\) 的下一个输入系数并应用输入递推。
因此，\(y=\frac{2x+3}{3x+2}\) 的连分数是直接从输入流生成出来的，并不需要先通过收敛分数重建 \(x\)。实现还会先验证短前缀 \(0,1,5,6,16,9,1,10,16,11\)，其前 10 项和为 \(75\)，然后才处理真正目标的 \(10^8\) 个输出系数。
设 \(M\) 是要求出的输出系数个数，\(N\) 是为了确定这 \(M\) 个输出而必须读取的输入系数个数。线性分式转化器本身执行 \(O(M+N)\) 次固定宽度算术更新，因为每次循环要么是一次读入更新，要么是一次输出更新。
唯一会增长的辅助结构是用来界定那些 \(1\) 块长度的素数表。按照这里使用的朴素增量试除法，生成素数的额外代价就是直到所需最大素数 \(P\) 为止的常规逐步素性测试成本。因此，空间复杂度为缓存素数所需的 \(O(\pi(P))\)，再加上 4 个状态量、计数器和累计和所需的 \(O(1)\) 空间。
Пусть \(p_1=2,p_2=3,p_3=5,\dots\) — последовательность простых чисел, и задано
$$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots].$$
Тогда коэффициенты цепной дроби для \(x\) начинаются так:
$$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots.$$
Далее реализации рассматривают преобразованное число
$$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots],$$
и нужно вычислить
$$S=\sum_{k=0}^{10^8-1}\beta_k.$$
Главная трудность в том, что нельзя сначала построить гигантские подходящие дроби для \(x\), а затем заново разложить \(y\). Вместо этого цепная дробь числа \(y\) порождается напрямую из цепной дроби числа \(x\) в потоковом режиме.
Ключевая идея состоит в том, чтобы хранить не сам текущий численный приближённый результат, а точное описание того, как преобразуется ещё не прочитанный хвост цепной дроби.
После начального \(2\) входные коэффициенты имеют жёсткую структуру: для каждого простого \(p_j\) идут ровно \(p_j\) единиц, а затем ещё одна \(2\). Поэтому начало входного потока имеет вид
$$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots.$$
Это важно, потому что алгоритм никогда не материализует всё число \(x\). Следующий входной коэффициент запрашивается только тогда, когда текущего состояния уже недостаточно, чтобы однозначно определить следующий выходной коэффициент числа \(y\).
Обозначим непрочитанный хвост исходной цепной дроби через \(z\). В любой момент оставшаяся задача записывается в форме
$$T(z)=\frac{Az+B}{Cz+D},$$
где \(A,B,C,D\) — положительные целые. В самом начале, до чтения входа,
$$T(z)=\frac{2z+3}{3z+2},$$
то есть стартовая матрица равна \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\).
Если следующий входной коэффициент равен \(n\), то текущий хвост заменяется на \([n;z]=n+\frac1z\). Подстановка в \(T\) даёт
$$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}.$$
Следовательно, один шаг чтения обновляет матрицу по правилу
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix}. $$
Это точное рекуррентное соотношение, без каких-либо численных приближений.
Любой непрочитанный хвост регулярной цепной дроби положителен, то есть \(z>0\). Для текущего состояния \(T(z)=\frac{Az+B}{Cz+D}\) сравним \(T(z)\) с рациональными числами \(\frac{A}{C}\) и \(\frac{B}{D}\):
$$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$$
Эти две разности всегда имеют противоположные знаки, поэтому \(T(z)\) для любого допустимого хвоста лежит между \(\frac{A}{C}\) и \(\frac{B}{D}\). Значит, если
$$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a,$$
то следующий коэффициент цепной дроби числа \(y\) уже неизбежно равен \(a\), независимо от того, как выглядит остальная часть входа.
После удаления этой целой части и обращения дробного остатка получаем
$$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}.$$
Поэтому один выходной шаг записывается как
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix}. $$
Именно этот переход поочерёдно превращает входную цепную дробь в выходную.
Изначально определитель равен
$$AD-BC=2\cdot2-3\cdot3=-5.$$
Каждый шаг чтения соответствует умножению справа на \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\), у которой определитель \(-1\), а каждый шаг вывода тоже лишь меняет знак определителя. Поэтому на всём протяжении вычисления выполняется
$$|AD-BC|=5.$$
Это не основной источник ускорения, но очень полезная инварианта, подтверждающая, что преобразование остаётся точным.
Начинаем с
$$T(z)=\frac{2z+3}{3z+2}.$$
Первый входной коэффициент равен \(2\). После одного шага чтения имеем
$$T_1(z)=\frac{7z+2}{8z+3}.$$
Теперь
$$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0,$$
значит, первый выходной коэффициент равен \(\beta_0=0\). После его удаления получается
$$T_2(z)=\frac{8z+3}{7z+2}.$$
И снова целые части совпадают, потому что
$$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
поэтому \(\beta_1=1\). Следующие ещё не прочитанные входные коэффициенты — это \(1,1,2\). После чтения этих трёх коэффициентов получаем
$$T_3(z)=\frac{41z+16}{8z+3},$$
и теперь
$$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5.$$
Следовательно, \(\beta_2=5\). Продолжая тот же процесс, получаем проверенный префикс
$$0,1,5,6,16,9,1,10,16,11,\dots.$$
Реализации на C++, Python и Java порождают простые числа по мере необходимости, используя пробные деления на уже найденные простые. Эти простые задают входную цепную дробь числа \(x\): один начальный \(2\), затем блоки единиц простых длин, и после каждого блока ещё одна \(2\).
Реализация хранит только четыре целых числа для текущего линейно-дробного состояния, счётчик уже выведенных коэффициентов и накопленную сумму. Как только две рациональные границы \(\frac{A}{C}\) и \(\frac{B}{D}\) имеют одинаковую целую часть, именно это число сразу добавляется в цепную дробь числа \(y\) и в сумму. Если же целые части ещё различаются, читается следующий входной коэффициент числа \(x\), после чего применяется входное рекуррентное обновление.
Таким образом, цепная дробь числа \(y=\frac{2x+3}{3x+2}\) строится напрямую из входного потока, без восстановления \(x\) по подходящим дробям. Реализации также проверяют короткий префикс \(0,1,5,6,16,9,1,10,16,11\), у которого сумма первых десяти членов равна \(75\), а затем переходят к полному целевому вычислению для \(10^8\) выходных коэффициентов.
Пусть \(M\) — число требуемых выходных коэффициентов, а \(N\) — число входных коэффициентов, которые нужно прочитать, чтобы эти \(M\) коэффициентов однозначно определились. Сам линейно-дробный преобразователь выполняет \(O(M+N)\) обновлений с машинной арифметикой фиксированной ширины, потому что каждая итерация цикла — это либо один шаг чтения, либо один шаг вывода.
Единственная вспомогательная структура, которая растёт, — список простых чисел, необходимый для задания длин блоков из единиц. При используемом здесь простом генераторе на основе пробных делений стоимость получения простых чисел равна обычной накопленной стоимости последовательных проверок на простоту вплоть до наибольшего использованного простого \(P\). Поэтому память составляет \(O(\pi(P))\) для кэша простых чисел и \(O(1)\) для четырёх чисел состояния, счётчиков и текущей суммы.
لتكن \(p_1=2,p_2=3,p_3=5,\dots\) هي الأعداد الأولية، ولنعرّف
$$x=[2;\underbrace{1,\ldots,1}_{p_1},2,\underbrace{1,\ldots,1}_{p_2},2,\underbrace{1,\ldots,1}_{p_3},2,\dots].$$
وبذلك تبدأ معاملات الكسر المستمر لـ \(x\) بالشكل
$$2,1,1,2,1,1,1,2,1,1,1,1,1,2,\dots.$$
ثم تتعامل التطبيقات مع العدد المحوَّل
$$y=\frac{2x+3}{3x+2}=[\beta_0;\beta_1,\beta_2,\dots],$$
والمطلوب هو حساب
$$S=\sum_{k=0}^{10^8-1}\beta_k.$$
الصعوبة الحقيقية هي أننا لا نريد بناء \(x\) أو \(y\) عبر كسور تقريبية ضخمة. بدلًا من ذلك، يتم توليد الكسر المستمر لـ \(y\) مباشرة من الكسر المستمر لـ \(x\) على هيئة تدفّق واحد.
الفكرة الأساسية هي تتبّع كيفية تأثير التحويل في الذيل الذي لم يُقرأ بعد من \(x\)، بدلًا من إعادة حساب القيمة الكاملة كلما ظهر معامل جديد.
بعد الـ \(2\) الأولى، تأتي معاملات الإدخال وفق نمط صارم جدًا: لكل أولي \(p_j\) يوجد بالضبط \(p_j\) نسخة من \(1\)، ثم تأتي \(2\) أخرى. لذلك تكون بداية السلسلة
$$2,\underbrace{1,1}_{p_1=2},2,\underbrace{1,1,1}_{p_2=3},2,\underbrace{1,1,1,1,1}_{p_3=5},2,\dots.$$
وهذا مهم لأن الخوارزمية لا تبني \(x\) كاملًا في أي لحظة. إنها تطلب المعامل التالي فقط عندما لا تكفي الحالة الحالية لتحديد المعامل التالي الخارج من \(y\).
لنرمز إلى الذيل غير المقروء من الكسر المستمر الأصلي بالرمز \(z\). في أي لحظة يمكن كتابة المهمة المتبقية على الصورة
$$T(z)=\frac{Az+B}{Cz+D},$$
حيث \(A,B,C,D\) أعداد صحيحة موجبة. في البداية، قبل قراءة أي إدخال، يكون
$$T(z)=\frac{2z+3}{3z+2},$$
ومن ثم فالمصفوفة الابتدائية هي \(\begin{pmatrix}2&3\\3&2\end{pmatrix}\).
إذا كان معامل الإدخال التالي هو \(n\)، فإن الذيل الحالي يصبح \([n;z]=n+\frac1z\). وبالتعويض داخل \(T\) نحصل على
$$T\!\left(n+\frac1z\right)=\frac{(An+B)z+A}{(Cn+D)z+C}.$$
إذًا، خطوة قراءة واحدة تحدّث المصفوفة وفق العلاقة
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}An+B&A\\ Cn+D&C\end{pmatrix}. $$
هذه العلاقة دقيقة تمامًا، ولا تحتوي على أي تقريب عددي.
كل ذيل غير مقروء من كسر مستمر منتظم يحقق \(z>0\). للحالة الحالية \(T(z)=\frac{Az+B}{Cz+D}\)، نقارن \(T(z)\) بالكسرين \(\frac{A}{C}\) و \(\frac{B}{D}\):
$$T(z)-\frac{A}{C}=\frac{BC-AD}{C(Cz+D)},\qquad T(z)-\frac{B}{D}=\frac{z(AD-BC)}{D(Cz+D)}.$$
هذان الفرقان لهما دائمًا إشارتان متعاكستان، ولذلك فإن \(T(z)\) يقع بين \(\frac{A}{C}\) و \(\frac{B}{D}\) لأي ذيل مقبول. وعليه، إذا تحقق
$$\left\lfloor\frac{A}{C}\right\rfloor=\left\lfloor\frac{B}{D}\right\rfloor=a,$$
فإن معامل الكسر المستمر التالي للعدد \(y\) يكون محسومًا ويساوي \(a\)، بغض النظر عن بقية الإدخال المرتبط بالأعداد الأولية.
بعد نزع هذا الجزء الصحيح وقلب الباقي نحصل على
$$T(z)=a+\frac{1}{T_1(z)},\qquad T_1(z)=\frac{Cz+D}{(A-aC)z+(B-aD)}.$$
إذًا تصبح خطوة الإخراج
$$ \begin{pmatrix}A&B\\ C&D\end{pmatrix} \longmapsto \begin{pmatrix}C&D\\ A-aC&B-aD\end{pmatrix}. $$
وهذه هي الآلية التي تحوّل الكسر المستمر الداخل إلى الكسر المستمر الخارج معاملًا بعد معامل.
يبدأ المحدد بالقيمة
$$AD-BC=2\cdot2-3\cdot3=-5.$$
كل خطوة قراءة تعني الضرب من اليمين في \(\begin{pmatrix}n&1\\1&0\end{pmatrix}\)، ومحدد هذه المصفوفة يساوي \(-1\)، كما أن كل خطوة إخراج تغيّر إشارة المحدد فقط. لذلك يبقى لدينا طوال التنفيذ
$$|AD-BC|=5.$$
هذا ليس المصدر الرئيسي للسرعة، لكنه ثابت مفيد يؤكد أن التحويل يظل دقيقًا في كل مرحلة.
نبدأ من
$$T(z)=\frac{2z+3}{3z+2}.$$
أول معامل إدخال هو \(2\). بعد خطوة قراءة واحدة نحصل على
$$T_1(z)=\frac{7z+2}{8z+3}.$$
والآن
$$\left\lfloor\frac{7}{8}\right\rfloor=\left\lfloor\frac{2}{3}\right\rfloor=0,$$
إذن أول معامل خارج هو \(\beta_0=0\). بعد إزالة هذا المعامل تصبح الحالة
$$T_2(z)=\frac{8z+3}{7z+2}.$$
ومرة أخرى يتساوى الجزء الصحيح لأن
$$\left\lfloor\frac{8}{7}\right\rfloor=\left\lfloor\frac{3}{2}\right\rfloor=1,$$
ومن ثم \(\beta_1=1\). معاملات الإدخال التالية غير المقروءة هي \(1,1,2\). وبعد قراءة هذه الثلاثة نحصل على
$$T_3(z)=\frac{41z+16}{8z+3},$$
وحينها
$$\left\lfloor\frac{41}{8}\right\rfloor=\left\lfloor\frac{16}{3}\right\rfloor=5.$$
إذًا \(\beta_2=5\). وبالاستمرار بالطريقة نفسها نحصل على المقدمة التي تم التحقق منها
$$0,1,5,6,16,9,1,10,16,11,\dots.$$
تولّد تطبيقات C++ وPython وJava الأعداد الأولية تدريجيًا باستخدام القسمة التجريبية على الأوليات التي اكتُشفت سابقًا. هذه الأوليات هي التي تحدد الكسر المستمر الداخل للعدد \(x\): أولًا \(2\)، ثم كتل من \(1\) طولها أولي، وبعد كل كتلة تأتي \(2\) أخرى.
تحتفظ الخوارزمية بأربعة أعداد صحيحة فقط لوصف الحالة الكسرية الخطية الحالية، إضافة إلى عدّاد لعدد المعاملات الخارجة المنتجة حتى الآن ومجموعها التراكمي. كلما كان للكسرين \(\frac{A}{C}\) و \(\frac{B}{D}\) الجزء الصحيح نفسه، يُضاف هذا الجزء مباشرة إلى الكسر المستمر للعدد \(y\) وإلى المجموع. وإذا لم يتساويا بعد، يُقرأ معامل الإدخال التالي من \(x\) وتُطبَّق علاقة التحديث الخاصة بالقراءة.
وبهذا يتم توليد الكسر المستمر للعدد \(y=\frac{2x+3}{3x+2}\) مباشرة من تيار الإدخال، من دون إعادة بناء \(x\) من الكسور التقاربية. كما تتحقق التطبيقات أولًا من المقدمة القصيرة \(0,1,5,6,16,9,1,10,16,11\)، التي يساوي مجموع أول عشرة حدود منها \(75\)، قبل الانتقال إلى الهدف الكامل وهو \(10^8\) معاملات خارجة.
إذا كان \(M\) هو عدد معاملات الإخراج المطلوبة، و\(N\) هو عدد معاملات الإدخال التي يجب قراءتها حتى تُحسم هذه القيم \(M\)، فإن المحول الكسري الخطي ينفذ \(O(M+N)\) من تحديثات الحساب ذات العرض الثابت، لأن كل دورة من الحلقة هي إما خطوة قراءة واحدة أو خطوة إخراج واحدة.
البنية المساعدة الوحيدة التي تنمو هي قائمة الأعداد الأولية اللازمة لتحديد أطوال كتل الواحدات. ومع مولد الأوليات البسيط المعتمد هنا على القسمة التجريبية، تكون كلفة توليد الأوليات هي الكلفة التراكمية المعتادة لاختبارات الأولية حتى أكبر أولي مستخدم \(P\). لذلك يكون استهلاك الذاكرة \(O(\pi(P))\) لتخزين الأوليات المكتشفة، بالإضافة إلى \(O(1)\) لحالة المحول ذات الأربعة أعداد، والعدادات، والمجموع الجاري.