Perfect Cuboid, Задача про цілочисельний паралелепіпед Налаштування

[x3mEn]

Раціональний кубоїд (або цілочисельна цеглина, або ідеальний кубоїд) — прямокутний паралелепіпед,
у якого всі сім основних величин (три ребра, три лицьових діагоналі і просторова діагональ) є цілими числами, є однією з відкритих математичних проблем
Інакше кажучи, раціональний кубоїд — цілочисельне рішення системи діофантових рівнянь.

Досі невідомо, чи існує такий паралелепіпед. Комп'ютерний перебір не знайшов жодної цілочисельної цеглини з ребрами до 10^11.
Втім, знайдено кілька «майже цілочисельних» паралелепіпедів, у яких цілочисельними є всі величини, крім однієї:
— одна з лицевих діагоналей не ціле число.
, — одне з ребер не ціле число.
Велика кількість паралелепіпедів Ейлера (з нецілою просторовою діагоналлю, див. нижче).
Косокутні паралелепіпеди, у яких всі сім величин цілі. При цьому досить одного непрямого кута.
У 2005 році тбіліський студент Лаша Маргішвілі запропонував доведення, що цілочисельний кубоід не існує — однак на 2009 рік робота так і не пройшла перевірку незалежними вченими.

Паралелепіпед Ейлера
Прямокутний паралелепіпед, у якого цілочисельні тільки ребра і лицьові діагоналі, називається ейлеровим.
Найменший з паралелепіпедів Ейлера — (240, 117, 44), з лицьовими діагоналями 267, 244 і 125.
Ще кілька паралелепіпедів Ейлера:
(275, 252, 240),
(693, 480, 140),
(720, 132, 85),
(792, 231, 160).
Ейлер описав два сімейства таких паралелепіпедів (звідси назва). Втім, повного опису всіх паралелепіпедів Ейлера також немає.
Відомі такі вимоги до ейлерового паралелепіпеда (а значить, і до цілочисельної цеглини):
- Одне ребро ділиться на 4, друге ділиться на 16, третє непарне (якщо, звичайно, він примітивний — тобто, НСД (a, b, c) = 1).
- Одне ребро ділиться на 3 і ще одне — на 9.
- Одне ребро ділиться на 5.
- Одне ребро ділиться на 11.
- Одне ребро ділиться на 19.
- Одне ребро або просторова діагональ діляться на 13.
- Одне ребро, лицьова або просторова діагональ діляться на 17.
- Одне ребро, лицьова або просторова діагональ діляться на 29.
- Одне ребро, лицьова або просторова діагональ діляться на 37.
- Добуток ребер, лицьових і просторової діагоналі має ділитися на 2^8·3^4·5^3·7·11·13·17·19·29·37

Це повідомлення відредагував x3mEn: Oct 22 2013, 09:16

[molo]

Дякую, x3mEn
Хороша робота!

Тільки ще би маленького мануала для усіх

Щодо GPU версії, то звичайно потрібно, але почати можна би було і зі звичайної CPU версії для Windows OS. Потім неодмінно покрити інші.

Клієнтська частина виглядає не дуже складною (простий перебір, щоб 100% перевірити) + комунікація з серверною частиною (відсилка результатів, отримання задачі, оновлення клієнта) - для початку, здається досить.

