Версія даної теми для друку

Натисніть сюди для перегляду даної теми у оригінальному форматі

Розподілені обчислення в Україні _ Інші українські проекти _ Perfect Cuboid

Автор: x3mEn Aug 6 2010, 00:01



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

Досі невідомо, чи існує такий паралелепіпед. Комп'ютерний перебір не знайшов жодної цілочисельної цеглини з ребрами до 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

Автор: Rilian Aug 6 2010, 00:47

я эту задачу уже рассматривал, не зря тестовый боинк висел у нас на поддомене cuboid smile.gif)

потом почитал новости по теме, там уже перебрали немеряное кол-во чисел, и для больших ничего не нашли

Автор: x3mEn Aug 6 2010, 01:16

Є одна дуже цікава задача мого дитинства - задача про "цілочисельний паралепіпед".
Прямокутний паралепіпед, в якого є 7 невідомих:
3 ребра, 3 його лицьові діагоналі, 1 просторова діагональ.
Задача полягає, чи існує такий паралепіпед, в якого всі 7 вказаних змінних є цілими числами?
Задача еквівалента вирішенню системи діафантових рівнянь:
a2+b2=d2
a2+c2=e2
b2+c2=f2
b2+e2=g2
Станом на 1988 задача не була вирішена, як і не було доведено, що рішення не існує.

Пропоную організувати прямий розумний перебір.
Беремо 3 натуральних числа a, b и c, такі, що
a < b < c,
a+1 <= b <= (a^2-4)/4,
b+1 < с <= (a^2-1)/2
Для кожного а організовуємо 2 вкладені цикли:


for b = (a + 1) to int((a^2 - 4)/4)
if checkab(a, b) <> 0 then
d = checkz(a, b)
if d <> 0 then
for c = (b + 1) to int((a^2 - 1)/2)
if checkabc(a, b, c) <> 0 then
e = checkz(a, c)
if e <> 0 then
f = checkz(b, c)
if f <>0 then
g = checkz(b, e)
if g <> 0 then addresult(a, b, c, d, e, f, g)
endif
endif
endif
endif
endfor
endif
endif
endfor


В функції checkab(a, b) перевіряємо, що a і b не є одночасно непарними.

В функції checkabc(a, b, c) перевіряємо, що:
1. серед a, b і c тільки одне число непарне.
2. одне з чисел ділить на 4, а одне з інших - на 16
3. одне з чисел ділить на 3, а одне з інших - на 9
4. одне з чисел ділить на 5
5. одне з чисел ділить на 7
6. одне з чисел ділить на 9
7. одне з чисел ділить на 11
8. одне з чисел ділить на 19

В функції checkz(x, y) перевіряємо, чи існує натуральне z, таке, що
x2+y2=z2. Якщо не існує, повертаємо 0. Існує - звісно повертаємо z.

Тут є декілька думок:
Перша - перевірка останньої цифри суми квадратів.
Оскільки остання цифра квадрату може бути:
1 - 1
2 - 4
3 - 9
4 - 6
5 - 5
6 - 6
7 - 9
8 - 4
9 - 1
0 - 0
Отже квадрат може закінчуватись тільки на (0, 1, 4, 5, 6, 9), а сума квадратів може приймати значення з імовірностями:
0 - 16,67%
1 - 11,11%
2 - 5,56%
3 - 5,56%
4 - 11,11%
5 - 16,67%
6 - 11,11%
7 - 5,56%
8 - 5,56%
9 - 11,11%
Отже, ще до будь-яких піднесень до квадратів можна одразу відкинути 2/9 всіх пар чисел.
Ще один випадок, що можна швиденько відкинути: якщо остання цифра суми квадратів закінчується на 0, шуканий квадрат має закінчуватись на 00.
Задля цієї перевірки достатньо перевірити:
k = x rem 100
l = y rem 100
тобто k і l - числа, складені з двох останніх цифр x та y відповідно.
Тоді треба перевірити, що
(k^2 + 2k + l^2 + 2l) rem 100 = 0

Ну а далі треба шукати швидкі методи пошуку натуральних коренів.

Поки що все.

P.S.: Процедура addresult() зберігає результат і виплачує премію в 1000 дол. smile.gif

P.P.S.: Почитав пости назад у часі... ідея з пошуком "ідеального кубоіда" вже була, тільки що brute force без особливих оптимізацій.
Тому вибачаюсь за повтор. Витирати посилання не буду, оскільки приклав багато зусиль, щоб все викласти, що в голові було.

P.P.P.S: якщо є обчислювальні обмеження з точним обрахунком квадрату числа (можу припустити, що так воно і є), можу запропонувати організацію вкладених циклів в оберненому порядку від більшого числа до меншого.
Тобто спочатку фіксуємо найбільше з ребер c, потім організовуємо цикл вниз від (с-1) до int(sqrt(4c+4)) для числа b, ну а потім цикл вниз від (b-1) до int(sqrt(2c+1)) для найменшого з ребер a.
Ну а все інше - як викладено вище.

На вхід подається 2 числа, m і n:
m <= c <= n

for c = m to n
for b = (с - 1) downto int(sqrt(4c + 4))
if checkab(b, c) <> 0 then
f = checkz(b, c)
if f <> 0 then
for a = (b - 1) downto int(sqrt(2c+1))
if checkabc(a, b, c) <> 0 then
d = checkz(a, b)
if d <> 0 then
e = checkz(a, c)
if e <>0 then
g = checkz(b, e)
if g <> 0 then addresult(a, b, c, d, e, f, g)
endif
endif
endif
endif
endfor
endif
endif
endfor
endfor

Числа m і n визначають, як вся задача розрізається на окремі завдання.

Вартість завдання можна визначати, наприклад:
1. за кількістю заходів в checkz
2. за кількістю нетривіальних перевірок в середині checkz (алгоритм якої ще треба придумати).
3. за кількістю заходів в checkab
4. за кількістю заходів в checkabc
Всі 4 числа мають різну вагу, тому що складність виконання різна.

Валідність розрахунку можна визначати теж за цим показником.

(Rilian @ Aug 6 2010, 01:47) *

я эту задачу уже рассматривал, не зря тестовый боинк висел у нас на поддомене cuboid smile.gif)

потом почитал новости по теме, там уже перебрали немеряное кол-во чисел, и для больших ничего не нашли


А в мене з дитинства залишилась віра, що, якшо знайшли майже ідеальний паралелепіпед (6 з 7 - натуральні),
то має бути і повністю ідеальний цеглоїд. smile.gif Всі 7 величин! 7 - це Боже число. Як знайдемо, то кінець світу настане! smile.gif

Автор: x3mEn Aug 28 2010, 19:44

Ситуація така: я задачу не залишив, за останній місяць перечитав достатньо багато літератури з тематики "ідеального кубоїда"
і врешті написав на Delphi 7 LE тестову програму.
Ось основна література, на якій базується мій "розумний" перебір:
http://kingmatematikoff.narod.ru/29th.htm
http://kingmatematikoff.narod.ru/kv0399senderov.pdf

На Вікіпедії вказано, що якщо такий кубоїд існує, найменше ребро має бути більшим за 100млн.
100млн. - це, очевидь, обмеження 32-біт.
Тому задача дуже амбітна: перебрати всі підходящі просторові діагоналі для всіх 64-бітних цілих чисел і або таки знайти кубоїд, або довести, що його не існує і серед 64-бітних цілих чисел.
Реально це, чи ні - ви самі можете оцінити, виходячи із швидкості перебору на одному ядрі CPU (див. вклад.)
Алгоритм пошуку дуже відрізняється від того, що я описав навіть місяць назад.
Якщо коротко: я перейшов від перебору ребер до перебору просторових діагоналей.
Просторова діагональ може бути тільки числом, що розкладається на прості числа виду 4k+1.

Наступна задача - написати GPU-аналог.
Виходячи з того, яка швидкість перебору з використанням cuda-клієнта для Collatz Conjecture,
мені здається, що на GPU подібні перебори набагато ефективніше працюватимуть.
Якщо є специ, що мають досвід роботи з CUDA SDK, відгукніться, будь ласка.


Приєднані файл(и)
Приєднаний файл  pcuboid.zip ( 285.04Кб ) Кількість викачувань: 562

Автор: molo Aug 30 2010, 07:06

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

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

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

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

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

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

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

Автор: x3mEn Aug 30 2010, 10:46

(molo @ Aug 30 2010, 08:06) *

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

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


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

Ну, по-перше перебір ведеться серед діагоналей, що утворюються різними комбінаціями добутків простих чисел виду 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. smile.gif
Власне, це найкращий порядок, якого я досяг. За рахунок певних оптимізацій, таких як, наприклад:
- попередня перевірка, що 2 ребра не можуть бути одночасно непарними числами,
- для обраної лицьової діагоналі F перебір одного з ребер тільки до значення sqrt(F) і таке інше
кількість переборів ще скорочується, може десь в 2-3 рази.

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

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

Автор: x3mEn Sep 1 2010, 11:47

Нова версія тестової програми.

Зміни:
+ Нова статистика, підраховується кількість циклів, ASPG / AGPS - Average seconds per G (diagonal) / Average G (diagonals) per second
+ Змінено формат збереження тестових завдань, тепер у вигляді Ini файла. За рахунок цього дискові опреації відбуваються за таймером.
+ Додано збереження проміжного результату статистики (дата початку, тривалість, кількість оброблених діагоналей та ін.)
+ Пофіксені баги, які могли б "вістрилити" на числах більших за 32 біти
+ Додано кнопку Reset, аби можна було перервати виконання з обнуленням всіх даних
+ Змінено логіку визначення кінця завдання. Тепер, якщо вказано, що Finish position, припустимо, 53**1, це значить, що 53**1 буде останнім числом завдання

У самому алгоритмі, нажаль, ніяких змін не відбулося. sad.gif
Останнім часом не можу придумати, як ще можна було б зменшити кількість переборів.

Вибачте, що викладаю ехе-шник. По-перше не у всіх є Delphi, щоб відкомпілювати, а по-друге, сам алгоритм певним чином складає для мене певну цінність.
Я поділюся сорсами тільки якщо знайду того, хто допоможе написати або GPU аналог, або клієнта і сервер, нехай навіть для CPU.


Приєднані файл(и)
Приєднаний файл  pcuboid64.zip ( 290.08Кб ) Кількість викачувань: 513

Автор: molo Jan 28 2011, 08:06

Привіт Усім!

Дякуючи хорошим ідеям про ‘наш проект’ - раді повідомити, про початок розробки проекту по пошуку ідеального паралелепіпеда - http://perfectcuboid.com/

Якщо є бажання і час - ласкаво просимо до проекту. Роботи вистачить на усіх smile.gif

Короткий список активностей:
1. Розробка/обговорення алгоритму обчислення
2. Тестування
3. Веб дизайн
4. Адмінування
5. Підтримка сайту
6. Розробка клієнтської частини
7. Розробка серверної частини
8. …

