| 30,13 → 30,16 |
|---|
| Basically, a \useterm{formal power series} (implemented through the |
| domain \adtype{FormalPowerSeries} is given through a |
| \adtype{DataStream}. However, we add a few more fields to the data |
| structure since we want to allow recursive definitions of |
| structure, since we want to allow recursive definitions of |
| \useterm{formal power series}. |
| % |
| Full laziness, also says that neither the arithmetic operations on |
| power series nor their creation using % |
| \adname[FormalPowerSeries]{new:(I->Generator R,()->SeriesOrder)->%} |
| is allowed to do any real computation. They are $O(1)$ operations. |
| \adname[FormalPowerSeriesCategory]{new0}, |
| \adname[FormalPowerSeriesCategory]{new1}, and |
| \adname[FormalPowerSeriesCategory]{new2} is allowed to do any real |
| computation. They are $O(1)$ operations and only affect the data |
| structure, but do no actual computation of coefficents. |
| |
| More details can be found at the documentation of |
| \adtype{FormalPowerSeries}. |
| 72,6 → 75,8 |
|---|
| *: (%, %) -> %; |
| } |
| } |
| <<cat: BadIndexExceptionType>> |
| <<dom: BadIndexException>> |
| <<cat: FormalPowerSeriesCategory>> |
| <<dom: SeriesOrder>> |
| <<dom: FormalPowerSeries>> |
| 113,9 → 118,29 |
|---|
| is made dependent on whether or not \adassertion{TRACE} is set |
| via the macro \admacro{SETNAME}. |
| \end{enumerate} |
| |
| The output should be piped through the following small \xPerl{} |
| program in order to indent the code properly. |
| Just say |
| \begin{verbatim} |
| notangle -R treatblock.pl series.as.nw > treatblock.pl |
| perl treatblock.pl trace.out > trace.out.formatted |
| \end{verbatim} |
| where \genfile{trace.out} is the output of the \genfile{TestSuite} |
| program. |
| \begin{verbatim} |
| \end{rhx} |
| \end{ToDo} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<TRACE: FormalPowerSeriesCategory>>= |
| #if TRACE |
| name: % -> String; |
| setName!: String -> % -> %; |
| #endif |
| @ %def setName! name |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<treatblock.pl>>= |
| sub treatBlock { |
| my($s)=@_; |
| while(<>) { |
| 125,18 → 150,8 |
|---|
| } |
| } |
| treatBlock(""); |
| \end{verbatim} |
| in order to indent the code properly. |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<TRACE: FormalPowerSeriesCategory>>= |
| #if TRACE |
| name: % -> String; |
| setName!: String -> % -> %; |
| #endif |
| @ %def setName! name |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| \end{rhx} |
| \end{ToDo} |
| |
| \begin{+++} |
| \begin{adusage} |
| 192,7 → 207,7 |
|---|
| for i in aord.. repeat yield i::R; |
| } |
| approximateOrder(): SeriesOrder == 5::SeriesOrder; |
| f: \adtype{FormalPowerSeries}(R) := new(coeffs, approximateOrder); |
| f: \adtype{FormalPowerSeries}(R) := \adthisname(coeffs, approximateOrder); |
| \end{adusage} |
| \begin{addescription}{Creates a new series.} |
| \adcode$\adthisname(coeffs, sord)$ creates a new series by giving |
| 211,7 → 226,10 |
|---|
| % |
| The function \adcode$coeffs$ is never called if the initial |
| \useterm{approximate order} turns out to be |
| \adname[SeriesOrder]{infinity}. |
| \adname[SeriesOrder]{infinity}. In this case the series is taken |
| to be the zero series. |
| |
| In the above example we have $f = (0,0,0,0,0,5,6,7,8,\ldots)$. |
| \end{addescription} |
| \begin{adseealso} |
| \adname{set!} |
| 219,7 → 237,7 |
|---|
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| new: (I -> Generator R, () -> SeriesOrder) -> %; |
| new0: (I -> Generator R, () -> SeriesOrder) -> %; |
| @ |
| |
| |
| 236,7 → 254,7 |
|---|
| for i in 1..aord repeat yield 0; |
| for i in aord.. repeat yield coefficient(x, i-1); |
| } |
| f: \adtype{FormalPowerSeries}(Integer) == \adthisname(shift x, \adname[SeriesOrder]{increment}, x); |
| h: \adtype{FormalPowerSeries}(Integer) == \adthisname(shift, \adname[SeriesOrder]{increment}, f); |
| \end{adusage} |
| \begin{addescription}{Creates a new series from a given one.} |
| \adcode$\adthisname(coeffs, sord, x)$ creates a new series by |
| 257,6 → 275,9 |
|---|
| The function \adcode$coeffs$ is never called if the initial |
| \useterm{approximate order} turns out to be |
| \adname[SeriesOrder]{infinity}. |
| |
| In the above example, $f = (2,6,12,20,30,\ldots)$ and $h = |
| (0,2,6,12,20,30,\ldots)$. |
| \end{addescription} |
| \begin{adseealso} |
| \adname{set!} |
| 264,7 → 285,7 |
|---|
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| new: (I -> Generator R, SeriesOrder -> SeriesOrder, %) -> %; |
| new1: (% -> I -> Generator R, SeriesOrder -> SeriesOrder, %) -> %; |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| 274,9 → 295,12 |
|---|
| \begin{adusage} |
| plus(x: %, y: %)(aord: I): Generator R == generate { |
| for n: I in 1..aord repeat yield 0@R; |
| for n: I in aord.. repeat yield coefficient(x, n) + coefficient(y, n); |
| for n: I in aord.. repeat yield \adname{coefficient}(x, n) + \adname{coefficient}(y, n); |
| } |
| f: \adtype{FormalPowerSeries}(Integer) := new(plus(x, y), min, x, y); |
| g: Generator R == generate yield 1; |
| u := g :: \adtype{FormalPowerSeries}(Integer); |
| v: \adtype{FormalPowerSeries}(Integer) := \adname{term}(1, 3); |
| w: \adtype{FormalPowerSeries}(Integer) := \adthisname(plus, \adname{min}, u, v); |
| \end{adusage} |
| \begin{addescription}{Creates a new series from two given ones.} |
| \adcode$\adthisname(coeffs, sord, x, y)$ creates a new series by |
| 297,6 → 321,9 |
|---|
| The function \adcode$coeffs$ is never called if the initial |
| \useterm{approximate order} turns out to be |
| \adname[SeriesOrder]{infinity}. |
| |
| In the above example, $u = (1,1,1,1,1,\ldots)$, and $v = |
| (0,0,0,1,0,0,\ldots)$, and $u = (1,1,1,2,1,\ldots)$. |
| \end{addescription} |
| \begin{adseealso} |
| \adname{set!} |
| 304,7 → 331,7 |
|---|
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| new: (I -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder, %, %) -> %; |
| new2: ((%, %) -> I -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder, %, %) -> %; |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| 341,6 → 368,8 |
|---|
| |
| The coefficients are equal to the coefficients of |
| \adcode$\adname{term}(1, 0)$. |
| |
| The order of this series is \adname[SeriesOrder]{0}. |
| \end{addescription} |
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| 363,6 → 392,8 |
|---|
| |
| The coefficients are equal to the coefficients of |
| \adcode$\adname{term}(1, 1)$. |
| |
| The order of this series is \adname[SeriesOrder]{1}. |
| \end{addescription} |
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| 428,6 → 459,22 |
|---|
| |
| Since series are 0-based $c=4$ and $d=0$ in the above example. |
| \end{addescription} |
| \begin{adexceptions} |
| \adthrows{BadIndexException} if the series is recursively defined |
| and the computation of the $n$-th coefficient requires to know a |
| coefficient with index $\ge n$. |
| \end{adexceptions} |
| \begin{adremarks} |
| Note that we allow recursive definitions of series like $f=x+f^2$ |
| or $f = f'+x$. In the latter case, the \useterm{approxomate order} |
| would be determined to be zero, but in order to compute the zeroth |
| coefficient of $f$ one would need to compute the zeroth |
| coefficient of its derivative $f'$, i.e. the first coefficient of |
| $f$. Such a recursion scheme is not appropriate. The function |
| $\adthisname(f,n)$ will raise an exception if during the |
| computation of the $n$-th coefficient, a coefficient with index |
| $\ge n$ is needed. |
| \end{adremarks} |
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| 489,21 → 536,24 |
|---|
| \begin{gather} |
| f = \sum_{i=0}^\infty {f_i x^i}, |
| \end{gather} |
| the call \adcode$\adthisname(f)$ returns a number $o$. |
| the call \adcode$\adthisname(f)$ returns a number $n\in \setN \cup |
| \Set{\adname[SeriesOrder]{infinity}, |
| \adname[SeriesOrder]{unknown}}$, \ie, an element of |
| \adtype{SeriesOrder}. |
| % |
| If $o=\adname[SeriesOrder]{infinity}$ then the series is known to |
| If $n=\adname[SeriesOrder]{infinity}$ then the series is known to |
| be \adname{0}. |
| % |
| If $o=\adname[SeriesOrder]{unknown}$ then it is not (yet) clear |
| If $n=\adname[SeriesOrder]{unknown}$ then it is not (yet) clear |
| what the order of the series is. |
| % |
| It is however ensured that after the call |
| It is, however, ensured that after the call |
| \adcode$\adname{coefficient}(f,i)$ with an $i$ for which |
| $\Set{f_0,\ldots,f_i} \ne \Set{0}$, the call \adcode$\adthisname(f)$ |
| does not return \adname[SeriesOrder]{unknown}, but rather the true |
| order $n$ of the series $f$. |
| % |
| If $o=n\geq0$ then $f_n\ne0$ and $f_i=0$ for all $i<n$, \ie, |
| If $n\geq0$ then $f_n\ne0$ and $f_i=0$ for all $i<n$, \ie, |
| \begin{gather} |
| f = \sum_{i=n}^\infty {f_i x^i}. |
| \end{gather} |
| 534,22 → 584,45 |
|---|
| \begin{gather} |
| f = \sum_{i=0}^\infty {f_i x^i}, |
| \end{gather} |
| the call \adcode$\adthisname(f)$ returns a number $a$. |
| the call \adcode$\adthisname(f)$ returns |
| $n\in\setN\cup\Set{\infty}\subseteq \adtype{SeriesOrder}$. |
| % |
| If $a=\adname[SeriesOrder]{infinity}$ then the series is known to |
| If $n=\adname[SeriesOrder]{infinity}$ then the series is known to |
| be \adname{0}. |
| % |
| The value of $a$ is never \adname[SeriesOrder]{unknown} since the |
| The value of $n$ is never \adname[SeriesOrder]{unknown} since the |
| function computes an \useterm{approximate order}. |
| % |
| The function guesses the order from the construction of the series |
| without accessing any coefficient that has not yet been computed. |
| % |
| If $a$ is a non-negative integer (\ie, can be coerce to such a |
| If $n$ is a non-negative integer (\ie, can be coerced to such a |
| type) then $f_i=0$ for all $i<n$, \ie, |
| \begin{gather} |
| \begin{gather}\label{eq:FormalPowerSeriesCategory:approximateOrder} |
| f = \sum_{i=n}^\infty {f_i x^i}. |
| \end{gather} |
| In other words, $n\leq\adname{order}(f)$. |
| |
| In cases like $f=x+f^2$ where there are two power series solutions |
| with different order (namely, 0 and 1), the function \adthisname{} |
| prefers the maximal possible value. Since the approximate order is |
| only a guess that can be made without actually accessing any |
| elements of the series, maximality cannot be assured in all cases. |
| |
| However, \adthistype{} is assumed to return the maximal value that |
| fulfils the system of equations for the order. So in equation |
| systems like |
| \begin{align*} |
| f &= x + g^3\\ |
| g &= x^3 + f^2 |
| \end{align*} |
| whose order equation system is |
| \begin{align*} |
| \ord f &= \min(1, 3\ord g)\\ |
| \ord g &= \min(3, 2\ord f) |
| \end{align*} |
| the maximal solution is $(\ord f, \ord g) = (1, 2)$ and these |
| values will be returned by \adthisname{}. |
| \end{addescription} |
| \begin{adremarks} |
| It might happen that the function returns different values when |
| 556,11 → 629,13 |
|---|
| called on the same series. For example, $a_1$ at one time and |
| $a_2$ at a later point in time. |
| % |
| In accordance with the specification above, it holds $a_1\le a_2$. |
| In accordance with the specification |
| \eqref{eq:FormalPowerSeriesCategory:approximateOrder}, it holds |
| $a_1\le a_2$. |
| \begin{adsnippet} |
| l: List Integer := [0,0,0,0,4,0]; |
| s: \adtype{DataStream} := stream generator l; |
| f: \adtype{FormalPowerSeries}(Integer) := s :: \adtype{FormalPowerSeries}(Integer); |
| s: \adtype{DataStream} Integer := stream generator l; |
| f := s :: \adtype{FormalPowerSeries}(Integer); |
| a1: \adtype{SeriesOrder} := \adthisname(f); |
| assert(0 = a1 :: MachineInteger); |
| z: Integer := \adname{coefficient}(f, 2); |
| 637,10 → 712,12 |
|---|
| \end{adusage} |
| \begin{addescription}{Coerces a stream to a series.} |
| For a generator $g$ which generates $f_0, f_1, f_2, \ldots$, the |
| call \adcode$\adthisname(g)$ constructs the series |
| call \adcode$\adthisname(g)$ constructs the \useterm{formal power series} |
| \begin{gather} |
| u = \sum_{n=0}^\infty {f_n x^n}. |
| \end{gather} |
| The operation constructs a \useterm{formal power series} whose |
| initial \useterm{approximate order} is \adname[SeriesOrder]{0}. |
| \end{addescription} |
| \begin{adseealso} |
| \adname{coerce: DataStream R -> %} |
| 664,10 → 741,14 |
|---|
| \end{adusage} |
| \begin{addescription}{Coerces a stream to a series.} |
| For a stream $s = (f_0, f_1, f_2, \ldots)$, the call |
| \adcode$\adthisname(s)$ constructs the series |
| \adcode$\adthisname(s)$ constructs the \useterm{formal power series} |
| \begin{gather} |
| u = \sum_{n=0}^\infty {f_n x^n}. |
| u = \sum_{n=0}^\infty {f_n x^n} |
| \end{gather} |
| whose \useterm{approximate order} depends on the cached values of |
| the stream $s$, \ie, if there is a $k < \adname[DataStream]{#}s$ |
| with $f_k\ne0$ and $f_i=0$ for all $i<k$ then the first call to |
| \adname{approximateOrder} on $u$ will return $k$. |
| \end{addescription} |
| \begin{adseealso} |
| \adname{coerce: Generator R -> %} |
| 688,9 → 769,10 |
|---|
| g: Generator T := generate for i in 0.. repeat yield i*i; |
| s: \adtype{DataStream} T := \adname[DataStream]{stream:Generator T->%} g; |
| u := s :: \adtype{FormalPowerSeries}(T); |
| t := u :: \adtype{DataStream}(T); |
| \end{adusage} |
| \begin{addescription}{Coerces a series to a stream.} |
| For a series |
| For a \useterm{formal power series} |
| \begin{gather} |
| u = \sum_{n=0}^\infty {f_n x^n}. |
| \end{gather} |
| 697,6 → 779,10 |
|---|
| the call \adcode$\adthisname(s)$ constructs the stream $s = (f_0, |
| f_1, f_2, \ldots)$. |
| \end{addescription} |
| \begin{adremarks} |
| In the above example, $s$ and $t$ contain the same sequence of |
| elements but may or may not share memory. |
| \end{adremarks} |
| \begin{adseealso} |
| \adname{coerce: DataStream R -> %} |
| \end{adseealso} |
| 798,7 → 884,7 |
|---|
| l1: List Integer := [1,1,2,5,14,42]; |
| l2: List Integer := [x for i in l1 for x in \adname{coefficients} s]; |
| assert(l1=l2); |
| ones: \adtype{FormalPowerSeries} Integer := series stream 1; |
| ones: := (stream 1) :: \adtype{FormalPowerSeries} Integer; |
| pos: \adtype{FormalPowerSeries} Integer := ones * ones; |
| m1: List Integer := [1,2,3,4,5,6,7]; |
| m2: List Integer := [x for i in m1 for x in \adname{coefficients} pos]; |
| 884,7 → 970,7 |
|---|
| s: S := stream(1) :: GS; |
| a: Array S := [s,s,s,s,s,s]; |
| l1: List Z := [6,6,6,6,6,6,6,6,6,6]; |
| l2: List Z := [x for i in l1 for x in \adname{coefficients} \adthisname{} g]; |
| l2: List Z := [x for i in l1 for x in \adname{coefficients} \adthisname{} a]; |
| assert(l1=l2); |
| \end{adusage} |
| \begin{addescription}{Finite sum of series.} |
| 895,13 → 981,11 |
|---|
| \begin{gather} |
| f = \sum_{n=0}^\infty {\sum_{k=0}^m (s_k)_n x^n}. |
| \end{gather} |
| where $(g_k)_n$ denotes the coefficient of $x^n$ in the series |
| where $(s_k)_n$ denotes the coefficient of $x^n$ in the series |
| $s_k$. |
| |
| The function \adthisname{} returns 0 for an empty input array. |
| \end{addescription} |
| \begin{adremarks} |
| The behaviour of the function is undefined if the input array |
| is of length 0. |
| \end{adremarks} |
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| 926,7 → 1010,7 |
|---|
| \begin{addescription}{Finite or infinite sum of series.} |
| Let $g = (g_0, g_1,g_2,g_3,\ldots)$ be a finite or infinite |
| sequence of \useterm{formal power series}. For simplicity, we |
| extend a finite sequence into an infinite one by adding zero |
| extend a finite sequence into an infinite one by adding \adname{0} |
| series. However, we do not allow $g$ to generate nothing at all. |
| |
| The call $\adthisname(g)$ returns a \useterm{formal power series} |
| 941,11 → 1025,12 |
|---|
| $g_k$. |
| \end{addescription} |
| \begin{adremarks} |
| The way in which we defined $f$ basically says that $f=\sum_{k=0}^\infty |
| g_k$ if $\ord(g_n)\geq n$. Although theoretically for finite sequences |
| $g=(g_0,g_1,\ldots, g_n)$ the order condition would not be necessary, |
| we must require it, since there is no way to figure out in advance |
| whether the given sequence $g$ is, in fact, finite. |
| The way in which we defined $f$ basically says that |
| $f=\sum_{k=0}^\infty g_k$ if $\ord(g_k)\geq k$ for all |
| $k\in\setN$. Although theoretically for finite sequences |
| $g=(g_0,g_1,\ldots, g_n)$ the order condition would not be |
| necessary, we must require it, since there is no way to figure out |
| in advance whether the given sequence $g$ is, in fact, finite. |
| |
| The behaviour of the function is undefined if input generator does |
| not generate any element. |
| 975,27 → 1060,33 |
|---|
| \begin{addescription}{Finite or infinite sum of series.} |
| Let $g = (g_0, g_1,g_2,g_3,\ldots)$ be a finite or infinite |
| sequence of \useterm{formal power series}. For simplicity, we |
| extend a finite sequence into an infinite one by adding zero |
| extend a finite sequence into an infinite one by adding \adname{1} |
| series. However, we do not allow $g$ to generate nothing at all. |
| |
| The call $\adthisname(g)$ returns a \useterm{formal power series} |
| For every $n$ the series $g_n$ must be of the form |
| \begin{gather}\label{eq:FormalPowerSeriesCategory:product} |
| g_n = 1 + \sum_{i=n}^\infty a_{ni} x^i. |
| \end{gather} |
| For all $n \in \setN$ let $h_n$ be defined by |
| \begin{gather} |
| f = \sum_{n=0}^\infty {f_n x^n}. |
| h_n = \sum_{k=0}^n {h_{nk} x^k} := \prod_{k=0}^n {g_{k}}. |
| \end{gather} |
| where for all $n\in\setN$ |
| |
| The call $\adthisname(g)$ returns a \useterm{formal power series} |
| \begin{gather} |
| f_n = \sum_{k=0}^n (g_k)_n |
| f = \prod_{k=0}^\infty {g_{k}} = \sum_{n=0}^\infty {h_{nn} x^n}. |
| \end{gather} |
| and $(g_k)_n$ denotes the coefficient of $x^n$ in the series |
| $g_k$. |
| \end{addescription} |
| \begin{adremarks} |
| The way in which we defined $f$ basically says that $f=\sum_{k=0}^\infty |
| g_k$ if $\ord(g_n)\geq n$. Although theoretically for finite sequences |
| $g=(g_0,g_1,\ldots, g_n)$ the order condition would not be necessary, |
| we must require it, since there is no way to figure out in advance |
| whether the given sequence $g$ is, in fact, finite. |
| The way in which we defined $f$ basically says that the $n$-th |
| coefficient of the resulting series only depends on the first $n$ |
| input series. |
| |
| Although theoretically for finite sequences $g=(g_0,g_1,\ldots, |
| g_n)$ such a condition would not be necessary, we must require it, |
| since there is no way to figure out in advance whether the given |
| sequence $g$ is, in fact, finite. |
| |
| The behaviour of the function is undefined if input generator does |
| not generate any element. |
| \end{adremarks} |
| 1012,14 → 1103,6 |
|---|
| |
| |
| |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| if R has with {*: (Integer, %) -> %} then { |
| <<exports: FormalPowerSeriesCategory differentiate>> |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| \begin{+++} |
| \begin{adusage} |
| \end{adusage} |
| 1042,6 → 1125,13 |
|---|
| differentiate: % -> %; |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| if R has with {*: (Integer, %) -> %} then { |
| <<exports: FormalPowerSeriesCategory differentiate>> |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| |
| 1050,13 → 1140,6 |
|---|
| |
| |
| |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| if R has with {*: (Fraction Integer, %) -> %} then { |
| <<exports: FormalPowerSeriesCategory integrate>> |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| \begin{+++} |
| \begin{adusage} |
| 1082,6 → 1165,13 |
|---|
| integrate: (%, integrationConstant: R == 0) -> %; |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| if R has with {*: (Fraction Integer, %) -> %} then { |
| <<exports: FormalPowerSeriesCategory integrate>> |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| |
| 1090,13 → 1180,6 |
|---|
| |
| |
| |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| if R has with {*: (Integer, %) -> %; *: (Fraction Integer, %) -> %} then { |
| <<exports: FormalPowerSeriesCategory exponentiate>> |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| \begin{+++} |
| \begin{adusage} |
| 1122,6 → 1205,13 |
|---|
| exponentiate: % -> %; |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<exports: FormalPowerSeriesCategory>>= |
| if R has with {*: (Integer, %) -> %; *: (Fraction Integer, %) -> %} then { |
| <<exports: FormalPowerSeriesCategory exponentiate>> |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| |
| 1146,6 → 1236,7 |
|---|
| |
| |
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsection{FormalPowerSeries} |
| \label{sec:FormalPowerSeries} |
| 1152,8 → 1243,8 |
|---|
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \addescribetype{FormalPowerSeries} |
| |
| This domain implements the ring $R[ [x] ]$ of \useterm{formal power |
| series} over a ring $R$. |
| The domain \adthistype{} implements the ring $R[ [x] ]$ of |
| \useterm{formal power series} over a ring $R$. |
| |
| For a greater range of applicability, our \xAldor{} implementation |
| only requires that $R$ provides ring-like operations, \ie, $R$ must |
| 1168,7 → 1259,157 |
|---|
| |
| A series is basically a stream of elements of $R$. |
| % |
| However, we want to be able to deal with code like the following. |
| However, we want to be able to deal series definitions like |
| \eqref{eq:fps:defining}. |
| |
| Let $f_1, f_2, \ldots, f_n$ be a number of (not necessarily different) |
| binary operations on \useterm{formal power series} and assume that we |
| have given a system |
| \begin{equation} |
| \begin{split} |
| s_1 &= f_1(s_{i_{11}}, s_{i_12})\\ |
| s_2 &= f_2(s_{i_{21}}, s_{i_22})\\ |
| &\cdots\\ |
| s_n &= f_n(s_{i_{n1}}, s_{i_n2}) |
| \end{split}\label{eq:fps:defining} |
| \end{equation} |
| where $i_{k1},i_{k2}\in\Set{1,\ldots,n}$ for all |
| $k\in\Set{1,\ldots,n}$. |
| |
| We would like to be able to determine the power series |
| $s_1,\ldots,s_n$ by our implementation. |
| |
| To the operations $f_1,\ldots,f_n$ correspond certain operations |
| $o_1,\ldots,o_n$ on the order% |
| \footnote{The order of a powerseries is the smallest power of $x$ that |
| has a non-zero coefficient.} |
| % |
| of the series, respectively. |
| % |
| For example, to addition corresponds the minimum of the |
| orders\footnote{If $h=f+g$ then in general we have the relation $\ord |
| h\ge \min(\ord f,\ord g)$. We will, however, take this with the |
| equality sign as the definition of the \useterm{approximate |
| order}.}, to multiplication corresponds addition of the orders, |
| and to composition of series corresponds multiplication of the orders. |
| |
| Thus, to the above system \eqref{eq:fps:defining} of series |
| corresponds a system of the (approximate) orders. |
| \begin{equation} |
| \begin{split} |
| \ord s_1 &= o_1(\ord s_{i_{11}}, \ord s_{i_12})\\ |
| \ord s_2 &= o_2(\ord s_{i_{21}}, \ord s_{i_22})\\ |
| &\cdots\\ |
| \ord s_n &= o_n(\ord s_{i_{n1}}, \ord s_{i_n2}). |
| \end{split}\label{eq:ord:defining} |
| \end{equation} |
| |
| \begin{Definition} |
| An \defineterm{approximate order} of a series $s_k$ defined by a |
| system~\eqref{eq:fps:defining} is a maximal solution (for |
| $\ord(s_k)$) of the corresponding system~\eqref{eq:ord:defining}. |
| \end{Definition} |
| Note that we mean here maximal in each component if one considers the |
| vector $(\ord s_1, \ldots, \ord s_n)$. Existence of a (maximal) |
| solution to \eqref{eq:ord:defining} does not mean that a unique |
| solution to \eqref{eq:fps:defining} exists. A counter example is the |
| system |
| \begin{equation} |
| \begin{split} |
| x = \xi(s, s)\\ |
| s = x + t\\ |
| t = \delta(s, s) |
| \end{split} |
| \label{eq:fps:impossible} |
| \end{equation} |
| where $\delta(s, s)=s'$ means differentiation of $s$ by $x$. The |
| \useterm{approximate order} vector is $(1, 0, 0)$, but the solution to |
| the obove system is $(x, 1+x+c\cdot\exp x, 1+c\cdot\exp x)$ with an |
| arbitrary constant $c$. |
| |
| We only introduce the \useterm{approximate order} as an auxiliary |
| concept that allows us to define some series recursively, by assigning |
| 0 to a number of initial values of the series. |
| |
| Once the \useterm{approximate order} has been computed, it is smaller |
| or equal to the true order of the corresponding series. |
| |
| In fact, the \defineterm{order computation} is done in two phases. |
| \begin{enumerate} |
| \item\label{approximateOrder:Phase1} \emph{Compute a solution to the |
| system~\eqref{eq:ord:defining} without accessing any coefficient |
| of the involved series.} |
| |
| The first phase is started by a call to % |
| \adname{computeApproximateOrder!: % -> Boolean} % |
| and completed when this function returns false. |
| |
| Starting from $\infty$, the order system~\eqref{eq:ord:defining} is |
| iterated. In each step the (iterated) value of the |
| \useterm{approximate order} is either decreased or stays as it was. |
| If during iteration the value of the \useterm{approximate order} |
| would increase, an error is signalled and the computation is |
| aborted. (Such an error should never happen if the order functions |
| $o_k$ are monotone% |
| \footnote{A function $f: X^2\to X$ is \emph{monotone} if $a\le |
| a'$ and $b\le b'$ imply $f(a,b)\le f(a',b')$.} |
| in the arguments they actually depend on.) |
| % |
| Therefore, that iteration process must terminate with a solution, |
| since the order is bounded from below by 0. |
| |
| \item\label{approximateOrder:Phase2} \emph{Improve the |
| \useterm{approximate order} until a non-zero coefficient is found |
| and thus the true order of the series is known.} |
| |
| The second phase is started under the condition that the (internal) |
| function \adname{initialized?} returns true by the function |
| \adname{improveOrder!}. |
| % |
| The phase is completed when the true order of the series can be |
| verified by accessing a (precomputed) non-zero coefficient. |
| % |
| If this phase is completed, the \useterm{approximate order} is equal |
| to the true order of the series. |
| |
| In the second phase, coefficients must actually be computed. An |
| exception (\adtype{BadIndexException}) is raised, if during the |
| computation of a coefficient with index $k$ the computation of a |
| coefficient with index $\ge k$ is required. |
| \end{enumerate} |
| |
| Both phases will be triggered by a call to the (internal) function |
| \adname{initialize!} which is called every time the function |
| \adname{zero?} is called. |
| % |
| Phase~\ref{approximateOrder:Phase1} for a series might have |
| been triggered already by a recursive call to % |
| \adname{computeApproximateOrder!: % -> Boolean} % |
| even without having invoked \adname{initialize!} on that series. |
| |
| Let us consider the example. |
| \begin{equation} |
| \begin{split} |
| x &= \xi(s, s)\\ |
| s &= x + t\\ |
| t &= s \cdot s. |
| \end{split} |
| \end{equation} |
| where $\xi$ is a function that ignores its arguments and returns the |
| series $x$. To $\xi$ corresponds the function $\eta$ on the order |
| which also ignores its arguments and returns 1. So the corresponding |
| system is given by |
| \begin{equation} |
| \begin{split} |
| \ord x &= \eta(\ord s, \ord s)\\ |
| \ord s &= \min(\ord x, \ord t)\\ |
| \ord t &= \ord s + \ord s. |
| \end{split} |
| \end{equation} |
| That system has actually two solutions for $(\ord x, \ord s, \ord t)$, |
| namely, $(1,0,0)$ and $(1,1,2)$. The latter one is maximal. |
| |
| The above system is encoded in the following way. |
| \begin{adsnippet} |
| import from Integer; |
| s: \adthistype{} Integer := \adname{new: () -> %}(); |
| 1177,7 → 1418,7 |
|---|
| l1: List Integer := [0, 1, 1, 2, 5, 14, 42]; |
| l2: List Integer := [x for i in l1 for x in \adname{coefficients} s]; |
| \end{adsnippet} |
| And we want that the two lists $l_1$ and $l_2$ agree. |
| We want that the two lists $l_1$ and $l_2$ agree. |
| |
| Note that the series equation actually is $s = x + s^2$ which, in |
| fact, has two solutions. |
| 1190,15 → 1431,13 |
|---|
| For applications in generating series, we are only interested in |
| series with non-negative coefficients. Since we cannot test infinitely |
| many coefficients we choose one of the series by another method. We |
| simply take the one that has the biggest order.% |
| \footnote{The order of a powerseries is the smallest power of $x$ that |
| has a non-zero coefficient.} |
| simply take the one that has the biggest order. |
| |
| In fact, such an approach is reasonable in order to help prevent |
| infinite recursion. Note that in our design we never see the whole |
| defining series equation. All that we can build on are data structures |
| and the local operators \adname[FormalPowerSeriesCategory]{+} and |
| \adname[FormalPowerSeriesCategory]{*}. So we cannot invoke a solver |
| and the local operators like \adname[FormalPowerSeriesCategory]{+} and |
| \adname[FormalPowerSeriesCategory]{*} etc. So we cannot invoke a solver |
| that returns the radical expression and from there generate the |
| series. |
| |
| 1208,29 → 1447,21 |
|---|
| the biggest possible order would be so that the series still fulfils |
| the equation. |
| |
| To do that algorithmically, we first assume an unknown order an try to |
| adjust it at the operator places. |
| |
| |
| % |
| In fact, to break recursion, it is sufficient to work with an |
| approximate order. An \defineterm{approximate order} of a series is |
| either unknown or it is smaller or equal to the true order of the |
| series.% |
| \footnote{Of course, this is quite a vague definition since it would |
| allow us to define the approximate order to be 0. However, the |
| approximate order should be \emph{close enough} to the true order so |
| that it can be exploited to break recursion.} |
| % |
| So internally, we store an approximate order and the true order of the |
| series. Initially, (except for certain series like 0 or 1) these |
| values are set to \adname[SeriesOrder]{unknown}. If the first |
| coefficient needs to be accessed, the \useterm{approximate order} is |
| computed (and not earlier). The true order is then figured out |
| starting from the \useterm{approximate order} and checking |
| \emph{already accessed} elements. |
| Internally, we store an \useterm{approximate order} and the true order |
| of the series. Initially, (except for certain series like |
| \adname[FormalPowerSeriesCategory]{0} or |
| \adname[FormalPowerSeriesCategory]{1}) these values are set to |
| \adname[SeriesOrder]{unknown}. If the first coefficient needs to be |
| accessed, the \useterm{approximate order} is computed (Phase~\ref{approximateOrder:Phase1}). The true order is then figured out starting from the |
| \useterm{approximate order} and checking \emph{already accessed} |
| elements (Phase~\ref{approximateOrder:Phase2}). |
| |
| \begin{Convention}\label{convention:Order:DontStepGenerator} |
| In no case is the order computation allowed to step the generator |
| that is stored insided the stream from the representation. |
| In no case is the \useterm{order computation} allowed to step the |
| generator that is stored insided the stream from the representation. |
| \end{Convention} |
| |
| Another example that we want to be able to deal with is given by the |
| 1261,12 → 1492,6 |
|---|
| |
| |
| |
| \begin{ToDo} |
| \begin{rhx} |
| 12-Sep-2006: Add a proof that under certain conditions there is |
| only one such sequence with maximal order. |
| \end{rhx} |
| \end{ToDo} |
| |
| |
| |
| 1281,7 → 1506,6 |
|---|
| |
| |
| |
| |
| \begin{+++} |
| \begin{adusage} |
| macro R == Integer; |
| 1304,6 → 1528,7 |
|---|
| Y == rep y; |
| T == rep t; |
| } |
| <<macros: FormalPowerSeries>> |
| <<representation: FormalPowerSeries>> |
| import from R, Rep, I, SeriesOrder; |
| <<TRACE: FormalPowerSeries>> |
| 1326,7 → 1551,7 |
|---|
| tw := s :: TextWriter; |
| tw << name(x) << " [" << X.order; |
| tw << "," << X.approximateOrder; |
| tw << "," << X.approximateOrderChanged? << ","; |
| tw << "," << X.touched? << ","; |
| if initialized? x then { |
| tw << "#" << #(X.coefficientStream); |
| } else { |
| 1368,17 → 1593,17 |
|---|
| created and one series for the \adname{+} operation. The latter one is |
| identical to $s$. |
| |
| That seems to be a waste of memory, but it basically saves |
| That seems to be a waste of memory, but it basically saves/caches |
| intermediate results, that would have to be recomputed otherwise. |
| |
| If any improvement with respect to memory consumption is started |
| later, one should take care not to remove the structure that stores |
| the approximate order of these auxiliary series. |
| the \useterm{approximate order} of these auxiliary series. |
| |
| The \useterm{approximate order} is heavily used to avoid recursion in |
| the above examples. Basically, before any coefficient is accessed, an |
| approximate order is computed for every series involved in the |
| expression. |
| \useterm{approximate order} is computed for every series involved in |
| the expression. |
| |
| If we abbreviate $x=\adname{monom}$, we can write the second example |
| as: |
| 1411,8 → 1636,81 |
|---|
| \label{sec:representation:FormalPowerSeries} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| \begin{ToDo} |
| \begin{rhx} |
| 18-Sep-2008: Collect the functions from \adtype{DataStream} that |
| are really needed here. This data structure should eventually |
| become a parameter, so that we could have caching and non-caching |
| powerseries. |
| \begin{verbatim} |
| DataStream: (R: ArithmeticType) -> with { |
| new: () -> %; |
| #: % -> I; |
| constant?: % -> Boolean; |
| apply: (%, I) -> R; |
| stream: R -> %; |
| stream: Generator R -> %; |
| elements: (%, startFromIndex: I == 0) -> Generator R; |
| generator: % -> Generator R; |
| } |
| \end{verbatim} |
| \end{rhx} |
| \end{ToDo} |
| |
| The representation of elements of \adthistype{} contains entries that |
| are relevant for the \useterm{order computation} and certain other |
| functions. |
| \begin{description} |
| \item[\adname{computeApproximateOrder!}:] For |
| Phase~\ref{approximateOrder:Phase1}, the following fields are of |
| importance. |
| \begin{description} |
| \item[approximateOrder:] This field is initially set to |
| \adname[SeriesOrder]{unknown} when a series is created using one |
| of the functions whose name start with |
| \adname[FormalPowerSeriesCategory]{new}. It is reset to |
| \adname[SeriesOrder]{infinity} when |
| Phase~\ref{approximateOrder:Phase1} actually begins and will be |
| decreased in \adname{computeApproximateOrder!}. |
| \item[computeApproximateOrder!] is called to compute the |
| \useterm{approximate order} of the series in question. |
| \item[touched?] is usually false, but set to true before |
| \adname{computeApproximateOrder!} is started recursively in order |
| to prevent infinite recursion and set to false again on return of |
| that function. |
| \end{description} |
| |
| \item[\adname{improveOrder!}:] For Phase~\ref{approximateOrder:Phase2}, |
| the following fields are of importance. |
| \begin{description} |
| \item[coefficientStream] holds the stream of coefficients. |
| \item[approximateOrder] is increased according to precomputed values |
| in the above stream. |
| \item[order] either holds \adname[SeriesOrder]{unknown} or the true |
| order of the series. |
| \end{description} |
| |
| \item[\adname{initialize!}:] These fields are set between |
| Phase~\ref{approximateOrder:Phase1} and |
| Phase~\ref{approximateOrder:Phase2}. |
| \begin{description} |
| \item[computeCoefficients] is used to form the stream of the series. |
| \item[coefficientStream] is set with the data taken from the above |
| field and the \useterm{approximate order} (after |
| computeApproximateOrder! returns false). |
| \item[initializedCoefficients?] is set from false to true if the |
| above stream initialization has been finished. |
| \end{description} |
| |
| \item[\adname{coefficient}:] These fields used to compute a |
| coefficient of the series. |
| \begin{description} |
| \item[coefficientStream] holds all the coefficients. |
| \item[index] is usually set to \admacro{unassigned}, but used to |
| prevent infinite recursion in the computation of coefficients. |
| \end{description} |
| \end{description} |
| |
| Note that if the following data structure is changed, the function |
| \adname{set!: (%, %) -> ()} must be changed appropriately. |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| 1421,27 → 1719,42 |
|---|
| #if TRACE |
| TRACENAME: String, |
| #endif |
| order: SeriesOrder, |
| approximateOrder: SeriesOrder, |
| approximateOrderChanged?: Boolean, |
| computeApproximateOrder!: % -> (), |
| initializedCoefficients?: Boolean, |
| coefficientStream: DataStream R |
| order: SeriesOrder, -- Phase 2 |
| approximateOrder: SeriesOrder, -- Phase 1 (dec), Phase 2 (inc) |
| computeApproximateOrder!: % -> Boolean, -- Phase 1 |
| computeCoefficients: I -> Generator R, -- initialize! |
| coefficientStream: DataStream R, -- initialize!,Phase 2,coefficient |
| initializedCoefficients?: Boolean, -- initialize!, |
| touched?: Boolean, -- Phase 1 |
| index: I -- coefficient |
| ); |
| macro BRACKET(o, ao, c?, cao, i?, c) == per [ |
| @ %def TRACENAME coefficientStream approximateOrderChanged? initializedCoefficients? touched? |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| The macro \addefinemacro{unassigned} is just used to indicated that |
| the index entry in the representation record is currently unused. |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<macros: FormalPowerSeries>>= |
| macro unassigned == -1; -- for index entry |
| macro BRACKET(o, ao, cao, cc, c, i?) == per [ |
| #if TRACE |
| "??", |
| #endif |
| o, ao, c?, cao, i?, c]; |
| @ %def TRACENAME coefficientStream BRACKET approximateOrderChanged? initializedCoefficients? |
| o, ao, cao, cc, c, i?, false, unassigned]; |
| @ %def unassigned BRACKET |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| We have the following possible meanings: |
| Before Phase~\ref{approximateOrder:Phase1}, order and |
| \useterm{approximate order} are initialized to |
| \adname[SeriesOrder]{unknown}. |
| % |
| After Phase~\ref{approximateOrder:Phase1}, we have the following |
| possible combinations. |
| % |
| \begin{center} |
| \begin{tabular}{|l|l|l|} |
| \hline |
| \adcode$order$ & \adcode$approximateOrder$ & meaning\\ |
| \hline |
| unknown & unknown & order is not yet computed\\ |
| unknown & $n\geq0$ & order is computed but not verified\\ |
| unknown & $\infty$ & should never happen\\ |
| $\infty$ & $\infty$ & the series is zero\\ |
| 1457,6 → 1770,20 |
|---|
| only if it is necessary to get the real value of a coefficient of the |
| series. |
| |
| Other relations between the fields. If $t$ is a |
| \adtype{FormalPowerSeries} then |
| % |
| { |
| \def\ao{\texttt{rep(t).approximateOrder}} |
| \def\o{\texttt{rep(t).order}} |
| \def\u{\adname[SeriesOrder]{unknown}} |
| \begin{align*} |
| \ao=\u &\implies \texttt{not \adname{initialized?} t},\\ |
| \ao=\u &\implies \o=\u. |
| \end{align*} |
| } |
| |
| |
| The value \adname[SeriesOrder]{unknown} is returned from the function |
| \adname[FormalPowerSeriesCategory]{order} to the user if it is not yet |
| known what the (true) order of the series is. |
| 1561,40 → 1888,43 |
|---|
| \begin{enumerate} |
| \item Build the representation record with some uninitialized data. |
| \item Right before the first coefficient is accessed, the |
| \useterm{approximate order} is computed and the coefficient stream |
| is initialized. |
| \useterm{approximate order} is computed |
| (Phase~\ref{approximateOrder:Phase1}) and the coefficient stream is |
| initialized by the function \adname{initialize!}. |
| \end{enumerate} |
| |
| In fact, we delay not only the order computation until a coefficient |
| is needed, but even the computation of the stream of coefficients is |
| delayed. Since we have to put something in the representation at the |
| place where the coefficient stream is stored, we decided to put the |
| empty stream. |
| In fact, we delay not only the \useterm{order computation} until a |
| coefficient is needed, but even the computation of the stream of |
| coefficients is delayed. Since we have to put something in the |
| representation at the place where the coefficient stream is stored, we |
| decided to put the empty stream. |
| % |
| \addefinename{uninitializedStream: DataStream R}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local uninitialized: DataStream R == new() $ DataStream(R); |
| @ %$ |
| local uninitializedStream: DataStream R == new() $ DataStream(R); |
| @ %def uninitializedStream |
| %$ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| Whether or not the field \useterm{coefficientStream} is uninitialized, |
| should correspond to the value stored in the field |
| \useterm{initializedCoefficients?}. |
| |
| Furthermore, we want to be able to check whether coefficients can |
| actually be accessed. |
| \addefinename{initialized?:%->Boolean}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local initialized?(x: %): Boolean == X.initializedCoefficients?; |
| @ %def initialized? |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| Via that field we make sure that the initialization, \ie, the |
| computation of an \useterm{approximate order} and the actual |
| compuation of the coefficient stream is done only once. |
| Via the field \adcode$initializedCoefficients?$ we make sure that the |
| initialization, \ie, the computation of an \useterm{approximate order} |
| and the actual compuation of the coefficient stream is done only once. |
| |
| The following function \adname{initialize!} is an auxiliary function |
| that is called at the beginning of the function \adname{zero?} (\cf{} |
| Section~\ref{sec:FormalPowerSeries:ZeroRecognition}) and (through the |
| call to \adname{zero?} also in the function \adname{coefficient}) in |
| order to compute an \useterm{approximate order} of the series, to |
| improve a previously computed order, and to set the true order if it |
| can be verified that the \useterm{approximate order} is the true order |
| of the series. |
| order to do the \useterm{order computation} and initialize the |
| \adcode$coefficientStream$. |
| % |
| In fact, the function is called any time before a coefficient is |
| accessed in order to make sure everything is properly set. |
| 1605,220 → 1935,106 |
|---|
| since in that case it is assumed that the coefficient stream has |
| already been initialized. In that case also the \useterm{approximate |
| order} must be known. Nothing must be done. |
| \item If the \useterm{approximate order} is known, then (at the time |
| \adname{initialize!} is called) also the coefficient stream must |
| already have been initialized. In that case we can try to improve |
| the \useterm{approximate order} and possibly set the true order of |
| the series. |
| \item If the series is known to be initialized, \ie, its coefficient |
| stream is set, then \useterm{approximate order} is known as well. In |
| that case we can try to improve the \useterm{approximate order} and |
| possibly set the true order of the series, see |
| \adname{improveOrder!}. |
| \item If nothing is known, the actual initialization is started. It |
| first computes an \useterm{approximate order} and then initializes |
| the coefficient stream. |
| first computes an \useterm{approximate order} |
| (Phase~\ref{approximateOrder:Phase1}) and then initializes the |
| coefficient stream. |
| \end{enumerate} |
| |
| All this is done via the function |
| \adcode$\adname{computeApproximateOrder!}(x)$\footnote{% |
| That function should rather be called |
| \texttt{initializeApproximateOrderAndCoefficients!} since it also |
| initializes the coefficient stream if it was not set when the |
| function was invoked. However, the main and complicated task of |
| the function is the computation of the \useterm{approximate |
| order}. Unfortunately, we have not found a better place for the |
| coefficient initialization code.}. |
| Note that the following function only accesses already computed |
| coefficients if the data structure is known to be initialized, \ie, in |
| Phase~\ref{approximateOrder:Phase2}. |
| % |
| \addefinename{computeApproximateOrder!: % -> ()}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local computeApproximateOrder!(x: %): () == { |
| (X.computeApproximateOrder!)(x); |
| assert(X.approximateOrder ~= unknown); |
| } |
| @ %def computeApproximateOrder! |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| Otherwise only the data structure of $x$ is initialized, but \emph{no} |
| coefficient is actually computed in accordance with |
| Convention~\ref{convention:Order:DontStepGenerator}. |
| % |
| With the help of the functions \adname{approximateOrder!}, |
| \adname[FormalPowerSeriesCategory]{new:()->%}, |
| and \adname{set!} a recursive approximation of the |
| order can be done. |
| In no case will the following function compute any new coefficient of |
| $x$, \ie, |
| \adcode$\adname[FormalPowerSeriesCategory]{#}(x::\adtype{DataStream})$ |
| is an invariant of this function. |
| % |
| A very important fact is that for the function |
| \adname{computeApproximateOrder!} it can happen that the |
| \useterm{approximate order} is set to something different than |
| \adname[SeriesOrder]{unknown} and at the same time the coefficient |
| stream is uninitialized. In particular that happens for recursive |
| definitions of streams like the following. |
| \begin{adsnippet} |
| s: \adthistype{} Integer := \adname{new: () -> %}(); |
| \adname{set!}(s, \adname{1} \adname{+} \adname{monom} \adname{*} s); |
| \end{adsnippet} |
| \end{enumerate} |
| % |
| \addefinename{initialize!: % -> ()}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local initialize!(x: %): () == { |
| TRACEFPS("initialize!", "B", x); |
| X.order ~= unknown => return; -- nothing to do |
| ao: SeriesOrder := X.approximateOrder; |
| assert(ao ~= infinity); -- because order would be equal to infinity |
| ao ~= unknown => {<<try to improve the approximate order ao>>} |
| assert(not initialized? x); |
| computeApproximateOrder! x; |
| TRACEFPS("initialize!", "E", x); |
| assert(initialized? x); |
| TRACEFPS("initialize!", "BEGIN", x); |
| X.order ~= unknown => {assert(initialized? x); return} -- nothing to do |
| assert(X.approximateOrder ~= infinity); |
| -- X.approximateOrder ~= infinity implies X.order = infinity. |
| initialized? x => improveOrder! x; -- Phase 2 |
| while computeApproximateOrder! x repeat { -- Phase 1 |
| TRACEFPS("initialize!", "while", x); |
| } |
| -- Now we must set the coefficient stream |
| ao: SeriesOrder := X.approximateOrder; |
| assert(ao ~= unknown); |
| TRACEFPS("initialize!", "set coeff", x); |
| if ao = infinity then { |
| X.order := infinity; |
| X.coefficientStream := stream(0); |
| } else { |
| g: Generator R := (X.computeCoefficients)(ao::I); |
| X.coefficientStream := stream g; |
| } |
| X.initializedCoefficients? := true; |
| TRACEFPS("initialize!", "END", x); |
| } |
| @ % |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| The while loop above cannot iterate infinitely often. The |
| implementation of \adname{setApproximateOrder!} (which is used in |
| Phase~\ref{approximateOrder:Phase1}) ensures that the |
| \useterm{approximate order} does not strictly increase. So if ever the |
| \useterm{approximate order} changes from |
| \adname[SeriesOrder]{infinity} to some finite value it can either |
| strictly decrease only finitely often or it stays as it is. In any |
| case, the \useterm{approximate order} is eventually not changed and |
| thus, \adname{computeApproximateOrder!} must return false. |
| |
| Before we come to the function \adname{computeApproximateOrder!}, let |
| us deal with the case where an \useterm{approximate order} is known |
| and we need to verify whether the \useterm{approximate order} is, in |
| fact, the true order of the series. The code below does this by |
| testing whether the entry in the position given by the |
| \useterm{approximate order} is really non-zero. |
| % |
| If that is the case, it changes the \adcode$order$ entry in the |
| representation from \adname[SeriesOrder]{unknown} to the |
| \useterm{approximate order}. |
| % |
| If it is not the case, the \useterm{approximate order} can be |
| increased by 1 and another check is done. According to |
| Convention~\ref{convention:Order:DontStepGenerator}, this iteration |
| can only be done for the finitely many elements of the series that |
| have already been accessed. |
| % |
| If this iteration does not recognize the true order of the series, we |
| wait for the next call to \adname{initialize!} to improve the |
| \useterm{approximate order} further. |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Phase 1: Computation of an Approximate Order} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| We have chosen such a stepwise approach since $x$ might be the zero |
| series coming, for example, from |
| \begin{adsnippet} |
| x := \adname[DataStream]{stream: Generator T -> %}(generate repeat yield 0) :: \adthistype{}(Integer); |
| \end{adsnippet} |
| For such a series \adname{initialize!} would not terminate while |
| trying to improve the \useterm{approximate order}. |
| % |
| See also the implementation of the function \adname{coerce} in |
| \adthistype{} as given in |
| Section~\ref{sec:FormalPowerSeries:SeriesConstructors}. |
| |
| To check the true order, we must access elements of the given series |
| without violating Convention~\ref{convention:Order:DontStepGenerator}. |
| Phase~\ref{approximateOrder:Phase1} of \useterm{order computation} is |
| the process that starts at invocation of the function |
| \adname{computeApproximateOrder!} and stops when after multiple calls |
| this function returns false (which means \emph{nothing has changed}). |
| % |
| The computation of the order should in no case start the generator |
| that is stored inside the stream of the series, order computation is, |
| however, allowed to access elements of the stream that are already |
| computed, \ie, for a series $x$ and |
| \begin{adsnippet} |
| s := x :: \adtype{DataStream}(\adtype{Integer}); |
| \end{adsnippet} |
| it is allowed to call |
| \begin{adsnippet} |
| c: Integer := s.n; |
| \end{adsnippet} |
| for any $n<\adname[DataStream]{#}s$. |
| |
| Note that, in case we have realized that the series is the zero |
| series, the order and the \useterm{approximate order} have been set to |
| \adname[SeriesOrder]{infinity}. Thus if we know that the order is |
| \adname[SeriesOrder]{unknown} then we also know that the |
| \useterm{approximate order} is not \adname[SeriesOrder]{infinity}. |
| |
| \addefinename{computeApproximateOrder!: % -> Boolean}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<try to improve the approximate order ao>>= |
| i: I := ao :: I; |
| c: DataStream R := X.coefficientStream; |
| n: I := #c; |
| TRACE("number of cached values = ", n); |
| i >= n => {<<try to recognize the zero series>>} |
| while i < n and zero? c.i repeat { |
| TRACE("verifyOrder! zero i = ", i); |
| i := next i; |
| X.approximateOrder := i :: SeriesOrder; |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local computeApproximateOrder!(x: %): Boolean == { |
| changed? := (X.computeApproximateOrder!)(x); |
| assert(X.approximateOrder ~= unknown); |
| changed?; |
| } |
| if i < n then { -- "if not zero? c.i" might be more costly |
| TRACE("verifyOrder! non-zero i = ", i); |
| X.order := i :: SeriesOrder; |
| } |
| @ |
| %" |
| @ %def computeApproximateOrder! |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| To recognize the zero series is only possible if we detect that the |
| underlying stream is constant. If that is the case and the last |
| computed value is 0, then we know we have the zero series, since we |
| only run the following code if all values at entries less than the |
| current \useterm{approximate order} are 0. |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<try to recognize the zero series>>= |
| TRACE("Constant stream?: ", constant? c); |
| not constant? c => return; -- for non-constant series we cannot do anything |
| assert(zero?(c.(prev #c))); |
| X.approximateOrder := infinity; |
| X.order := infinity; |
| @ % |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| Note that we do not need to test anymore whether the constant value is |
| zero. Either the \useterm{approximate order} is already bigger than |
| $\adname{#}(c)$ or it has been increased one by one in previous |
| invocations of \adname{initialize!}. |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Computation of an Approximate Order} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| |
| Let us describe how to compute an \useterm{approximate order} if it |
| has not yet been done. |
| |
| Our representation data structure (see |
| Section~\ref{sec:representation:FormalPowerSeries}) contains an entry |
| \begin{adsnippet} |
| computeApproximateOrder!: % -> () |
| computeApproximateOrder!: % -> Boolean |
| \end{adsnippet} |
| which is used for the computation of an \useterm{approximate order} if |
| it is needed. How the \useterm{approximate order} should be computed, |
| is stored in that entry. |
| it is needed. |
| % |
| This function computes a new \useterm{approximate order}. It can make |
| use of the entry |
| This function should check the entry |
| \begin{adsnippet} |
| approximateOrderChanged?: Boolean |
| touched?: Boolean |
| \end{adsnippet} |
| in the representation. That entry is initially set to |
| \adname[Boolean]{true} and is particularly useful to avoid infinite |
| recursion while computing an \useterm{approximate order} in |
| recursively defined series as given, for example, in the following |
| code. |
| in the representation and do nothing if this entry is true. That entry |
| is initially set to \adname[Boolean]{true} and is particularly useful |
| to avoid infinite recursion while computing an \useterm{approximate |
| order} in recursively defined series as given, for example, in the |
| following code. |
| \begin{adsnippet} |
| import from Integer; |
| s: \adthistype{} Integer := \adname{new}(); |
| 1828,9 → 2044,6 |
|---|
| \end{adsnippet} |
| In particular the function \adname{approximateOrder!} uses that entry |
| in a non-trivial way. |
| % |
| Basically, the computation recurses until the \useterm{approximate |
| order} does not change anymore. |
| |
| |
| |
| 1847,40 → 2060,37 |
|---|
| Let us now describe functions that could be stored in the |
| representation data structure at \adcode$computeApproximateOrder!$. |
| % |
| We allow the following functions. |
| \begin{description} |
| \item[\adname{doNothing}:] The function does nothing at all. It is a |
| dummy function for cases where an (\useterm[approximate]{approximate |
| order}) order is known at creation time of the series. |
| \item[\adname{doNothing}:] The function does nothing at all, except |
| returning with \adname[Boolean]{false}. It is a dummy function for |
| cases where an (\useterm[approximate]{approximate order}) order is |
| known at creation time of the series. |
| \item[\adname{uninitialized}:] The function is an auxiliary function |
| for the definition of an uninitialized power series through the |
| function \adname{new:()->%}. |
| This function raises an exception when called. |
| \item[\adname{approximateOrder!}:] This function (or rather |
| \emph{these} functions, since there is a nullary, unary, and binary |
| version) computes a new \useterm{approximate order} from approximate |
| orders of its arguments. It should be understood as a wrapper |
| function around the functions such as \adname[SeriesOrder]{+} and |
| \adname[SeriesOrder]{*} from \adtype{SeriesOrder} which takes care |
| of recursively defined series. |
| \item[\adname{approximateOrder0!}, \adname{approximateOrder1!}, |
| \adname{approximateOrder2!}:] Functions that compute a new |
| \useterm{approximate order} from approximate orders of its |
| arguments. They should be understood as a wrapper function around |
| functions such as \adname[SeriesOrder]{min}, |
| \adname[SeriesOrder]{+}, and \adname[SeriesOrder]{*} from |
| \adtype{SeriesOrder} which takes care of recursively defined series. |
| |
| These functions do not fit into the entry |
| \adcode$computeApproximateOrder!$ (see |
| Section~\ref{sec:representation:FormalPowerSeries}), but rather |
| something like |
| \begin{adsnippet} |
| \adname{approximateOrder2!}(\adname[SeriesOrder]{min}, x, y) |
| \end{adsnippet} |
| has the right signature |
| \begin{adsnippet} |
| % -> Boolean |
| \end{adsnippet} |
| that matches the signature of the entry. |
| \end{description} |
| |
| For some series there is no need to do an order computation at all, |
| since the order is already known at creation time. Examples are given |
| by the implementation of the series \adname{0}, \adname{1}, |
| \adname{monom}, and \adname{term} in |
| Section~\ref{sec:FormalPowerSeries:SeriesConstructors}. |
| % |
| \addefinename{doNothing: % -> ()} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local doNothing(x: %): () == { |
| TRACEFPS("doNothing", "|", x); |
| assert(X.approximateOrder ~= unknown); |
| assert(initialized? x); |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| |
| 1887,33 → 2097,34 |
|---|
| |
| |
| |
| |
| |
| |
| Now we consider the complicated part of the order computation of the |
| function \adname{initialize!}, namely the function |
| \adname{approximateOrder!}. |
| Now we consider the complicated part of the \useterm{order |
| computation} of the function \adname{initialize!}, namely the |
| function \adname{computeApproximateOrder!}. |
| % |
| There is a nullary, unary, and binary version of that function. Since |
| their implementation is very similar, we only describe the binary |
| version. |
| The actual work is done by a nullary (\adname{approximateOrder0!}), |
| unary (\adname{approximateOrder1!}), and binary ( |
| \adname{approximateOrder2!}) version of a wrapper functions around the |
| functions such as \adname[SeriesOrder]{min}, \adname[SeriesOrder]{+}, |
| and \adname[SeriesOrder]{*} from \adtype{SeriesOrder}. |
| % |
| Since their implementation is very similar, we only describe the |
| binary version. |
| |
| This function computes a new \useterm{approximate order} from |
| approximate orders of its arguments. It should be understood as a |
| wrapper function around the functions such as \adname[SeriesOrder]{+} |
| and \adname[SeriesOrder]{*} from \adtype{SeriesOrder} which takes care |
| of recursively defined series. |
| approximate orders of its arguments. |
| % |
| Functions such as \adname[SeriesOrder]{+} and \adname[SeriesOrder]{*} |
| appear as the argument \adcode$newOrder$ in the function declaration |
| below. |
| Functions such as \adname[SeriesOrder]{min}, \adname[SeriesOrder]{+}, |
| \adname[SeriesOrder]{*}, \adname[SeriesOrder]{increment}, and |
| \adname[SeriesOrder]{boundedDecrement} appear as the argument |
| \adcode$newOrder$ in the function declaration below. |
| % |
| For understanding of how the function \adname{approximateOrder!} is |
| For understanding of how the function \adname{approximateOrder2!} is |
| used, look, for example, into the definition of \adname{+} in |
| Section~\ref{sec:FormalPowerSeries:SeriesAddition} and at the |
| implementation of % |
| \adname{new:(I->Generator R,(SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%}. |
| implementation of \adname{new2} and % |
| \adname{new:(I->Generator R,approximateOrder!:%->Boolean)->%}. |
| |
| |
| For some series we can compute the \useterm{approximate order} |
| according to equations \eqref{eq:OrderPlus} and \eqref{eq:OrderTimes}. |
| That holds in particular for the sum and product of series, \cf{} |
| 1920,7 → 2131,7 |
|---|
| Sections~\ref{sec:FormalPowerSeries:SeriesAddition} and |
| \ref{sec:FormalPowerSeries:SeriesMultiplication}, respectively. |
| |
| The basic idea for \adname{approximateOrder!} is that initially it |
| The basic idea for \adname{approximateOrder2!} is that initially it |
| sets all unknown approximate orders (of series involved in the |
| definition of the series in question) to |
| \adname[SeriesOrder]{infinity} and then (according to the structure of |
| 1929,150 → 2140,98 |
|---|
| as given by \eqref{eq:OrderPlus} and \eqref{eq:OrderTimes} until a |
| stabilized situation is achieved. |
| |
| We should add a note here about the fact that |
| \adname{approximateOrder!} does not only compute an |
| \useterm{approximate order}, but (in case at invocation time the |
| \useterm{approximate order} was \adname[SeriesOrder]{unknown}) it also |
| initializes the coefficient stream. Thus, if the coefficient stream is |
| known to be initialized, then there is no need to do the computation |
| of the \useterm{approximate order} again. |
| The follwing are invariants of \adname{approximateOrder!}. |
| { |
| \def\ao{\texttt{T.approximateOrder}} |
| \def\o{\texttt{T.order}} |
| \def\u{\adname[SeriesOrder]{unknown}} |
| \begin{align} |
| \ao=\u &\implies \texttt{not initialized? t} \\ |
| \ao=\u &\implies \o=\u |
| \end{align} |
| } |
| As can be seen from the code below, if |
| \adname{initializeCoefficientStream!} is called, the approximate |
| orders of $x$, $y$, and $t$ have already been properly computed. |
| % |
| \addefinename{approximateOrder!:(%,%,(SeriesOrder,SeriesOrder)->SeriesOrder)->%->()}% |
| \addefinename{approximateOrder2!:((SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%->Boolean}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local approximateOrder!( |
| computeCoefficients: I -> Generator R, |
| local approximateOrder2!( |
| newOrder: (SeriesOrder, SeriesOrder) -> SeriesOrder, |
| x: %, |
| y: % |
| )(t: %): () == { |
| )(t: %): Boolean == { |
| TRACEFPS("approximateOrder2!", "{ t", t); |
| T.touched? or initialized? t => { |
| TRACEFPS("approximateOrder2!", "touched}", t); |
| false; |
| } |
| TRACEFPS("approximateOrder2!", "x", x); |
| TRACEFPS("approximateOrder2!", "y", y); |
| initialized? t => {TRACEFPS("approximateOrder2!", "i}", t); return} |
| ochanged?: Boolean := T.approximateOrderChanged?; |
| mustInitializeCoefficientStream? := T.approximateOrder = unknown; |
| macro aOrd(x, y) == newOrder(X.approximateOrder, Y.approximateOrder); |
| ao: SeriesOrder := aOrd(x, y); |
| if ao = unknown then ao := infinity; -- start at maximum |
| unknown?: Boolean := T.approximateOrder = unknown; |
| if unknown? then T.approximateOrder := infinity; -- start at maximum |
| T.touched? := true; -- avoid recursion |
| xchanged? := computeApproximateOrder! x; |
| ychanged? := computeApproximateOrder! y; |
| T.touched? := false; |
| ao: SeriesOrder := newOrder(X.approximateOrder, Y.approximateOrder); |
| tchanged?: Boolean := setApproximateOrder!(t, ao); |
| if ochanged? or tchanged? then { |
| TRACEFPS("approximateOrder2!", "recurse{", t); |
| computeApproximateOrder! x; |
| computeApproximateOrder! y; |
| ao := aOrd(x, y); |
| tchanged? := setApproximateOrder!(t, ao); |
| TRACEFPS("approximateOrder2!", "recurse}", t); |
| } |
| assert(not initialized? t); |
| if mustInitializeCoefficientStream? then { |
| TRACEFPS("approximateOrder2!", "set coeff", t); |
| initializeCoefficientStream!(computeCoefficients, t); |
| } |
| TRACE("approximateOrder2! unknown?: ", unknown?); |
| TRACE("approximateOrder2! xchanged?: ", xchanged?); |
| TRACE("approximateOrder2! ychanged?: ", ychanged?); |
| TRACE("approximateOrder2! tchanged?: ", tchanged?); |
| TRACEFPS("approximateOrder2!", "}", t); |
| unknown? or xchanged? or ychanged? or tchanged?; |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| We have a similar function for operations that just need one argument. |
| \addefinename{approximateOrder1!:(SeriesOrder->SeriesOrder,%)->%->Boolean}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local approximateOrder!( |
| computeCoefficients: I -> Generator R, |
| local approximateOrder1!( |
| newOrder: SeriesOrder -> SeriesOrder, |
| x: % |
| )(t: %): () == { |
| )(t: %): Boolean == { |
| TRACEFPS("approximateOrder1!", "{ t", t); |
| T.touched? or initialized? t => { |
| TRACEFPS("approximateOrder1!", "touched}", t); |
| false; |
| } |
| TRACEFPS("approximateOrder1!", "x", x); |
| initialized? t => {TRACEFPS("approximateOrder1!", "i}", t); return} |
| ochanged?: Boolean := T.approximateOrderChanged?; |
| mustInitializeCoefficientStream? := T.approximateOrder = unknown; |
| macro aOrd x == newOrder(X.approximateOrder); |
| ao: SeriesOrder := aOrd x; |
| if ao = unknown then ao := infinity; -- start at maximum |
| unknown?: Boolean := T.approximateOrder = unknown; |
| if unknown? then T.approximateOrder := infinity; -- start at maximum |
| T.touched? := true; -- avoid recursion |
| xchanged? := computeApproximateOrder! x; |
| T.touched? := false; |
| ao: SeriesOrder := newOrder X.approximateOrder; |
| tchanged?: Boolean := setApproximateOrder!(t, ao); |
| if ochanged? or tchanged? then { |
| TRACEFPS("approximateOrder1!", "recurse{", t); |
| computeApproximateOrder! x; |
| ao := aOrd x; |
| tchanged? := setApproximateOrder!(t, ao); |
| TRACEFPS("approximateOrder1!", "recurse}", t); |
| } |
| assert(not initialized? t); |
| if mustInitializeCoefficientStream? then { |
| TRACEFPS("approximateOrder1!", "set coeff", t); |
| initializeCoefficientStream!(computeCoefficients, t); |
| } |
| TRACE("approximateOrder1! unknown?: ", unknown?); |
| TRACE("approximateOrder1! xchanged?: ", xchanged?); |
| TRACE("approximateOrder1! tchanged?: ", tchanged?); |
| TRACEFPS("approximateOrder1!", "}", t); |
| unknown? or xchanged? or tchanged?; |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| And finally, we have a version where we assume that the computation of |
| the approximate order is given by some function that does not involve |
| (through recursion) the approximat order or $t$. |
| the \useterm{approximate order} is given by some function that does |
| not involve (through recursion) the \useterm{approximate order} or |
| $t$. |
| \addefinename{approximateOrder0!:(()->SeriesOrder)->%->Boolean}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local approximateOrder!( |
| computeCoefficients: I -> Generator R, |
| local approximateOrder0!( |
| newOrder: () -> SeriesOrder |
| )(t: %): () == { |
| )(t: %): Boolean == { |
| TRACEFPS("approximateOrder0!", "{", t); |
| initialized? t => {TRACEFPS("approximateOrder0!", "i}", t); return} |
| assert(T.approximateOrder = unknown); |
| ao := newOrder(); |
| setApproximateOrder!(t, ao); |
| initializeCoefficientStream!(computeCoefficients, t); |
| initialized? t => { |
| TRACEFPS("approximateOrder0!", "already initialized}", t); |
| false; |
| } |
| unknown?: Boolean := T.approximateOrder = unknown; |
| tchanged?: Boolean := setApproximateOrder!(t, newOrder()); |
| TRACEFPS("approximateOrder0!", "}", t); |
| unknown? or tchanged?; |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| Note that through the following function we only initialize the data |
| structure of $x$, but do \emph{not} actually compute any coefficient |
| in accordance with |
| Convention~\ref{convention:Order:DontStepGenerator}. |
| % |
| \addefinename{initializeCoefficientStream!:(I->Generator R, %)->()}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local initializeCoefficientStream!( |
| computeCoefficients: I -> Generator R, |
| x: % |
| ): () == { |
| ao: SeriesOrder := X.approximateOrder; |
| assert(ao ~= unknown); |
| if ao = infinity then { |
| X.order := infinity; |
| X.coefficientStream := stream(0); |
| } else { |
| X.coefficientStream := stream computeCoefficients(ao::I); |
| } |
| X.initializedCoefficients? := true; |
| } |
| @ %def initializeCoefficientStream! |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| The function \adname{setApproximateOrder!} returns |
| \adname[Boolean]{true} if the \useterm{approximate order} has been |
| changed and \adname[Boolean]{false} otherwise. It sets the |
| \adcode$approximateOrderChanged?$ entry in the representation of its |
| first argument to this return value. |
| changed and \adname[Boolean]{false} otherwise. |
| % |
| \addefinename{setApproximateOrder!: (%, SeriesOrder) -> Boolean}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| 2079,10 → 2238,17 |
|---|
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local setApproximateOrder!(x: %, newOrder: SeriesOrder): Boolean == { |
| TRACEFPS("setApproximateOrder!", "(", x); |
| X.approximateOrderChanged? := (X.approximateOrder ~= newOrder); |
| assert(not initialized? x); |
| assert(newOrder ~= unknown); |
| ao := X.approximateOrder; |
| changed? := (ao ~= newOrder); |
| X.approximateOrder := newOrder; |
| TRACEFPS("setApproximateOrder!", ")", x); |
| X.approximateOrderChanged? |
| -- During the initialization phase of an approximate order, it |
| -- is not allowed to strictly increase it. |
| ao = unknown or ao = infinity => changed?; |
| newOrder = infinity or (ao::I) < (newOrder::I) => never; |
| changed?; |
| } |
| @ %def setApproximateOrder |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| 2101,7 → 2267,144 |
|---|
| |
| |
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Phase 2: Improving the Approximate Order} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| In Phase~\ref{approximateOrder:Phase2}, the series is initialized, |
| \ie, the field \adcode$initializedCoefficients?$ contains true and the |
| \useterm{approximate order} is known. |
| % |
| We need to verify whether the \useterm{approximate order} is, in fact, |
| the true order of the series. |
| |
| The code below does this by |
| testing whether the entry in the position given by the |
| \useterm{approximate order} is really non-zero. |
| % |
| If that is the case, it changes the \adcode$order$ entry in the |
| representation from \adname[SeriesOrder]{unknown} to the |
| \useterm{approximate order}. |
| % |
| If it is not the case, the \useterm{approximate order} can be |
| increased by 1 and another check is done. According to |
| Convention~\ref{convention:Order:DontStepGenerator}, this iteration |
| can only be done for the finitely many elements of the series that |
| have already been accessed. |
| % |
| If this iteration does not recognize the true order of the series, we |
| wait for the next call to \adname{initialize!} to improve the |
| \useterm{approximate order} further. |
| |
| We have chosen such a stepwise approach since $x$ might be the zero |
| series coming, for example, from |
| \begin{adsnippet} |
| x := \adname[DataStream]{stream: Generator T -> %}(generate repeat yield 0) :: \adthistype{}(Integer); |
| \end{adsnippet} |
| For such a series \adname{initialize!} would not terminate while |
| trying to improve the \useterm{approximate order}. |
| % |
| See also the implementation of the function \adname{coerce} in |
| \adthistype{} as given in |
| Section~\ref{sec:FormalPowerSeries:SeriesConstructors}. |
| |
| To check the true order, we must access elements of the given series |
| without violating Convention~\ref{convention:Order:DontStepGenerator}. |
| % |
| The computation of the order should in no case start the generator |
| that is stored inside the stream of the series, order computation is, |
| however, allowed to access elements of the stream that are already |
| computed, \ie, for a series $x$ and |
| \begin{adsnippet} |
| s := x :: \adtype{DataStream}(\adtype{Integer}); |
| \end{adsnippet} |
| it is allowed to call |
| \begin{adsnippet} |
| c: Integer := s.n; |
| \end{adsnippet} |
| for any $n<\adname[DataStream]{#}s$. |
| |
| Note that, in case we have realized that the series is the zero |
| series, the order and the \useterm{approximate order} have been set to |
| \adname[SeriesOrder]{infinity}. Thus if we know that the order is |
| \adname[SeriesOrder]{unknown} then we also know that the |
| \useterm{approximate order} is not \adname[SeriesOrder]{infinity}. |
| |
| \addefinename{improveOrder!: % -> ()}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local improveOrder!(x: %): () == { |
| assert(initialized? x); |
| assert(X.order = unknown); |
| i: I := (X.approximateOrder) :: I; |
| c: DataStream R := X.coefficientStream; |
| n: I := #c; |
| TRACE("number of cached values = ", n); |
| i >= n => {<<try to recognize the zero series>>} |
| while i < n and zero? c.i repeat { |
| TRACE("verifyOrder! zero i = ", i); |
| i := next i; |
| X.approximateOrder := i :: SeriesOrder; |
| } |
| if i < n then { -- "if not zero? c.i" might be more costly |
| TRACE("verifyOrder! non-zero i = ", i); |
| X.order := i :: SeriesOrder; |
| } |
| } |
| @ %def improveOrder! |
| %" |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| To recognize the zero series is only possible if we detect that the |
| underlying stream is constant. If that is the case and the last |
| computed value is 0, then we know we have the zero series, since we |
| only run the following code if all values at entries less than the |
| current \useterm{approximate order} are 0. |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<try to recognize the zero series>>= |
| TRACE("Constant stream?: ", constant? c); |
| not constant? c => return; -- for non-constant series we cannot do anything |
| assert(zero?(c.(prev #c))); |
| X.approximateOrder := infinity; |
| X.order := infinity; |
| @ % |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| Note that we do not need to test anymore whether the constant value is |
| zero. Either the \useterm{approximate order} is already bigger than |
| $\adname{#}(c)$ or it has been increased one by one in previous |
| invocations of \adname{initialize!}. |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Zero Recognition} |
| \label{sec:FormalPowerSeries:ZeroRecognition} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 2117,8 → 2420,9 |
|---|
| multiplied by another series. |
| \end{enumerate} |
| Note that we fail to recognize, for example, that a sum of an infinite |
| series and its negation is zero. The function \adname{zero?} is only a |
| \emph{partial} zero test. |
| series and its negation is zero. The function |
| \adname[FormalPowerSeriesCategory]{zero?} is only a \emph{partial} |
| zero test. |
| % |
| \addefinename{zero?: % -> Boolean} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| 2126,6 → 2430,7 |
|---|
| zero?(x: %): Boolean == { |
| TRACEFPS("zero?", "{", x); |
| initialize! x; |
| assert(initialized? x); |
| TRACEFPS("zero?", "}", x); |
| X.order = infinity; |
| } |
| 2162,6 → 2467,10 |
|---|
| $s$ or a generator $g$. Since no other information is given, the only |
| reasonable guess is that the \useterm{approximate order} is zero. |
| % |
| For \adtype{DataStream} arguments, we are allowed to check chached |
| values thus may get a better value for the \useterm{approximate |
| order}. |
| % |
| See Section~\ref{sec:representation:FormalPowerSeries} for the fields |
| in the representation. |
| % |
| 2169,14 → 2478,23 |
|---|
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| coerce(g: Generator R): % == (stream(g) $ DataStream(R)) :: %; |
| coerce(s: DataStream R): % == BRACKET( |
| unknown, -- order |
| 0, -- approximateOrder |
| false, -- approximateOrderChanged? |
| doNothing, -- computeApproximateOrder! |
| true, -- initializedCoefficients? |
| s -- coefficientStream |
| ); |
| coerce(s: DataStream R): % == { |
| k: I := 0; |
| n: I := #s; |
| while k < n and zero? s.k repeat k := next k; |
| o: SeriesOrder := unknown; |
| ao: SeriesOrder := k :: SeriesOrder; |
| if n > 0 and not zero? s.k then o := ao; |
| cc(i: I): Generator R == elements s; |
| BRACKET( |
| o, -- order |
| ao, -- approximateOrder |
| doNothing, -- computeApproximateOrder! |
| cc, -- computeCoefficients (dummy an never used) |
| s, -- coefficientStream |
| true -- initializedCoefficients? |
| ); |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| 2185,11 → 2503,20 |
|---|
| compute an \useterm{approximate order}. It is for this reason that |
| here and for the following few cases the function \adname{doNothing} |
| is the right choice. |
| % |
| \addefinename{doNothing: % -> ()} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local doNothing(x: %): Boolean == { |
| TRACEFPS("doNothing", "|", x); |
| assert(initialized? x); |
| false; |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| |
| |
| |
| Next let us define the the constant series \adname{0}, \adname{1}, |
| \adname{monom}, and \adname{term}. |
| % |
| 2204,12 → 2531,12 |
|---|
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| new(o: SeriesOrder, g: Generator R): % == BRACKET( |
| o, -- order |
| o, -- approximateOrder |
| false, -- approximateOrderChanged? |
| doNothing, -- computeApproximateOrder! |
| true, -- initializedCoefficients? |
| stream g -- coefficientStream |
| o, -- order |
| o, -- approximateOrder |
| doNothing, -- computeApproximateOrder! |
| (i: I): Generator R +-> g, -- computeCoefficients (dummy) |
| stream g, -- coefficientStream |
| true -- initializedCoefficients? |
| ); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| 2220,9 → 2547,9 |
|---|
| \addefinename{monom: %}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| 0: % == SETNAME("0") new(infinity, generate yield 0); |
| 1: % == SETNAME("1") new(0, generate {yield 1; yield 0}); |
| monom: % == SETNAME("x") new(1, generate {yield 0; yield 1; yield 0}); |
| 0: % == SETNAME("0") new(infinity, generate yield 0); |
| 1: % == SETNAME("1") new(0, generate {yield 1; yield 0}); |
| monom: % == SETNAME("x") new(1, generate {yield 0; yield 1; yield 0}); |
| @ % |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| The the implementation of \adname[FormalPowerSeriesCategory]{term} is |
| 2263,12 → 2590,12 |
|---|
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| new(): % == BRACKET( |
| unknown, -- order |
| unknown, -- approximateOrder |
| true, -- approximateOrderChanged? |
| uninitialized, -- computeApproximateOrder! |
| false, -- initializedCoefficients? |
| uninitialized -- coefficientStream |
| unknown, -- order |
| unknown, -- approximateOrder |
| uninitialized, -- computeApproximateOrder! |
| (i: I): Generator R +-> generate {}, -- computeCoefficients (dummy) |
| uninitializedStream, -- coefficientStream |
| false -- initializedCoefficients? |
| ); |
| @ |
| %$ |
| 2280,7 → 2607,7 |
|---|
| \addefinename{uninitialized: % -> ()} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local uninitialized(x: %): () == { |
| local uninitialized(x: %): Boolean == { |
| TRACEFPS("uninitialized", "", x); |
| never; |
| } |
| 2302,10 → 2629,12 |
|---|
| #endif |
| Y.order := X.order; |
| Y.approximateOrder := X.approximateOrder; |
| Y.approximateOrderChanged? := X.approximateOrderChanged?, |
| Y.computeApproximateOrder! := X.computeApproximateOrder!; |
| Y.computeCoefficients := X.computeCoefficients; |
| Y.coefficientStream := X.coefficientStream; |
| Y.initializedCoefficients? := X.initializedCoefficients?; |
| Y.coefficientStream := X.coefficientStream; |
| Y.touched? := X.touched?; |
| Y.index := X.index; |
| } |
| @ |
| %" |
| 2317,75 → 2646,6 |
|---|
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Series Selector Functions} |
| \label{sec:FormalPowerSeries:SeriesSelectors} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| For the \useterm{ordinary generating series} |
| \begin{gather} |
| f = \sum_{n=0}^\infty {f_n x^n} |
| \end{gather} |
| \adcode$\adname{coefficient}(f, n)$ returns $f_n$. |
| % |
| Note that the function \adname{zero?} starts a computation of an |
| \useterm{approximate order}. |
| |
| \begin{ToDo} |
| \begin{rhx} |
| 15-Sep-2006: Maybe \adcode$f.n$ should also be allowed. |
| \end{rhx} |
| \end{ToDo} |
| % |
| \addefinename{coefficient: (%, MachineInteger) -> R}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| coefficient(x: %, n: MachineInteger): R == { |
| TRACEFPS("coefficient", "|", x); |
| TRACE("coefficient n = ", n); |
| zero? x => 0; |
| n < (X.approximateOrder) :: I => 0; |
| assert(initialized? x); |
| X.coefficientStream.n; |
| } |
| @ |
| %" |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| Note that the computation of the order and the \useterm{approximate |
| order} has to obey |
| Convention~\ref{convention:Order:DontStepGenerator}. Thus, we can only |
| check the coefficients that have already been computed. This is taken |
| care of by the function \adname{initialize!}. |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| order (x: %): SeriesOrder == {initialize! x; X.order} |
| approximateOrder(x: %): SeriesOrder == {initialize! x; X.approximateOrder} |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| coerce(x: %): DataStream R == { |
| initialize! x; |
| assert(initialized? x); |
| X.coefficientStream; |
| } |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| % |
| \addefinename{coefficients: % -> Generator R}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| coefficients(x: %): Generator R == { |
| initialize! x; |
| generator X.coefficientStream; |
| } |
| @ |
| %" |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Creating New Series for Recursive Use} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| 2396,9 → 2656,12 |
|---|
| Additionally, we also require a function that returns an |
| \useterm{approximate order} from the given approximate order(s). |
| |
| There is a nullary, univariate and a bivariate version. The univariate |
| version is used for univariate operations like, for example, |
| \adname{differentiate}, \adname{integrate}, and \adname{exponentiate}. |
| There is a nullary (\adname{new0}), univariate (\adname{new1}) and a |
| bivariate (\adname{new2}) version. |
| % |
| The univariate version is used for univariate operations like, for |
| example, \adname{differentiate} and \adname{integrate}. |
| % |
| The bivariate version is invoked for \adname{+}, \adname{*}, and |
| \adname{compose}. |
| % |
| 2406,7 → 2669,7 |
|---|
| \adname[CycleIndexSeries]{coerce:%->ExponentialGeneratingSeries} |
| in \adtype{CycleIndexSeries}. |
| |
| Note that the functions \adname{approximateOrder!} just forms a |
| Note that the functions \adname{approximateOrder2!} just forms a |
| function closure, but does not actually compute any order during the |
| call to one of the following functions. |
| |
| 2414,62 → 2677,68 |
|---|
| tracing the computation. |
| |
| Let us start with the binary version. |
| \addefinename{new:(I->Generator R,(SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%}% |
| \addefinename{new2:((%,%)->I->Generator R,(SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| new( |
| computeCoefficients: I -> Generator R, |
| new2( |
| coefficientsOp: (%, %) -> I -> Generator R, |
| orderOp: (SeriesOrder, SeriesOrder) -> SeriesOrder, |
| x: %, |
| y: % |
| ): % == new(approximateOrder!(computeCoefficients, orderOp, x, y)); |
| ): % == new(coefficientsOp(x, y), approximateOrder2!(orderOp, x, y)); |
| |
| macro NEW2(op)(computeCoefficients, orderOp, x, y) == { |
| SETNAME("("+name(x)+op+name(y)+")") |
| new(computeCoefficients, orderOp, x, y); |
| macro NEW2(op)(coefficientsOp, orderOp, x, y) == { |
| SETNAME("("+name(x)+op+name(y)+")") |
| new2(coefficientsOp, orderOp, x, y); |
| } |
| @ %def NEW2 |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| The unary version is very similar. |
| \addefinename{new1:(%->I->Generator R,SeriesOrder->SeriesOrder,%)->%}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| new( |
| computeCoefficients: I -> Generator R, |
| new1( |
| coefficientsOp: % -> I -> Generator R, |
| orderOp: SeriesOrder -> SeriesOrder, |
| x: % |
| ): % == new(approximateOrder!(computeCoefficients, orderOp, x)); |
| ): % == new(coefficientsOp x, approximateOrder1!(orderOp, x)); |
| |
| macro NEW1(op)(computeCoefficients, orderOp, x) == { |
| SETNAME(op+"("+name(x)+")") |
| new(computeCoefficients, orderOp, x); |
| macro NEW1(op)(coefficientsOp, orderOp, x) == { |
| SETNAME(op+"("+name(x)+")") |
| new1(coefficientsOp, orderOp, x); |
| } |
| @ %def NEW1 |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| The nullary version works in a similar fashion, too. |
| \addefinename{new0:(I->Generator R,()->SeriesOrder,%)->%}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| new( |
| new0( |
| computeCoefficients: I -> Generator R, |
| orderOp: () -> SeriesOrder |
| ): % == new(approximateOrder!(computeCoefficients, orderOp)); |
| ): % == new(computeCoefficients, approximateOrder0! orderOp); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| All three versions above use the following function to build the data |
| structure. |
| \addefinename{new:(I->Generator R,approximateOrder!:%->Boolean)->%}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| -- This function is, in fact, a local one, but the compiler forbids to |
| -- put a "local" keyword in front. |
| new(approximatOrder!: % -> ()): % == BRACKET( |
| unknown, -- order |
| unknown, -- approximateOrder |
| true, -- approximateOrderChanged? |
| approximatOrder!, -- computeApproximateOrder! |
| false, -- initializedCoefficients? |
| uninitialized -- coefficientStream |
| new( |
| computeCoefficients: I -> Generator R, |
| approximateOrder!: % -> Boolean |
| ): % == BRACKET( |
| unknown, -- order |
| unknown, -- approximateOrder |
| approximateOrder!, -- computeApproximateOrder! |
| computeCoefficients, -- computeCoefficients |
| uninitializedStream, -- coefficientStream |
| false -- initializedCoefficients? |
| ); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| 2496,6 → 2765,87 |
|---|
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Series Selector Functions} |
| \label{sec:FormalPowerSeries:SeriesSelectors} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| For the \useterm{ordinary generating series} |
| \begin{gather} |
| f = \sum_{n=0}^\infty {f_n x^n} |
| \end{gather} |
| \adcode$\adname{coefficient}(f, n)$ returns $f_n$. |
| % |
| Note that the function \adname{zero?} starts a computation of an |
| \useterm{approximate order}. |
| |
| \begin{ToDo} |
| \begin{rhx} |
| 15-Sep-2006: Maybe \adcode$f.n$ should also be allowed. |
| \end{rhx} |
| \end{ToDo} |
| |
| The domain \adtype{FormalPowerSeries} allows recursive definitions. |
| But not all such definitions are recursion schemes that can be treated |
| by the current implementation. For example, the equation $f = f' + x$ |
| has infinitely many solutions. $f = 1 + x + c \cdot \exp x$ for any |
| constant $c$. |
| |
| We cannot even find the solution $f=1+x$, because if $f$ is asked to |
| reveal its zeroth coefficient, the algorithm checks the zeroth |
| coefficient of $f'=\adname[FormalPowerSeries]{differentiate}(f)$, |
| \ie, the coefficient with index 1 of $f$. Such an procedure would |
| never stop. If we detect that by asking for a coefficient with index |
| $n$ in a recursive process it is asked for a coefficients with index |
| $\ge n$ then we throw an exception, \adtype{BadIndexException}. |
| |
| \addefinename{coefficient: (%, MachineInteger) -> R}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| coefficient(x: %, n: MachineInteger): R == { |
| TRACEFPS("coefficient", "|", x); |
| TRACE("coefficient n = ", n); |
| zero? x => 0; -- Treat case where X.approximateOrder = infinity. |
| assert(initialized? x); -- now X.approximateOrder ~= unknown |
| n < (X.approximateOrder) :: I => 0; |
| idx := X.index; |
| idx ~= unassigned => { |
| n < idx => X.coefficientStream.n; |
| throw BadIndexException; |
| } |
| X.index := n; |
| c := X.coefficientStream.n; |
| X.index := unassigned; |
| c; |
| } |
| @ |
| %" |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| Note that the computation of the order and the \useterm{approximate |
| order} has to obey |
| Convention~\ref{convention:Order:DontStepGenerator}. Thus, we can only |
| check the coefficients that have already been computed. This is taken |
| care of by the function \adname{initialize!}. |
| % |
| \addefinename{coefficients: % -> Generator R}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| order (x: %): SeriesOrder == {initialize! x; X.order} |
| approximateOrder(x: %): SeriesOrder == {initialize! x; X.approximateOrder} |
| coerce (x: %): DataStream R == {initialize! x; X.coefficientStream} |
| coefficients (x: %): Generator R == generator(x::DataStream(R)); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Series Addition} |
| \label{sec:FormalPowerSeries:SeriesAddition} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| 2511,8 → 2861,7 |
|---|
| of one of its arguments at creation time, since \adname{zero?} starts |
| a computation of an \useterm{approximate order}. |
| |
| The last two arguments of |
| \adname[FormalPowerSeriesCategory]{new: (%, %, (%, %, I) -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder) -> %} |
| The last two arguments of \adname[FormalPowerSeriesCategory]{new2} |
| give a way to compute the coefficients of $x+y$ and an approximate |
| order from the orders of $x$ and $y$. |
| % |
| 2519,7 → 2868,7 |
|---|
| \addefinename{+: (%, %) -> %}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| (x: %) + (y: %): % == NEW2("+")(plus(x, y), min, x, y); |
| (x: %) + (y: %): % == NEW2("+")(plus, min, x, y); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| 2526,12 → 2875,6 |
|---|
| Generating the coefficients of a sum of two series is a simple task. |
| The third parameter give a lower approximation on the order of the |
| series. |
| \begin{ToDo} |
| \begin{rhx} |
| 16-Sep-2006: Should first do without \adname[DataStream]{elements}. |
| \end{rhx} |
| \end{ToDo} |
| |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries: auxiliary functions>>= |
| local plus(x: %, y: %)(aord: I): Generator R == generate { |
| 2581,7 → 2924,7 |
|---|
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Finite Sum} |
| \subsubsection{Finite Sum of Series} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \begin{ToDo} |
| \begin{rhx} |
| 2608,10 → 2951,11 |
|---|
| } |
| } |
| sum(a: Array %): % == { |
| zero? # a => 0; |
| #if TRACE |
| names: String := "sum("+name a.0; |
| for i in 1..#a-1 repeat { |
| names := names + ","+name a.i; |
| names := names + "," + name a.i; |
| } |
| names := names + ")"; |
| SETNAME(names)((sumCoefficients a) :: %); |
| 2628,7 → 2972,7 |
|---|
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Potentially Infinite Sum} |
| \subsubsection{Potentially Infinite Sum of Series} |
| \label{sec:FormalPowerSeries:InfiniteSeriesSum} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \begin{ToDo} |
| 2700,7 → 3044,7 |
|---|
| \addefinename{*: (%, %) -> %}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| (x: %) * (y: %): % == NEW2("*")(times(x, y), +, x, y); |
| (x: %) * (y: %): % == NEW2("*")(times, +, x, y); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| 2753,7 → 3097,7 |
|---|
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsubsection{Potentially Infinite Products} |
| \subsubsection{Potentially Infinite Product of Series} |
| \label{sec:FormalPowerSeries:InfiniteSeriesProduct} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| 2862,7 → 3206,7 |
|---|
| \addefinename{compose: (%, %) -> %}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries>>= |
| compose(x: %, y: %): % == NEW2(" o ")(compose(x, y), *, x, y); |
| compose(x: %, y: %): % == NEW2(" o ")(compose, *, x, y); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| 2894,7 → 3238,7 |
|---|
| yield coefficient(x, 0); |
| restX: % := SETNAME("R("+name(x)+")")(elements(x::DataStream R, 1)::%); |
| z: % := compose(restX, y) * y; |
| zero? z => 0@R; -- initialize z!!! |
| zero? z => yield(0@R); -- initialize z!!! |
| d: DataStream R := z :: DataStream R; |
| for e in elements(d, 1) repeat yield e; |
| } |
| 2931,7 → 3275,7 |
|---|
| \addefinename{differentiate: % -> %}% |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries differentiate>>= |
| differentiate(x: %): % == NEW1("D")(differentiate x, boundedDecrement, x); |
| differentiate(x: %): % == NEW1("D")(differentiate, boundedDecrement, x); |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| 2985,7 → 3329,7 |
|---|
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<implementation: FormalPowerSeries integrate>>= |
| integrate(x: %, integrationConstant: R == 0): % == { |
| zero? integrationConstant => NEW1("I")(integrate x, increment, x); |
| zero? integrationConstant => NEW1("I")(integrate, increment, x); |
| SETNAME("I1("+name(x)+")") new(0, integrateNonZero(x, integrationConstant)); |
| } |
| @ |
| 3164,9 → 3508,35 |
|---|
| |
| |
| |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \subsection{Exceptions Thrown by FormalPowerSeries} |
| \label{sec:FormalPowerSeries:Exceptions} |
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| |
| See \adname[FormalPowerSeries]{coefficient} of why we need the |
| following exception. |
| |
| \begin{+++} |
| \begin{addescription}{Type of an exception that signals an access to |
| an undefined element.} |
| \end{addescription} |
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<cat: BadIndexExceptionType>>= |
| define BadIndexExceptionType: Category == with; |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| \begin{+++} |
| \begin{addescription}{Exception that signals an access to an |
| undefined element.} |
| \end{addescription} |
| \end{+++} |
| %CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC |
| <<dom: BadIndexException>>= |
| BadIndexException: BadIndexExceptionType == add; |
| @ |
| %TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT |
| |
| |
| |