Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 24 25 26 27 28 29 [30] 31 32 33   вперед  Ctrl
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
Двойка посчитана. Давайте разберёмся. Я-бы хотел профиксить возможные баги в самом раннем этапе тестирования.

#Pi
12
23
35
47
511
613
717
819
923
1029
1131
1237
1341
....
9 май 09, 22:23    [7165034]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
студентик
vino, кстати а сколько времени ваша реализция высчитывала приведенные выше числа?
построение решета для диапазона 1..231 на Pentium D 2,8 не превышает 113 секунд. А вот проверка 1001 числа в диапазоне 4611686014132419609..4611686014132420609, конечно, существенно больше, но около 1500 секунд.
IMHO, это малополезная информация, та как сравнивать-то разные проги надо на одном железе.
Топовое число 4611686014132420609 = (231-1)2, т.е. сначала считается решето до (231-1), а потом факторизация
9 май 09, 22:27    [7165039]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
студентик
Решил ускорить проверку на делимость числа. Результат функция опеределяющая является ли указанное число делителем второго числа. У меня повысило работспособность перебора где-то в 1.5 раза... Оговорюсь дает прирост в скорости только для типов Int64.

Ты хочешь сказать что эта функция работает быстрее, чем стандартный MOD или DIV ?
9 май 09, 22:29    [7165041]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
студентик
Решил ускорить проверку на делимость числа. Результат функция опеределяющая является ли указанное число делителем второго числа. У меня повысило работспособность перебора где-то в 1.5 раза... Оговорюсь дает прирост в скорости только для типов Int64.
function IsFactor64(value, divisor: Int64): Boolean;
var
  k: Int64;

begin
  k := divisor shl 1;
  divisor := divisor shr 1;
  while (value >= k) do
    begin
      if Odd(value) then
        begin
          value := value shr 1;
          value := value - divisor
        end
      else
        value := value shr 1
    end;
  Result := (value = k shr 1)
end;

На чем основана замена деления?
9 май 09, 22:30    [7165042]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
студентик
Решил ускорить проверку на делимость числа. Результат функция опеределяющая является ли указанное число делителем второго числа. У меня повысило работспособность перебора где-то в 1.5 раза... Оговорюсь дает прирост в скорости только для типов Int64.

Ты хочешь сказать что эта функция работает быстрее, чем стандартный MOD или DIV ?

Абсолютно верно для 64 бит, для 32бит конечно же уступает. Результаты приведенные программой Vino считало
1) с опрацие mod время - 1 142, 109 (сек)
2) с IsFactor64 время - 797, 703 (сек)
Поэтому рекомендую к тестированию и просьба по возможности огласить результаты работы.
9 май 09, 22:56    [7165055]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
студентик
Поэтому рекомендую к тестированию и просьба по возможности огласить результаты работы.

Мне интересно его происхождение. Не является-ли он следствием из алгоритма Евклида?
9 май 09, 23:10    [7165063]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
vino
студентик
Решил ускорить проверку на делимость числа. Результат функция опеределяющая является ли указанное число делителем второго числа. У меня повысило работспособность перебора где-то в 1.5 раза... Оговорюсь дает прирост в скорости только для типов Int64.
function IsFactor64(value, divisor: Int64): Boolean;
var
  k: Int64;

begin
  k := divisor shl 1;
  divisor := divisor shr 1;
  while (value >= k) do
    begin
      if Odd(value) then
        begin
          value := value shr 1;
          value := value - divisor
        end
      else
        value := value shr 1
    end;
  Result := (value = k shr 1)
end;

На чем основана замена деления?


Алгоритм найден мной вручную и особо не изучен, пока у меня имеется только интуитивные предположения, но скорее всего просто бинарное разложение числа. Например: 51 и предполагаемый делитель 7
1) так как проверяются составные числа вида к1*к2*...кн, где к - простые числа
то данное представление всегда представимо как (к1-1)*к2*...*кн + к2*...*кн, где (к1-1) четно, а значит представисо как 2*р, где р натуральное
2) 51 = 2*25 + 1 = 2*24 + 3 = ... = 2*22 + 7 Значит пытаемся разложить 22 на 7
2*11 11 меньше чем 2*7, а значит чсло неразложимо
пример для 3 2*25 + 1 = 2*24 + 3 = 24 и 3 24 = 2 *12 = 2 * 2 *6 = 2*2*2*3 3=3 делитель совпал
число 3 является делителем 51
9 май 09, 23:13    [7165067]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
студентик
Поэтому рекомендую к тестированию и просьба по возможности огласить результаты работы.

