From: Richard Kreckel <Richard.Kreckel@uni-mainz.de>
Date: Thu, 20 Apr 2000 04:13:55 +0000 (+0000)
Subject: - Timings D and E: finer time resolution
X-Git-Tag: release_0-6-0~17
X-Git-Url: https://www.ginac.de/ginac.git//ginac.git?p=ginac.git;a=commitdiff_plain;h=d6dd9e5350d479533b319dd1dfedaa2467627fe3

- Timings D and E: finer time resolution
- Timings P, P', Q, Q': construct matrix with some loops instead of reading
  it from a const ex[][].  time_lw_w101n.h is not needed any more.
- check_matrices.cpp: check the new fraction free determinant.
---

diff --git a/check/check_matrices.cpp b/check/check_matrices.cpp
index 5721a942..71893bb1 100644
--- a/check/check_matrices.cpp
+++ b/check/check_matrices.cpp
@@ -22,12 +22,13 @@
 
 #include "checks.h"
 
-// determinants of some sparse symbolic size x size matrices
-static unsigned matrix_determinants(void)
+// determinants of some sparse symbolic size x size matrices over
+// an integral domain.
+static unsigned integdom_matrix_determinants(void)
 {
     unsigned result = 0;
     symbol a("a");
-
+    
     for (int size=3; size<17; ++size) {
         matrix A(size,size);
         for (int r=0; r<size-1; ++r) {
@@ -50,6 +51,35 @@ static unsigned matrix_determinants(void)
     return result;
 }
 
+static unsigned rational_matrix_determinants(void)
+{
+    unsigned result = 0;
+    symbol a("a"), b("b"), c("c");
+    
+    for (int size=3; size<13; ++size) {
+        matrix A(size,size);
+        for (int r=0; r<size-1; ++r) {
+            // populate one element in each row:
+            // FIXME: the line using sparse_tree() should be used:
+            // A.set(r,unsigned(rand()%size),sparse_tree(a, b, c, 3, true, true)/sparse_tree(a, b, c, 2, true, true));
+            A.set(r,unsigned(rand()%size),dense_univariate_poly(a,4)/dense_univariate_poly(a,2));
+        }
+        for (int c=0; c<size; ++c) {
+            // set the last line to a linear combination of two other lines
+            // to guarantee that the determinant vanishes:
+            A.set(size-1,c,A(0,c)-A(size-2,c));
+        }
+        if (!A.determinant().is_zero()) {
+            clog << "Determinant of " << size << "x" << size << " matrix "
+                 << endl << A << endl
+                 << "was not found to vanish!" << endl;
+            ++result;
+        }
+    }
+    
+    return result;
+}
+
 unsigned check_matrices(void)
 {
     unsigned result = 0;
@@ -57,7 +87,8 @@ unsigned check_matrices(void)
     cout << "checking symbolic matrix manipulations" << flush;
     clog << "---------symbolic matrix manipulations:" << endl;
     
-    result += matrix_determinants();  cout << '.' << flush;
+    result += integdom_matrix_determinants();  cout << '.' << flush;
+    result += rational_matrix_determinants();  cout << '.' << flush;
     
     if (!result) {
         cout << " passed " << endl;
diff --git a/check/checks.h b/check/checks.h
index 02fb4eb8..4c79e2f3 100644
--- a/check/checks.h
+++ b/check/checks.h
@@ -35,6 +35,8 @@ using namespace GiNaC;
 // prototypes for the expression generating functions in:
 const ex dense_univariate_poly(const symbol & x, unsigned degree);
 const ex dense_bivariate_poly(const symbol & x1, const symbol & x2, unsigned degree);
+const ex sparse_tree(const symbol & x, const symbol & y, const symbol & z,
+                     int level, bool trig = false, bool rational = true);
 
 // prototypes for all individual checks should be unsigned fcn():
 unsigned check_numeric();
diff --git a/check/genex.cpp b/check/genex.cpp
index eabfa122..dacb40eb 100644
--- a/check/genex.cpp
+++ b/check/genex.cpp
@@ -101,9 +101,9 @@ sparse_tree(const symbol & x,
     if (level == 0)
         return random_symbol(x,y,z,rational);
     switch (abs(rand()) % 7) {
-    case 0:
-    case 1:
-        return add(sparse_tree(x,y,z,level-1, trig, rational),
+        case 0:
+        case 1:
+            return add(sparse_tree(x,y,z,level-1, trig, rational),
                        sparse_tree(x,y,z,level-1, trig, rational));
         case 2:
         case 3:
diff --git a/check/time_lw_D.cpp b/check/time_lw_D.cpp
index 092d5cc9..1f63e58f 100644
--- a/check/time_lw_D.cpp
+++ b/check/time_lw_D.cpp
@@ -63,7 +63,7 @@ unsigned time_lw_D(void)
     } else {
         cout << " failed ";
     }
-    cout << int(1000*(time/count))*0.001 << 's' << endl;
+    cout << int(100000*(time/count))*0.00001 << 's' << endl;
     
     return result;
 }
diff --git a/check/time_lw_E.cpp b/check/time_lw_E.cpp
index 934d52b5..5dc004d2 100644
--- a/check/time_lw_E.cpp
+++ b/check/time_lw_E.cpp
@@ -63,7 +63,7 @@ unsigned time_lw_E(void)
     } else {
         cout << " failed ";
     }
-    cout << int(1000*(time/count))*0.001 << 's' << endl;
+    cout << int(100000*(time/count))*0.00001 << 's' << endl;
     
     return result;
 }
diff --git a/check/time_lw_P.cpp b/check/time_lw_P.cpp
index 3145093a..2f7569f0 100644
--- a/check/time_lw_P.cpp
+++ b/check/time_lw_P.cpp
@@ -22,18 +22,26 @@
  */
 
 #include "times.h"
-#include "time_lw_w101n.h"
 
 static unsigned test(void)
 {
-    matrix m(101,101);
-    for (unsigned r=0; r<101; ++r) {
-        for (unsigned c=0; c<10; ++c) {
-            m.set(r,
-                  unsigned(ex_to_numeric(w101_numeric[r][2*c+1]).to_int()-1),
-                  w101_numeric[r][2*c+2]);
-        }
-    }
+    // This is a pattern that comes up in graph theory:
+    const unsigned n = 10;
+    matrix m(n*n+1,n*n+1);
+    for (unsigned i=1; i<=n*n; ++i)
+        m.set(i-1,i-1,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!(i%n))
+            m.set(i-1,n*n,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!((i-1)%n))
+            m.set(n*n,i-1,n-(i-1)/n);
+    for(unsigned i=1; i<=n; ++i)
+        for (unsigned j=1; j<=n; ++j)
+            if (i-j)
+                for (unsigned k=1; k<n; ++k)
+                    m.set((i-1)*n+k-1,(j-1)*n+k,n+1-j);
+    
     ex det = m.determinant();
     
     if (det!=numeric("75810815066186520")) {
diff --git a/check/time_lw_Pprime.cpp b/check/time_lw_Pprime.cpp
index 5fb670da..7860e4ac 100644
--- a/check/time_lw_Pprime.cpp
+++ b/check/time_lw_Pprime.cpp
@@ -22,33 +22,39 @@
  */
 
 #include "times.h"
-#include "time_lw_w101n.h"
 
 static unsigned test(void)
 {
-    matrix m(101,101);
-    for (unsigned r=0; r<101; ++r) {
-        for (unsigned c=0; c<10; ++c) {
-            m.set(r,
-                  unsigned(ex_to_numeric(w101_numeric[r][2*c+1]).to_int()-1),
-                  w101_numeric[r][2*c+2]);
-        }
-    }
+    // create the matrix from test P...
+    const unsigned n = 10;
+    matrix m(n*n+1,n*n+1);
+    for (unsigned i=1; i<=n*n; ++i)
+        m.set(i-1,i-1,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!(i%n))
+            m.set(i-1,n*n,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!((i-1)%n))
+            m.set(n*n,i-1,n-(i-1)/n);
+    for(unsigned i=1; i<=n; ++i)
+        for (unsigned j=1; j<=n; ++j)
+            if (i-j)
+                for (unsigned k=1; k<n; ++k)
+                    m.set((i-1)*n+k-1,(j-1)*n+k,n+1-j);
+    // ...and then another, more dense one:
     matrix m2(m);
     ex a;
-    for (unsigned r=0; r<101; ++r) {
+    for (unsigned r=0; r<=n*n; ++r) {
         a = m2(r,0);
-        for (unsigned c=0; c<100; ++c) {
+        for (unsigned c=0; c<n*n; ++c)
             m2.set(r,c,m2(r,c+1));
-        }
         m2.set(r,100,a);
     }
-    for (unsigned r=0; r<101; ++r) {
-        for (unsigned c=0; c<101; ++c) {
+    for (unsigned r=0; r<=n*n; ++r)
+        for (unsigned c=0; c<=n*n; ++c)
             if (!m(r,c).is_zero())
                 m2.set(r,c,m(r,c));
-        }
-    }
+    
     ex det = m2.determinant();
     
     if (det!=numeric("140816284877507872414776")) {
diff --git a/check/time_lw_Q.cpp b/check/time_lw_Q.cpp
index 0c29dfb0..c8d586b1 100644
--- a/check/time_lw_Q.cpp
+++ b/check/time_lw_Q.cpp
@@ -22,19 +22,27 @@
  */
 
 #include "times.h"
-#include "time_lw_w101n.h"
 
 static unsigned test(void)
 {
-    matrix m(101,101);
+    // same matrix as in test P:
+    const unsigned n = 10;
+    matrix m(n*n+1,n*n+1);
+    for (unsigned i=1; i<=n*n; ++i)
+        m.set(i-1,i-1,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!(i%n))
+            m.set(i-1,n*n,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!((i-1)%n))
+            m.set(n*n,i-1,n-(i-1)/n);
+    for(unsigned i=1; i<=n; ++i)
+        for (unsigned j=1; j<=n; ++j)
+            if (i-j)
+                for (unsigned k=1; k<n; ++k)
+                    m.set((i-1)*n+k-1,(j-1)*n+k,n+1-j);
+    
     symbol lambda("lambda");
-    for (unsigned r=0; r<101; ++r) {
-        for (unsigned c=0; c<10; ++c) {
-            m.set(r,
-                  unsigned(ex_to_numeric(w101_numeric[r][2*c+1]).to_int()-1),
-                  w101_numeric[r][2*c+2]);
-        }
-    }
     ex cp = m.charpoly(lambda);
     
     if (cp.coeff(lambda,96) != numeric("75287520")) {
diff --git a/check/time_lw_Qprime.cpp b/check/time_lw_Qprime.cpp
index b60ba11b..139b09b1 100644
--- a/check/time_lw_Qprime.cpp
+++ b/check/time_lw_Qprime.cpp
@@ -22,34 +22,39 @@
  */
 
 #include "times.h"
-#include "time_lw_w101n.h"
 
 static unsigned test(void)
 {
-    matrix m(101,101);
-    symbol lambda("lambda");
-    for (unsigned r=0; r<101; ++r) {
-        for (unsigned c=0; c<10; ++c) {
-            m.set(r,
-                  unsigned(ex_to_numeric(w101_numeric[r][2*c+1]).to_int()-1),
-                  w101_numeric[r][2*c+2]);
-        }
-    }
+    // same matrix as in test P':
+    const unsigned n = 10;
+    matrix m(n*n+1,n*n+1);
+    for (unsigned i=1; i<=n*n; ++i)
+        m.set(i-1,i-1,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!(i%n))
+            m.set(i-1,n*n,1);
+    for (unsigned i=1; i<=n*n; ++i)
+        if (!((i-1)%n))
+            m.set(n*n,i-1,n-(i-1)/n);
+    for(unsigned i=1; i<=n; ++i)
+        for (unsigned j=1; j<=n; ++j)
+            if (i-j)
+                for (unsigned k=1; k<n; ++k)
+                    m.set((i-1)*n+k-1,(j-1)*n+k,n+1-j);
     matrix m2(m);
     ex a;
-    for (unsigned r=0; r<101; ++r) {
+    for (unsigned r=0; r<=n*n; ++r) {
         a = m2(r,0);
-        for (unsigned c=0; c<100; ++c) {
+        for (unsigned c=0; c<n*n; ++c)
             m2.set(r,c,m2(r,c+1));
-        }
         m2.set(r,100,a);
     }
-    for (unsigned r=0; r<101; ++r) {
-        for (unsigned c=0; c<101; ++c) {
+    for (unsigned r=0; r<=n*n; ++r)
+        for (unsigned c=0; c<=n*n; ++c)
             if (!m(r,c).is_zero())
                 m2.set(r,c,m(r,c));
-        }
-    }
+    
+    symbol lambda("lambda");
     ex cp = m2.charpoly(lambda);
     
     if (cp.coeff(lambda,0) != numeric("140816284877507872414776")) {
diff --git a/check/time_lw_w101n.h b/check/time_lw_w101n.h
deleted file mode 100644
index 247fe46d..00000000
--- a/check/time_lw_w101n.h
+++ /dev/null
@@ -1,103 +0,0 @@
-static ex w101_numeric[101][21] = {
-    {  1,  1, 1, 12, 9, 22, 8, 32, 7, 42, 6, 52, 5, 62, 4, 72, 3, 82, 2, 92, 1 },
-    {  2,  2, 1, 13, 9, 23, 8, 33, 7, 43, 6, 53, 5, 63, 4, 73, 3, 83, 2, 93, 1 },
-    {  3,  3, 1, 14, 9, 24, 8, 34, 7, 44, 6, 54, 5, 64, 4, 74, 3, 84, 2, 94, 1 },
-    {  4,  4, 1, 15, 9, 25, 8, 35, 7, 45, 6, 55, 5, 65, 4, 75, 3, 85, 2, 95, 1 },
-    {  5,  5, 1, 16, 9, 26, 8, 36, 7, 46, 6, 56, 5, 66, 4, 76, 3, 86, 2, 96, 1 },
-    {  6,  6, 1, 17, 9, 27, 8, 37, 7, 47, 6, 57, 5, 67, 4, 77, 3, 87, 2, 97, 1 },
-    {  7,  7, 1, 18, 9, 28, 8, 38, 7, 48, 6, 58, 5, 68, 4, 78, 3, 88, 2, 98, 1 },
-    {  8,  8, 1, 19, 9, 29, 8, 39, 7, 49, 6, 59, 5, 69, 4, 79, 3, 89, 2, 99, 1 },
-    {  9,  9, 1, 20, 9, 30, 8, 40, 7, 50, 6, 60, 5, 70, 4, 80, 3, 90, 2, 100, 1 },
-    { 10, 10, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0 },
-    { 11,  2, 10, 11, 1, 22, 8, 32, 7, 42, 6, 52, 5, 62, 4, 72, 3, 82, 2, 92, 1 },
-    { 12,  3, 10, 12, 1, 23, 8, 33, 7, 43, 6, 53, 5, 63, 4, 73, 3, 83, 2, 93, 1 },
-    { 13,  4, 10, 13, 1, 24, 8, 34, 7, 44, 6, 54, 5, 64, 4, 74, 3, 84, 2, 94, 1 },
-    { 14,  5, 10, 14, 1, 25, 8, 35, 7, 45, 6, 55, 5, 65, 4, 75, 3, 85, 2, 95, 1 },
-    { 15,  6, 10, 15, 1, 26, 8, 36, 7, 46, 6, 56, 5, 66, 4, 76, 3, 86, 2, 96, 1 },
-    { 16,  7, 10, 16, 1, 27, 8, 37, 7, 47, 6, 57, 5, 67, 4, 77, 3, 87, 2, 97, 1 },
-    { 17,  8, 10, 17, 1, 28, 8, 38, 7, 48, 6, 58, 5, 68, 4, 78, 3, 88, 2, 98, 1 },
-    { 18,  9, 10, 18, 1, 29, 8, 39, 7, 49, 6, 59, 5, 69, 4, 79, 3, 89, 2, 99, 1 },
-    { 19, 10, 10, 19, 1, 30, 8, 40, 7, 50, 6, 60, 5, 70, 4, 80, 3, 90, 2, 100, 1 },
-    { 20, 20, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 21,  2, 10, 12, 9, 21, 1, 32, 7, 42, 6, 52, 5, 62, 4, 72, 3, 82, 2, 92, 1 },
-    { 22,  3, 10, 13, 9, 22, 1, 33, 7, 43, 6, 53, 5, 63, 4, 73, 3, 83, 2, 93, 1 },
-    { 23,  4, 10, 14, 9, 23, 1, 34, 7, 44, 6, 54, 5, 64, 4, 74, 3, 84, 2, 94, 1 },
-    { 24,  5, 10, 15, 9, 24, 1, 35, 7, 45, 6, 55, 5, 65, 4, 75, 3, 85, 2, 95, 1 },
-    { 25,  6, 10, 16, 9, 25, 1, 36, 7, 46, 6, 56, 5, 66, 4, 76, 3, 86, 2, 96, 1 },
-    { 26,  7, 10, 17, 9, 26, 1, 37, 7, 47, 6, 57, 5, 67, 4, 77, 3, 87, 2, 97, 1 },
-    { 27,  8, 10, 18, 9, 27, 1, 38, 7, 48, 6, 58, 5, 68, 4, 78, 3, 88, 2, 98, 1 },
-    { 28,  9, 10, 19, 9, 28, 1, 39, 7, 49, 6, 59, 5, 69, 4, 79, 3, 89, 2, 99, 1 },
-    { 29, 10, 10, 20, 9, 29, 1, 40, 7, 50, 6, 60, 5, 70, 4, 80, 3, 90, 2, 100, 1 },
-    { 30, 30, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 31,  2, 10, 12, 9, 22, 8, 31, 1, 42, 6, 52, 5, 62, 4, 72, 3, 82, 2, 92, 1 },
-    { 32,  3, 10, 13, 9, 23, 8, 32, 1, 43, 6, 53, 5, 63, 4, 73, 3, 83, 2, 93, 1 },
-    { 33,  4, 10, 14, 9, 24, 8, 33, 1, 44, 6, 54, 5, 64, 4, 74, 3, 84, 2, 94, 1 },
-    { 34,  5, 10, 15, 9, 25, 8, 34, 1, 45, 6, 55, 5, 65, 4, 75, 3, 85, 2, 95, 1 },
-    { 35,  6, 10, 16, 9, 26, 8, 35, 1, 46, 6, 56, 5, 66, 4, 76, 3, 86, 2, 96, 1 },
-    { 36,  7, 10, 17, 9, 27, 8, 36, 1, 47, 6, 57, 5, 67, 4, 77, 3, 87, 2, 97, 1 },
-    { 37,  8, 10, 18, 9, 28, 8, 37, 1, 48, 6, 58, 5, 68, 4, 78, 3, 88, 2, 98, 1 },
-    { 38,  9, 10, 19, 9, 29, 8, 38, 1, 49, 6, 59, 5, 69, 4, 79, 3, 89, 2, 99, 1 },
-    { 39, 10, 10, 20, 9, 30, 8, 39, 1, 50, 6, 60, 5, 70, 4, 80, 3, 90, 2, 100, 1 },
-    { 40, 40, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 41,  2, 10, 12, 9, 22, 8, 32, 7, 41, 1, 52, 5, 62, 4, 72, 3, 82, 2, 92, 1 },
-    { 42,  3, 10, 13, 9, 23, 8, 33, 7, 42, 1, 53, 5, 63, 4, 73, 3, 83, 2, 93, 1 },
-    { 43,  4, 10, 14, 9, 24, 8, 34, 7, 43, 1, 54, 5, 64, 4, 74, 3, 84, 2, 94, 1 },
-    { 44,  5, 10, 15, 9, 25, 8, 35, 7, 44, 1, 55, 5, 65, 4, 75, 3, 85, 2, 95, 1 },
-    { 45,  6, 10, 16, 9, 26, 8, 36, 7, 45, 1, 56, 5, 66, 4, 76, 3, 86, 2, 96, 1 },
-    { 46,  7, 10, 17, 9, 27, 8, 37, 7, 46, 1, 57, 5, 67, 4, 77, 3, 87, 2, 97, 1 },
-    { 47,  8, 10, 18, 9, 28, 8, 38, 7, 47, 1, 58, 5, 68, 4, 78, 3, 88, 2, 98, 1 },
-    { 48,  9, 10, 19, 9, 29, 8, 39, 7, 48, 1, 59, 5, 69, 4, 79, 3, 89, 2, 99, 1 },
-    { 49, 10, 10, 20, 9, 30, 8, 40, 7, 49, 1, 60, 5, 70, 4, 80, 3, 90, 2, 100, 1 },
-    { 50, 50, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 51,  2, 10, 12, 9, 22, 8, 32, 7, 42, 6, 51, 1, 62, 4, 72, 3, 82, 2, 92, 1 },
-    { 52,  3, 10, 13, 9, 23, 8, 33, 7, 43, 6, 52, 1, 63, 4, 73, 3, 83, 2, 93, 1 },
-    { 53,  4, 10, 14, 9, 24, 8, 34, 7, 44, 6, 53, 1, 64, 4, 74, 3, 84, 2, 94, 1 },
-    { 54,  5, 10, 15, 9, 25, 8, 35, 7, 45, 6, 54, 1, 65, 4, 75, 3, 85, 2, 95, 1 },
-    { 55,  6, 10, 16, 9, 26, 8, 36, 7, 46, 6, 55, 1, 66, 4, 76, 3, 86, 2, 96, 1 },
-    { 56,  7, 10, 17, 9, 27, 8, 37, 7, 47, 6, 56, 1, 67, 4, 77, 3, 87, 2, 97, 1 },
-    { 57,  8, 10, 18, 9, 28, 8, 38, 7, 48, 6, 57, 1, 68, 4, 78, 3, 88, 2, 98, 1 },
-    { 58,  9, 10, 19, 9, 29, 8, 39, 7, 49, 6, 58, 1, 69, 4, 79, 3, 89, 2, 99, 1 },
-    { 59, 10, 10, 20, 9, 30, 8, 40, 7, 50, 6, 59, 1, 70, 4, 80, 3, 90, 2, 100, 1 },
-    { 60, 60, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 61,  2, 10, 12, 9, 22, 8, 32, 7, 42, 6, 52, 5, 61,   1, 72, 3, 82, 2, 92, 1 },
-    { 62,  3, 10, 13, 9, 23, 8, 33, 7, 43, 6, 53, 5, 62,   1, 73, 3, 83, 2, 93, 1 },
-    { 63,  4, 10, 14, 9, 24, 8, 34, 7, 44, 6, 54, 5, 63,   1, 74, 3, 84, 2, 94, 1 },
-    { 64,  5, 10, 15, 9, 25, 8, 35, 7, 45, 6, 55, 5, 64,   1, 75, 3, 85, 2, 95, 1 },
-    { 65,  6, 10, 16, 9, 26, 8, 36, 7, 46, 6, 56, 5, 65,   1, 76, 3, 86, 2, 96, 1 },
-    { 66,  7, 10, 17, 9, 27, 8, 37, 7, 47, 6, 57, 5, 66,   1, 77, 3, 87, 2, 97, 1 },
-    { 67,  8, 10, 18, 9, 28, 8, 38, 7, 48, 6, 58, 5, 67,   1, 78, 3, 88, 2, 98, 1 },
-    { 68,  9, 10, 19, 9, 29, 8, 39, 7, 49, 6, 59, 5, 68,   1, 79, 3, 89, 2, 99, 1 },
-    { 69, 10, 10, 20, 9, 30, 8, 40, 7, 50, 6, 60, 5, 69,   1, 80, 3, 90, 2, 100, 1 },
-    { 70, 70, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 71,  2, 10, 12, 9, 22, 8, 32, 7, 42, 6, 52, 5, 62, 4, 71,   1, 82, 2, 92, 1 },
-    { 72,  3, 10, 13, 9, 23, 8, 33, 7, 43, 6, 53, 5, 63, 4, 72,   1, 83, 2, 93, 1 },
-    { 73,  4, 10, 14, 9, 24, 8, 34, 7, 44, 6, 54, 5, 64, 4, 73,   1, 84, 2, 94, 1 },
-    { 74,  5, 10, 15, 9, 25, 8, 35, 7, 45, 6, 55, 5, 65, 4, 74,   1, 85, 2, 95, 1 },
-    { 75,  6, 10, 16, 9, 26, 8, 36, 7, 46, 6, 56, 5, 66, 4, 75,   1, 86, 2, 96, 1 },
-    { 76,  7, 10, 17, 9, 27, 8, 37, 7, 47, 6, 57, 5, 67, 4, 76,   1, 87, 2, 97, 1 },
-    { 77,  8, 10, 18, 9, 28, 8, 38, 7, 48, 6, 58, 5, 68, 4, 77,   1, 88, 2, 98, 1 },
-    { 78,  9, 10, 19, 9, 29, 8, 39, 7, 49, 6, 59, 5, 69, 4, 78,   1, 89, 2, 99, 1 },
-    { 79, 10, 10, 20, 9, 30, 8, 40, 7, 50, 6, 60, 5, 70, 4, 79,   1, 90, 2, 100, 1 },
-    { 80, 80, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 81,  2, 10, 12, 9, 22, 8, 32, 7, 42, 6, 52, 5, 62, 4, 72, 3, 81,   1, 92, 1 },
-    { 82,  3, 10, 13, 9, 23, 8, 33, 7, 43, 6, 53, 5, 63, 4, 73, 3, 82,   1, 93, 1 },
-    { 83,  4, 10, 14, 9, 24, 8, 34, 7, 44, 6, 54, 5, 64, 4, 74, 3, 83,   1, 94, 1 },
-    { 84,  5, 10, 15, 9, 25, 8, 35, 7, 45, 6, 55, 5, 65, 4, 75, 3, 84,   1, 95, 1 },
-    { 85,  6, 10, 16, 9, 26, 8, 36, 7, 46, 6, 56, 5, 66, 4, 76, 3, 85,   1, 96, 1 },
-    { 86,  7, 10, 17, 9, 27, 8, 37, 7, 47, 6, 57, 5, 67, 4, 77, 3, 86,   1, 97, 1 },
-    { 87,  8, 10, 18, 9, 28, 8, 38, 7, 48, 6, 58, 5, 68, 4, 78, 3, 87,   1, 98, 1 },
-    { 88,  9, 10, 19, 9, 29, 8, 39, 7, 49, 6, 59, 5, 69, 4, 79, 3, 88,   1, 99, 1 },
-    { 89, 10, 10, 20, 9, 30, 8, 40, 7, 50, 6, 60, 5, 70, 4, 80, 3, 89,   1, 100, 1 },
-    { 90, 90, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 91,  2, 10, 12, 9, 22, 8, 32, 7, 42, 6, 52, 5, 62, 4, 72, 3, 82, 2, 91,   1 },
-    { 92,  3, 10, 13, 9, 23, 8, 33, 7, 43, 6, 53, 5, 63, 4, 73, 3, 83, 2, 92,   1 },
-    { 93,  4, 10, 14, 9, 24, 8, 34, 7, 44, 6, 54, 5, 64, 4, 74, 3, 84, 2, 93,   1 },
-    { 94,  5, 10, 15, 9, 25, 8, 35, 7, 45, 6, 55, 5, 65, 4, 75, 3, 85, 2, 94,   1 },
-    { 95,  6, 10, 16, 9, 26, 8, 36, 7, 46, 6, 56, 5, 66, 4, 76, 3, 86, 2, 95,   1 },
-    { 96,  7, 10, 17, 9, 27, 8, 37, 7, 47, 6, 57, 5, 67, 4, 77, 3, 87, 2, 96,   1 },
-    { 97,  8, 10, 18, 9, 28, 8, 38, 7, 48, 6, 58, 5, 68, 4, 78, 3, 88, 2, 97,   1 },
-    { 98,  9, 10, 19, 9, 29, 8, 39, 7, 49, 6, 59, 5, 69, 4, 79, 3, 89, 2, 98,   1 },
-    { 99, 10, 10, 20, 9, 30, 8, 40, 7, 50, 6, 60, 5, 70, 4, 80, 3, 90, 2, 99,   1 },
-    { 100, 100, 1, 101, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0  },
-    { 101,  1, 10, 11, 9, 21, 8, 31, 7, 41, 6, 51, 5, 61, 4, 71, 3, 81, 2, 91, 1 }
-};