Как стать автором
Обновить

Комментарии 25

> которую я писал когда-то и которая искала простые числа с помощью Решета Аткина.

Сделайте честное сравнение с одинаковыми алгоритмами.
32 бит вполне достаточно для поиска простых чисел до 4 294 967 295


Вообще то должно быть достаточно до 32 млрд, в каждом байте 8 бит.

А вообще я начинал программирование с этой задачи. Давно, под дос ещё.
Я не очень понял, можно поподробнее?

Я имел в виду максимальное беззнаковое число, которое можно представить 4 байтами. Самое большое число в этой программе — максимальное число, ограничивающее поиск, поэтому я и написал про 4 294 967 295.
Я понял, что это 32 бита на указатель, это 4гб памяти, а поскольку на флаг вычеркивания вы используете 1 байт, то таким образом можно вычислить простые числа до 4млрд. А вообще то на флаг можно использовать 1 бит, кроме того не нужно проверять четные числа, так что требования к памяти для решета можно было бы снизить в 16 раз.
Действительно, можно исключить четные числа, ноль и использовать по 1 биту на флаг. Но это сделало бы программу несколько менее понятной, так что я отказался от этой идеи. Все-таки это учебный пример, в котором должно быть легко разобраться.

По поводу выделения 4Гб — мне кажется, столько выделить не получится. Все будет зависеть от того, сколько памяти в распоряжении у ОС в момент выделения.
Поскольку используется явно 32-битное окружение, выделить (под win32) получится чуть менее 2гб. Если все затеяно в кач-ве обучения — можно попробовать и 64битные режимы, там с памятью ограничения другие )
32бит а не 32байт. внимательнее читайте ;)
Возможно, в следующий раз я займусь этим. Интересная задача.
Я как-то разбирался с FAIM — ICQ клиент, написанный на asm + WinAPI. Автор маньяк! К сожалению, проект заброшен уже лет пять как.
На самом деле с гольным винапи (в том числе для gui) работать на ассемблере не много сложнее, чем на чистом си, например. Тем более, если использовать всякие аналоги invoke для masm и прочие. А протоколы на asm реализовывать вообще сказка. В универе я немалую часть задач на asm кодил, очень уж я тогда его любил. В том числе писал всякие 3D моделирования, матрицы, преобразования, гуро и фонги, полсотни gui-контролов и окошечек, сопроцессорные оптимизации, вот уж проектик был. Недавно только смотрел, слезу аж пустил. Щас мне бы влом такое было делать в 21 веке)
Друг от нечего делать накодил на асме аналог MediaPlayerClassic. Мало того что размером 40 кбайт (оригинал под 5 метров), так еще и летает как птичка на допотопных машинах.
Даёшь больше тёплого лампового асма и меньшая javascript и HTML5 в качестве приложений для десткопа!
> Для себя я решил передавать аргументы подпрограммам через регистры и указывать в комментариях

fastcall же!
В принципе, как-то так и получается: fastcall предполагает передачу аргументов через регистры.
Если честно, результаты в 15-25 секунд не впечатляют.

В этом топике Результаты новогоднего Хабра-соревнования по программированию, анализ и обсуждение решалась похожая задача, и лучшие времена были порядка 0.04s — 1s. Прямолинейное решение «в лоб» работало порядка 8.5 секунд, что говорит о том, что улучшение алгоритма приводило к ускорению в 10-300 раз. Не уверен, что на ассемблере легко доступна подобная алгоритмическая оптимизация.

В комментариях отписывались, что 4-х поточный Аткинс работал примерно столько же, сколько и простейший однопоточный Эратосфен. Так что сравнение с 25s на C++ (с возможно менее удачным алгоритмом) вряд ли корректно.
Да тут и не было цели реализовать оптимальный по скорости алгоритм. Так что я не претендовал на то, чтобы впечатлить всех временем выполнения.

Но сравнение алгоритмов интересное. Вроде бы, Аткинс должен быть быстрее Эратосфена. Может быть, все дело в реализации? Например, реализация алгоритма работы на первом месте очень оригинальная:

