Кто может сделать быстрее? "Задача о восьми Ферзях"

locki
Мдя уж, не хило - терабайт чисел Пи. Пускай мой алгоритм сможет сделать это за 40 итераций (впрочем какое время займет итерация, если в ней куча делений - х.з.), но такое число просто негде хранить - ту оперативки надо немерянно, или по меньшей мере терабайтный RAID.

P.S.: Интересная статья, о людях способных к быстрому устному счету. Заставляет задуматься - а на пользу ли нам визуальное изучение математики, может мозг с ней не может справлятся оптимально?

 

alpet
выложи описание твоего алгоритма (в смысле не код, а че за чем) я через тангенс считал, как то - оч. медленно.
Кстати его распараллелить можно???

 

locki

На счет количества итераций, я явно напутал - их будет наверняка больше 40. При 40 итераций достигается значение угла равное 1/2^40 от всей окружности. Значение абсолютно точное для данного угла, и если его умножить, точнее сдвинуть на 40 влево, получится PI с явно недотягивающей по точности до 1 трлн. чисел. Затрудняюсь вобщем представить точное число операций.

Вычисление Пи в себя включает:
Перевод значения угла из радиан в двоичные градусы (это когда вся окружность состоит из N - градусов, равных некоторой степени двойки). Например у нас вся окружность будет поделена на 1Тб двоичных градусов, и угол на ней может быть представленно 40 битным числом градусов соотв.
В дальнейшем циклически будем делить, сектора окружности пополам, начав с прямоугольного сектора AOB (представленно на рисунке в аттаче).
Само деление в себя включает:
1. Нахождение центральной точки C между A и B.
2. Получение расстояния между C и O, с помощью формулы z = sqrt (C.x^2 + C.y^2)
3. Деление соотв. C.x и C.y на значение z, что даст точку D
4. Теперь А присваивается значение D и цикл повторяется.

Когда будет совершенно 40 таких циклов, последнее значение надо будет сдвинуть влево на
42 (плюс 4 четверти), в результате чего получится PI.

Насколько мне ясно - самая трудоемкая операция, это извлечение квадратного корня. Есть алгоритмы сводящие ее к набору делений. Параллелится алгоритм частично - например квадраты чисел можно одновременно вычислять, и делить C.x и C.y можно одновременно.

 

locki
Навороченный интерфейс будет тормозить прогу больше чем вывод по 10 раз в секунду

Jakob
Думаю с такой хорошей оптимизацией программу можно версией 1.3 назвать. Еще небольшой прирост скорости получился от исключения пары лишних push/pop и замены циклов с while(P){} на if (P) do{}while(P).

 

Black_mirror
в последующих версиях поправь описку "вычисляютя"

 

alpet

В P4 латентности FSQRT и FDIV одинаковы, в P6 и AMD деление выполняется быстрее, но не более чем в 1.5 (максимум 2) раза

 

Black_mirror
я не знаю может это только у меня, но ругается, что архив битый, асм- выходит, а ехе не разархивируется...-(

 

leo
Насколько мне известно, эти операции вобщем-то не применимы для чисел с точностью трлн. знаков после запятой? Или все-таки есть алгоритмы которые их используют?

 

locki
Видимо это у меня винрар левой версии (3.30), заархивировал в zip, заодно опечатку исправил.

Результат версии 1.3(АтлонXP1700+):
F(20)=39029188884 time=24385093 ms speed=1600534 v/s

Вот ссылка на число расстановок для N от 1 до 25. Интересно на каком компе они для 25 они это вычислили.

 

Я понял что ферзя всегда нужно ставить на ту горизонталь или вертикаль, на которой минимальное количество свободных клеток. В архиве экспериментальная версия программы, оптимизации еще нет (для последних 10-12 ферзей нужно наверно будет старый алгоритм использовать, если получится данные привести к одному формату). На маленьких полях злобно тормозит, но на поле 32 на 32 находит по 100К расстановок в секунду.

 

Black_mirror
Версия 1.3 вылетает при 2 и более потоках на моей (одноядерном селероне, на Пне с Хипер Трейд-ом, на Четырехпроц Оптеронах) и других машинах особенно с приоритетом Риал тайм...
Причем вываливается на предпоследней секунде...

 

Black_mirror
не последний вариант слишком тяжелый стал: 17 ферзей расставлял v1.3 за 38 секунд, а ща v?.? 410секунд - половина вариантов...
Есть!
F(17)=95815104 time=910141 ms speed=105275 v/s

 

alpet
я заметил, что суперПи во время работы создает временные файлы...

 

locki
Проверь тогда эту версию.

А новую программу лучше всего сравнивать с другими при N=31

 

вылетает, блин ... те же симптомы: предпоследняя секунда, 2 потока...

 

а в тяжелой версии считаются видимо не все варианты либо переполнение переменной, т. к. в ней
31-26393862 вариантов (time=184921 ms speed=142730 v/s)
а по твоей ссылке посчитано: уже при 25 о-го-го скока!
19-4968057848 - уже вроде превышает 2^32
25-2207893435808352 - меньше 2^64

8-92
9-352
10-724
11-2680
12-14200
13-73712
14-365596
15-2279184
16-14772512
17-95815104
18-666090624
19-4968057848
20-39029188884
21-314666222712
22-2691008701644
23-24233937684440
24-227514171973736
25-2207893435808352

 

locki
Мдя, даже если она и создает временные файлы - проблемы с терабайтным числом это не решит. Мало того что надо рейд собирать, это еще и тормоз получится - вычислять можно будет и на первом пне с таким же успехом. Вобщем эту задачу надо как-то решать, чтобы использовалось по минимому памяти, и при этом винт не забивался. С другой стороны PI число иррациональное, врядли упаковывается хорошо...

Касательно количества расстановок - чем больше полей, тем сильнее соотв. растет их кол-во. Если уже на 25, достигается увеличение почти на порядок, при добавлении поля... Получается число около 3e21 - долго рассчитывать вобщем...

 

Проверь, вылетает на этом участке (при попытке push в несуществующий стек) :

Код (Text):

1. thread_exit:
2.         lea ebx,[esp+page_size]
3.         mov esp,[esp+28]
4.         cmp ebx,[cnt_end]
5.         jb thread_next
6.         lock dec [thcnt]
7.         jnz .l2
8.         invoke PostMessage,[hdlg],WM_COMMAND,IDSTOP,0
9.     .l2:
10.         mov dword [ebx+20],0
11.         invoke ExitThread,0

Когда один поток уже завершился и его стек исчез из памяти, то следующий поток почему-то обращается к стеку предыдущего (т.е. во втором потоке esp от первого)

 

bogrus
Спасибо за помощь.
locki
Баг вроде искоренён, а экспериментальная версия может считать и дальше (счётчик так и остался 64х-разрядным), просто после запуска фокус на кнопку стоп устанавливается, видимо ты случайно пробел нажал и программа остановилась.

 

если есть еще желание посостязаться, то посостязайся с ИНТЕЛОМ:

Их алгоритм http://images.people.overclockers.ru/preview/82395.jpg

Результат ихней программы:____P-M(Banias)_P4-M____P3-M___Athl____Athl_XP
Частота,МГц____________________1600_____1500____1000____1000____1667
Время выполнения Queen 32,(сек)__26,8_____33______39______30,5_____21,3
Замеряй, за скока у тебя готова первая расстановка для 32-х ферзей.
В моей программе 136,375 сек. на Сел-Д 3,6Ггц. Гы-Гы...-)