Пределы магических квадратов

 

      Letter.htm              - избранные места из переписки,

      MagicSquare.java - текст исходной программы,

      Result3.java          - результат суперкомпиляции при dim=3,

      MagicSquare.zip   - результаты всех суперкомпиляций.

 

     Пусть  M - магический квадрат, составленный из последовательных натуральных чисел, начиная с 1.

     В этом примере рассматриваем магические квадраты нечетного размера, потому что используем простой способ построения такого квадрата.

    Для пятерки способ построения показан ниже. Составляется таблица по-порядку по диагоналям, затем наружные числа сдвигаются на свободные места.

 

        1        
      6   2      
    11   7   3    
  16   12   8   4  
21   17   13   9   5
  22   18   14   10  
    23   19   15    
      24   20      
        25        

 
11 24 7 20 3
4 12 25 8 16
17 5 13 21 9
10 18 1 14 22
23 6 19 2 15

 

 

     Пусть 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  стремящемся к бесконечности матрицы 

     A^n.

     Замечание 1. Если делить не на s, то в пределе получается либо 0, либо бесконечность. Доказательство - не очень простое упражнение по курсу алгебра для первого курса.

     Замечание 2. В ответе получается матрица из одинаковых элементов, равных 1/dim (1/размер квадрата).

     Предлагается программа на Java,

     - параметром которой является размер квадрата dim (переменная dim расположена в начале программы MagicSquare.java - я ее менял вручную для каждой суперкомпиляции и каждого пуска),

     - которая сначала строит магический квадрат согласно приведенной для пятерки схеме,

     - затем вычисляется указанный предел путем многократного умножения матрицы A на себя.

     Предел для двойной точности получается уже при 20-ой степени, но у меня сделан большой цикл с целью измерить время исполнения.

     При суперкомпиляции этой программы происходит следующее

      - процесс построения магического квадрата полностью специализируется, то есть матрица получается как заданная, причем не массивом, а набором переменных.

      - каждый элемент матрицы получается одним оператором Явы, а не несколькими, как было раньше.

      - матрицы промежуточных вычислений почему-то превращаются в набор одномерных массивов. Если бы в набор чисел, то ускорение исполнения было бы еще больше.

      - скорость исполнения повышается примерно в четыре раза.

     В поддиректориях Result3, Result5, Result7, Result9, Result11, Result13 MagicSquare.zip приведены результаты суперкомпиляции для указанных размеров квадратов.

   Привожу времена исполнения исходной программы и программы после суперкомпиляции (умножение в цикле - 100 000 раз). В первой таблице используется вариант счета без параметра  -Xint 

dim время до суперкомпиляции время после суперкомпиляции коэффицент ускорения  
3  0.14 0.3 4.6  
5  0.67 0.12 5.5  
7  1.6 0.29 5.4  
9  3.16 0.6 5.3  
11  5.5 1.1 5.0  
13 8.8 30.5 0.3  
15  14.0 45.0 0.3  

 

      Во второй таблице используется параметр -Xint

dim время до суперкомпиляции время после суперкомпиляции коэффицент ускорения  
3  1.810 0.575  3.14  
5  7.185 2.245  3.20  
7  18.220 5.660  3.22  
9  37.30 10.50  3.55  
11  66.7 18.50  3.60  
13 108.2 28.94  3.74  
15  163.7 43.20  3.79  

 

     Обсуждение полученных чисел приведено в избранной переписке по этому поводу Letter.htm.