Контакти:
http://perfectcuboid.com/contact-us
team@perfectcuboid.com

Першочергові кроки:
1. Початкова інфраструктура серверної частини – в процесі
2. Фіналізувати початковий API для комунікації серверної і клієнтської частини – в процесі
3. Розробка клієнтської частини для Windows

Якщо адміністрація distributed.org.ua дозволить – раді продовжити обговорення в даній темі, або новоствореній темі.

Автор: re_SET Jan 28 2011, 10:02

molo, Насколько сложная задача в плане выч. мощностей?

Автор: molo Jan 28 2011, 11:41

(re_SET @ Jan 28 2011, 10:02) *

molo, Насколько сложная задача в плане выч. мощностей?


Хороше питання, re_SET!

Передусім об’єм обрахунків буде залежати лід алгоритму. x3mEn уже зробив певні дослідження в цьому напрямку.

Пригадую я вже робив заміри на десктопному процесорі (див. вище по темі)
Повторивши результати:

1.6GHz processor - 1 ядро (laptop)
10^9 комбінацій ~ 5хв – простий перебір

Щоб обрахувати кубоід з 10^6 ( 1-1,000,000):
10^6 * 10^6 * 10^6 = 10^18 комбінацій
10^18 комбінацій / (10^9 комб/5хв) = 10^9 циклів по 5хв = 5*10^9 хв = 83,333,333 год = 3,472,222 доби = 9,512 роки

Переведемо на 1GHz:

Щоб обрахувати кубоід з 10^6 на 1GHz (10^18 комбінацій):
9,512 * 1.6 = 15,219 роки


Щоб обрахувати кубоід з 10^11 на 1GHz (10^33 комбінацій) - повторити теперішні обрахунки:
10^33 / 10^18 = 10^15 циклів по 15,219 роки
10^15 * 15,219 роки ~ 15 * 10^15 років

Так як навіть зараз процесори мають більші потужності ~ 2*2.5 = 5GHz. Не кажучи про 6-ти ядерні від AMD – 3.5GHz * 6core = 21GHz. Тому з часом швидкість обрахунків буде тільки зростати в рази.

Основною складовою буде, як завжди, в розподільних обчисленнях, буде кількість учасників.

Виглядає досить амбітно і довготривало.

Автор: Rilian Jan 28 2011, 12:43

molo, мне кажется я видел в интернете инфу что какие-то китайцы вычислили до 10^18 все кубоиды и идеального не нашли...

Автор: molo Jan 28 2011, 19:22

(Rilian @ Jan 28 2011, 12:43) *

molo, мне кажется я видел в интернете инфу что какие-то китайцы вычислили до 10^18 все кубоиды и идеального не нашли...


Тоді хочеться вірити, що початкові підрахунки в мільярди років не зовсім вірні і ми зможемо обрахувати все значно швидше smile.gif

Основна ідея проекту - відкритість результатів, доступних 24/7. Отже кожен зможе слідкувати за статусом.

Автор: x3mEn Jan 28 2011, 19:31

(molo @ Jan 28 2011, 11:41) *

(re_SET @ Jan 28 2011, 10:02) *

molo, Насколько сложная задача в плане выч. мощностей?

Щоб обрахувати кубоід з 10^6 ( 1-1,000,000):
10^6 * 10^6 * 10^6 = 10^18 комбінацій
10^18 комбінацій / (10^9 комб/5хв) = 10^9 циклів по 5хв = 5*10^9 хв = 83,333,333 год = 3,472,222 доби = 9,512 роки


В дійсності і кількість варіантів і оцінка тривалості зовсім інші.
За моїм алгоритмов задля того, щоб підрахувати кількість варіантів, які треба перебрати, треба зробити наступне:
1) знайти всі прості числа виду 4k+1 в діапазоні від 5 до (2^64)/(5^2) (якщо треба, можу пояснити, чому саме до цього числа)
2) із всіх цих простих чисел утворити всі їх комбінації такі, що П p(i)^k(p) < 2^64, де p(i) - просте число, k(p) - ступінь, до якої підноситься це просте число.

Це ми отримаємо кількість всіх діагоналей-кандидатів.
Діагональ-кандидат дорівнює, відповідно П p(i)^k(p)
Потім для кожної діагоналі треба знайти всі розклади на суму квадратів.
Кількість таких розкладів вираховується за формулою П (k(p)+1)
Час перевірки однієї діагоналі залежить від кількості різних розкладів приблизно у кубічній залежності.

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

Хто візьметься зробити хоча б пункт #1, порахувати кількість простих чисел виду 4k+1 в діапазоні від 5 до (2^64)(5^2) ? icon_trollface.png
Щоб зрозуміти, цю всю масу простих чисел реально зібрати на одній машині для нарізки завдань, чи для цього ще треба буде організувати підпроект?

Автор: molo Jan 28 2011, 20:48

(x3mEn @ Jan 28 2011, 19:31) *



Хто візьметься зробити хоча б пункт #1, порахувати кількість простих чисел виду 4k+1 в діапазоні від 5 до (2^64)/5/13 ? icon_trollface.png
Щоб зрозуміти, цю всю масу простих чисел реально зібрати на одній машині для нарізки завдань, чи для цього ще треба буде організувати підпроект?


Це може бути першою стадією того ж проекту.

З іншого боку підбір діагоналей може бути здійнений на тому ж клієнті.
Для прикладу - пакет 100k-200k

спочатку клієнт перебирає діагоналі в заданому діапазоні, а потім веде розрахунки по вибраним діагонаям.

Автор: x3mEn Jan 28 2011, 22:35

Саме так і працює моя програма.
Поясню на прикладі, як відбувається перебір діагоналей.

Перші члени послідовності простих чисел виду 4k+1 наступні:
5, 13, 17, 29, 37, 41...
Беремо перший елемент 5. Це і є перша діагональ.
Друга діагональ - це 5^2, третя - 5^3 і т.д. аж до 5^27 (5^28 вже більше 2^64)
Тепер ступінь 5 обнулюємо, беремо наступне просте - 13. Це наступна діагональ.
Наступна діагональ - 13*5, наступна - 13*5^2 і т.д. аж до 13*5^25.
Далі беремо 13^2 і утворюємо діагональ добутком з усіма ступенями 5, аж до (13^2)*(5^24).

Ну, я думаю зрозуміло.

Проблема полягає тільки у тому, що набір простих чисел виду 4k+1 заздалагідь невідомий і треба вирішити, чи то спочатку організувати пошук простих виду 4k+1, сформувати базу, а потім у завданні для клієнта просто віддавати набори простих чисел, які треба комбінаторно перебрати, аби не змушувати шукати прості числа числа. Чи то залишити за клієнтом задачу пошуку простих чисел виду 4k+1 у заданому діапазоні.

Я особисто схильний до того, щоб клієнти не займалися пошуками простих чисел, а лише перебирали всі їх комбінації.
Як показує моя практика, якщо вже є якийсь, назвемо базовий набір простих, чисел, наприклад (73, 53^2), то для клієнта буде достатньо роботи, аби утворити і перевірити всі комбінації простих чисел виду 4k+1 із множини (5, 13, 17, 29, 37, 41) у всіх різноманітних їх ступенях у комбінації з базовим набором, так, що їх загальний добуток менший за 2^64.

Тому я пропоную завдання для клієнта формувати наступним чином:
(базовий набір) ; (динамічний набір).
Так, наприклад завдання виду
(53^2, 73) ; (5, 13, 17, 29, 37, 41) буде означати, що треба перебрати всі комбінації діагоналей, утворених добутком елементів базового набору (53^2, 73) з усіма можливими комбінаціями елементів динамічного набору (5, 13, 17, 29, 37, 41) в усіх можливих ступенях, таких, що загальний добуток менший за 2^64
За такої постановки задачі клієнти не будуть витрачати час на пошук простих чисел.
Звичайно, що знайти наступне просте число виду 4k+1 не є великою проблемою для клієнта, якщо 4k+1, скажімо, менше за 1 000 000, але 1 000 000 - це тільки 2^20, а що робити, коли просте число буде порядку 2^50 і треба буде знайти наступне просте число? Клієнт вимушений буде витратити годину часу, аби тільки знайти, перевірити на простоту і, між іншим, лише задля того, щоб утворити з ним умовно кажучи пару-трійку комбінацій і впевнитись, що вони не утворюють Ідеального кубоїда. Дуже не ефективне використання ресурсів.

Розмір динамічного діапазону залижить від елементів базового набору. Чим добуток елементів базового набору менший, тим менший має бути набір динамічного набору, адже за маленького добутку елементів базового набору ступенів свободи для динамічного набору більше. І навпаки. коли базовий набір буде рости і наближатися до 2^64, тим менше ступенів свободи у динамічного набору, а значить менша кількість діагоналей які треба перебрати, а отже, щоб завдання не було зовсім коротким, базовий набір для одного завдання буде складатися з великого за кількістю елементів базового набору великих простих чисел виду 4k+1.

Ну, я сподіваюсь ви не позасинали, поки дочитали до звідси. smile.gif
В дійсності в цьомі проекті буде дуже багато математики, комбінаторики, теорії чисел і таке інше, тому звикайте smile.gif
Або не читайте і віддайте на потану тим, кому це цікаво. smile.gif

Автор: Death Jan 28 2011, 22:59

список простых чисел примерно до миллиарда давно известен.
проверить их на форму 4к+1 - 10 минут.

надо просто этот список нагуглить. ещё 2 минуты.

быстрее

Welcome to Prime-Numbers.org. This website provides entire small prime numbers list. You can browse all small prime numbers(small than 10000000000) here. ...
www.prime-numbers.org/

олсо

The Goldbach conjecture verification project reports that it has computed all primes below 1018.[1] That means 24,739,954,287,740,860 primes, but they were not stored. There are known formulas to evaluate the prime-counting function (the number of primes below a given value) faster than computing the primes. This has been used to compute that there are 1,925,320,391,606,803,968,923 primes (roughly 2×10^21) below 10^23.

Автор: x3mEn Jan 28 2011, 23:02

Я сподіваюсь, що після усього мною сказаного зрозуміло, що цей проект має дуже багато спільного з PrimeGrid. Я, до речі, намагався налагодити контакти з ідейним керівником PrimeGrid. Його зацікавила моя ідея, але не більше. Власне через те, що їх метою є пошук простих чисел, а моєю - використання бази простих чисел для власного субпроекту, я думаю, наша переписка далі балачок не просунулась.
Власне, якщо б мати базу всіх простих чисел до (2^64)/(5^2), можна було б зайнятися прогою для нарізки завдань.
Дійсно, спочатку треба дізнатися, скільки така база буде важити.
Я сподіваюсь, що не більше пари гіг
Якщо б так, можна було б спробувати порахувати, скільки завдань треба буде нарізати, ну і скільки це загалом триватиме.