Я так, розумію, питання щодо серверної частини досі відкрите - чи будемо використовувати Boinc чи інший аналог (точно і не знаю чи щось нове з'явилось).Іншим варіантом є розробка своєї серверної частини (Java або .NET, maybe PHP + database MySQL).

Чим раніше ми би випустили робочу версію (клієнт-сервер + реєстрація користувачів + статистика) тим потенційно більше би людей ми могли б найти для проекту. Бо більшість серйозних людей навіть не звернуть увагу, коли у нас крім балачок нічого ще нема.

Як тільки буде визначено з серверною частиною, то, гадаю, ми могли б шукати бажаючих допомогти і формувати активну частину проекту (внутрішні обговорення, SVN, wiki, TODOs etc.)

[x3mEn]

Дякую, x3mEn
Хороша робота!

Тільки ще би маленького мануала для усіх

Мануал до тестової програми?

Ну, по-перше перебір ведеться серед діагоналей, що утворюються різними комбінаціями добутків простих чисел виду 4k+1 у різних ступенях.
У віконці Current position можна побачити поточну позицію перебору. У таблиці - фактори і їх ступені, в полі Diagonal - відповідне значення діагоналі.
Squares - кількість різних розкладань числа Diagonal на суму двох квадратів.
До речі, перевірити розкладання можна, якщо поставити галочку Save squares to .txt files, тоді в директорії, звідки зпускалась програма, будуть створюватись файли з назвою = значенню Diagonal, а всередині через кому будуть перелічені всі пари розкладів.
Кількість розкладів можна розрахувати за відомою формулою.
Власне, я дуже втішаюсь, що кількість розкладів, що я отримую за алгоритмом, збігається із значенням за формулою.
Наприклад:
5**7
13**1
17**2
29**2
37**2
41**1
53**1
Тобто діагональ = 734328519856953125
Кількість розкладів: [((2*7+1)(2*1+1)(2*2+1)(2*2+1)(2*2+1)(2*1+1)(2*1+1)+1)/2] = [(15*3*5*5*5*3*3+1)/2] = 25313

Для кожної діагоналі на основі її розкладу на суму квадратів відбувається пошук усіх інших 6 вимірів (3 ребра, 3 лицьові діагоналі).
Розділ Last Checked Candidate власне створений для того, щоб візулізувати пошук.
Для кожної діагоналі кількість переборів має порядок Q^2, де Q - кількість розкладів.
У найгіршому випадку = (Q^2)/2, у найкращому - 0.
Власне, це найкращий порядок, якого я досяг. За рахунок певних оптимізацій, таких як, наприклад:
- попередня перевірка, що 2 ребра не можуть бути одночасно непарними числами,
- для обраної лицьової діагоналі F перебір одного з ребер тільки до значення sqrt(F) і таке інше
кількість переборів ще скорочується, може десь в 2-3 рази.

Settings: встановлення початкової і кінцевої позицій перебору.
Manual - вручну, інакше - з файлу.
Метод вручну обмежується встановленням одного значення фактору і його ступеню.
Через файл початкову і кінцеву позицію можна встановити точніше.
У будь-якому випадку під час обрахунку у файлі зберігається остання позиція.
Власне, за змовченням встановлено метод "Через файл", разом з exe я додав task64.txt з останною позицією, до якої я дорахував на той момент.
Якщо обрати метод Manual, тоді файл буде створено самостійно, пізніше за великого бажання можна самостійно змінити початкові і кінцеві позиції через будь-який текстовий редактор.
Параметр "кінцева позиція" є необов'язковим, якщо спочатку не вказано, перебір буде тривати, поки не перебере все до кінця.
Refresh Frequence (sec) я створив для того випадку, якщо перебір відбувається вже надто швидко і візуалізація гальмує сам перебір.
Це було корисно, наприклад, коли я створив версію програми, що відтворює пошук лише серед 32 бітних цілих. Тоді перебір відбувається аж надто швидко.
Якщо цікаво, можу скомпілювати 32 бітну версію і викласти сюди. В мене є враження, що 32-бітний перебір взагалі можна зробити силами однієї машини.
В мене, правда, є певні сумніви щодо швидкості пошуку простих чисел у високих діапазонах чисел, можливо це свого часу стане серйозним гальмом.
Але, принаймні за пігодинки в 32-бітній версії я перебрав всі варіанти факторів аж десь до 70000. Для 32 біт переломним є число 46000, після чого кількість варіантів розкладів тільки падає.
А основне гальмо в цьому переборі це не абсолютне значення діагоналі, а кількість розкладів цього числа на суми квадратів.

В розділі Statistics показується загальна статистика процесу від початку запуску.
Найцікавішими є такі значення:
Diagonals checked - кількість перебраних діагоналей
Avg Time per G (sec) - середня тривалість перевірки однієї діагоналі
Avg Squares per G - середня кількість розкладів діагоналі на суму двох квадратів