28 Test Formal Power Series
This file tests formal power series as defined in See src/series.as.nw.
685⟨* 13⟩+
≡ ⊲676 704 ⊳
-------------------------------------------------------------------
----
---- Combinat
---- Copyright (C) Ralf Hemmecke <ralf@hemmecke.de>
---- svn co svn://svn.risc.uni-linz.ac.at/hemmecke/combinat/
----
-------------------------------------------------------------------
#assert DontNeedLibraryTestCases
#include "testcases"
TestFormalPowerSeries: TestCaseType with {
#include "series.signatures.as"
} == add {
import from TestCaseTools;
macro {
GS == FormalPowerSeries Z;
FPQ == FormalPowerSeries Q;
}
import from Z, List Z, DataStream Z, I, SeriesOrder;
⟨test series 686a⟩
}
Defines:
TestFormalPowerSeries, never used.
Uses DataStream 386, FormalPowerSeries 242, I 47, Q 47, SeriesOrder 289, and Z 47.
686a⟨test series 686a⟩≡ (685 704) 686b ⊳
testPlus1(): () == {
gs0: GS := stream(0) :: GS;
gs1: GS := stream(1) :: GS;
sum1 := gs0 + gs1;
sum2 := gs1 + gs1;
for i: I in 0 .. 10 repeat {
assertEquals(Integer, 0, coefficient(gs0, i));
assertEquals(Integer, 1, coefficient(gs1, i));
assertEquals(Integer, 1, coefficient(sum1, i));
assertEquals(Integer, 2, coefficient(sum2, i));
}
}
Uses I 47 and Integer 66.
686b⟨test series 686a⟩+
≡ (685 704) ⊲686a 687a ⊳
testPlus2(): () == {
l1: List Integer := [ 1, 2, 4, 8];
l2: List Integer := [-1, 0, -1, -9, 22];
l3: List Integer := [ 0, 2, 3, -1, 22];
gs1: GS := stream(generator l1, 0) :: GS;
gs2: GS := stream(generator l2, 0) :: GS;
sum := gs1 + gs2;
for i in l3 for n: I in 0.. repeat {
assertEquals(Integer, i, coefficient(sum, n));
}
for n in #l3 .. 10 repeat {
assertEquals(Integer, 0, coefficient(sum, n));
}
}
Uses I 47 and Integer 66.
687a⟨test series 686a⟩+
≡ (685 704) ⊲686b 687b ⊳
testZero(): () == {
import from List Integer;
s: GS := stream(generator [0,2,3,0]) :: GS;
assertFalse(zero? s);
s := 0;
assertTrue(zero? s);
s := stream(generator [0]) :: GS;
assertFalse(zero? s);
assertEquals(Integer, 0, coefficient(s, 0));
assertFalse(zero? s);
assertEquals(Integer, 0, coefficient(s, 1));
assertTrue(zero? s);
}
Uses Integer 66.
687b⟨test series 686a⟩+
≡ (685 704) ⊲687a 688a ⊳
testTimes1(): () == {
gs0 := stream(0) :: GS;
gs1 := stream(1) :: GS;
prod0 := gs0 * gs1;
prod2 := gs1 * gs1;
for i: I in 0 .. 10 repeat {
assertEquals(Integer, 0, coefficient(prod0, i));
assertEquals(Integer, (i+1)::Integer, coefficient(prod2, i));
}
}
Uses I 47 and Integer 66.
688a⟨test series 686a⟩+
≡ (685 704) ⊲687b 688b ⊳
testTimes2(): () == {
a: Array Integer := [ 1, 2, 4, 8];
b: Array Integer := [-1, 0, -1, -9, 22];
c: Array Integer := [-1, -2, -5, -19, 0, 0, 16, 176];
gsa: GS := stream(generator a, 0) :: GS;
gsb: GS := stream(generator b, 0) :: GS;
prod := gsa * gsb;
local assertEq(arr: Array Integer, gs: GS): () == {
for n: I in 0..10 repeat {
x: Integer := if n < #arr then arr.n else 0;
y: Integer := coefficient(gs, n);
assertEquals(Integer, x, y);
}
}
assertEq(a, gsa);
assertEq(b, gsb);
assertEq(c, prod);
}
Uses Array 599, I 47, and Integer 66.
688b⟨test series 686a⟩+
≡ (685 704) ⊲688a 689a ⊳
testRecursive0(): () == {
s: GS := new();
set!(s, 1 + monom * s);
assertEquals(I, 0, approximateOrder(s) :: I);
assertEquals(SeriesOrder, unknown, order s);
l1: List Integer := [ 1, 1, 1, 1, 1, 1];
l2: List Integer := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
}
Uses I 47, Integer 66, and SeriesOrder 289.
689a⟨test series 686a⟩+
≡ (685 704) ⊲688b 689b ⊳
testRecursive1(): () == {
s: GS := new();
set!(s, 1 + monom * s * s);
assertEquals(I, 0, approximateOrder(s) :: I);
assertEquals(SeriesOrder, unknown, order s);
l1: List Integer := [ 1, 1, 2, 5, 14, 42];
l2: List Integer := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
}
Uses I 47, Integer 66, and SeriesOrder 289.
689b⟨test series 686a⟩+
≡ (685 704) ⊲689a 690a ⊳
testRecursive1b(): () == {
s: GS := new();
set!(s, monom + s * s);
assertEquals(I, 1, approximateOrder(s) :: I);
assertEquals(SeriesOrder, unknown, order s);
l1: List Integer := [0, 1, 1, 2, 5, 14, 42];
l2: List Integer := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
}
Uses I 47, Integer 66, and SeriesOrder 289.
690a⟨test series 686a⟩+
≡ (685 704) ⊲689b 690b ⊳
testRecursive2(): () == {
s: GS := new();
t: GS := new();
set!(s, 1 + monom * t * t * t);
set!(t, 1 + monom * s * s);
default l1, l2: List Integer;
l1 := [1, 1, 3, 9, 34, 132, 546, 2327, 10191];
l2 := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
l1 := [1, 1, 2, 7, 24, 95, 386, 1641, 7150];
l2 := [x for i in l1 for x in coefficients t];
assertEquals(List Integer, l1, l2);
}
Uses Integer 66.
690b⟨test series 686a⟩+
≡ (685 704) ⊲690a 691a ⊳
testRecursive2b(): () == {
s: GS := new();
t: GS := new();
set!(s, monom + t * t * t);
set!(t, monom + s * s);
default l1, l2: List Integer;
l1 := [0, 1, 0, 1, 3, 3, 7, 30, 63];
l2 := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
l1 := [0, 1, 1, 0, 2, 6, 7, 20, 75];
l2 := [x for i in l1 for x in coefficients t];
assertEquals(List Integer, l1, l2);
}
Uses Integer 66.
691a⟨test series 686a⟩+
≡ (685 704) ⊲690b 691b ⊳
testRecursive3(): () == {
s: GS := new();
set!(s, 1 + monom * s * s * s);
l1: List Integer := [1,1,3,12,55,273,1428,7752,43263,246675];
l2: List Integer := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
}
Uses Integer 66.
ToDo ⊲ 88 ⊳ rhx ⊲ 69 ⊳ 03-Oct-2006: Add the following test case if
multiplication takes care of constant streams.
-
-
g: Generator Integer := elements(s :: DataStream Integer);
e: List Integer := [x for i: I in 0..9 for x in g];
assertEquals(List Integer, [1,2,1], e);
691b⟨test series 686a⟩+
≡ (685 704) ⊲691a 692a ⊳
testPlusTimes1(): () == {
s: GS := (1 + monom) * (1 + monom);
l1: List Integer := [1,2,1,0,0,0];
l2: List Integer := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
}
Uses Integer 66.
692a⟨test series 686a⟩+
≡ (685 704) ⊲691b 692b ⊳
testCompose1(): () == {
s: GS := stream(1) :: GS;
t: GS := stream(generator [0,0,1]) :: GS;
u := compose(s, t);
l1: List Integer := [1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34];
l2: List Integer := [x for i in l1 for x in coefficients u];
assertEquals(List Integer, l1, l2);
}
Uses Integer 66.
692b⟨test series 686a⟩+
≡ (685 704) ⊲692a 692c ⊳
testCompose2(): () == {
s: GS := stream(1) :: GS;
t: GS := stream(generator [0,0,1,0]) :: GS;
u := compose(s, t);
assertEquals(I, 0, approximateOrder(u) :: I);
assertEquals(SeriesOrder, unknown, order u);
l1: List Integer := [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1];
l2: List Integer := [x for i in l1 for x in coefficients u];
assertEquals(List Integer, l1, l2);
assertEquals(I, 0, approximateOrder(u) :: I);
assertEquals(I, 0, order(u) :: I);
}
Uses I 47, Integer 66, and SeriesOrder 289.
Now we compose s = 
with t = 
and we get 
.
692c⟨test series 686a⟩+
≡ (685 704) ⊲692b 693a ⊳
testCompose3(): () == {
s: GS := stream(1) :: GS;
t: GS := stream(generator [0,1]) :: GS;
u := compose(s, t);
l1: List Integer := [1,1,2,4,8,16,32,64,128,256,512,1024,2048,4096];
l2: List Integer := [x for i in l1 for x in coefficients u];
assertEquals(List Integer, l1, l2);
}
Uses Integer 66.
See ToDo 10.
693a⟨test series 686a⟩+
≡ (685 704) ⊲692c 693b ⊳
testDifferentiate1(): () == BugWorkaround(GS has with {differentiate: %->%}) {
s: GS := stream(1) :: GS;
u := differentiate s;
l1: List Integer := [i for i:Integer in 1..10];
l2: List Integer := [x for i in l1 for x in coefficients u];
assertEquals(List Integer, l1, l2);
}
Uses BugWorkaround 48 and Integer 66.
693b⟨test series 686a⟩+
≡ (685 704) ⊲693a 694 ⊳
testDifferentiate2(): () == BugWorkaround(GS has with {differentiate: %->%}) {
s: GS := new();
set!(s, 1 + monom * s * s);
s := differentiate s;
l1: List Integer := [1*1, 2*2, 3*5, 4*14, 5*42];
l2: List Integer := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
}
Uses BugWorkaround 48 and Integer 66.
 |