Автор: x3mEn Jan 28 2011, 23:17

(Death @ Jan 28 2011, 22:59) *

roughly 2х10^21 below 10^23

(2^64)/(5^2) = ~ 7.3*10^18
Якщо в загальній масі простих чисел приблизно 2%, а нас цікавлять виду 4k+1, тобто десь половина, отже це 1% від 7.3*10^18, тобто десь 7.3*10^16
Для зберігання одного числа все одно треба буде виділяти 64 біта, получається, що всього для зберігання база має бути 7.3*10^16 * 8 байт = 56'294Тб.
Мда, трохи забагато...

Я здається ніде не помилився в розрахунках?
Навіть якщо замість 64 біт використовувати якийсь тип із динамічним виділенням розміру, все одно багато виходить...

Автор: x3mEn Jan 28 2011, 23:36

До речі, простих чисел менших за 2^32 якщо теж близько 2%, для того, щоб їх всіх зберігати треба лише щось близько 350Мб,
а для 2^48 - 858Гб. Якщо подумати, не так вже і багато. molo, може для початку спробувати сили в діапазоні до 2^48?

Автор: Death Jan 29 2011, 00:00

не, там дальше их количество уменьшается.
пи(х) нелинейно.

Автор: x3mEn Jan 29 2011, 00:36

(Death @ Jan 29 2011, 00:00) *

не, там дальше их количество уменьшается.
пи(х) нелинейно.

На 10 млрд - 4.55%, на 10^23 - 2%
від цього нічого особливо не міняється.
ну, на 2^48 буде не 900Гб, а 2Тб.
Подумаєш, терабайт туда, терабайт сюда... smile.gif

Автор: A1ex01 Jan 29 2011, 09:33

пока разобрал шо на рисунке blink.gif
перерисовал по своему

Приєднане зображення

зы: добавил dab, dac

Автор: x3mEn Jan 29 2011, 10:29

A1ex01,
так зрозуміліше.
тільки я б діагоналі назвав по іншому.
Адже загалом задача зводиться до вирішення системи діафантових рівнянь
a^2 + b^2 = d^2
a^2 + c^2 = e^2
b^2 + c^2 = f^2
a^2 + f^2 = g^2
Хоча, звичайно, якими саме літерами назвати грані і діагоналі, немає особливого значення.

Автор: x3mEn Jan 29 2011, 10:44

Я переспав з цією проблемою, де зберігати прості числа і прийшов до такої думки:
якщо мета - перебрати всі діагоналі в діапазоні до 2^64, а діагональ утворюється добутком простих чисел, то достатньо отримати базу простих чисел в діапазоні від 2 до 2^32, адже будь-які діагоналі, що утворюються добутком, в якому присутнє просте число, більше за 2^32, не може містити іншого простого числа, більшого за 2^32. Отже для формування завдань з використанням простих чисел, більших за 2^32, достатньо буде тримати базу простих чисел від 2 до 2^32, а в діапазоні від 2^32 до 2^64 організувати вікно, що буде рухатись вгору по мірі виконання завдань.
Таким чином прості числа в діапазоні від 2^32 до 2^64 будуть шукати окремим підпроектом і немає необхідності їх десь зберігати.
Єдине що, одним з бонусів підпроекту має бути оголошення всіх знайдених простих чисел в діапазоні від 2^32 до 2^64 на окремий сервіс, який займається збиранням простих чисел, наприклад у той самий http://www.prime-numbers.org, якщо в них оголошення простих чисел передбачено...

Автор: re_SET Jan 29 2011, 20:47

(x3mEn @ Jan 29 2011, 10:44) *

Я переспав з цією проблемою, де зберігати прості числа і прийшов до такої думки:
якщо мета - перебрати всі діагоналі в діапазоні до 2^64, а діагональ утворюється добутком простих чисел, то достатньо отримати базу простих чисел в діапазоні від 2 до 2^32, адже будь-які діагоналі, що утворюються добутком, в якому присутнє просте число, більше за 2^32, не може містити іншого простого числа, більшого за 2^32. Отже для формування завдань з використанням простих чисел, більших за 2^32, достатньо буде тримати базу простих чисел від 2 до 2^32, а в діапазоні від 2^32 до 2^64 організувати вікно, що буде рухатись вгору по мірі виконання завдань.
Таким чином прості числа в діапазоні від 2^32 до 2^64 будуть шукати окремим підпроектом і немає необхідності їх десь зберігати.
Єдине що, одним з бонусів підпроекту має бути оголошення всіх знайдених простих чисел в діапазоні від 2^32 до 2^64 на окремий сервіс, який займається збиранням простих чисел, наприклад у той самий http://www.prime-numbers.org, якщо в них оголошення простих чисел передбачено...

cool2.gif

Автор: A1ex01 Jan 29 2011, 22:01

(x3mEn @ Aug 28 2010, 19:44) *


Просторова діагональ може бути тільки числом, що розкладається на прості числа виду 4k+1.


напиши почему так, а то ссылки твои здохли
по 29 гипотеза Альошина -http://2605556.ru/Alschin.html
"29. Целочисленного параллепипеда не существует (Разраб.)"

простые числа на прайме:
http://www.primegrid.com/torrent/

http://www.primegrid.com/download/primes_iso/

Автор: x3mEn Jan 29 2011, 23:19

A1ex01,
я збирався це зробити.
основний дуже важливий документ, з якого я зробив цей висновок, доступний за адресою
http://kvant.mirror1.mccme.ru/pdf/1999/03/kv0399senderov.pdf

Доведення буде складатися з деяких частин.
Нажаль треба багато часу, щоб навести його тут цілком, тому почну з початку:

Теорема 1.
Всякое нечётное число, представимое в виде суммы квадратов двух целых чисел при делении на 4 даёт остаток 1, а не 3.
Доказательство:
Из двух квадратов, сумма которых нечетна, обязательно один четен, а другой нечетен.
Квадрат четного числа нацело делится на 4, а квадрат нечетного числа при делении на 4 даёт остаток 1.

Теорема 2.
Любое простое число p, которое при делении на 4 даёт остаток 1, представимо в виде суммы квадратов двух натуральных чисел.
Доказательство состоит из двух лемм:
Лемма 1.
Для любого простого числа p = 4k+1, где k - натуральное, существует такое целое число m, что m^2+1 кратно p.
Лемма 2.
Любой простой делитель p числа m^2+1, где m - целое, представим в виде суммы квадратов двух натуральных чисел.

Из Теорем 1 и 2 следует, что простое число p>2 не представимо в виде суммы двух квадратов, если оно имеет вид 4k+3, и представимо, если p = 4k+1

Критерий Жирара.
Натуральное число представимо в виде суммы квадратов двух целых чисел тогда и только тогда, когда в его разложении на простые множители любой простой множитель вида 4k+3 входит в чётной степени.

Автор: A1ex01 Jan 30 2011, 09:27

теорема 1 понятна и так, особенно в двоичной системе

теорема 2 о простых числах, почему диагональ всегда простое число?
по моему это частный случай, т.е. если диагональ простое -тогда твоя формула...

Автор: molo Jan 30 2011, 11:06

(A1ex01 @ Jan 29 2011, 22:01) *

...
простые числа на прайме:
http://www.primegrid.com/torrent/

http://www.primegrid.com/download/primes_iso/


Djakuju, A1ex01

Vygljadaje, scho po torrentu nihto ne rozdaje.
Ale prjami linky pracjujut' - probuju vykachaty i pidnjaty. Nevpevnenyj scho tam - bachu obrazy DVD, ale scho v seredyni...

Htos' mozhlyvo zustrichav dazu/spysok - Euler brick (Прямоугольный параллелепипед, у которого целочисленные только рёбра и лицевые диагонали, называется эйлеровым. )? To by moglo pomogty na pershyh stadijah rozrahunkiv, a takozh dlja perevirky pravyl'nosti nashyh teorij.

Автор: x3mEn Jan 30 2011, 11:23

A1ex01,
якраз збирався написати другу частину.

Загальна формула для представлення добутку суми двох квадратів у вигляді суми двох квадратів наступна:
(a^2+b^2)(x^2+y^2) = a^2*x^2 + a^2*y^2 + b^2*x^2 + b^2*y^2,
додамо і віднімемо 2axby:
(a^2+b^2)(x^2+y^2) = a^2*x^2 + 2axby + b^2*y^2 + a^2*y^2 - 2axby + b^2*x^2 = (ax + by)^2 + (bx - ay)^2 (1)
Запам'ятаємо цю формулу, вона нам ще дуже знадобиться.

а) Якщо число n є сумою двох квадратів, то і число 2n представляється у вигляді суми двох квадратів.
Доведення:
Якщо n = x^2 + y^2, то
(x+y)^2 + (x-y)^2 = x^2 + 2xy + y^2 + x^2 - 2xy + y^2 = 2x^2 + 2y^2 = 2(x^2+y^2) = 2n
Тобто
2n = (x+y)^2 + (x-y)^2
Власне, цю формулу можно отримати і з формули (1), якщо згадати, що 2 = 1^2 + 1^2, тобто в формулі (1) a і b = 1.

Теорема 3 (основна теорема арифметики):
Ціле число розкладається на прості множники одним єдиним способом (з точністю до перестановки множників і асоціативності)
Доведення цієї теореми залишимо за дужками.

Будь-яке число n можна представити у вигляді добутку простих чисел трьох типів: 2^a, p(i)^a(i), q(j)^b(j),
де p(i) - прості числа виду 4k+1, a(i) - ступінь числа p(i)
q(j) - прості числа виду 4k+3, b(j) - ступінь числа q(j).
Нехай Q = П q(j)^b(j)
Тоді, якщо Q не є повним квадратом (а це можливо лише тоді, коли всі b(j) парні), то n не можна розкласти на суму квадратів (критерій Жирара).
Якщо ж Q є повним квадратом, то кількість розкладів n дорівнює кількості розкладів числа П(p(i)^a(i)) на суми квадратів

Теорема 4 (формула Діріхле):
Якщо число n розкладається на суму квадратів, то кількість представлень дорівнює [ (П (a(i)+1) +1) / 2 ] (2)
(Якщо кількість множників рівна 0, то добуток вважається рівним 1. Представлення, що відрізняються порядком доданків, не розрізняються)

Запам'ятайте і цю формулу. Вона нам теж знадобиться для перевірки, що ми правильно розклали число на всі можливі суми квадратів.
Доведення цієї теореми можна знайти у тому ж самому пдф-документі (ст.21)

Основні висновки з цієї теореми: :
1) всі ступені 4k+3 мають бути парними, щоб n мало розклади
2) кількість розкладів n залежить тільки від ступенів 4k+1
3) наявність чи відсутність у розкладі двійки (2) у будь-яких ступенях не впливає ні на "розкладність" n, ні на кількість розкладів

