Языки программирования Опции

[Эроласт]

Да не знаю просто знаю что есть где-то

[packa]

Хватить хренью маяться, делом уже займись.

[Berserker]

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

[Эроласт]

Сплайсинг-то не изучен, но я вообще не понял о чем идет речь... Я поолный чайник

[tolich]

Так Берс понял, что ты полный чайник и поставил тебя на огонь, теперь ждёт, когда ты закипишь.

[ChASnock]

Отличная шутка

Нет, правда.

[Эроласт]

Не, не получится мне закипеть, в меня бочку соли высыпали

[tolich]

Программка для Microsoft C++, просеивает числа через решето Эратосфена.

CODE

#include <memory.h>
#include <stdio.h>

typedef unsigned int uint;
typedef unsigned char uchar;

struct set{
uchar *data;
bool testBit(uint i);
void setBit(uint i);
void fill(bool val);
set() { data=new uchar [0x20000000]; }
~set() { delete [] data; }
}
erathosphen;

void set::setBit(uint i)
{
data[i>>3] |= (1<<(i&7));
}

bool set::testBit(uint i)
{
return ((data[i>>3]>>(i&7))&1)==1;
}

void set::fill(bool val)
{
memset(data,val?255:0,sizeof data);
}

void filter(uint value)
{
if(erathosphen.testBit(value)) return;
printf("\r%u",value);
uint i=value*2;
while(i<=0x80000000) { erathosphen.setBit(i); i+=value; }
while(i> 0x80000000) { erathosphen.setBit(i); i+=value; }
}

int main()
{
erathosphen.fill(false);

erathosphen.setBit(0);
erathosphen.setBit(1);

filter(2); filter(3);
for(uint i=6; i<65536; i+=6){
filter(i-1); filter(i+1);
}

printf("\nWriting grid");
FILE *file=fopen("eragrid.bin","wb");
if ( file ) {
fwrite(erathosphen.data,1,0x20000000,file);
fclose(file);
}

printf("\nWriting primaries");
file=fopen("primary.bin","wb");
if ( file ) {
for(uint i=0; i<0xFFFFFFFE; ++i){
if(!erathosphen.testBit(i))
fwrite(&i,4,1,file);
}
fclose(file);
}

return 0;
}

Be warned!

Общий объём результирующих файлов приближается к полутора гигабайтам.

[Etoprostoya]

1) Какого [censored] в теге кода отображаются смайлы!?
2)

Код

    for(uint i=0; i<0xFFFFFFFE; ++i){
      if(!erathosphen.testBit(i))
        fwrite(&i,4,1,file);
    }

Кошмар!

[tolich]

Не волнуйся, начальная фильтрация всё равно дольше.

[Etoprostoya]

Я заметил, но этот цикл впечатлил особо.

[tolich]

P.S. Смайлы поправил.

Я заметил, но этот цикл впечатлил особо.

А что в нём не так?


Конечно, можно было, например, обрабатывать байт целиком и писать до 4 простых чисел зараз, но, мне кажется, такое усложнение совершенно ни к чему для одноразовой задачи.

Можно было, кстати, вообще хранить только данные для чисел 6*i±1.

[Etoprostoya]

Для меня это примерно как

Код

for(uint i=0; i; ++i)

бесконечный цикл с записью в файл. Да там вообще всё не так. Пример того, как не надо писать программы.

[tolich]

Ты не прав, Борис, цикл не бесконечный. Даже если бы там стояло 0xFFFFFFFF, кстати. А всё потому, что шаг всего 1. Вот с фильтрацией пришлось поколдовать, ибо переполнение.

Для меня это примерно как

Код

for(uint i=0; i; ++i)

бесконечный цикл с записью в файл. Да там вообще всё не так. Пример того, как не надо писать программы.

Це ж не бесконечный.

[Etoprostoya]

Ты не прав, Борис, цикл не бесконечный.

Код

for(uint i=0; i; ++i)

Це ж не бесконечный.

Ну да, всего лишь 4 миллиарда прогона цикла
В каждом прогоне проверка, которая идёт не правильно, как ты и сказал, с переполнением 32-битного регистра.
В каждом втором, примерно, прогоне идёт запись в файл. Причём записывается информация из блоков памяти, чтение которых, как я понимаю, скорее всего будет невозможно в нормальной ОС.

Код

fwrite(&i,4,1,file)

При i=0 откуда будет читаться?

[tolich]

Ну да, всего лишь 4 миллиарда прогона цикла

Ты так говоришь, как будто это что-то плохое.

В каждом прогоне проверка, которая идёт не правильно, как ты и сказал, с переполнением 32-битного регистра.

А где я сказал, что это неправильно? На самом деле, так задумано.

Причём записывается информация из блоков памяти, чтение которых, как я понимаю, скорее всего будет невозможно в нормальной ОС.

Тащемта, в файл записывается непосредственно значение i, все 4 байта.

Программа строит битовое множесто на 4294967296 элементов (которое хранится упакованным в байты по 8 bool-ов), в котором будут исключительно составные числа, методом "решета Эратосфена".
Потом записывает это множество на диск, а рядом записывает все числа, которые в это множество не входят.
Где ошибка? По-моему, всё правильно. Что самое забавно, программа работает, и файлы генерирует.

К слову:

в нормальной ОС

Это в какой именно?

[Etoprostoya]

>> Ты так говоришь, как будто это что-то плохое.
Ты так говоришь, как будто это нормально. К тому же я неуверен, что смогут записаться все те 4 миллиарда, а не 2Гб. Это зависит, конечно, от системы.

>> Тащемта, в файл записывается непосредственно значение i
Странно. Я это понимаю не так:

Код

uint i=0;
fwrite(&i,4,1,file) //fwrite(const void*p, size_t size,size_t n,FILE*f);

- неправильно

Код

uint i=0;
fwrite(&erathosphen.data[i],4,1,file);

- правильно

>> Это в какой именно?
В ОС, в которой можно читать не всё подряд, а только то, что можно с правами пользователя. Грубо говоря, в ОС с виртуализацией памяти, если я правильно выразился.

[tolich]

Странно. Я это понимаю не так:

Код

uint i=0;
fwrite(&i,4,1,file) //fwrite(const void*p, size_t size,size_t n,FILE*f);

- неправильно

Код

uint i=0;
fwrite(&erathosphen.data[i],4,1,file);

- правильно

Неправильно понимаешь. В файл записывается значение, хранящееся в переменной i, именно для этого в fwrite передаётся её адрес и размер, а не фрагмент erathosphen.data.
Ещё раз: во второй файл записываются те и только те значения i, которые отсутствуют в множестве erathosphen. Размер primary.bin не 4Г, а всего-то 813120884 байт — всё-таки простые числа встречаются не часто.

[Etoprostoya]

Понятно. Идиотизма Странностей в алгоритме стало чуть-чуть меньше. Но меня вы не заставите применять такую программу, даже если

хранить только данные для чисел 6*i±1

[tolich]

Ну, если тебе внезапно понадобится решето Эратосфена, никто тебя не будет под пытками заставлять использовать мою программу. Ты вполне можешь придумать реализацию покрасивше.
К тому же, моя реализация очень ограничена — выдаёт простые числа только в пределах первых четырёх милливардов. В реальных приложениях (той же криптографии) частенько требуются простые числа куда как больше.