The contest for the best optimization of the program

Message boards : News : The contest for the best optimization of the program
Message board moderation

To post messages, you must log in.

AuthorMessage
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2059 - Posted: 20 Jul 2018, 17:35:37 UTC
Last modified: 20 Jul 2018, 18:01:50 UTC

Dear participants of the project!

Probably, there are many programmers among you.

A contest is announced to the best optimization of program of search the orthogonal LS for a given LS of order 10.
This is a very important program!

The author of this program is colleague S. Belyaev.
The program was created and posted for general use on the Math Help Planet forum on February 29, 2016.
http://mathhelpplanet.com/viewtopic.php?p=261989#p261989

You can download the archive from the following link
https://yadi.sk/d/2sX-6d_Vphfsx

The source code of the program in archive is available.
https://yadi.sk/i/S417t0IpwnP6r
ID: 2059 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2060 - Posted: 20 Jul 2018, 17:49:04 UTC
Last modified: 20 Jul 2018, 17:59:36 UTC

I want to note that the excellent optimization of this program was made by the participant of the project team Harry White.
Optimization of Harry gave an acceleration of about 10 times.

You can download the version of the program Harry White from the following link
http://budshaw.ca/temp/lat02nmC.zip

The source code of the program is available.

But I think that there are still reserves for program optimization.
https://yadi.sk/i/S417t0IpwnP6r
ID: 2060 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2061 - Posted: 20 Jul 2018, 17:52:35 UTC
Last modified: 20 Jul 2018, 18:26:18 UTC

You can get acquainted with the transversals in the article: Ian M. Wanless "Transversals in Latin squares".
http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.244.6006&rank=17&q=Ian Wanless&osm=&ossid=

Abstract
A latin square of order n is an n×n array of n symbols in which each symbol occurs exactly once in each row and column. A transversal of such a square is a set of n entries such that no two entries share the same row, column or symbol. Transversals are closely related to the notions of complete mappings and orthomorphisms in (quasi)groups, and are fundamental to the concept of mutually orthogonal latin squares. Here we provide a brief survey of the literature on transversals. We cover (1) existence and enumeration results, (2) generalisations of transversals including partial transversals and plexes, (3) the special case when the latin square is a group table, (4) a connection with covering radii of sets of permutations. The survey includes a number of conjectures and open problems.

https://yadi.sk/i/S417t0IpwnP6r
ID: 2061 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2062 - Posted: 20 Jul 2018, 17:58:54 UTC
Last modified: 20 Jul 2018, 18:04:05 UTC

If you have any questions, please write

1) in this topic;
2) a personal message on the forum;
3) a personal message to e-mail natalimak1@yandex.ru
https://yadi.sk/i/S417t0IpwnP6r
ID: 2062 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2064 - Posted: 20 Jul 2018, 18:20:56 UTC

See also the topic "On transversals of Latin squares"
https://boinc.progger.info/odlk/forum_thread.php?id=47

In the topic there are several specific examples with illustrations.
https://yadi.sk/i/S417t0IpwnP6r
ID: 2064 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2065 - Posted: 20 Jul 2018, 18:37:21 UTC
Last modified: 20 Jul 2018, 19:00:22 UTC

A little information about working with the program Harry White.

All source LSs must be written to the inp.txt file
This is the default input file.

All orthogonal LSs will be written to the file Ort.txt
With each new program run, the Ort.txt file is cleared.

The console displays progress (+2048 LS).
https://yadi.sk/i/S417t0IpwnP6r
ID: 2065 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2068 - Posted: 21 Jul 2018, 10:47:46 UTC
Last modified: 21 Jul 2018, 10:59:00 UTC

Test

Unfortunately, the original program by S. Belyaev only accepts one LS for processing.
Therefore, I test one LS

0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
5 6 1 2 9 0 7 8 3 4
7 0 5 6 8 1 3 4 9 2
6 4 9 1 2 7 8 0 5 3
9 5 6 8 7 2 1 3 4 0
2 3 4 9 1 8 0 5 6 7
4 9 8 7 6 3 2 1 0 5
8 7 3 5 0 9 4 6 2 1
3 8 7 0 5 4 9 2 1 6

This is the protocol of the program by S. Belyaev

Name:a.txt
max=500
0 1 2 3 4 5 6 7 8 9
1 2 0 4 3 6 5 9 7 8
5 6 1 2 9 0 7 8 3 4
7 0 5 6 8 1 3 4 9 2
6 4 9 1 2 7 8 0 5 3
9 5 6 8 7 2 1 3 4 0
2 3 4 9 1 8 0 5 6 7
4 9 8 7 6 3 2 1 0 5
8 7 3 5 0 9 4 6 2 1
3 8 7 0 5 4 9 2 1 6
144 134 138 162 142 142 162 138 134 144 1440
100 39 244
200 87 194
300 126 217
Число найденных квадратов=336

The program worked a little more than 3 minutes.

This is the protocol of the program by Harry White

elapsed time 0:00:05

Total LS: 1, found: 336, min: 336, max: 336, avg: 336.00

Press a key to close the console

The program worked for 5 seconds.

For a given LS, 336 orthogonal LSs were found.

The processing time, of course, depends on LS.
https://yadi.sk/i/S417t0IpwnP6r
ID: 2068 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2082 - Posted: 23 Jul 2018, 16:05:20 UTC
Last modified: 23 Jul 2018, 16:11:37 UTC

I'll show you another test.

The original squares are 500 DLS. All these DLS have orthogonal DLS and LS.

First, the program by Belyshev ortogon(u) works.
This program finds only orthogonal DLSs.
The program operation protocol

Проверка ДЛК10 на марьяжность (ОДЛК)

Введено ДЛК:  500
Найдено ОДЛК: 500
Время работы: 1.747 сек

Here 576 orthogonal DLSs are found.
Note the execution time of the program: 1.747 sec.

Now we look at these DLS as LS.
The program by Harry White is working.

elapsed time 0:03:24

Total LS: 500, found: 2522, min: 1, max: 256, avg: 5.04

Running time 3 min. 24 sec.
2522 orthogonal LSs are found here, and 576 DLSs are included.

It is clear that the search for orthogonal DLS requires less time.
However, the time difference is too great.
Hence I draw a conclusion: there is a reserve for the optimization of the Harry White program.
Perhaps this is an erroneous conclusion.

PS. Belyshev published the program ortogon(u) for general use.
Look, for example, here
http://forum.boinc.ru/default.aspx?g=posts&m=89712#post89712

The source code of the program is available.
https://yadi.sk/i/S417t0IpwnP6r
ID: 2082 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
mmonnin

Send message
Joined: 29 May 17
Posts: 3
Credit: 1,029,836
RAC: 31,782
Message 2093 - Posted: 24 Jul 2018, 21:51:42 UTC

Is there going to be a new app for this project? Or an app to try with app_info?
ID: 2093 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Natalia Makarova
Project scientist
Avatar

Send message
Joined: 6 Apr 17
Posts: 1901
Credit: 0
RAC: 0
Message 2095 - Posted: 25 Jul 2018, 4:35:14 UTC - in response to Message 2093.  

Is there going to be a new app for this project? Or an app to try with app_info?

Not yet planned.

But if you are ready to help us ... :)
https://yadi.sk/i/S417t0IpwnP6r
ID: 2095 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote

Message boards : News : The contest for the best optimization of the program


©2018 (C) Progger