Так от, із Теореми 4 і загальної формули (1) випливає, якщо n - парне і розкладається на суму квадратів m різними способами,
то і число n/2 розкладається на суми квадратів і до того ж теж m різними способами.
При цьому способи розкладу n/2 утворюються із розкладів n одним єдиним способом.
Яким саме - залишаю вам це завдання в якості домашнього завдання. )

Отже, запам'ятаємо цей результат:
Якщо число n має m розкладів на суму квадратів n = x(i)^2 + y(i)^2, то і число 2n має m розкладів, при цьому самі розклади утворюються одним єдиним способом:
2n = (x+y)^2 + (x-y)^2
Цей факт буде використаний пізніше.

Автор: x3mEn Jan 30 2011, 14:03

Далі.
Якщо число n має m розкладів на суму квадратів n = x(i)^2 + y(i)^2, то число 4n теж має m розладів, до того ж самі розклади утворюються із розкладів n ще простіше, аніж для 2n:
4n = 2^2 * n = (2x)^2 + (2y)^2

Давайте тепер повернемося до нашої задачі.
a^2 + b^2 = d^2
a^2 + c^2 = e^2
b^2 + c^2 = f^2
a^2 + f^2 = g^2

Ребра a, b, c мають бути різні, це зрозуміло, тому
для g^2 має існувати як мінімум 3 різні розклади на суми квадратів:
g^2 = a^2 + f^2
g^2 = b^2 + e^2
g^2 = c^2 + d^2

Для того, щоб n = g^2 розкладалося на суму квадратів, потрібно, щоб у розкладі n прості числа 4k+3 були представлені у парних ступенях.
До того ж n має бути повним квадратом, а це можливо тоді і тільки тоді, коли всі прості множники n представлені у парних ступенях.

Тепер доведемо, що діагональ мінімального ідеального кубоїда є непарним числом.
По-перше зазначимо, що якщо ідеальний кубоїд існує, значить їх існує нескінченно багато.
Адже лінійно збільшуючи "габарити" кубоїда ми отримаємо так само ідеальний кубоїд.
Тому задача полягає в пошуку ідеального кубоїда мінімального розміру.

Припустимо, що просторова діагональ g є числом парним.
Тоді, як доведено вище, має розклад на суму квадратів і число (g/2)^2.
І нам відомо, яким саме єдиним чином:
(g/2)^2 = (a/2)^2 + (f/2)^2
(g/2)^2 = (b/2)^2 + (e/2)^2
(g/2)^2 = (c/2)^2 + (d/2)^2
З парності g випливає парність a, b, c, d, e, f
Отже кубоїд з парною просторовою діагоналлю g не є мінімальним.
Висновок: парні просторові діагоналі нас не цікавлять.
А значить шукана g має бути числом непарним.

Автор: x3mEn Jan 30 2011, 20:13

Далі.

Теорема 5.
Якщо просте число p не можна представити у вигляді суми двох квадратів, і якщо сума квадратів x^2+y^2 кратна p, то кожне із цілих чисел x, y кратне p.
Доведення цієї теореми наведено в пдф документі на сторінці 20.

Із Теорем 1 і 5 випливає, що якщо в розкладі просторовою діагоналі g є прості числа виду 4k+3 у будь-яких ступенях, то і всі a, b, c, d, e, f кратні всім цим 4k+3, оскільки прості числа виду 4k+3 НЕ розкладаються на суму квадратів,
а значить кубоїд не є мінімальним, оскільки всю систему рівнянь можна спростити, поділивши всі рівняння на число Q = П q(j)^b(j), де q(j) - попарно різні прості числа виду 4k+3, b(j) - ступені q(j).

Таким чином якщо ідеальний кубоїд мінімального розміру існує, його просторова діагональ має мати вигляд добутку простих чисел виду 4k+1:
g = П (p(i)^a(i))
На цьому доведення цієї чудової властивості завершено.

Є питання?

Автор: Alien Jan 30 2011, 20:15

алхимия какая-то =)

Автор: A1ex01 Jan 31 2011, 14:53

(x3mEn @ Jan 30 2011, 20:13) *

Є питання?

та да, может быстрее 3 числа в квадрате сравнить, чем делать кучу проверок?
пока вникаю nike_cannabis.gif

Автор: x3mEn Jan 31 2011, 20:45

(A1ex01 @ Jan 31 2011, 14:53) *

(x3mEn @ Jan 30 2011, 20:13) *

Є питання?

та да, может быстрее 3 числа в квадрате сравнить, чем делать кучу проверок?
пока вникаю nike_cannabis.gif

Ну, по-перше, ще ніяких перевірок робити не треба, я тільки навів доведення, чому має дорівнювати просторова діагональ і, власне, вже дав підказку, яким чином її формувати.
По-друге, якщо ти пропонуєш перебирати всі комбінації трьох чисел-ребер, то для початку порахуй, скільки взагалі існує комбінацій (a, b, c), таких, що a<b<с і a^2+b^2+c^2 < 2^128
По-третє, пдінесення до квадрату 64 бітних чисел - операція дуже витратна. А ще більш витратна - добування корення з 128 бітного числа.
Ну а по-четверте, коли вирішиш проблему, як точно порахувати квадрат 64 бітного числа, а потім з точністю хоча б до третього знака після коми порахувати корінь з 128 бітного числа, приходь, розповіси.

Свого часу я розповім, яким чином я уникаю проблему виходу із 64 бітного простору, хоча, по суті, перевіряю просторові діагоналі аж до 2^64, які за формулою нібито ще треба підносити до квадрату.

Автор: Death Jan 31 2011, 21:59

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

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


та гавно вопрос

a$ = 128bitnumber$;
b$ = sqrt( a$ );
printf b$;

Автор: molo Jan 31 2011, 22:17

(Death @ Jan 31 2011, 21:59) *

a$ = 128bitnumber$;
b$ = sqrt( a$ );
printf b$;

Mozha trohy konkretyky? Na chomu to napysano?

Bil'shist' cilyh (integer) chysel na .net/java obmezujet'sja 64bit -
-9,223,372,036,854,775,808 .. 9,223,372,036,854,775,807

Dlja 128bit mabut' pryjdet'sja svij 'type' vvodyty, ale to vzhe sprava realizaciji. Chastkovo bude opydsano tut - http://perfectcuboid.com/forum/4-development

UPD .NET - decimal value type - 79,228,162,514,264,337,593,543,950,335.

Автор: Death Feb 1 2011, 10:58

та ні на чому. абстракція.

я хотів сказати що це справа компілятора обчислювати корені й іншу фігню.

людина розробляє алгоритм - машина рахує.

Автор: vitalidze1 Feb 1 2011, 12:22

Йоптіль, як побачив ці квадрати, логарифми і іншу поєбень, аж мурашки по шкірі побігли.

PS. математику терпіти не можу fear.gif

Автор: x3mEn Feb 1 2011, 18:53

vitalidze1,
ну ясно, тру кранчер

Автор: A1ex01 Feb 1 2011, 22:15

(x3mEn @ Jan 31 2011, 20:45) *

По-третє, пдінесення до квадрату 64 бітних чисел - операція дуже витратна. А ще більш витратна - добування корення з 128 бітного числа.
Ну а по-четверте, коли вирішиш проблему, як точно порахувати квадрат 64 бітного числа, а потім з точністю хоча б до третього знака після коми порахувати корінь з 128 бітного числа, приходь, розповіси.


SSEx пробовал?-там регистры 128бит

Автор: A1ex01 Mar 25 2011, 17:56

x3mEn, по кубоиду
D^2=a^2+b^2+c^2
dab^2=a^2+b^2
dbc^2=b^2+c^2
dac^2=a^2+c^2

dab^2+dbc^2+dac^2=2(a^2+b^2+c^2)=2D^2 -сумма квадратов диагоналей четная, значит 2 диагонали нечетные или три четные =>D -четное


Автор: x3mEn Mar 25 2011, 20:09

A1ex01,
поясни, як ти зробив висновок, що з непарності двох із трьох діагоналей випливає парність просторової діагоналі.

Контраргумент:
D^2=a^2+b^2+c^2
dab^2=a^2+b^2
dbc^2=b^2+c^2
dac^2=a^2+c^2

неп^2=пар^2+пар^2+неп^2
пар^2=пар^2+пар^2
неп^2=пар^2+неп^2
неп^2=пар^2+неп^2

В дійсності ти вивів ще одну властивість кубоїда:
у ньому дві з трьох лицьових діагоналей непарні.

Автор: Allineer Mar 25 2011, 22:55

A1ex01, x3mEn, ребят, простите... а вы сейчас с кем разговариваете? smile.gif

Автор: x3mEn Mar 26 2011, 00:25

Allineer,
розмова почалась ось тут:
http://distributed.org.ua/forum/index.php?s=&showtopic=906&view=findpost&p=66404
продовжена ось тут:
http://perfectcuboid.com/forum/6---/9
перекладена ось тут:
http://www.rechenkraft.net/phpBB/viewtopic.php?f=56&t=11559
продубльована ось тут:
http://perfectcuboid.com/forum/4-development/28-theory

Якщо сильний математик чи програміст (а краще і той і той одночасно), приєднуйся до розмови, you are welcome!

Автор: x3mEn Mar 26 2011, 00:35

A1ex01,
не знаю, яким місцем ти відчув, але саме сьогодні, після майже 5 місячної перерви, я поновив роботу над задачею. Почав і вже майже закінчив писати безгуйового клієнта, заточеного на фактично виконання нарізаних гіпотетичним сервером завдань на перевірку діагоналей від і до.
Як доведу до ладу, можу викласти сорці разом із ехешником, якщо комусь цікаво буде. Я б не відмовився, якби хтось допоміг перекласти з Паскаля на С.
Без гуя в програмі залишилася чиста математика: динамічні масиви, 64 бітні цілі, сортування, перестановки і таке інше.
Адмін yoyo@home обіцяв розглянути можливість розгортання підпроекту на німецькому сервері, за умови, якщо прога буде написана на С. В них є досвід перекладання не-БОЇНК проектів на рейки БОЇНК.

Автор: A1ex01 Mar 26 2011, 08:36

если 2 диагонали нечетные

dab^2=a^2+b^2
dbc^2=b^2+c^2
dac^2=a^2+c^2
пусть dab и dbc нечет, тогда если a^2 нечет то и с^2 нечет, а b^2-чет

D^2=a^2+b^2+c^2
и в сумме D^2 -чет

правда, если a^2 чет то и с^2 чет, а b^2-нечет
D^2=a^2+b^2+c^2
и в сумме D^2 -нечет

значит D и чет и нечет st.gif

Автор: x3mEn Mar 26 2011, 08:54

пусть dab и dbc нечет, тогда если a^2 нечет то и с^2 нечет, а b^2-чет