(189)
|
See testCompose3. We use the two series s(x) = ex and t(x) = ex − 1.
694⟨test series 686a⟩+
≡ (685 704) ⊲693b 695a ⊳
testDifferentiate3(): () == BugWorkaround(GS has with {differentiate: %->%}) {
s: GS := stream(1) :: GS;
t: GS := stream(generator [0,1]) :: GS;
u := differentiate compose(s, t);
v := compose(differentiate s, t) * differentiate t;
l1: List Integer := [x for n:I in 0..10 for x in coefficients u];
l2: List Integer := [x for n:I in 0..10 for x in coefficients v];
assertEquals(List Integer, l1, l2);
l1 := [1, 4, 12, 32, 80, 192, 448, 1024, 2304, 5120, 11264];
assertEquals(List Integer, l1, l2);
}
Uses BugWorkaround 48, I 47, and Integer 66.
 |
(190)
|
695a⟨test series 686a⟩+
≡ (685 704) ⊲694 695b ⊳
testDifferentiate4(): () == BugWorkaround(GS has with {differentiate: %->%}) {
s: GS := new();
t: GS := new();
set!(s, monom + t * t * t);
set!(t, monom + s * s);
u := differentiate(s * t);
v := differentiate s * t + s * differentiate t;
l1: List Integer := [x for n:I in 0..10 for x in coefficients u];
l2: List Integer := [x for n:I in 0..10 for x in coefficients v];
assertEquals(List Integer, l1, l2);
}
Uses BugWorkaround 48, I 47, and Integer 66.
Compare the following example with testComposeBell.
695b⟨test series 686a⟩+
≡ (685 704) ⊲695a 696a ⊳
testExponentiate(): () == BugWorkaround(FPQ has with {exponentiate: % -> %}) {
local invfactorialStream: DataStream Q == stream(generate {
q: Q := 1;
yield 0;
yield q;
for n:Z in 2 .. repeat {q := q / n; yield q;}
});
f: FPQ := invfactorialStream :: FPQ; --f(x)=e^x-1
u: FPQ := exponentiate f;
z1: List Z := [1,1,2,5,15,52,203,877,4140,21147,115975];
l1: List Q := [z*i for z in z1 for i in invfactorialStream];
l1 := cons(1, rest l1);
l2: List Q := [x for i in l1 for x in coefficients u];
assertEquals(List Q, l1, l2);
}
Uses BugWorkaround 48, DataStream 386, Q 47, and Z 47.
696a⟨test series 686a⟩+
≡ (685 704) ⊲695b 696b ⊳
testIntegrate1a(): () == BugWorkaround(
FPQ has with {integrate: (%, integrationConstant: Q == 0) -> %}
){
s: FPQ := 0;
t: FPQ := integrate s;
assertTrue(zero? t);
}
Uses BugWorkaround 48 and Q 47.
696b⟨test series 686a⟩+
≡ (685 704) ⊲696a 697a ⊳
testIntegrate1b(): () == BugWorkaround(
FPQ has with {integrate: (%, integrationConstant: Q == 0) -> %}
){
import from Q, DataStream Q;
s: FPQ := 0;
t: FPQ := integrate(s, 1);
l1: List Q := [1,0,0,0,0,0];
l2: List Q := [x for i in l1 for x in coefficients t];
assertEquals(List Q, l1, l2);
assertTrue(constant?(t::DataStream(Q)));
}
Uses BugWorkaround 48, DataStream 386, and Q 47.
697a⟨test series 686a⟩+
≡ (685 704) ⊲696b 697b ⊳
testIntegrate2a(): () == BugWorkaround(
FPQ has with {integrate: (%, integrationConstant: Q == 0) -> %}
){
import from Q, DataStream Q;
s: FPQ := term(1, 0);
t: FPQ := integrate s;
l1: List Q := [0,1,0,0,0,0];
l2: List Q := [x for i in l1 for x in coefficients t];
assertEquals(List Q, l1, l2);
-- assertTrue(constant?(t::DataStream(Q)));
}
Uses BugWorkaround 48, DataStream 386, and Q 47.
697b⟨test series 686a⟩+
≡ (685 704) ⊲697a 698a ⊳
testIntegrate2b(): () == BugWorkaround(
FPQ has with {integrate: (%, integrationConstant: Q == 0) -> %}
){
import from Q, List Q, DataStream Q;
s: FPQ := term(1, 0);
t: FPQ := integrate(s, 1);
l1: List Q := [1,1,0,0,0,0];
l2: List Q := [x for i in l1 for x in coefficients t];
assertEquals(List Q, l1, l2);
-- assertTrue(constant?(t::DataStream(Q)));
}
Uses BugWorkaround 48, DataStream 386, and Q 47.
698a⟨test series 686a⟩+
≡ (685 704) ⊲697b 698b ⊳
testIntegrate3a(): () == BugWorkaround(
FPQ has with {integrate: (%, integrationConstant: Q == 0) -> %}
){
import from Q, List Q, DataStream Q;
s: FPQ := term(1, 4);
t: FPQ := integrate s;
l1: List Q := [0,0,0,0,0,inv 5,0,0,0,0];
l2: List Q := [x for i in l1 for x in coefficients t];
assertEquals(List Q, l1, l2);
-- assertTrue(constant?(t::DataStream(Q)));
}
Uses BugWorkaround 48, DataStream 386, and Q 47.
698b⟨test series 686a⟩+
≡ (685 704) ⊲698a 699a ⊳
testIntegrate3b(): () == BugWorkaround(
FPQ has with {integrate: (%, integrationConstant: Q == 0) -> %}
){
import from Q, DataStream Q;
s: FPQ := term(1, 4);
t: FPQ := integrate(s, 1);
l1: List Q := [1,0,0,0,0,inv 5,0,0,0,0];
l2: List Q := [x for i in l1 for x in coefficients t];
assertEquals(List Q, l1, l2);
-- assertTrue(constant?(t::DataStream(Q)));
}
Uses BugWorkaround 48, DataStream 386, and Q 47.
699a⟨test series 686a⟩+
≡ (685 704) ⊲698b 699b ⊳
testSum1(): () == {
s: GS := stream(1) :: GS;
g: Generator GS := s for n: I in 0..5;
l1: List Z := [1,2,3,4,5,6,6,6,6,6];
l2: List Z := [x for i in l1 for x in coefficients sum g];
assertEquals(List Z, l1, l2);
}
Uses Generator 617, I 47, and Z 47.
699b⟨test series 686a⟩+
≡ (685 704) ⊲699a 700 ⊳
testSum2(): () == {
s: GS := stream(1) :: GS;
g: Generator GS := s for n: I in 0..;
l1: List Z := [1,2,3,4,5,6,7,8,9];
l2: List Z := [x for i in l1 for x in coefficients sum g];
assertEquals(List Z, l1, l2);
}
Uses Generator 617, I 47, and Z 47.
This tests
 |