Мне интересно его происхождение. Не является-ли он следствием из алгоритма Евклида?

Возможно...
9 май 09, 23:14    [7165069]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
Студентик. Я попытался портировать твою функцию в С++.

Посмотри. Верно ли я понял смысл функции Odd?

bool IsFactor64(unsigned __int64 value,unsigned __int64 divisor)
{
	unsigned __int64 k=divisor<<1;
	divisor>>=1;
	while(value>=k)
	{
		//if (odd(value)) ???
		//Проверка на то, что число нечётное 
		if ((value&0x1)!=0)
		{
			value>>=1;
			value+=divisor;
		}
		else
		{
			value>>=1;
		}
	}
	return (value==(k>>1))?true:false;
}
9 май 09, 23:22    [7165077]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
Студентик. Я попытался портировать твою функцию в С++.

Посмотри. Верно ли я понял смысл функции Odd?

bool IsFactor64(unsigned __int64 value,unsigned __int64 divisor)
{
	unsigned __int64 k=divisor<<1;
	divisor>>=1;
	while(value>=k)
	{
		//if (odd(value)) ???
		//Проверка на то, что число нечётное 
		if ((value&0x1)!=0)
		{
			value>>=1;
			value+=divisor;
		}
		else
		{
			value>>=1;
		}
	}
	return (value==(k>>1))?true:false;
}

вроде все верно кроме value+=divisor;, надо value-=divisor
9 май 09, 23:29    [7165084]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
студентик
...Абсолютно верно для 64 бит, для 32бит конечно же уступает. Результаты приведенные программой Vino считало
1) с опрацие mod время - 1 142, 109 (сек)
2) с IsFactor64 время - 797, 703 (сек)
Поэтому рекомендую к тестированию и просьба по возможности огласить результаты работы.
Настораживает такое ускорение, так как с Int64 я не раз сталкивался с некоретной работой алгоритма, например, в вычислении корня, так как сдвиговые операции не корректно работали, но быстро выдавали плохой результат
9 май 09, 23:32    [7165087]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
студентик
mayton
Студентик. Я попытался портировать твою функцию в С++.

Посмотри. Верно ли я понял смысл функции Odd?

bool IsFactor64(unsigned __int64 value,unsigned __int64 divisor)
{
	unsigned __int64 k=divisor<<1;
	divisor>>=1;
	while(value>=k)
	{
		//if (odd(value)) ???
		//Проверка на то, что число нечётное 
		if ((value&0x1)!=0)
		{
			value>>=1;
			value+=divisor;
		}
		else
		{
			value>>=1;
		}
	}
	return (value==(k>>1))?true:false;
}

вроде все верно кроме value+=divisor;, надо value-=divisor

Плохо конечно что функция четности не присутсвует, просто боюсь что эффективное сравнение младшего байта value с байт маской будет заменено, на сравнение всех байтов value, надеюсь это мое заблуждение...
9 май 09, 23:33    [7165090]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
студентик
вроде все верно кроме value+=divisor;, надо value-=divisor

ОК. Отлично. Я не обещаю что протестирую сегодня. Я постоянно ломаю свой исходник и "бенчмарки" "плавают" и без того. Кроме того меня - уйма других интересов, но твоя функция уже оставила свой след в моём исходнике с копирайтом (с) Студентик Так что жди...
9 май 09, 23:36    [7165095]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
vino
студентик
...Абсолютно верно для 64 бит, для 32бит конечно же уступает. Результаты приведенные программой Vino считало
1) с опрацие mod время - 1 142, 109 (сек)
2) с IsFactor64 время - 797, 703 (сек)
Поэтому рекомендую к тестированию и просьба по возможности огласить результаты работы.
Настораживает такое ускорение, так как с Int64 я не раз сталкивался с некоретной работой алгоритма, например, в вычислении корня, так как сдвиговые операции не корректно работали, но быстро выдавали плохой результат