D^2=a^2+b^2+c^2
и в сумме D^2 -чет

ця ситуація неможлива, оскільки серед a, b, c тільки одне ребро може бути непарним.
Джерело: http://en.wikipedia.org/wiki/Perfect_cuboid
Some interesting facts about a primitive perfect cuboid:

Автор: x3mEn Mar 27 2011, 09:56

Закінчив писати консольну версію програми.
Хтось може помогти перекласти програму на С/С++?


Приєднані файл(и)
Приєднаний файл  pcuboid.0.01.zip ( 66.17Кб ) Кількість викачувань: 276

Автор: Rilian Mar 31 2011, 16:12

x3mEn, http://distributed.org.ua/forum/index.php?showtopic=1089&st=80&gopid=77522&#entry77522

ты в новостях smile.gif

Автор: x3mEn Mar 31 2011, 23:13

(Rilian @ Mar 31 2011, 17:12) *

x3mEn, http://distributed.org.ua/forum/index.php?showtopic=1089&st=80&gopid=77522&#entry77522

ты в новостях smile.gif

Я в курсі. Тільки толку мало. Мало народу там для конструктивної розмови.
Є там один, Роберт якийсь. Вважає себе пупом землі. Критикує мене мовляв надто багато завдань получається.
За його оцінкою десь 10^17 діагоналей. От сиджу тепер, перевіряю...

Може в когось є вже написана в Паскалі/Дельфі функція/процедура для факторизації?
А то мене щось ламає писати.

function MaxDivisor(n: int64; var Has4kp3: boolean): int64;
var
divnum: int64;
begin
Has4kp3:=false;
Result:=3;
while (Result<=sqrt(n)) and not Has4kp3 do begin
divnum:=trunc(n/Result);
if n=divnum*Result then begin
Has4kp3:=Result mod 4=3;
n:=divnum;
end
else inc(Result, 2);
end;
Result:=n;
end;

інколи працює довго. Це взагалі найтупіший метод.
Мені, власне, навіть не факторизація потрібна, а перевірка, чи є серед дивізорів прості числа 4k+3, а якщо нема, тоді найбільший простий 4k+1 множник.

Це так, чисто для статистики, порахувати, скільки серед випадково обраних чисел 4k+1, мають у розкладі на прості множники лише 4k+1.
А потім зробити апроксимацію на весь діапазон від 1 до 2^63

Автор: Death Mar 31 2011, 23:31

1. Гербиц http://www.google.com.ua/search?q=Robert+Gerbicz.
2. он программировал клиента для єйлера на йойо.

http://www.euler413.narod.ru/

Современый поиск

На момент начала открытия проекта (24 октября 2007г), самая быстрейшая программа из всех созданных для поиска чисел опровергающих гипотезу Эйлера, методом тотального поиска, является программа Euler413.exe Роберта Гербица (Венгрия).
http://robert.gerbicz.googlepages.com
К примеру вместо 30 лет работы простого перебора, она выполняет поиск до 1000000 за 4 сек. На данном этапе мы имеем реальную возможность в течении не слишком большого времени проверить все числа до 2 000 000 000. Простой перебор в этом случае говорит, что нам бы потребовалось порядка 1020 лет работы (многократно больше возраста вселенной). Дальше пока невозможно из за ограничения размеров чисел, с которыми работает программа. Переход на 64 битную версию и более быстрые процессоры в будущем дадут новый импульс в этой задаче.

Автор: x3mEn Mar 31 2011, 23:38

Ну, я ж кажу, вважає себе пупом землі.
Він мені одразу не сподобався.
Надто зухвало себе поводить, нібито його точка зору сама правильна, а інших бути не може. Я йому сторінки 2 доводив, що він робить висновки, коли ще не вкурив всю тему.

Автор: Death May 5 2011, 10:20


http://mathoverflow.net/questions/7330/which-math-paper-maximizes-the-ratio-importance-length/10875#10875

Доказательство в одно предложение, что все простые числа вида 4k+1 есть сумма двух квадратов (Цагир), опубликованное в настоящем математическом журнале.

Дана ссылка на JSTOR, каковой требует 12 баксов за статью. В комментах благодетельный юзер Zavosh нарушает копирайт и цитирует релевантный кусок статьи, бесплатно.

Автор: x3mEn May 5 2011, 11:35

(Death @ May 5 2011, 11:20) *

http://mathoverflow.net/questions/7330/which-math-paper-maximizes-the-ratio-importance-length/10875#10875

Доказательство в одно предложение, что все простые числа вида 4k+1 есть сумма двух квадратов (Цагир), опубликованное в настоящем математическом журнале.

Дана ссылка на JSTOR, каковой требует 12 баксов за статью. В комментах благодетельный юзер Zavosh нарушает копирайт и цитирует релевантный кусок статьи, бесплатно.

$S = {(x,y,z) in mathbb{N}^3 : x^2 +4yz = p }
$ defined by: [ (x,y,z)
mapsto left {
begin{array}{cc} (x+2z,z,y-x-z) &
text{if } x < y-z ( 2y-x, y, y-x+z ) &
text{if } y-z < x <2y ( x-2y, x-y+z, y ) &
text{if } x > 2y
end{array}
right.
]

Що це за мова така? MathCad, чи що?
І як це по-людськи зрозуміти?

Власне, мене доведення теореми не цікавить, я і так знаю, що прості 4k+1 розкладаються на суму квадратів, до того ж один єдиним чином.
Мене цікавить, чи з цієї абракадабри можна висмикнути якийсь ефективний алгоритм пошуку цього самого розкладу.
Бо, нажаль, на даний момент якогось іншого методу пошуку розкладу N=x^2+y^2, окрім як перебір x від 1 до sqrt(N/2) я не придумав.

Автор: Death May 5 2011, 12:52

Власне, мене доведення теореми не цікавить, я і так знаю


*facepalm*

$S = {(x,y,z) in mathbb{N}^3 : x^2 +4yz = p }

это TeX - разметка


Автор: Death May 5 2011, 12:58

хром рендерит круто


Автор: Death May 5 2011, 13:07

8. Разложение простых чисел р= 1 mod 4 на сумму двух квадратов [179]

http://1.iesod.z8.ru/nehudlit/self0001/hasse.rar


Автор: x3mEn May 5 2011, 13:58

Death,
ти сам хоч читав, що процитував?
Якщо число p = 4611686018427387817, а це просте число, можеш перевірити, і до того ж виду 4k+1
А ну зконструюй мені xΞ((p-1)/2)! mod p
Або на прикладі розкажи, як отримати розклад на суму квадратів.

Автор: Death May 5 2011, 16:12

напиши профессору шо он идиот, ок?

Автор: x3mEn May 10 2011, 11:10

(Death @ May 5 2011, 13:58) *

хром рендерит круто

Треба було тільки поклацати по "ієрогліфам", тепер і Maxthon (Webkit) рендерить.

Автор: Death Dec 1 2011, 10:47

x3 как прогресс?

Автор: x3mEn Dec 1 2011, 14:05

Death,
до задачі по Perfect Cuboid мені вдалося долучити Andrii Muliar.
Він дуже сильно вплинув на моє бачення реалізації проекту.
Зокрема він мене переконав, що прямий перебір діагоналей - не така вже витратна операція
Я планував влаштувати генерацію діагоналей як добуток простих чисел 4k+1 у всіх можливих комбінаціях (добуток менший за наперед задане число (2^63-1)).
Але, по-перше, такий перебір наврядчи буде завершено для всіх чисел з діапазону (2; 2^63-1), навіть за умови, що вони є добутком простих чисел 4k+1 (надто вже багато просто протих чисел виду 4k+1, а для утворення діагоналі-кандидата достатньо домножити це просте на 5 (5 - мінімальне просте виду 4k+1). А простих чисел 4k+1, таких, що 5*(4k+1) < 2^63-1 ну дуже вже багато).
А по-друге, результат проекту за такого пошуку буде звучати приблизно так:
Якщо ідеальний кубоїд існує і його просторова діагональ менша за 2^63, ця діагональ у своєму розкладі на дільники має містити фактор, що більший за 2^36.
Це звучить не дуже зрозуміло, чи не так, порівняно, наприклад, з таким результатом:
Якщо ідеальний кубоїд існує, його просторова діагональ більша за 2^36.
Такий результат проекту більш зрозумілий, чи не так?

Якщо в деталях,
на цей момент і з його, і з мого боку написані програми, які вміють:
1) перебирати діапазони чисел, розкладати числа на дільники, відсіюючи таким чином, що залишаються тільки ті числа, які є добутком простих чисел виду 4k+1.
2) розкладають ці прості числа на суми квадратів. На цей момент це досить витратна операція. Ми плануємо її оптимізувати
3) будує всі можливі розклади квадрата вихідного числа на всі можливі суми квадратів
4) шукає серед отриманих розкладів:
-- примітивні майже ідеальні кубоїди, в яких із 7-ми розмірностей не ціла тільки одна сторона
-- примітивні майже ідеальні кубоїди, в яких із 7-ми розмірностей не ціла тільки лицьова діагональ
-- ну і власне примітивні ідеальні кубоїди (якщо такі будуть)

Автор: Death Dec 1 2011, 23:12

уже ж до 10^10 пощитаны - насколько ты больше диапазон берёшь?

ну хотя да. http://www.wolframalpha.com/input/?i=2%5E63-10%5E10 = 9223372026854775808


есть топик на йойо? там реальнее всего запустить.

Автор: x3mEn Dec 2 2011, 09:43

http://www.rechenkraft.net/phpBB/viewtopic.php?f=56&t=11559. Толку нема.
адміністратор йойо казав, що може розглянути мою пропозицію тільки якщо:
а) програма буде написана на С (на якій саме, я не уточнював)
б) програма буде консольна
в) програма матиме чекпоїнти
г) програма матиме прогрес
ґ) програма не генеруватиме багато трафіку
д) проект матиме прогрес
е) ну і бажано, щоб проект мав кінець


(Death @ Dec 1 2011, 23:12) *

уже ж до 10^10 пощитаны - насколько ты больше диапазон берёшь?

Ну, Andrii Muliar на одній своїй машині порахував вже до 2^36. А log(2^36) = 10.837
А якщо програму ще оптимізувати та хоча б 1000 чоловік буде рахувати, можна цю планку підняти до 2^44, я думаю. А може і вище.

Автор: Death Dec 2 2011, 16:19

ну явно не на шарпе ))
си надо чтобы скомпилить под линух и мак

у тебя консольная? чекпоинты есть?
прогресс есть? трафик я думаю там небольшой будет или как?

не совсем понятно какой прогресс у проекта?

ну конец у него есть - пощитать до стопиццот миллиардов.

как говорится до бесконечности и не дальше.

Автор: Bel Dec 2 2011, 18:32

Что можно получить еще из этого проекта кроме доказать/опровергнуть существования идеального кубоида?