(191)
|
ToDo ⊲ 89 ⊳ rhx ⊲ 70 ⊳ 01-Mar-2007: We get a polynomial as result and the
seccond assert even recognizes it.
700⟨test series 686a⟩+
≡ (685 704) ⊲699b 701 ⊳
testProduct1(): () == {
import from List Z, DataStream Z;
s1: GS := generator([1,1,0]) :: GS;
s2: GS := generator([1,0,1,0]) :: GS;
s3: GS := generator([1,0,0,1,0]) :: GS;
s4: GS := generator([1,0,0,0,1,0]) :: GS;
s5: GS := generator([1,0,0,0,0,1,0]) :: GS;
s6: GS := generator([1,0,0,0,0,0,1,0]) :: GS;
a: Array GS := [s1,s2,s3,s4,s5,s6];
g: Generator GS := s for s in a;
p: GS := product g;
l1: List Z := [1,1,1,2,2,3,4,4,4,5,5,5,5,4,4,4,3,2,2,1,1,1,0,0,0,0];
l2: List Z := [x for i in l1 for x in coefficients p];
assertEquals(List Z, l1, l2);
--assertTrue(constant?(p :: DataStream(Z)));
}
Uses Array 599, DataStream 386, Generator 617, and Z 47.
Here we test identity (17)
 |
