2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 67  След.
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.09.2013, 14:01 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Sorry I got confused with mod 5. I can find many solutions:

(Оффтоп)

Counts 1 11 13 12 12

(1,4,2,3,1,4,3),
(4,2,1,1,4,2,4),
(2,2,2,3,1,2,1),
(2,2,1,1,3,1,3),
(2,3,4,4,3,4,3),
(3,3,2,4,3,4,4),
(4,2,1,2,3,1,0)

(4,4,3,2,2,0,3),
(2,3,2,2,4,4,1),
(2,4,3,2,2,2,3),
(1,4,1,1,3,4,4),
(1,1,4,1,2,3,1),
(2,3,3,1,4,2,3),
(1,4,2,4,1,3,3)

(1,3,4,2,2,2,4),
(3,3,4,1,2,1,4),
(1,4,2,2,2,3,4),
(2,1,4,3,3,2,3),
(4,4,3,2,2,4,4),
(3,1,3,1,1,1,3),
(4,2,3,2,1,0,1)

(4,3,3,2,2,3,1),
(1,3,1,3,2,2,1),
(1,2,4,3,4,3,1),
(1,3,2,1,2,2,2),
(4,4,2,4,3,2,4),
(3,4,0,2,4,2,3),
(4,4,1,3,1,4,1)


Counts 1 11 12 14 11

(4,4,4,2,4,3,2),
(3,2,2,1,3,4,3),
(0,4,2,2,1,3,1),
(3,1,1,1,4,1,2),
(3,2,3,3,3,1,3),
(4,1,2,2,2,3,4),
(1,4,4,2,1,3,3)

(2,3,4,1,4,3,1),
(4,2,3,2,3,3,1),
(2,1,4,4,4,2,1),
(2,2,4,1,2,4,3),
(3,3,4,1,3,2,2),
(3,3,1,0,1,3,2),
(2,4,3,4,1,1,3)

(4,2,0,1,3,1,2),
(1,4,2,4,2,3,2),
(1,3,4,1,2,3,4),
(3,4,3,3,3,3,4),
(3,1,1,4,4,4,1),
(2,3,1,2,2,1,2),
(4,1,2,3,2,3,3)

(3,3,3,1,4,2,2),
(0,2,2,3,3,4,4),
(1,2,1,2,1,3,3),
(2,1,1,3,1,4,1),
(2,4,3,1,3,4,1),
(2,2,2,4,3,2,3),
(3,4,1,4,3,4,4)

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.09.2013, 14:23 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Вопрос не в том чтобы найти какие-то шаблоны, а в том чтобы найти их все (если придётся доказывать, что решения N7S733 не существует).

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.09.2013, 14:33 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #763185 писал(а):
Вопрос не в том чтобы найти какие-то шаблоны, а в том чтобы найти их все (если придётся доказывать, что решения N7S733 не существует).

Ну тогда я пас. Таких шаблонов будет миллионы!

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.09.2013, 14:42 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Шаблонов по модулю 3(6) всего 120.
Хотя, шаблонов по модулю 4 действительно больше миллиона (1612440 с учетом всех изоморфов, при фиксированном положении тройки).

К тому же, если решение N7S733 существует, то есть надежда обойтись меньшим числом шаблонов.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.09.2013, 17:08 


02/11/12
141

(Оффтоп)

I discovered the C runtime library for Linux uses a shared random number generator. There is a generator for each process, not for each thread. The code that I supplied will run poorly under Linux. The gcc compiler does generate code that is 40% faster than VS 2008.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение12.09.2013, 18:26 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Существует всего 48 типов четвёрок попарно ортогональных точных покрытий по модулю 4:

(Оффтоп)

(0430,0430),(0430,0430)
(0430,0430),(0430,0511)
(0430,0430),(0430,1240)
(0430,0430),(0430,1321)
(0430,0430),(0430,1402)
(0430,0430),(0430,2050)
(0430,0430),(0430,2131)
(0430,0430),(0430,2212)
(0430,0430),(0511,0511)
(0430,0430),(0511,1240)
(0430,0430),(0511,1321)
(0430,0430),(0511,1402)
(0430,0430),(0511,2050)
(0430,0430),(0511,2131)
(0430,0430),(1240,1240)
(0430,0430),(1240,1321)
(0430,0430),(1240,2050)
(0430,0430),(1240,2131)
(0430,0430),(1321,1321)
(0430,0430),(2050,2050)
(0430,0511),(0430,0511)
(0430,0511),(0430,1240)
(0430,0511),(0430,1321)
(0430,0511),(0430,1402)
(0430,0511),(0430,2050)
(0430,0511),(0430,2131)
(0430,0511),(0511,0511)
(0430,0511),(0511,1240)
(0430,0511),(1240,1240)
(0430,0511),(1240,1321)
(0430,0511),(1240,2050)
(0430,1240),(0430,1240)
(0430,1240),(0430,1321)
(0430,1240),(0430,2050)
(0430,1240),(0430,2131)
(0430,1240),(0511,1240)
(0430,1240),(0511,1321)
(0430,1240),(1240,1240)
(0430,1240),(1240,1321)
(0430,1240),(1240,2050)
(0430,1321),(0430,1321)
(0430,1321),(0511,0511)
(0430,1321),(0511,1240)
(0430,1321),(1240,1240)
(0430,2050),(0430,2050)
(0511,1240),(0511,1240)
(0511,1240),(1240,1240)
(1240,1240),(1240,1240)