Автор: x3mEn Dec 3 2011, 08:04

(Death @ Dec 2 2011, 16:19) *

у тебя консольная? чекпоинты есть?
прогресс есть? трафик я думаю там небольшой будет или как?

Давай так. Я одразу розумів, що треба буде консольну, тому у мене на Дельфі прога консольна.
У Андрія поки на C#.
Чекпоїнти можна зробити.
Прогрес є.
Трафік взагалі мізерний: пару байт на вхід, пару кілобайт на вихід.
(Death @ Dec 2 2011, 16:19) *

не совсем понятно какой прогресс у проекта?

ну, наприклад, ось такий: http://www.rechenkraft.net/yoyo/y_status_hat.php
Це теж можна організувати.
(Death @ Dec 2 2011, 16:19) *

ну конец у него есть - пощитать до стопиццот миллиардов.
как говорится до бесконечности и не дальше.

Не зовсім. Є обмеження цілочисельних обрахунків.
Межа, яку я хотів би досягти - 2^63-1.
По-перше і до цієї межі дійти буде дуже важко.
А по-друге, якщо і припустити, що дійдемо, треба буде переписувати клієнта, оскільки поточні розрахунки вилітають в простір 256-бітної цілочисельної точності.
На цей момент все складається так, що для перевірки 64-бітних чисел потрібно виходити в простір 128-бітної цілочисельної точності.

Автор: Death Dec 4 2011, 01:34

ну учитывая что мы движемся по числовой прямой прогресс очевиден - видно докуда пощитали, прально?

а есть компилятор дельфи или шарпа под линупс?

Автор: x3mEn Dec 4 2011, 02:14

(Death @ Dec 4 2011, 01:34) *

ну учитывая что мы движемся по числовой прямой прогресс очевиден - видно докуда пощитали, прально?

Правильно. Буде
Мінімальне n в прогресі
Максимальне n в прогресі
Все, що посередині - це робоча область.

Кожне завдання - це діапазон [m;n]
В цьому діапазоні (n-m)/4 чисел, які треба перевірити.
Із цих (n-m)/4 чисел якась частина відсіюється на стадії факторизації.
Скільки саме - заздалегідь невідомо, але я міряв в районі 2^63, там залишається десь відсотків 10 чисел-кандидатів від початкової кількості.
В принципі складність перевірки цих чисел не залежить від їх розміру.
Тобто, що перевіряти 1000 чисел в районі 1 млн, що в районі 2^63, різниці майже ніякої.
Але густина цих чисел у різних районах різна.
Тому нарізати завдання ([m;n]) треба буде в якійсь залежності від розміру m

Це все для того, щоб самі завдання між собою були приблизно однакової складності (мали приблизно однаковий час виконання).
Це, між іншим, теж одна з умов проекту - очікуваний час виконання завдань.
Якщо в проекті різні завдання дуже відрізняються за часом - це не є гут.
Наприклад, в Harmonious Trees @ yoyo, де чим далі прогрес підпроекту, тим складніші і, відповідно, довші завдання.
А в NumberFields ще гірше - одночасно можуть прийти завдання, одне на 30 секунд, інше на 1 день - це взагалі опа якась.

Автор: Death Dec 4 2011, 12:05

а предварительная сеялка будет? как в прайме.

Автор: Bel Dec 4 2011, 21:06

x3mEn, может начинать поднимать сайт проекта? Beta версию, пока идут работы по написанию клиента..

Автор: x3mEn Dec 4 2011, 22:55

(Death @ Dec 4 2011, 12:05) *

а предварительная сеялка будет? как в прайме.

ні, в цьому немає сенсу.
Кожен клієнт сам відсіюватиме.
Факторизація для чисел < 2^63 - це відносно швидкий процес.
Тим більше, що Andrii Muliar придумав дуже цікавий метод, як одним циклом від 3 до sqrt(n) провести факторизацію цілого діапазону чисел.

Досить багато часу зараз займає розклад простих чисел на суми квадратів.
В принципі ось цей джава-аплет вміє це робити дуже швидко:
http://www.alpertron.com.ar/FSQUARES.HTM
Наприклад число n=1844674407370954349 аплет розкладає менше секунди:
n = a^2 + b^2
a = 1297540285
b = 401327318

Time elapsed: 0d 0h 0m 0s

Ось тут навіть описано, як він це робить:
http://www.alpertron.com.ar/4SQUARES.HTM
Я вже 100500 разів читав цей опис, але збагнути не можу.
Якщо хтось допоможе - буду вдячний.
Ось тут навіть є сорс джава скрипту:
http://www.alpertron.com.ar/fsquares.java

Автор: x3mEn Dec 4 2011, 23:19

(Bel @ Dec 4 2011, 21:06) *

x3mEn, может начинать поднимать сайт проекта? Beta версию, пока идут работы по написанию клиента..

Просто сайт про Perfect Cuboid давно вже є:
http://www.perfectcuboid.com

А до боїнк-проекту ще дуже далеко.
Окрім клієнта треба ще кучу серверних приблуд написати:
генератор завдань, фідер, валідатор і т.і.

Автор: Bel Dec 11 2011, 15:24

x3mEn, как продвигается написание проекта?

Автор: x3mEn Dec 11 2011, 20:01

Bel, ніяк. Андрій зайнятий. Я застряг на швидкому алгоритмі декомпозиції:
http://distributed.org.ua/forum/index.php?s=&showtopic=906&view=findpost&p=89102

Автор: Death Dec 11 2011, 22:04

спробуй написати автору

Автор: x3mEn Dec 11 2011, 23:03

Death, пробував, писав

Автор: A1ex01 May 12 2012, 23:24

(x3mEn @ Dec 5 2011, 00:19) *

Просто сайт про Perfect Cuboid давно вже є:
http://www.perfectcuboid.com

лежит похоже(

ап:
если соединить 2 кубоида, то пространственные диагонали образуют равнобедренный треугольник
из теоремы косинусов D =2*a/(2cos(x))=a/cos(x)
D- пространственная диагональ
a-сторона кубоида
x-угол между a и D

ап2:
если с кубоидом все так плохо, предлагаю новый проект: поиск лучшего алгоритма sha2)

Автор: rpisarev Dec 24 2012, 15:17

(x3mEn @ Dec 1 2011, 14:05) *

Death,
до задачі по Perfect Cuboid мені вдалося долучити Andrii Muliar.
Він дуже сильно вплинув на моє бачення реалізації проекту.
Зокрема він мене переконав, що прямий перебір діагоналей - не така вже витратна операція
Я планував влаштувати генерацію діагоналей як добуток простих чисел 4k+1 у всіх можливих комбінаціях (добуток менший за наперед задане число (2^63-1)).
Але, по-перше, такий перебір наврядчи буде завершено для всіх чисел з діапазону (2; 2^63-1), навіть за умови, що вони є добутком простих чисел 4k+1 (надто вже багато просто протих чисел виду 4k+1, а для утворення діагоналі-кандидата достатньо домножити це просте на 5 (5 - мінімальне просте виду 4k+1). А простих чисел 4k+1, таких, що 5*(4k+1) < 2^63-1 ну дуже вже багато).
А по-друге, результат проекту за такого пошуку буде звучати приблизно так:
Якщо ідеальний кубоїд існує і його просторова діагональ менша за 2^63, ця діагональ у своєму розкладі на дільники має містити фактор, що більший за 2^36.
Це звучить не дуже зрозуміло, чи не так, порівняно, наприклад, з таким результатом:
Якщо ідеальний кубоїд існує, його просторова діагональ більша за 2^36.
Такий результат проекту більш зрозумілий, чи не так?

Якщо в деталях,
на цей момент і з його, і з мого боку написані програми, які вміють:
1) перебирати діапазони чисел, розкладати числа на дільники, відсіюючи таким чином, що залишаються тільки ті числа, які є добутком простих чисел виду 4k+1.
2) розкладають ці прості числа на суми квадратів. На цей момент це досить витратна операція. Ми плануємо її оптимізувати
3) будує всі можливі розклади квадрата вихідного числа на всі можливі суми квадратів
4) шукає серед отриманих розкладів:
-- примітивні майже ідеальні кубоїди, в яких із 7-ми розмірностей не ціла тільки одна сторона
-- примітивні майже ідеальні кубоїди, в яких із 7-ми розмірностей не ціла тільки лицьова діагональ
-- ну і власне примітивні ідеальні кубоїди (якщо такі будуть)


А я вот в отпуске снова вчера копнул в тот джава код, почитал описание автора с точки зрения математики и сходу смог написать представления 4k+1 в виде 2 квадратов и 4k+3 в виде 4-х. Скорость декомпозиции 4k+1 сводится к алгоритму разрешимости квадратичного сравнения x^2 = -1 (mod 4k+1), т.е. по сути нахождению корня из -1 в поле Z(4p+1). Пока сделал "в лоб" - перебором: математика не знает лучших методов. Но функция нахождения корня параметр, т.е. в последствии можно бесшовно заменить. Известно лишь, что их 2, один четный, второй нечетный. Надо поискать результаты современной математики - может есть быстрый алгоритм.

Так же есть функция, которая принимает 2 числа, умеет их разложить в декомпозицию 4-х (в общем случае) квадратов и выдать ответ - декомпозиция в виде 4-х квадратов от произведения двух чисел. Понятно её можно обобщить на большее число.

Алгоритма факторизации пока нет и не уверен, что успею до конца отпуска.

Сейчас это консольная программа на Python, за день-два могу переписать на Си/Си++ (без длинной арифметики). Пока начал разбираться с общем случаем представления (хотя для решения задачи перфекткуба, кажется, это и не надо)

Автор: Rilian Dec 24 2012, 17:22

лучше на руби и выложить на гитхаб

Автор: Володимир Dec 24 2012, 17:45

Мені чомусь здається шо просторова діагональ завжд буде нераціональним числом. Хоча х/з.

А всі інші сторони та діагоналі - в принципі разом трикутники, повинні бути поєднанням різних видів цільних прямих трикутників - http://en.wikipedia.org/wiki/Integer_triangle (Піфагора, Герона, ін.)

Тута також шось про цільні прямі трикутники та квантові координати(???) http://www.wyzant.com/Tutors/OH/Dover/7286479/Blog/197/the_perfect_right_triangle_and_quantum_coordinates_in_cartesian_space.aspx

Також думав подивитися на проблему так шо - всі інші діагоналі то тільки проекції просторової діагоналі на три площини..

чисто раді різноманітності тута кидаю.

Д.Р. всім привіт - вибачаюся шо пропадав....

Автор: x3mEn Oct 22 2013, 06:17

Виніс в окрему тему.

Автор: A1ex01 Oct 23 2013, 08:23

(x3mEn @ Mar 25 2011, 21:09) *