Поэтому и предлагаю вам протестирвать А вообще пока ошибок в случае простых обнаружено не было, но кто знает... А вообще считать простые на промежутке 261 с диапазоном в 1000 за 797 секунд это всеравно долго.
9 май 09, 23:40    [7165100]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
mayton
студентик
вроде все верно кроме value+=divisor;, надо value-=divisor

ОК. Отлично. Я не обещаю что протестирую сегодня. Я постоянно ломаю свой исходник и "бенчмарки" "плавают" и без того. Кроме того меня - уйма других интересов, но твоя функция уже оставила свой след в моём исходнике с копирайтом (с) Студентик Так что жди...


Хорошо...
9 май 09, 23:40    [7165101]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
vino
mayton, догадываюсь, что у Вас не посчитаны 1 и 2 как простые числа, я уже выкладывал результаты


Нашёл у себя небольшой баг. Из-за "строгой" проверки условия последнее простое число теоретически могло быть игнорировано.

Было

for(main_type c1=min_prime;c1<max_prime;c1+=2)        

Заменил на

for(main_type c1=min_prime;c1<=max_prime;c1+=2)       
10 май 09, 00:37    [7165170]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
mayton
Двойка посчитана. Давайте разберёмся. Я-бы хотел профиксить возможные баги в самом раннем этапе тестирования.

#Pi
12
23
35
47
511
613
717
819
923
1029
1131
1237
1341
....

Выгрузил простые в файл, но он 1,2Гб и в архиве занял 268Мб, так что не знаю, куда его выкладывать. По смыслу алгоритма "решета" не просматриваются 1,2 и 5.
+ Остальные простые из начала и конца файла
3
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
73
79
83
89
97
101
103
107
109
113
127
131
137
139
149
151
157
163
167
173
179
181
191
193
197
199
...
2147483029
2147483033
2147483053
2147483059
2147483069
2147483077
2147483123
2147483137
2147483171
2147483179
2147483237
2147483249
2147483269
2147483323
2147483353
2147483399
2147483423
2147483477
2147483489
2147483497
2147483543
2147483549
2147483563
2147483579
2147483587
2147483629
2147483647
Time is 150688 msec. Rows = 105097563

Так и получается 3+105097563 = 105097566 простых чисел
10 май 09, 02:15    [7165263]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
Алгоритм проверки множителя приведенный выше неоптимален и неправилен вот истинный вариант...
function IsFactor64(value, divisor: Int64): Boolean;

begin
  while (value >= divisor shl 1) do
     if Odd(value) then
        value := (value - divisor) shr 1
      else
        value := value shr 1;

  Result := (value = divisor)
end;
10 май 09, 05:53    [7165312]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
vino

2147483647
Time is 150688 msec. Rows = 105097563

Так и получается 3+105097563 = 105097566 простых чисел

Забавынй факт. Последннее число в диапазоне знаковых 32-х битных 2147483647 является еще и простым числом Мерсенна (ПЧМ). Следующее ПЧМ равное 2305843009213693951 лежит в "очень высоком" диапазоне, который я достигну очень не скоро со своим брутфосом.
10 май 09, 10:44    [7165378]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
студентик
А вообще считать простые на промежутке 261 с диапазоном в 1000 за 797 секунд это всеравно долго.

Я решил вспомнить юность и открыл книжки по современному ассемблеру. Вот несколько мыслей:

Мысль №1

Можно использовать команды векторных операций SSE. Для выполнения делений (вычисления MOD) пачками. Например рассматривать один 128-битный SSE регистр как два 64-битных. Пример для деления привести не могу т.к. еще не нашёл.

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

vec_res.x = v1.x + v2.x;
vec_res.y = v1.y + v2.y;
vec_res.z = v1.z + v2.z;
vec_res.w = v1.w + v2.w;

Заменяем на

movaps xmm0,address-of-v1          ;xmm0=v1.w | v1.z | v1.y | v1.x 
addps xmm0,address-of-v2           ;xmm0=v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x               
movaps address-of-vec_res,xmm0 

