2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 13  След.
 
 Re: Al Zimmermann: non-coplanar points
Сообщение25.03.2016, 13:20 
Аватара пользователя


25/08/12
171
Germany
Pavlovsky в сообщении #1108980 писал(а):
1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.


You solve a diophantine equation for each z or just one? The latter is what I do.

Btw. here are the best solutions in the moment. Al has changed his policy:

{5, 8, 13, 18, 28, 32, 40, 44, 52, 62, 66, 79, 86, 88, 95, 105, 116, 119, 131, 136, 140, 150, 158, 167, 181}

I only have the best one for N=2..7

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение25.03.2016, 13:43 
Аватара пользователя


21/02/10
1594
Екатеринбург
Herbert Kociemba в сообщении #1109028 писал(а):
You solve a diophantine equation for each z or just one?

$ax+by+cz+d=0$
Перепишем так:
$ax+by=d'$ $d'=-cz-d$

Алгоритм Евклида сначала ищет решение
$ax_0+by_0=gcd(a,b)$

Это решение не зависит от d' и его можно сделать за пределами цикла перебирающего z.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение27.03.2016, 15:48 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Ал сделал новую страницу где показывает лучшие результаты. Это очень удобно!

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 11:05 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
dimkadimon в сообщении #1109002 писал(а):
Pavlovsky в сообщении #1108980 писал(а):
Наконец то и я решил эту задачу для общего случая. Получился простой, красивый и эффективный алгоритм.

1) Представим плоскость в виде: $ax+by+cz+d=0$
2) В цикле переберем координату z из интервала [0,N-1]
3) Получается линейное диафантово уравнение с двумя неизвестными (x,y). Решаем его расширенным алгоритмом Евклида.

Все!

Гениально! Но будет ли это быстрее?

Все это время потратил разработкой этого метода. Расширенный алгоритм Евклида штука не простая и там много подводных камней. Результат? Этот метод оказался в два раза медленее старого! Старый метод просто перебирает координаты $x,y$, а потом находит $z$ используя уравнение плоскости. Мой совет - не тратьте время на этот новый метод!

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 14:57 
Аватара пользователя


25/08/12
171
Germany
dimkadimon в сообщении #1109795 писал(а):
Мой совет - не тратьте время на этот новый метод!

I am not sure about this. Looping throgh the x,y coordinates should give a runtime O(N^2), while the runtime for the "new" method seems to be about O(N).
I generated 20 million random planes for N=10, 20, 30, 40, 50, 60, 70, 80, 90, 100 and it took about 11, 15, 20, 23, 25, 28, 31, 34, 37, 40 seconds to get the grid coordinates of the planes. Is your method really faster?

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 15:21 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Herbert Kociemba в сообщении #1109857 писал(а):
I am not sure about this. Looping throgh the x,y coordinates should give a runtime O(N^2), while the runtime for the "new" method seems to be about O(N).

Hmm... perhaps my implementation is terrible and has a large constant factor. I would have thought the Euclid method to be at least O(Nlog(N)) though - N for the z loop and log(N) for the Euclid algorithm. Also I am computing $gcd(a,b)$ for each new z, perhaps that's the main difference? I'll get back to you on this.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение28.03.2016, 15:26 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1109860 писал(а):
Also I am computing $gcd(a,b)$ for each new z,


Именно это делает алгоритм неэффективным.

Pavlovsky в сообщении #1109032 писал(а):
Алгоритм Евклида сначала ищет решение
$ax_0+by_0=gcd(a,b)$

Это решение не зависит от d' и его можно сделать за пределами цикла перебирающего z.

!

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 10:58 
Аватара пользователя


21/02/10
1594
Екатеринбург
Pavlovsky в сообщении #1107336 писал(а):
Спроецируем куб на плоскость образованную осями координат x и y.
Тогда
1) При проекции на плоскость x-y не появится прямая где более трёх точек.
2) При проекции на плоскость x-y, в полученном квадрате будет количество точек равное количеству точек в исходном решении или на 1 меньше.


Продолжу эту тему.

Поместим две произвольные точки в наше решение.
Проведем через эти точки все плоскости, имеющие хотя бы одну точку, не лежащую на прямой образуемой выбранными точками.
Пусть таких плоскостей K.
Тогда в решении будет не более K+2 точек.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 11:27 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1109862 писал(а):
Именно это делает алгоритм неэффективным.

Добавил это в свой метод, но он все равно медленее оригинального... Получив $gcd(a,b)$ я долго перебираю подходящии координаты x,y.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 11:34 
Аватара пользователя


21/02/10
1594
Екатеринбург
Расширенный алгоритм Евклида дает решение ввиде

$x=a_x+b_x*t$
$y=a_y+b_y*t$

Легко вычислить диапозон $[t_n,t_k]$ при котором точка (x,y,z) будет принадлежать кубу для всех целых t из $[t_n,t_k]$ .

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение29.03.2016, 12:26 
Аватара пользователя


25/08/12
171
Germany
Pavlovsky в сообщении #1110134 писал(а):
$x=a_x+b_x*t$
$y=a_y+b_y*t$

It should be $x=a_x+b_x*t_1$ and $y=a_y+b_y*t_2$. If you only use one parameter t the points will lie on a single line, which is not true.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение30.03.2016, 14:54 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Ура получилось! Огромное спасибо за подсказки.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение30.03.2016, 15:03 
Аватара пользователя


21/02/10
1594
Екатеринбург
dimkadimon в сообщении #1109545 писал(а):
Ал сделал новую страницу где показывает лучшие результаты. Это очень удобно!


Теперь нет смысла держать свои результаты под подушкой?! :D

Цитата:
7 23.51 Dmitry Kamenetsky Adelaide, Australia 30 Mar 2016 12:22

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение31.03.2016, 15:17 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Pavlovsky в сообщении #1110513 писал(а):
Теперь нет смысла держать свои результаты под подушкой?! :D

Это верно! Мне кажется Ал открыл рекорды чтобы всем дать шанс против Tomas и сделать соревнование интереснее.

 Профиль  
                  
 
 Re: Al Zimmermann: non-coplanar points
Сообщение31.03.2016, 15:37 
Аватара пользователя


10/11/12
121
Бобруйск
Конечно! Знание максимальных результатов в этой задаче никак не облегчает их нахождение.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 195 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7, 8 ... 13  След.

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



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

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


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

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