A1ex01,
поясни, як ти зробив висновок, що з непарності двох із трьох діагоналей випливає парність просторової діагоналі.

Контраргумент:
D^2=a^2+b^2+c^2
dab^2=a^2+b^2
dbc^2=b^2+c^2
dac^2=a^2+c^2

неп^2=пар^2+пар^2+неп^2
пар^2=пар^2+пар^2
неп^2=пар^2+неп^2
неп^2=пар^2+неп^2

В дійсності ти вивів ще одну властивість кубоїда:
у ньому дві з трьох лицьових діагоналей непарні.

походу перепутал диагонали с ребрами

надо будет покурить пол кубоида как прямоугольную пирамиду...
еще вариант - менять D, а 3 ребра вычислять через [ко]синус...

Автор: x3mEn Oct 23 2013, 10:06

Оскільки це давня відкрита математична проблема, я думаю, що легких доведень неіснування PC не буде.

Автор: A1ex01 Mar 23 2014, 21:07

предыдущая мысль ошибочна, пришел к новой)
D=dabc
D^2=a^2+b^2+c^2
D^2= a^2+dbc^2

в треугольнике отношение диагонали к стороне:
D больше a в k1(>1) раз=> a=D/k1, D больше dbc в k2(>k1) раз=> dbc =D/k2
D^2=(D/k1)^2+(D/k2)^2 => 1=(1/k1^2+1/k2^2)^(1/2)
основная мысль была -чем больше k тем меньше числа под корнем, а сумма должна быть=1
но http://www.wolframalpha.com/input/?i=1%3D%281%2Fk1%5E2%2B1%2Fk2%5E2%29%5E%281%2F2%29%2C+k2%3Ek1%2C+k1%3E1 выдал резалт
1<k1<2^(1/2), k2=(k1^2/(k1^2-1))^(1/2)
т.е. пространственная диагональ D больше a в число, которое больше 1 и меньше корень из 2(~1.41421356...)

Автор: A1ex01 Aug 5 2016, 14:50

ping x3mEn help.gif
шо нового?

если k1 идет к 1 то k2 в бесконечн, если k1 идет к sqr(2) то и k2 к sqr(2)? также остальные стороны/ребра
ап:
dbc/dabc=cos (dbc dabc) -угол между ними
b/dbc= cos (b dbc) -угол между ними
dabc=b/cos(угол1)/cos(угол2)

Автор: x3mEn May 31 2017, 20:29

Новини такі:

Після десь місяця різноманітних експериментів у мене є готова програма із пошуку 3 видів кубоїдів:
* Perfect Cuboid
* Edge Cuboid — майже ідеальний кубоїд, де цілочисельні усі сторони, окрім одного ребра.
* Diagonal Cuboid — майже ідеальний кубоїд, де цілочисельні усі сторони, окрім однієї лицьової діагоналі.

Пошук кубоїдів відштовхується від виду просторової діагоналі.
Програма консольна, написана на чистому С (не С++), є версії для
* Windows x86
* Windows x86_64
* Linux x86
* Linux x86_64

Програма приймає на вхід 2 параметри: початок та кінець діапазону пошуку, інформація про усі знайдені кубоїди пишеться в stdout, статитика — в stderr.
Програма розрахована для пошуку аж до 2^63.

Щодо швидкості. Швидкість залежить, від 3 параметрів:
1) процесор. тут все зрозуміло.
2) 64-бітна версія сильно (~ на 60% швидше) виграє у 32-бітної.
3) діапазон. чим більші числа, тим, зрозуміло, складніші завдання

Наведу тут приклад логу програми із статистичною інформацією:

Perfect Cuboid 1.06 (Windows 64-bit)
Copyright 2017, Alexander Belogourov aka x3mEn

Command line parameters : 244575149939 245273211192
Research Range borders  : 244575149941 245273211189
Total amount of Numbers : 174515313

Elapsed time            : 01:08:00.091 s
Candidates investigated : 30429317
Perfect Cuboids found   : 0
Edge Cuboids found      : 16
Diagonal Cuboids found  : 27

А ось 5 перших екземплярів із цього завдання із знайдених 16+27=43 кубоїдів:
D,244600187525,28161660483,76892843820,230485711456,81887658117,232199789635,√59036172616105401832336
E,244610350921,44854093440,121522347000,√43054653258982105514641,129535981560,212288819671,240462749879
D,244618979525,27628647696,93953798820,224160180803,97931907396,225856434115,√59075102970342683117209
E,244622018485,50414287248,108442705140,√45538511270870843862121,119588547348,219271775725,239370699061
D,244632158185,17208292297,144068966496,196959133800,√21051992431004560054225,197709447703,244026161496

Читати це так:
Перша літера P, E чи D — це тип кубоїда (див. вище).
Далі — просторова діагональ (G).
Наступні 3 числа — ребра (A, B, C).
Заключні 3 числа — лицьові діагоналі (D, E, F).

Уся робота легко розподіляється.
Щоб час виконання завдань був приблизно однаковий і не залежав від діапазону, я нарізав завдання за формулою, що залежить від початку діапазону:
y=1568625.2703x2+−183907100.8152x+5410490309.2381
, що виведена емпіричним шляхом.

Мета яку я ставлю:
1) на данний момент доведено, що якщо ідеальний кубоїд існує, його непарне ребро має бути більше за 3*10^12. Я збираюсь або знайти ідеальний кубоїд (що будо б ідеально), або хоча б 1000 разів перевершити (у певному сенсі) результат і сформулювати твердження, що якщо ідеальний кубоїд існує, його просторова діагональ має бути більшою, скажімо, за 10^15. Умовно кажучи, у ручному режимі зараз ми удвох із A1ex.UA досить скромними зусиллями за декілька днів виконали пошук до 250 млрд, тобто це 2.5*10^11. До 3*10^12 нам — "2 пісні, 3 приспіви" )
2) Знайти і опублікувати всі майже ідеальні кубоїди двох видів (Edge та Diagonal) із просторовою діагоналлю аж до 10^15.

Коли вдасться започаткувати BOINC-проект у мене є певні ідеї, як можна було б заохотити до участі: роздавати бейджі за кількість знайдених майже ідеальних кубоїдів двох видів. Тому, хто раніше приєднається, у того більше шансів "записати" майже ідеальні кубоїди на свій рахунок )
Але до того, як запустити BOINC-проект у мене є бажання провести тестування, код рев'ю та оптимізацію.
Тому я звертаюсь до усіх бажаючих:
а) програмістів (знання С та/або asm вітаються).
б) математиків (знання із теорії чисел).
а) просто бажаючих підтримати та допомогти започаткувати український математичний проект.

Усі бажаючі приєднуйтесь до групи у Telegram: https://t.me/joinchat/AAAAAA7IlqNyJx4jRSdEBA
А там я відповім на всі питання.

Автор: Death Jun 6 2017, 21:18

а без телеги? написал в скайп тебе

Автор: x3mEn Aug 15 2017, 23:22

28'000 tasks done
26'339 core*hours = 1097 core*days = 3 core*years spent
17'578'355'938'459 = ~ 2^44 achieved
—-------------------------------------------------
0 Perfect cuboids found
64'187 Edge cuboids found
111'237 Face cuboids found
0 Complex Perfect cuboids found
268'326 Imaginary cuboids found
1'331'250 Twilight cuboids found

Telegram: https://t.me/joinchat/AAAAAA7IlqNyJx4jRSdEBA

Автор: x3mEn Sep 3 2017, 23:49

3 вересня 2017 року Perfect Cuboid стартував як підпроект проекта http://www.rechenkraft.net/yoyo/.
Приєднуйтесь, в налаштуваннях yoyo залиште галочку навпроти підпроекту "Perfect Cuboid".

Автор: ale4316 Sep 4 2017, 11:16

Наконец и Украина выдвинула свой Boinc проект, а то как то за державу было обидно.Н у и первые проблемы: прогресс доходит до 49% за 4-ре минуты,сбрасывается и оооочень медленно начинает набирать ход. Дедлайн сутки-не вложусь. Athlon 270 up 4gHz 2память win7x64.

Автор: x3mEn Sep 4 2017, 14:40

(ale4316 @ Sep 4 2017, 12:16) *

Наконец и Украина выдвинула свой Boinc проект, а то как то за державу было обидно.Н у и первые проблемы: прогресс доходит до 49% за 4-ре минуты,сбрасывается и оооочень медленно начинает набирать ход. Дедлайн сутки-не вложусь. Athlon 270 up 4gHz 2память win7x64.

Є такий ефект.
Зазвичай при залучені до нового проекту / нового підпроекту, від самого початку очікуваний на виконання завдання час для клієнта визначається неправильно.
Наприклад 5 хвилин замість 3 годин. Через це поки програма не скаже боїнк-клієнту, де зараз прогрес, боїнк-клієнт намагається самостійно порахувати його, виходячи із часу що минув і його очікуваного часу на все завдання.
Тому до першого оновлення прогрес показує повну галіматью.
Спробуємо пофіксити це.

Автор: ale4316 Sep 4 2017, 14:50

Просьба увеличить дедлайн. Сутки-слишком мало, сделайте хотя бы 5.

Автор: x3mEn Sep 4 2017, 15:49

(ale4316 @ Sep 4 2017, 15:50) *

Просьба увеличить дедлайн. Сутки-слишком мало, сделайте хотя бы 5.

Це питання точно не до мене. Ці параметри виставляє адміністратор yoyo.
Думаю, що він знає, що робить. Програма у тестовій експлуатації, важливо мати можливість оперативно вносити зміни, якщо будуть глюки.
А деякі хости нагребли багато завдань, якщо вони будуть їх довго тримати у себе, процес виправлення помилок затягнеться.
Думаю, що коли все стабілізується, yoyo збільшить дедлайн.

Автор: x3mEn Sep 4 2017, 22:05

Версія 207.02
Microsoft Windows running on an AMD x86_64 or Intel EM64T CPU
Linux running on an AMD x86_64 or Intel EM64T CPU
Linux running on ARM, hardware FP
Linux running on 64-bit ARM

Пофіксено "прикол" із індикатором прогресу. Тепер від самого початку 0%
Крок прогресу зменшено з 1% до 0.25%. Так само як і частота збереження чекпоїнта.
Чекпоїнт тепер пишеться також коли знайдено кубоїди, тому не дивуйтесь, якщо появиться прогрес на позначці відмінній від кратного 0.25%
Невеличкі мінорні оптимізації stderr.

Поки не можу вмовити скомпілювати також 32-бітні версії під Windows та Linux.
Комусь, окрім мене, це потрібно?

Автор: 5erg Sep 5 2017, 03:01

(x3mEn @ Sep 4 2017, 23:05) *

Поки не можу вмовити скомпілювати також 32-бітні версії під Windows та Linux.
Комусь, окрім мене, це потрібно?


В жаркие печи все 32-битное (и твой ноут тоже)

