Happy new year!
[ginac.git] / check / time_lw_M2.cpp
1 /** @file time_lw_M2.cpp
2  *
3  *  Test M2 from the paper "Comparison of Polynomial-Oriented CAS" by Robert H.
4  *  Lewis and Michael Wester. */
5
6 /*
7  *  GiNaC Copyright (C) 1999-2005 Johannes Gutenberg University Mainz, Germany
8  *
9  *  This program is free software; you can redistribute it and/or modify
10  *  it under the terms of the GNU General Public License as published by
11  *  the Free Software Foundation; either version 2 of the License, or
12  *  (at your option) any later version.
13  *
14  *  This program is distributed in the hope that it will be useful,
15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
17  *  GNU General Public License for more details.
18  *
19  *  You should have received a copy of the GNU General Public License
20  *  along with this program; if not, write to the Free Software
21  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
22  */
23
24 #include "times.h"
25
26 static const bool do_test = false;  // set to true in order to run this beast
27
28 static unsigned test()
29 {
30         // Determinant of a sparse matrix that comes up in graph theory:
31         symbol x1("x1"), x2("x2"), x3("x3"), x4("x4"), x5("x5");
32         symbol x6("x6"), x7("x7"), x8("x8"), x9("x9"), xA("xA");
33         ex w[101][21] = {
34             { 1, 1, 1, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
35             { 2, 2, 1, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
36             { 3, 3, 1, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
37             { 4, 4, 1, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
38             { 5, 5, 1, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
39             { 6, 6, 1, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
40             { 7, 7, 1, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
41             { 8, 8, 1, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
42             { 9, 9, 1, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
43             {10, 10, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
44             {11, 2, xA, 11, 1, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
45             {12, 3, xA, 12, 1, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
46             {13, 4, xA, 13, 1, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
47             {14, 5, xA, 14, 1, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
48             {15, 6, xA, 15, 1, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
49             {16, 7, xA, 16, 1, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
50             {17, 8, xA, 17, 1, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
51             {18, 9, xA, 18, 1, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
52             {19, 10, xA, 19, 1, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
53             {20, 20, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
54             {21, 2, xA, 12, x9, 21, 1, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
55             {22, 3, xA, 13, x9, 22, 1, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
56             {23, 4, xA, 14, x9, 23, 1, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
57             {24, 5, xA, 15, x9, 24, 1, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
58             {25, 6, xA, 16, x9, 25, 1, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
59             {26, 7, xA, 17, x9, 26, 1, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
60             {27, 8, xA, 18, x9, 27, 1, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
61             {28, 9, xA, 19, x9, 28, 1, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
62             {29, 10, xA, 20, x9, 29, 1, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
63             {30, 30, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
64             {31, 2, xA, 12, x9, 22, x8, 31, 1, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
65             {32, 3, xA, 13, x9, 23, x8, 32, 1, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
66             {33, 4, xA, 14, x9, 24, x8, 33, 1, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
67             {34, 5, xA, 15, x9, 25, x8, 34, 1, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
68             {35, 6, xA, 16, x9, 26, x8, 35, 1, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
69             {36, 7, xA, 17, x9, 27, x8, 36, 1, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
70             {37, 8, xA, 18, x9, 28, x8, 37, 1, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
71             {38, 9, xA, 19, x9, 29, x8, 38, 1, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
72             {39, 10, xA, 20, x9, 30, x8, 39, 1, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
73             {40, 40, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
74             {41, 2, xA, 12, x9, 22, x8, 32, x7, 41, 1, 52, x5, 62, x4, 72, x3, 82, x2, 92, x1 },
75             {42, 3, xA, 13, x9, 23, x8, 33, x7, 42, 1, 53, x5, 63, x4, 73, x3, 83, x2, 93, x1 },
76             {43, 4, xA, 14, x9, 24, x8, 34, x7, 43, 1, 54, x5, 64, x4, 74, x3, 84, x2, 94, x1 },
77             {44, 5, xA, 15, x9, 25, x8, 35, x7, 44, 1, 55, x5, 65, x4, 75, x3, 85, x2, 95, x1 },
78             {45, 6, xA, 16, x9, 26, x8, 36, x7, 45, 1, 56, x5, 66, x4, 76, x3, 86, x2, 96, x1 },
79             {46, 7, xA, 17, x9, 27, x8, 37, x7, 46, 1, 57, x5, 67, x4, 77, x3, 87, x2, 97, x1 },
80             {47, 8, xA, 18, x9, 28, x8, 38, x7, 47, 1, 58, x5, 68, x4, 78, x3, 88, x2, 98, x1 },
81             {48, 9, xA, 19, x9, 29, x8, 39, x7, 48, 1, 59, x5, 69, x4, 79, x3, 89, x2, 99, x1 },
82             {49, 10, xA, 20, x9, 30, x8, 40, x7, 49, 1, 60, x5, 70, x4, 80, x3, 90, x2, 100, x1 },
83             {50, 50, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
84             {51, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 51, 1, 62, x4, 72, x3, 82, x2, 92, x1 },
85             {52, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 52, 1, 63, x4, 73, x3, 83, x2, 93, x1 },
86             {53, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 53, 1, 64, x4, 74, x3, 84, x2, 94, x1 },
87             {54, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 54, 1, 65, x4, 75, x3, 85, x2, 95, x1 },
88             {55, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 55, 1, 66, x4, 76, x3, 86, x2, 96, x1 },
89             {56, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 56, 1, 67, x4, 77, x3, 87, x2, 97, x1 },
90             {57, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 57, 1, 68, x4, 78, x3, 88, x2, 98, x1 },
91             {58, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 58, 1, 69, x4, 79, x3, 89, x2, 99, x1 },
92             {59, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 59, 1, 70, x4, 80, x3, 90, x2, 100, x1 },
93             {60, 60, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
94             {61, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 61, 1, 72, x3, 82, x2, 92, x1 },
95             {62, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 62, 1, 73, x3, 83, x2, 93, x1 },
96             {63, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 63, 1, 74, x3, 84, x2, 94, x1 },
97             {64, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 64, 1, 75, x3, 85, x2, 95, x1 },
98             {65, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 65, 1, 76, x3, 86, x2, 96, x1 },
99             {66, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 66, 1, 77, x3, 87, x2, 97, x1 },
100             {67, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 67, 1, 78, x3, 88, x2, 98, x1 },
101             {68, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 68, 1, 79, x3, 89, x2, 99, x1 },
102             {69, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 69, 1, 80, x3, 90, x2, 100, x1 },
103             {70, 70, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
104             {71, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 71, 1, 82, x2, 92, x1 },
105             {72, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 72, 1, 83, x2, 93, x1 },
106             {73, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 73, 1, 84, x2, 94, x1 },
107             {74, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 74, 1, 85, x2, 95, x1 },
108             {75, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 75, 1, 86, x2, 96, x1 },
109             {76, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 76, 1, 87, x2, 97, x1 },
110             {77, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 77, 1, 88, x2, 98, x1 },
111             {78, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 78, 1, 89, x2, 99, x1 },
112             {79, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 79, 1, 90, x2, 100, x1 },
113             {80, 80, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
114             {81, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 81, 1, 92, x1 },
115             {82, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 82, 1, 93, x1 },
116             {83, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 83, 1, 94, x1 },
117             {84, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 84, 1, 95, x1 },
118             {85, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 85, 1, 96, x1 },
119             {86, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 86, 1, 97, x1 },
120             {87, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 87, 1, 98, x1 },
121             {88, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 88, 1, 99, x1 },
122             {89, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 89, 1, 100, x1 },
123             {90, 90, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
124             {91, 2, xA, 12, x9, 22, x8, 32, x7, 42, x6, 52, x5, 62, x4, 72, x3, 82, x2, 91, 1 },
125             {92, 3, xA, 13, x9, 23, x8, 33, x7, 43, x6, 53, x5, 63, x4, 73, x3, 83, x2, 92, 1 },
126             {93, 4, xA, 14, x9, 24, x8, 34, x7, 44, x6, 54, x5, 64, x4, 74, x3, 84, x2, 93, 1 },
127             {94, 5, xA, 15, x9, 25, x8, 35, x7, 45, x6, 55, x5, 65, x4, 75, x3, 85, x2, 94, 1 },
128             {95, 6, xA, 16, x9, 26, x8, 36, x7, 46, x6, 56, x5, 66, x4, 76, x3, 86, x2, 95, 1 },
129             {96, 7, xA, 17, x9, 27, x8, 37, x7, 47, x6, 57, x5, 67, x4, 77, x3, 87, x2, 96, 1 },
130             {97, 8, xA, 18, x9, 28, x8, 38, x7, 48, x6, 58, x5, 68, x4, 78, x3, 88, x2, 97, 1 },
131             {98, 9, xA, 19, x9, 29, x8, 39, x7, 49, x6, 59, x5, 69, x4, 79, x3, 89, x2, 98, 1 },
132             {99, 10, xA, 20, x9, 30, x8, 40, x7, 50, x6, 60, x5, 70, x4, 80, x3, 90, x2, 99, 1 },
133             {100, 100, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
134             {101, 1, xA, 11, x9, 21, x8, 31, x7, 41, x6, 51, x5, 61, x4, 71, x3, 81, x2, 91, x1}
135         };
136         matrix m(101,101);
137         for (unsigned r=0; r<101; ++r) {
138                 for (unsigned c=0; c<10; ++c) {
139                         m.set(r,
140                               unsigned(ex_to<numeric>(w[r][2*c+1]).to_int()-1),
141                               w[r][2*c+2]);
142                 }
143         }
144         ex det = m.determinant();
145         if (det.nops()!=85228) {
146                 clog << "The determinant was miscalculated." << endl;
147                 return 1;
148         }
149         return 0;
150 }
151
152 unsigned time_lw_M2()
153 {
154         unsigned result = 0;
155         unsigned count = 0;
156         timer piaget;
157         double time = .0;
158         
159         cout << "timing Lewis-Wester test M2 (101x101 sparse, det)" << flush;
160         clog << "-------Lewis-Wester test M2 (101x101 sparse, det):" << endl;
161         
162         if (do_test) {
163                 piaget.start();
164                 // correct for very small times:
165                 do {
166                         result = test();
167                         ++count;
168                 } while ((time=piaget.read())<0.1 && !result);
169                 cout << '.' << flush;
170                 
171                 if (!result) {
172                         cout << " passed ";
173                         clog << "(no output)" << endl;
174                 } else {
175                         cout << " failed ";
176                 }
177                 cout << int(1000*(time/count))*0.001 << 's' << endl;
178         } else {
179                 cout << " disabled" << endl;
180                 clog << "(no output)" << endl;
181         }
182         
183         return result;
184 }