Мысль №2

Можно использовать некоторые MMX-features для разгона узких мест. Следующий пример вычисляет квадратный корень для float.

float isqrt_asm(float x)
{
	float z;
    _asm
    {
        rsqrtss  xmm0, x
        rcpss    xmm0, xmm0
        movss    z, xmm0            // z ~= sqrt(x) to 0.038%
    }
    return z;	
}

Надо только поискать целочисленный аналог rsqrtss для диапазона 64бит. К сожалению я не сильно крут в асме. т.к. кодил сравнительно давно, да и под наборы команд i386. Но может быть в форуме кто-то уже в курсе этих новых веяний. У меня "на борту" стоит довольно мощная железяка - двухголовый Athlon X2. И жалко будет не использовать его возможностей.
10 май 09, 11:19    [7165393]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
студентик
Алгоритм проверки множителя приведенный выше неоптимален и неправилен вот истинный вариант...
function IsFactor64(value, divisor: Int64): Boolean;

begin
  while (value >= divisor shl 1) do
     if Odd(value) then
        value := (value - divisor) shr 1
      else
        value := value shr 1;

  Result := (value = divisor)
end;

Остаются сомнения в том, что операция машинного деления медленнее, чем вызов функции - это же нонсенс!
10 май 09, 11:38    [7165409]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
mayton
Я решил вспомнить юность и открыл книжки по современному ассемблеру. Вот несколько мыслей:

Мысль №1
Можно использовать команды векторных операций SSE. Для выполнения делений (вычисления MOD) пачками. Например рассматривать один 128-битный SSE регистр как два 64-битных. Пример для деления привести не могу т.к. еще не нашёл...

Мысль №2
Можно использовать некоторые MMX-features для разгона узких мест...

Для мысли №2 простой ответ - везде есть сопроцессор, так что рулит только целочисленное вычисление корня.
Насчет векторных операций - они приспособлены к матричной обработке, а рассмотренные нами алгоритмы - последовательные. Правда при факторизации, как раз, можно фиксированно ускорится, но это не связано с распараллеливанием вычислений на несколько CPU.
Посмотрите в этом направлении, очень полезный ресурс
10 май 09, 12:00    [7165418]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
mayton
Member

Откуда: loopback
Сообщений: 40417
Спасибо. Почитаю.
10 май 09, 12:29    [7165431]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
студентик
Member

Откуда: Альфа Центавра
Сообщений: 294
vino
студентик
Алгоритм проверки множителя приведенный выше неоптимален и неправилен вот истинный вариант...
function IsFactor64(value, divisor: Int64): Boolean;

begin
  while (value >= divisor shl 1) do
     if Odd(value) then
        value := (value - divisor) shr 1
      else
        value := value shr 1;

  Result := (value = divisor)
end;

Остаются сомнения в том, что операция машинного деления медленнее, чем вызов функции - это же нонсенс!


В том то и дело, что тип int64 неподдерживается нашими компиляторами, которые разлагают его на два 32бит источника. Да и думаю использование 64бит ресурсов современного проца, пока еще неоравданно в связи с перенеосимостью программы, хотя если есть желание... данный алгоритм конечно же проигрывает целочисленной mod, но ТОЛЬКО для 32 бит. Для 64 бит операция взятия остатка заменяется компилятором, на громоздкие подпрограммы, поэтому данный алгоритм и выигрывет, но это наверняка справедливо только для режима эмуляции 64 бит. Если вы используете свой проц на макс, имеется поддержка 64бит как процессором так и компилятором, еще и ОС, то тогад дела будут обстоять по другому...
10 май 09, 13:27    [7165486]     Ответить | Цитировать Сообщить модератору
 Re: решение тривиальной алгоритмической задачи разными подходами и средствами  [new]
vino
Member

Откуда:
Сообщений: 1191
студентик, IsFactor64(6,2) = false, IsFactor64(7,2) = true
Что не так?
10 май 09, 14:23    [7165516]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 24 25 26 27 28 29 [30] 31 32 33   вперед  Ctrl
Все форумы / Программирование Ответить