Пределы магических квадратов
index.htm - English text
MagicSquare2.zip - результаты всех суперкомпиляций.
Пусть M - магический квадрат, составленный из последовательных натуральных чисел, начиная с 1.
В этом примере рассматриваем магические квадраты нечетного размера dim, потому что используем простой способ построения такого квадрата.
Для dim=5 способ построения показан ниже. Составляется таблица по-порядку по диагоналям, затем наружные числа сдвигаются на свободные места.
|
|
Пусть s - сумма чисел по строке, по столбцу или по диагонали.
Обозначим через A матрицу M / s . Например, для квадрата 3 на 3 получается матрица
| 4/15 | 9/15 | 2/15 |
| 3/15 | 5/15 | 7/15 |
| 8/15 | 1/15 | 6/15 |
Теперь рассматриваем предел при n, стремящемся к бесконечности, матрицы An.
Замечание 1. Если делить не на s, то в пределе получается либо 0, либо бесконечность. Доказательство - не очень простое упражнение по курсу алгебра для первого курса.
Замечание 2. В ответе получается матрица из одинаковых элементов, равных 1/dim.
Рассматриваем программы на языке Java,
Предел для двойной точности получается уже при 20-ой степени, но мы делаем большой цикл с целью измерить время исполнения.
При суперкомпиляции этих программ процесс построения магического квадрата полностью специализируется, то есть матрица получается как заданная.
С точки зрения суперкомпиляции - пример очень хорош. Первый участок программ, где происходит вычисление магического квадрата, - полностью сворачивается. На втором участке из нескольких вложенных циклов остается лишь один
В настоящий момент имеются три программы для пределов магических квадратов (в архивированном приложении MagicSquare2.zip соответственно три директории)
1. Моя программа korlyukov.htm , которая больше похожа на программу на Фортране, чем на программу на Яве.
2. Программа Павла Чекина chekin.htm , которую он написал, увидев предыдущую программу.
3. Программа jama.htm , в которой используется пакет Jama
http://math.nist.gov/javanumerics/jama/
http://math.nist.gov/javanumerics/jama/Jama-1.0.1.zip
В пакете Jama реализованы функции работы с матрицами, в качестве примера использования пакета проиводится программа построения магических квадратов. Поэтому программа jama.htm получилась компактной.
Все три программы благополучно суперкомпилируются. Остаточные программы не очень отличаются друг от друга.
В трех директориях приложения MagicSquare2.zip приведено все, необходимое для суперкомпиляции и пусков на счет исходной и остаточной программ. В поддиректория Res приведены результаты суперкомпиляции для dim=5.
Приведем совокупную таблицу (dim=5, iters=100 000)
| Korlyukov | Chekin | Jama | |
| время суперкомпиляции | 11 сек | 25 сек | 9 сек |
| время исполнения исходной программы | 0.661 | 0.63 | 1.170 |
| время исполнения остаточной программы | 0.12 | 0.11 | 0.54 |
| коэффициент ускорения | 5.5 | 5.7 | 2.2 |
Результат суперкомпиляции для dim=3 (Korlyukov)
//-------------------------------------- 1 sec - postprocessing...
public static double[][] test (final double[][] a_2)
{
final double[] rr_7 = new double[3];
rr_7[0] = 0.26666666666666666D;
rr_7[1] = 0.2D;
rr_7[2] = 0.5333333333333333D;
for (int iiii_226 = 0; iiii_226 < MagicSquare.iter; iiii_226++) {
final double rr1_1_278 = rr_7[0] * 0.2D + rr_7[1] * 0.3333333333333333D + rr_7[2] * 0.4666666666666667D;
final double rr1_2_307 = rr_7[0] * 0.5333333333333333D + rr_7[1] * 0.06666666666666667D + rr_7[2] * 0.4D;
rr_7[0] = rr_7[0] * 0.26666666666666666D + rr_7[1] * 0.6D + rr_7[2] * 0.13333333333333333D;
rr_7[1] = rr1_1_278;
rr_7[2] = rr1_2_307;
continue;}
/*for*/
MagicSquare.res[0][0] = rr_7[0];
MagicSquare.res[0][1] = rr_7[1];
MagicSquare.res[0][2] = rr_7[2];
rr_7[0] = 0.6D;
rr_7[1] = 0.3333333333333333D;
rr_7[2] = 0.06666666666666667D;
for (int iiii_490 = 0; iiii_490 < MagicSquare.iter; iiii_490++) {
final double rr1_1_542 = rr_7[0] * 0.2D + rr_7[1] * 0.3333333333333333D + rr_7[2] * 0.4666666666666667D;
final double rr1_2_571 = rr_7[0] * 0.5333333333333333D + rr_7[1] * 0.06666666666666667D + rr_7[2] * 0.4D;
rr_7[0] = rr_7[0] * 0.26666666666666666D + rr_7[1] * 0.6D + rr_7[2] * 0.13333333333333333D;
rr_7[1] = rr1_1_542;
rr_7[2] = rr1_2_571;
continue;}
/*for*/
MagicSquare.res[1][0] = rr_7[0];
MagicSquare.res[1][1] = rr_7[1];
MagicSquare.res[1][2] = rr_7[2];
rr_7[0] = 0.13333333333333333D;
rr_7[1] = 0.4666666666666667D;
rr_7[2] = 0.4D;
for (int iiii_754 = 0; iiii_754 < MagicSquare.iter; iiii_754++) {
final double rr1_1_806 = rr_7[0] * 0.2D + rr_7[1] * 0.3333333333333333D + rr_7[2] * 0.4666666666666667D;
final double rr1_2_835 = rr_7[0] * 0.5333333333333333D + rr_7[1] * 0.06666666666666667D + rr_7[2] * 0.4D;
rr_7[0] = rr_7[0] * 0.26666666666666666D + rr_7[1] * 0.6D + rr_7[2] * 0.13333333333333333D;
rr_7[1] = rr1_1_806;
rr_7[2] = rr1_2_835;
continue;}
/*for*/
MagicSquare.res[2][0] = rr_7[0];
MagicSquare.res[2][1] = rr_7[1];
MagicSquare.res[2][2] = rr_7[2];
return MagicSquare.res;
}
//-------------------------------------- 3 sec - JScp version 0.0.75
Результат суперкомпиляции для dim=3 (Chekin).
//-------------------------------------- 2 sec - postprocessing...
public static void main (final java.lang.String[] args_2)
{
int i_1390 = 0;
WHILE_1391:
while (i_1390 < MagicSquareTest.iprint) {
final long startTime_1396 = java.lang.System.currentTimeMillis() /*static*/;
final double[][] m2_1537 = new double[3][3];
final double[][] m3_1541 = new double[3][3];
final double[] m2_0_1534 = m2_1537[0];
m2_0_1534[0] = 0.26666666666666666D;
m2_0_1534[1] = 0.2D;
m2_0_1534[2] = 0.5333333333333333D;
final double[] m2_1_1535 = m2_1537[1];
m2_1_1535[0] = 0.6D;
m2_1_1535[1] = 0.3333333333333333D;
m2_1_1535[2] = 0.06666666666666667D;
final double[] m2_2_1536 = m2_1537[2];
m2_2_1536[0] = 0.13333333333333333D;
m2_2_1536[1] = 0.4666666666666667D;
m2_2_1536[2] = 0.4D;
double[][] m2_2257 = m2_1537;
double[][] m3_2256 = m3_1541;
int iter_2254 = 0;
while (iter_2254 < MagicSquareTest.iters) {
m3_2256[0][0] = 0.26666666666666666D * m2_2257[0][0] + 0.6D * m2_2257[0][1] + 0.13333333333333333D * m2_2257[0][2];
m3_2256[0][1] = 0.2D * m2_2257[0][0] + 0.3333333333333333D * m2_2257[0][1] + 0.4666666666666667D * m2_2257[0][2];
m3_2256[0][2] = 0.5333333333333333D * m2_2257[0][0] + 0.06666666666666667D * m2_2257[0][1] + 0.4D * m2_2257[0][2];
m3_2256[1][0] = 0.26666666666666666D * m2_2257[1][0] + 0.6D * m2_2257[1][1] + 0.13333333333333333D * m2_2257[1][2];
m3_2256[1][1] = 0.2D * m2_2257[1][0] + 0.3333333333333333D * m2_2257[1][1] + 0.4666666666666667D * m2_2257[1][2];
m3_2256[1][2] = 0.5333333333333333D * m2_2257[1][0] + 0.06666666666666667D * m2_2257[1][1] + 0.4D * m2_2257[1][2];
m3_2256[2][0] = 0.26666666666666666D * m2_2257[2][0] + 0.6D * m2_2257[2][1] + 0.13333333333333333D * m2_2257[2][2];
m3_2256[2][1] = 0.2D * m2_2257[2][0] + 0.3333333333333333D * m2_2257[2][1] + 0.4666666666666667D * m2_2257[2][2];
m3_2256[2][2] = 0.5333333333333333D * m2_2257[2][0] + 0.06666666666666667D * m2_2257[2][1] + 0.4D * m2_2257[2][2];
final int iter_2622 = iter_2254 + 1;
final double[][] m2_2632 = m2_2257;
m2_2257 = m3_2256;
m3_2256 = m2_2632;
iter_2254 = iter_2622;
continue;}
/*while*/
final long endTime_2634 = java.lang.System.currentTimeMillis() /*static*/;
if (m2_2257 == null) {
java.lang.System.out.println("Execution time: " + (double)(endTime_2634 - startTime_1396) * 0.001D) /*virtual*/;
i_1390++;
continue WHILE_1391;}
else {
java.lang.System.out.print(m2_2257[0][0] + " ") /*virtual*/;
java.lang.System.out.print(m2_2257[0][1] + " ") /*virtual*/;
java.lang.System.out.print(m2_2257[0][2] + " ") /*virtual*/;
java.lang.System.out.println() /*virtual*/;
java.lang.System.out.print(m2_2257[1][0] + " ") /*virtual*/;
java.lang.System.out.print(m2_2257[1][1] + " ") /*virtual*/;
java.lang.System.out.print(m2_2257[1][2] + " ") /*virtual*/;
java.lang.System.out.println() /*virtual*/;
java.lang.System.out.print(m2_2257[2][0] + " ") /*virtual*/;
java.lang.System.out.print(m2_2257[2][1] + " ") /*virtual*/;
java.lang.System.out.print(m2_2257[2][2] + " ") /*virtual*/;
java.lang.System.out.println() /*virtual*/;
java.lang.System.out.println("Execution time: " + (double)(endTime_2634 - startTime_1396) * 0.001D) /*virtual*/;
i_1390++;
continue WHILE_1391;}}
/*WHILE_1391*/
return;
}
//-------------------------------------- 5 sec - JScp version 0.0.75
Результат суперкомпиляции для dim=3 (Jama)
//-------------------------------------- 2 sec - postprocessing...
public static void main (final java.lang.String[] argv_2)
{
int i_931 = 1;
WHILE_932:
while (i_931 <= MagicSquareLimit.iters1) {
final long start_937 = java.lang.System.currentTimeMillis() /*static*/;
final Jama.Matrix X_1108 = new Jama.Matrix(3, 3);
//- this is X_1108 = new Jama.Matrix(3, 3)
// X_1108.m = 3;
// X_1108.n = 3;
// final double[][] A_1113 = new double[3][3];
// X_1108.A = A_1113;
final double[][] A_1113 = X_1108.A;
final double[] A_0_1110 = A_1113[0];
A_0_1110[0] = 0.5333333333333333D;
A_0_1110[1] = 0.06666666666666667D;
A_0_1110[2] = 0.4D;
final double[] A_1_1111 = A_1113[1];
A_1_1111[0] = 0.2D;
A_1_1111[1] = 0.3333333333333333D;
A_1_1111[2] = 0.4666666666666667D;
final double[] A_2_1112 = A_1113[2];
A_2_1112[0] = 0.26666666666666666D;
A_2_1112[1] = 0.6D;
A_2_1112[2] = 0.13333333333333333D;
Jama.Matrix C_1452 = X_1108;
int j_1451 = 1;
while (j_1451 <= MagicSquareLimit.iters) {
final Jama.Matrix X_1458 = new Jama.Matrix(3, 3);
//- this is X_1458 = new Jama.Matrix(3, 3)
// X_1458.m = 3;
// X_1458.n = 3;
// final double[][] A_1463 = new double[3][3];
// X_1458.A = A_1463;
final double[][] A_1463 = X_1458.A;
final double Bcolj_0_1471 = C_1452.A[0][0];
final double Bcolj_1_1478 = C_1452.A[1][0];
final double Bcolj_2_1485 = C_1452.A[2][0];
final double[] A_0_1460 = A_1463[0];
A_0_1460[0] = 0.5333333333333333D * Bcolj_0_1471 + 0.06666666666666667D * Bcolj_1_1478 + 0.4D * Bcolj_2_1485;
final double[] A_1_1461 = A_1463[1];
A_1_1461[0] = 0.2D * Bcolj_0_1471 + 0.3333333333333333D * Bcolj_1_1478 + 0.4666666666666667D * Bcolj_2_1485;
final double[] A_2_1462 = A_1463[2];
A_2_1462[0] = 0.26666666666666666D * Bcolj_0_1471 + 0.6D * Bcolj_1_1478 + 0.13333333333333333D * Bcolj_2_1485;
final double Bcolj_0_1593 = C_1452.A[0][1];
final double Bcolj_1_1600 = C_1452.A[1][1];
final double Bcolj_2_1607 = C_1452.A[2][1];
A_0_1460[1] = 0.5333333333333333D * Bcolj_0_1593 + 0.06666666666666667D * Bcolj_1_1600 + 0.4D * Bcolj_2_1607;
A_1_1461[1] = 0.2D * Bcolj_0_1593 + 0.3333333333333333D * Bcolj_1_1600 + 0.4666666666666667D * Bcolj_2_1607;
A_2_1462[1] = 0.26666666666666666D * Bcolj_0_1593 + 0.6D * Bcolj_1_1600 + 0.13333333333333333D * Bcolj_2_1607;
final double Bcolj_0_1715 = C_1452.A[0][2];
final double Bcolj_1_1722 = C_1452.A[1][2];
final double Bcolj_2_1729 = C_1452.A[2][2];
A_0_1460[2] = 0.5333333333333333D * Bcolj_0_1715 + 0.06666666666666667D * Bcolj_1_1722 + 0.4D * Bcolj_2_1729;
A_1_1461[2] = 0.2D * Bcolj_0_1715 + 0.3333333333333333D * Bcolj_1_1722 + 0.4666666666666667D * Bcolj_2_1729;
A_2_1462[2] = 0.26666666666666666D * Bcolj_0_1715 + 0.6D * Bcolj_1_1722 + 0.13333333333333333D * Bcolj_2_1729;
j_1451++;
C_1452 = X_1458;
continue;}
/*while*/
C_1452.print(2, 3) /*virtual*/;
final long end_1848 = java.lang.System.currentTimeMillis() /*static*/;
java.lang.System.out.println("Total time = " + (double)(end_1848 - start_937) * 0.001D) /*virtual*/;
i_931++;
continue;}
/*WHILE_932*/
return;
}
//-------------------------------------- 3 sec - JScp version 0.0.75