Где шаблон точного покрытия, например, 1240 означает, что имеется 1 ряд типа "9" 2 ряда типа "13" и четыре ряда типа "17". См. http://dxdy.ru/post759141.html#p759141

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 08:07 
Заслуженный участник
Аватара пользователя


19/12/10
1546
mertz в сообщении #763223 писал(а):
I discovered the C runtime library for Linux uses a shared random number generator. There is a generator for each process, not for each thread. The code that I supplied will run poorly under Linux.

Можно попробовать вызывать генератор псевдослучайных чисел из функции оболочки. Которая будет подсчитывать число обращений к генератору и заново его инициализировать при необходимости.

Например, так:

Используется синтаксис C++
inline int random(){
        static int count;
        if(++count > RAND_MAX / 3){
                srand(clock());
                count = 0;
        }
        return rand();
}

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 14:45 


02/11/12
141
The problem is all threads use the same generator. This means a mutex has to be locked by each thread to get a single random number. Every thread has to wait in line. Locking mutex's is VERY expensive. With one thread I could do 78 searches per second. With 12 threads I was only getting 20 searches per second. Now that I replaced the rand() function, I am getting 640 searches per second with 12 threads.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 16:57 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Функция rand() определяет последовательность из, примерно, 30000 псевдослучайных чисел. При 640 обращениях в секунду, эта последовательность будет исчерпана менее чем за минуту. Далее начнётся повтор, что никак не отвечает представлению о случайной последовательности. Теоретически это может привести к зацикливанию программы на малой доле возможных вариантов.

Чтобы побороть эти негативные эффекты нужно периодически заново инициализировать генератор псевдослучайных чисел, причём в качестве "затравки" (seed) нужно брать действительно случайное число.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 17:01 
Заслуженный участник


31/12/05
1516
whitefox в сообщении #763524 писал(а):
Функция rand() определяет последовательность из, примерно, 30000 псевдослучайных чисел.
Боже мой, какой ужас! Это в какой библиотеке так?

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 17:11 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Имеется 42112968 шаблонов по модулю 4 с учётом всех изоморфов и при фиксированном положении тройки.

База данных занимает 5 гигабайт (650 мегабайт в сжатом виде).

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 17:48 


02/11/12
141
The random number generator in C was not designed for scientific research. See the Numerical Recipes in C book for alternatives with longer sequences and different properties. Using rand() % n is incorrect usage to get a number from 0 to n-1. Using rand() and using it incorrectly has lead to many erroneous papers being published.

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 18:23 
Заслуженный участник
Аватара пользователя


19/12/10
1546
tolstopuz в сообщении #763527 писал(а):
Боже мой, какой ужас! Это в какой библиотеке так?

Пользуюсь VC++ со стандартной библиотекой.

Насчёт 30000 это я сильно преуменьшил :-)
Каюсь, погорячился.

Пришлось залезть в код библиотеки чтобы выяснить вопрос.
Функция такая:
$$\mathrm X_{n+1}=(\mathrm X_n\cdot214013+2531011)\bmod 2^{32}$$$$\mathrm Y_{n+1}=(\mathrm X_{n+1}\gg16)\; \& \; 0\mathrm x7\mathrm{fff}$$

-- 13 сен 2013, 20:15 --

Более математическая запись$$\mathrm Y_{n+1}=\lfloor\mathrm X_{n+1}/2^{16}\rfloor\bmod2^{15}$$

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение13.09.2013, 19:30 
Заслуженный участник
Аватара пользователя


19/12/10
1546
whitefox в сообщении #763529 писал(а):
Имеется 42112968 шаблонов по модулю 4 с учётом всех изоморфов и при фиксированном положении тройки.

Опечатка, читать следует "по модулю 12".

 Профиль  
                  
 
 Re: Дьявольские магические квадраты из простых чисел
Сообщение14.09.2013, 14:30 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
whitefox в сообщении #763529 писал(а):
Имеется 42112968 шаблонов по модулю 4 с учётом всех изоморфов и при фиксированном положении тройки.

База данных занимает 5 гигабайт (650 мегабайт в сжатом виде).

Да моноговато. Интересно, а сколько требуется времени чтобы проверить один из шаблонов и возможно ли это вообще?

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1005 ]  На страницу Пред.  1 ... 55, 56, 57, 58, 59, 60, 61 ... 67  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group