Автор: ale4316 Sep 5 2017, 14:19

Тихий ужас творится с заданиями .... Посчиталось корректно Аж одно. Ждем стабильности в проекте.

Автор: x3mEn Sep 5 2017, 15:59

А що, у тебе є хоча б одне інвалідне завдання?
Я поки що жодного не бачив, якщо не брати до уваги ті, які були абортнуті юзером чи стали просроченими через дедлайн.
Те, що у тебе на данний момент пройшло валідацію лише 1 завдання, не значить, що у проекта проблеми.
Просто WU з кворумом 2, багато завдань чекають на виконання іншим дабл-чекером для початку процедури валідації.
Деякі хости нагребли собі тучу завдань, через 1 день сплинув дедлайн, завдання були відправлені повторно.
Ну, так, вибач, це не проблеми проекту, що хтось нагріб стільки завдань, скільки навіть теоретично не здатен виконати.
Пропонуєш обмежити видачу завдань не більше 20 на день на хост? Так інші стануть волати "а в мене супер-пупер-мега комп із 24 ядрами, я можу 100500 за день зробити, а мене тут обмежують".
Наскільки я знаю, зараз стоїть обмеження у 500 завдань на день на хост.

Автор: x3mEn Sep 5 2017, 16:31

ale4316, це твої хости?
http://www.rechenkraft.net/yoyo//hosts_user.php?userid=33375
У хоста із AMD FX™-4100 Quad-Core проблеми із скачування файлів.

<message>
app_version download error: couldn't get input files:
<file_xfer_error>
  <file_name>primes4k1.bin.1</file_name>
  <error_code>-120 (RSA key check failed for file)</error_code>
  <error_message>signature verification failed</error_message>
</file_xfer_error>

</message>


Спробуй на цій машині зробити Reset project.

Автор: ale4316 Sep 5 2017, 20:42

Описываю ситуацию: При первом подключении к проекту (настройки Boinc получать задания на 1 день работы) сервер выдает сразу до двадцати заданий на любую подключаемую машину. Задания грузятся и сразу же все выбивают ошибку загрузки (на всех машинах). После этого машина запрашивает повторно задания у проекта , получает их и коректно начинает с ними работать. Проблема еще в том, что дедлайн у проекта - сутки, а начальное расчетное время приходящих заданий с сервера 4-8 минут, которые перерастают в реальные 3-4 часа расчетного машинного времени, а с учетом количества получаемых заданий - почти все они не успевают посчитаться. Как то так.

О, проект начал давать по заданию на ядро и не больше. Уже лутше.

Автор: x3mEn Sep 5 2017, 20:45

Яка версія BOINC? У мене 7.6.33 і подібних ефектів немає.
На жодній із машин помилок закачки не було. Можу припустити, що в тебе антивірус на деякий час блокує закачку.
Від самого початку виконання завдань очікуваний час може і неточний, але не 4-8 хвилин, а пару годин. Окрім того, в налаштуваннях "Store up to an additional 0 days of work", тому BOINC запитує у сервера рівно стільки завдань, скільки ядер. Якось так.

Автор: ale4316 Sep 5 2017, 20:52

Boinc 7.6.33. На одной машине есть антивирус, на другой - нет, но картина была одинакова. Сейчас полученые задания с 5 -ти часовым временем на просчет.

Автор: x3mEn Sep 5 2017, 21:06

Ну, якщо чесно, то я не знаю, чому yoyo вирішив завдання зробити такими довгими. Зараз вони орієнтовані на 2 години на 1 ядрі i5-3570K, хоча від самого початку я рекомендував зробити задачі у 4 рази коротші. Ми в ручному режимі накранчили до 30'000'000'000'000 і експериментальним шляхом я з'ясував, що 30 хв. — це оптимально. У когось 1 година 20 хв., у когось — 20 хв.

Автор: ale4316 Sep 5 2017, 21:24

Ну 3-4 часа на средних машинах, в принципе, жить можно.

Автор: x3mEn Sep 5 2017, 21:42

В принципі можна. Але він же ж (навіщось) лупанув ще 2 версії для ARM, а там завдання тупо в дедлайн не вкладаються. І тепер yoyo у пєчалі, що робити. А вихід же ж лежить на поверхні — зменшити довжину завдань хоча б у 4 рази, щоб на всяких планшето-смартфонах 1 завдання хоча б годин за 8 виконувалось.

Автор: ale4316 Sep 5 2017, 21:53

И извените за не скромный вопрос: Кубоид чистый украиский проект, или совмесный?

Автор: x3mEn Sep 5 2017, 22:09

Perfect Cuboid чисто український підпроект чисто німецького проекту yoyo@home.

Автор: ale4316 Sep 5 2017, 22:26

Приятно, и главное чтоб не последний. Зайду на Boinc.ru - похвастаюсь.

Автор: Vasyan_Nyasha Sep 6 2017, 20:34

ale4316, , полностью согласен. 3 часа с дедлайном в день - лично для меня это сложно. Можно сделать либо 3-5 дней дедлайн, либо как говорит x3mEn сделать задания в 3-6 раз меньше.

Автор: dimus8210 Sep 7 2017, 15:43

мені як завжди щастить

Client error Aborted by user

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

б-муха, 24 завдання порахувалось нормально

при встановленому запасані завдань 0.1-0.2 дні, насипало біля 200 завдань

мабуть абортну і перезавантажу проект.

Автор: x3mEn Sep 8 2017, 00:17

У підпроекта з'явилась сторінка статусу:
http://www.rechenkraft.net/yoyo/y_status_pcu.php
на мітки легенди можна натискати, вкл/викл показ категорії.
натисніть, наприклад, на To Do, щоб побачити Done.
Done — це неперервний діапазон перевірених результатів.
In Progress — це діапазон, де зараз ведеться робота.
To Do — це те, що нам ще треба пройти до досягнення мети батчу.
Перша мета — 2^50.

Діапазон Skip залишили на десерт. Там дуже багато кубоїдів, а тому, кому вони дістануться — розіграємо у лотерею.
Коли з'явиться персональний облік кількості знайдених кубоїдів.

Автор: x3mEn Sep 10 2017, 08:03

Дедлайн збільшено до 5 днів.
За 7 днів підпроект, стартувавши з 10Т, вже перевищив 70Т.
При цьому утворюючи неперевний діапазон (як мінімум) двічі перевірених чисел від 10Т до 31Т.
Нагадаю, що мануальний кранч досяг 30Т десь приблизно за 2 місяці.
Як то кажуть — відчуйте різницю.

Підпроект набирає оберти. Це видно за графіком Unsent tasks.
Графік стабілізувався, була помилка із оцінкої складності завдання (заменшена у 30 разів), через що на самому початку проекту клієнти від сервера отримували більше завдань, ніж ті здатні порахувати до дедлайну.
Тепер все ґаразд, кількість активних юзверів день від дня зростає.

Результати мануального кранчу, якій закінчився/призупинився позавчора:
40'730 tasks done
38'115 hours = 1588 days = 4,348 years spent
30'359'586'957'394 achieved
—-------------------------------------------------
0 perfect cuboids found
74'706 edge cuboids found
129'983 face cuboids found
0 perfect complex cuboids found
313'393 imaginary cuboids found
1'554'246 twilight cuboids found

Я вдячний всім, хто приймав участь у альфа тестуванні і допоміг зробити програму кращою, а це:
A1ex01
rpisarev
5erg
dimus8210
vasyannyasha
firstomega
(_KoDAk_)

Даю посилання на групу в Telegram, якщо будуть якісь питання чи потрібна допомога:
https://t.me/joinchat/BrFEbg7IlqMFl4PBRSdEBA

Автор: Vasyan_Nyasha Sep 15 2017, 18:11

Считаються таски... Решил посмотреть с кем "делю ложе".
Оказалось что из 4 тасков 1 в пендинге dimus8210, а еще 1 в пендинге 5erg.
Мир тесен drinks.gif

Автор: dimus8210 Sep 15 2017, 22:05

(Vasyan_Nyasha @ Sep 15 2017, 19:11) *

Считаються таски... Решил посмотреть с кем "делю ложе".
Оказалось что из 4 тасков 1 в пендинге dimus8210, а еще 1 в пендинге 5erg.
Мир тесен drinks.gif


drinks2.gif

Автор: x3mEn Oct 28 2017, 01:40

9 жовтня ми додали до https://www.rechenkraft.net//yoyo/home.php таблицю із кількістю знайдених кубоїдів різних типів, так само як http://www.rechenkraft.net/yoyo/y_status_pcu.php була розширена загальною їх кількістю.

Вчора, 27 жовтня, ми додали Hits до підпроекту Perfect Cuboid, тож відтепер ви можете змагатись не тільки у кількості зароблених Кредитів, але й у кількості знайдених кубоїдів. Free-DC уже показує Hits на http://stats.free-dc.org/stats.php?page=userwork&proj=yoy&subproj=pcuboid.

І також гарна новина — вчора ми пройшли екватор першого батча, Max In Progress перевищив 2^49 = 562.949.953.421.312, яке є половиною нашої першої мети — 2^50.

Автор: ale4316 Dec 16 2017, 21:24

Почему заданий нет?

Автор: fram Dec 16 2017, 22:36

(ale4316 @ Dec 16 2017, 21:24) *

Почему заданий нет?

дік походу все чо нужно - пересчитали. Во всяком случае статистику проекта я так понимаю.

Автор: x3mEn Jan 6 2018, 00:43

Ми розпочали новий батч. Є завдання для Windows 64-bit.
На підході Linux 64-bit та ARM 64.

Автор: x3mEn Feb 2 2018, 17:06

Результати 2-го батчу (2^50-2^51):
6665 Face cuboids
13330 Imaginary cuboids
59985 Twilight cuboids

Якщо ідеальний кубоїд існує, його просторова діагональ має бути більша за 2^51.

Скоро розпочинається 3-ій батч. Я так сподіваюсь, що він буде в діапазоні 2^51-2^52.

Автор: ale4316 Feb 4 2018, 21:37

Пошли задания. Пора браться за дело ...

Автор: x3mEn Oct 7 2018, 20:09

3-ій батч майже завершено. Принаймні генератор завдань вже зупинено, тепер декілька тижднів для валідації всіх відправлених завдань.
Але вже зараз можна із 99.999% впевненістю казати, що якщо Ідеальний паралелепіпед існує, його просторова діагональ перевищує 2^53 = 9'007'199'254'740'992.
Як я і обіцяв, я опублікував сорс-код на https://github.com/renyxadarox/pcuboid
Всі, хто зацікавлений у валідації коду, будь ласка, долучайтесь.
Якщо є питання, їх можна запитати в спеціалізованій групі Perfect Cuboid в Telegram: https://t.me/joinchat/BrFEbg7IlqMFl4PBRSdEBA

Invision Power Board
© Invision Power Services