Пределы магических квадратов
Пусть M - магический квадрат, составленный из последовательных натуральных чисел, начиная с 1.
В этом примере рассматриваем магические квадраты нечетного размера, потому что используем простой способ построения такого квадрата.
Для пятерки способ построения показан ниже. Составляется таблица по-порядку по диагоналям, затем наружные числа сдвигаются на свободные места.
|
|
Пусть s - сумма чисел по строке, по столбцу или по диагонали.
Обозначим через A матрицу M / s
Например, для квадрата 3 на 3 получается матрица
| 4/15 | 9/15 | 2/15 |
| 3/15 | 5/15 | 7/17 |
| 8/15 | 1/15 | 6/15 |
Теперь рассматриваем предел при n стремящемся к бесконечности матрицы
A^n
Замечание 1. Если делить не на s, то в пределе получается либо 0, либо бесконечность. Доказательство - не очень простое упражнение по курсу алгебра для первого курса.
Замечание 2. В ответе получается матрица из одинаковых элементов, равных 1/dim (1/размер квадрата).
Предлагается программа на Java,
у которой параметром является размер квадрата dim,
и которая сначала строит магический квадрат согласно приведенной для пятерки схеме,
а затем вычисляется указанный предел путем многократного умножения матрицы A на себя.
Предел для двойной точности получается уже при 20 степени, но у меня сделан большой цикл с целью померить время исполнения.
При суперкомпиляции этой программы происходит следующее
- процесс построения магического квадрата полностью специализируется, то есть матрица получается как заданная, причем не массивом, а набором переменных.
- каждый элемент матрицы получается одним оператором Явы, а не несколькими, как было раньше.
- матрицы промежуточных вычислений почему-то превращаются в набор одномерных массивов. Если бы в набор чисел, то ускорение исполнения было бы еще больше.
- скорость исполнения повышается примерно в два раза.
В поддиректориях Result3, Result5, Result7 приведены результаты суперкомпиляции для указанных размеров квадратов.
Копию данного текста помещаю в приложение.
Если пример представляет интерес для других, то разрешаю разослать его более широкой аудитории без специального разрешения.
Привожу текст программы.
class MagicSquare {
public static final int dim=3; /* Dimension of matrix */
public static int iter;
public static double[][] a = new double[dim][dim];
public static void main (String args[])
{
long start = System.currentTimeMillis();
iter = 100000;
test();
long end = System.currentTimeMillis();
System.out.println("Total time = "+ (end-start)*0.001);
for (int i = 0; i < dim; i++)
{
for (int j = 0; j < dim; j++)
System.out.print(a[i][j] + " " );
System.out.println(" ");
};
System.out.println(" " );
}
public static void test()
{
double[][] magic = new double[dim][dim];
double[][] c = new double[dim][dim];
double[][] c1 = new double[dim][dim];
int x = (dim - 1)/2 + (dim + 1);
int y = -(dim - 1)/2 + (dim - 1);
int n = 1;
for (int i = 0; i < dim; i++)
{
x = x - (dim + 1);
y = y - (dim - 1);
for (int j = 0; j < dim; j++)
{
if (x >= dim) magic[x-dim][y] = n; else
if (x < 0 ) magic[x+dim][y] = n; else
if (y >= dim) magic[x][y-dim] = n; else
if (y < 0 ) magic[x][y+dim] = n; else
magic[x][y] = n;
n++;
x++;
y++;
}
}
int summa = dim * (dim*dim + 1) /2;
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++)
magic[i][j] = magic[i][j] / summa;
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++)
c[i][j] = 0.0;
for (int i = 0; i < dim; i++)
c[i][i] = 1.0;
for (int iiii = 0; iiii < iter; iiii++)
{
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++)
{
c1[i][j] = 0.0;
for (int k = 0; k < dim; k++)
c1[i][j] = c1[i][j] + c[i][k]*magic[k][j];
};
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++)
c[i][j] = c1[i][j];
};
for (int i = 0; i < dim; i++)
for (int j = 0; j < dim; j++)
a[i][j] = c[i][j];
}
}
Результат суперкомпиляции для тройки
public static void test () {
final double[][] daa9 = new double[3][3] ;
final double d96 = 4D / 15D;
final double d100 = 3D / 15D;
final double d104 = 8D / 15D;
final double d113 = 9D / 15D;
final double d117 = 5D / 15D;
final double d121 = 1D / 15D;
final double d130 = 2D / 15D;
final double d134 = 7D / 15D;
final double d138 = 6D / 15D;
final double[] da6 = daa9[0];
da6[0] = 0D;
da6[1] = 0D;
da6[2] = 0D;
final double[] da7 = daa9[1];
da7[0] = 0D;
da7[1] = 0D;
da7[2] = 0D;
final double[] da8 = daa9[2];
da8[0] = 0D;
da8[1] = 0D;
da8[2] = 0D;
da6[0] = 1D;
da7[1] = 1D;
da8[2] = 1D;
for (int iiii_397 = 0; iiii_397 < MagicSquare.iter; iiii_397++) {
final double d441 = da6[0] * d100 + da6[1] * d117 + da6[2] * d134;
final double d463 = da6[0] * d104 + da6[1] * d121 + da6[2] * d138;
final double d490 = da7[0] * d96 + da7[1] * d113 + da7[2] * d130;
final double d512 = da7[0] * d100 + da7[1] * d117 + da7[2] * d134;
final double d534 = da7[0] * d104 + da7[1] * d121 + da7[2] * d138;
final double d561 = da8[0] * d96 + da8[1] * d113 + da8[2] * d130;
final double d583 = da8[0] * d100 + da8[1] * d117 + da8[2] * d134;
final double d605 = da8[0] * d104 + da8[1] * d121 + da8[2] * d138;
da6[0] = da6[0] * d96 + da6[1] * d113 + da6[2] * d130;
da6[1] = d441;
da6[2] = d463;
da7[0] = d490;
da7[1] = d512;
da7[2] = d534;
da8[0] = d561;
da8[1] = d583;
da8[2] = d605;
continue;}
MagicSquare.a[0][0] = da6[0];
MagicSquare.a[0][1] = da6[1];
MagicSquare.a[0][2] = da6[2];
MagicSquare.a[1][0] = da7[0];
MagicSquare.a[1][1] = da7[1];
MagicSquare.a[1][2] = da7[2];
MagicSquare.a[2][0] = da8[0];
MagicSquare.a[2][1] = da8[1];
MagicSquare.a[2][2] = da8[2];
return;
}
//-----------------------------------------------------------