(192)
|
in Section 1.4 of [BLL98] which is the type generating series of the species of
permutations.
701⟨test series 686a⟩+
≡ (685 704) ⊲700 702a ⊳
testProduct2(): () == BugWorkaround(FPQ has with {exponentiate: % -> %}){
import from Q;
m(n: I): Generator Q == generate {
n := prev n;
yield 1; repeat {for i in 1..n repeat yield 0; yield 1}
}
s(n: I): Generator Q == generate {
import from Q;
q := inv(coerce(n)$Z);
n := prev n;
yield 0; repeat {for i in 1..n repeat yield 0; yield q}
}
lhs: FPQ := product (m(n) :: FPQ for n:I in 1..);
rhs: FPQ := exponentiate sum(s(n) :: FPQ for n:I in 1..);
l: List Q := [coefficient(lhs, n) for n:I in 0..10];
r: List Q := [coefficient(rhs, n) for n:I in 0..10];
assertEquals(List Q, l, r);
}
Uses BugWorkaround 48, Generator 617, I 47, Q 47, and Z 47.
If the series has been accessed at a non-zero entry or beyond such an entry, the
series should know its true order.
702a⟨test series 686a⟩+
≡ (685 704) ⊲701 702b ⊳
testOrder1(): () == {
import from List Integer;
s: GS := stream(generator [0,0,1,0]) :: GS;
assertEquals(SeriesOrder, unknown, order s);
assertEquals(I, 0, approximateOrder(s) :: I);
assertEquals(Integer, 0, coefficient(s, 0));
assertEquals(SeriesOrder, unknown, order s);
assertEquals(I, 1, approximateOrder(s) :: I);
assertEquals(Integer, 1, coefficient(s, 2));
assertEquals(SeriesOrder, 2 :: SeriesOrder, order s);
assertEquals(I, 2, approximateOrder(s) :: I);
}
Uses I 47, Integer 66, and SeriesOrder 289.
702b⟨test series 686a⟩+
≡ (685 704) ⊲702a 703 ⊳
testOrder2(): () == {
import from List Integer;
s: GS := stream(generator [0,0,0,5,2,0]) :: GS;
assertEquals(SeriesOrder, unknown, order s);
assertEquals(I, 0, approximateOrder(s) :: I);
assertEquals(Integer, 0, coefficient(s, 0));
assertEquals(SeriesOrder, unknown, order s);
assertEquals(I, 1, approximateOrder(s) :: I);
assertEquals(Integer, 0, coefficient(s, 1));
assertEquals(SeriesOrder, unknown, order s);
assertEquals(I, 2, approximateOrder(s) :: I);
assertEquals(Integer, 0, coefficient(s, 9));
assertEquals(SeriesOrder, 3 :: SeriesOrder, order s);
assertEquals(I, 3, approximateOrder(s) :: I);
}
Uses I 47, Integer 66, and SeriesOrder 289.
703⟨test series 686a⟩+
≡ (685 704) ⊲702b 705 ⊳
testOrder3(): () == {
import from List Integer;
s: GS := stream(generator [0,0,0,0,4,0]) :: GS;
assertEquals(I, 0, approximateOrder(s) :: I);
assertEquals(I, 0, #(s :: DataStream Z));
assertEquals(SeriesOrder, unknown, order s);
assertTrue(zero? coefficient(s, 2));
assertEquals(I, 3, #(s :: DataStream Z));
assertEquals(I, 3, approximateOrder(s) :: I);
assertEquals(SeriesOrder, unknown, order s);
assertTrue(zero? coefficient(s, 9));
assertEquals(I, 6, #(s :: DataStream Z));
assertEquals(I, 4, approximateOrder(s) :: I);
assertEquals(SeriesOrder, 4 :: SeriesOrder, order s);
}
Uses DataStream 386, I 47, Integer 66, SeriesOrder 289, and Z 47.