//@shadeware
#include <cstdio>
#include <vector>
#include <cmath>
unsigned i,n,Q,j,L;long long u[66],A;int main(){for(;i<448;i++)u[i/7+2]=u[i/7+2]*96+"+.Uy[e^4MAqc>,3Vq8a}n3-teC`p2r/)Fl[2Z)|>Ke2O~7<Co2:Q]dpI23fM5~22\'X S\'}2\"z;})81lu^+vx1s sc[U1g%Wzq+1s3 ?1[1HQoI$^1TH2EaX1cEzV,Z1CHMY7o1DHmqPA1D#4oe]1F&|\'F^1R`5\'k)0{z2\\Oc1<T/G)x10BVH)~1B,ZzW:1)>FZ%$1+[%c\"<0dAd/tP1->\"0M!1;JwZ6!1*%j_y00V6$w!u10I dHR1PXF]r20!?Xhxw1?nbdEr0e-/ZE_0s:6:z.0[}+qG51<y9WfF0.^#nCQ0s)I(d/0XfrAQB10^,7e?0^X\'W4 13M.MfL0"
"5Q2Oz50fxnC)E0V@NGo+0=Z?sS/0I_*[l0\\W)O u1pw[AYJ/A?Xk;g0rbiYbu1*{Pj>f0\'\"aEs60OP;ZHs0zsjvXg0:~BPSu/aWY+&F1_aM,<q"[i]-32;for(i=0;i<64;i++)u[i+2]+=2*u[i+1]-u[i];scanf("%u",&n);Q=sqrt(n)+1e-7,L=n>>24<<24;A=u[(n>>24)+1]+2*!L*!!~-n;std::vector<bool>S(Q/2+1),B(n-L+2);B[1]=!L;for(i=3;i<=Q;i+=2)if(!S[i/2]){for(j=3*i;j<=Q;j+=2*i)S[j/2]=1;for(j=L?(L+i-1)/i*i:2*i;j<=n;j+=i)B[j-L]=1;}for(i=1;i+L<=n;i+=2)B[i]?0:A+=i+L;printf("%llu\n",A);} 
Подобная «каша» — следствие жёсткого ограничения на размер исходников. Автор делится идеей, и более красивыми исходниками: идея, «красивый код»

Кстати, зачем писать на asm, если не задаваться целью написать быстрый код?
Ясное дело, что все из-за ограничения на размер исходников.

Лично я пишу на ассемблере, потому что это интересно само по себе, дает представление о том, как процессор выполняет код и дает отличное представление об организации памяти. Так же можно упомянуть низкоуровневую отладку. Без ассемблера вряд ли получится все это освоить.

А если бы мне нужен был быстрый код, я писал бы на C/C++ и компилировал с оптимизациями )
>>Кстати, зачем писать на asm, если не задаваться целью написать быстрый код?

В последнее время компиляторы умнее разработчиков в программах сложнее сложения двух чисел. После оптимизаций код в большинстве случаев получится более производительным, чем при ручном написании на asm.
Отдельно можно рассмотреть ситуации типа «истории одного байта» или всяких 1k demo, когда все силы брошены на минимальный размер. Тогда да — asm наше все.

Мне вот нравится писать на асме just for fun: начиная с bios/dos программок, и заканчивая GUI софтом типа графического редактора, специфичных обработчиков файлов, да и драйвер с криптографией для win приходилось писать. На более высокоуровневых ЯП это все заняло бы сильно меньше времени, но это банально не интересно :)
Абсолютно не согласен, с тем что компиляторы умнее разработчиков — я как-то писал код изобилущий коммандами битового сдвига, если это писать на си++, а потом взглянуть на дизасембли — то выйдет совершенно невнятная простынь кода, как ни странно на асме получилось короче, напрмер по той причние что компиляторы С/С++ категорически не хотят задейсвовать операции циклического битового сдвига, а на результат линейного сдвига расходуют целый регистр.
Короче не значит быстрее.

Вот некоторым атомам вообще нужно в коротких функциях перед ret поставить пару nop и в результате будет быстрее.
код в большинстве случаев получится

Да, компиляторы иногда тупят. Речь не о небольших частных случаях, а о ситуации в целом — межпроцедурный и межмодульный анализы они выполняют лучше, подчас отлично додумывая за разработчика, подсовывая векторые инструкции, выполняя встраивание (inline) и т.п.
Современные C++ компиляторы пишут код лучше 95% программистов на ассемблере, при условии правильного C++ кода :-)
А что на правах организатора известного соревнования по простым числам можете сказать по поводу сравнения алгоритмов Аткинса и Эратосфена? )
Я могу сказать, что скорость их отличается в разы в лучшем случае, и сильно зависит от реализации => различные трюки и оптимизации позволяют выйти победителем на любом из них.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории