ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи
76 сообщений из 76, показаны все 4 страниц
  все  
Решение одной задачи
    #38915939
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Здравствуйте. Решал сегодня одну задачу (и кстати воспользовался типом данных из языка С++ что мне давеча посоветовали). На 8 тесте валится. Вероятно проблема с алгоритмом. Подскажите пожалуйста как бы её решали на языке С++ или С.

Текущее решение (проблема с 8 тестом)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
#include <stdio.h>
#include <stdlib.h>

int count_op(int z, int s)
{
	if (z == s) return 0;
	div_t d = div(z, s);
	if (z==0 || s==0 || d.rem != 0 || z / s < 0) return -1;
	int t = 0;
	while (d.quot == 0){
		d.quot /= 2;
		t += 1;
	}
	int delta = (d.quot == 1) ? 1 : 0;
	return t * 2 + d.quot - delta;
}


int main()
{
	int z, s;
	FILE* in = freopen("input.txt", "r", stdin);
	scanf("%i %i", &s, &z);
	fclose(in);
	FILE* out = freopen("output.txt", "w", stdout);
	printf("%i", count_op(z, s));
	fclose(out);
	return 0;
}




PS
Данная тема скорее относится к разделу Программирование, но в связи очередной недавней дискриминацией самого себя (подраздела Программирования) , больше не хочу задавать вопросов в том разделе. С другой стороны, я не сторонник строгой дифференциации, тем более, инструментом решения данной конкретной задачи является семейство языков С/С++
...
Рейтинг: 0 / 0
25.03.2015, 09:26
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38915986
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
С проверками разберись. Сначала на ноль делишь, а потом проверяешь что s==0

Про div() тут как-раз прекрасный пример что не надо читаемостью жертвовать.
Написал бы вместо него
Код: plaintext
1.
quot = z / s;


не накосячил бы с делением на ноль.

Это бесконечный цикл
Код: plaintext
1.
2.
3.
4.
	while (d.quot == 0){
		d.quot /= 2;
		t += 1;
	}
...
Рейтинг: 0 / 0
25.03.2015, 09:59
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916011
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Раз уж ты за супер-мега оптимизаторство борешься, то
Код: plaintext
1.
t += 1;


и
Код: plaintext
1.
t++;


это разные операции для процессора. Есть отдельная команда процессора ( INC ) для увеличения на 1, она быстрее чем сложение ( ADD ), и сложение требует отдельного хранения второго слагаемого.
...
Рейтинг: 0 / 0
25.03.2015, 10:11
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916020
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
По первому замечанию согласен, рефакторинг

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
int count_op(int z, int s)
{
	if (z == s)	return 0;
	if (z == 0 || s == 0)
exit:
	return -1;
	div_t d = div(z, s);
	if (d.rem != 0 || d.quot < 0) goto exit;

	int t = 0;
	while (d.quot == 0){
		d.quot /= 2;
		++t;
	}
	int delta = (d.quot == 1) ? 1 : 0;
	return t * 2 + d.quot - delta;
}



Бесконечного цикла, как мне кажется, быть не должно.. Может что-то не учёл, но такой контрпример не могу подобрать
...
Рейтинг: 0 / 0
25.03.2015, 10:18
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916021
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima TЕсть отдельная команда процессора ( INC ) для увеличения на 1, она быстрее чем сложение ( ADD ), и сложение требует отдельного хранения второго слагаемого.
Я думаю, что и в этом случае компилятор умнее программиста и выберет то что быстрее ))
...
Рейтинг: 0 / 0
25.03.2015, 10:18
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916022
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Дмитрий, просто

Код: plaintext
1.
t+=1;



смотрится красивее чем унарный инкремент :)
Но я исправил
...
Рейтинг: 0 / 0
25.03.2015, 10:20
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916023
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercury,

За goto внутрь if надо отрывать руки.
Не говоря уже о том, что goto тут нафиг не нужен.
...
Рейтинг: 0 / 0
25.03.2015, 10:21
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916030
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly MoskovskySashaMercury,

За goto внутрь if надо отрывать руки.
Не говоря уже о том, что goto тут нафиг не нужен.

Дело в том, что вы конечно в чём то правы, но мне захотелось посмотреть как будет выглядеть код с goto :) Например, недавно я увидел код Дмитрия следующего вида
Код: plaintext
1.
2.
3.
	while (smth){
		smth do;
	}



И хотя ранее, я никогда не использовал такую стилистику в своём коде, мне понравилось, потому что я увидел как это выглядит. А теперь использую. Вот и сейчас захотел посмотреть :)
...
Рейтинг: 0 / 0
25.03.2015, 10:26
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916031
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Anatoly MoskovskyЯ думаю, что и в этом случае компилятор умнее программиста и выберет то что быстрее ))
Чего тут думать, проверить просто:
Код: plaintext
1.
2.
3.
4.
5.
	int x = GetTickCount();
0040100C  call        dword ptr [__imp__GetTickCount@0 (40A000h)] 
00401012  mov         esi,eax 
	x+=1;
00401014  add         esi,1


MS VC 2008 Express. Сборка Release c дефолтными настройками оптимизации

Не особо умный :)
...
Рейтинг: 0 / 0
25.03.2015, 10:27
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916053
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Dima T,

В Express ограничен уровень оптимизаций, так что этот пример ни о чем не говорит.
А например gcc генерит одинаковый код для +=1 и ++.
...
Рейтинг: 0 / 0
25.03.2015, 10:36
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916055
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercury
Код: plaintext
1.
2.
3.
4.
5.
	if (z == 0 || s == 0)
exit:
	return -1;
	div_t d = div(z, s);
	if (d.rem != 0 || d.quot < 0) goto exit;



вместо goto exit рука не поднялась написать return -1?
Забудь про goto, особенно в таком извращенном применении.

SashaMercuryБесконечного цикла, как мне кажется, быть не должно..
А если подумать головой? Не буду подсказывать, сам догадайся.
...
Рейтинг: 0 / 0
25.03.2015, 10:36
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916063
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryмне понравилось, потому что я увидел как это выглядит. А теперь использую.
Ну кому-то и бухать и колоться нравится. Но это не повод ))
...
Рейтинг: 0 / 0
25.03.2015, 10:39
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916073
wst
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
wst
Участник
Глупый вопрос - чему будет равно t на выходе из
Код: plaintext
1.
while (d.quot == 0){...

если d.quot перед входом в цикл =0?
 
И с какой стати этому циклу вообще завершаться?
...
Рейтинг: 0 / 0
25.03.2015, 10:42
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916079
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercury,

goto можно применять только если в функции есть нетривиальный завершающий код, который надо вызывать из разных веток кода.
Все остальные варианты goto - бессмысленны и вредны.
Схема использования такая:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
int func()
{
    init();
    maincode();
    if (error) goto error:
    maincode();    
    cleanup();
    return 0;
    
error:    
    cleanup();
    return -1;
}
...
Рейтинг: 0 / 0
25.03.2015, 10:44
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916094
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Anatoly MoskovskyDima T,

В Express ограничен уровень оптимизаций, так что этот пример ни о чем не говорит.
А например gcc генерит одинаковый код для +=1 и ++.
Говорит что все компиляторы разные. Полной версии MS VC нет чтобы сравнить. Хотя тот же экспрес оптимизирует такую конструкцию
Код: plaintext
1.
2.
3.
4.
5.
6.
	int x = 1;
	x+=1;
	printf("%d\n", x);
0040100B  push        2    
0040100D  push        offset string "%d\n" (40B3C4h) 
00401012  call        printf (401038h)



И вообще не оптимизирует div()
Код: plaintext
1.
2.
3.
4.
div_t d = div(4, 2);
0040100B  push        2    
0040100D  push        4    
0040100F  call        div (401041h)


Саш, div() это тормоз, по крайней мере в MSVC Express
...
Рейтинг: 0 / 0
25.03.2015, 10:49
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916214
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryНапример, недавно я увидел код Дмитрия следующего вида
Код: plaintext
1.
2.
3.
	while (smth){
		smth do;
	}



И хотя ранее, я никогда не использовал такую стилистику в своём коде, мне понравилось, потому что я увидел как это выглядит. А теперь использую. Вот и сейчас захотел посмотреть :)
Это основы. Причем любого языка, а не только С. Три вида циклов: for(), while() и do ... while()
Если плохо понимаешь как они работают - потрать время на изучение.

while() работает так
Код: plaintext
1.
2.
3.
4.
5.
6.
:while
if(d.quot == 0){
	d.quot /= 2;
	t += 1;
	goto while;
}


SashaMercuryБесконечного цикла, как мне кажется, быть не должно.. Может что-то не учёл, но такой контрпример не могу подобрать
Весь код не посмотрел сразу, в твоем случае не зациклится потому что цикл никогда не выполнится, т.к. все варианты где d.quot == 0 у тебя отсекают предварительные проверки. Т.е. ты написал ненужный кусок кода. Тоже косяк, т.к. зачем-то ты его писал.

PS В суть алгоритма не вдумывался, просто указал на очевидные ошибки.
...
Рейтинг: 0 / 0
25.03.2015, 11:59
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916232
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
Anatoly MoskovskyЗа goto внутрь if надо отрывать руки.каждый начинающий программист должен понаступать на все старые грабли, они ведь так удобно лежат
...
Рейтинг: 0 / 0
25.03.2015, 12:04
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916250
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
Dima TЭто бесконечный цикл
Код: plaintext
1.
2.
3.
4.
	while (d.quot == 0){
		d.quot /= 2;
		t += 1;
	}

с чего бы? d.quot целое ведь.

а вот эта конструкция бессмыссленна:
Код: plaintext
1.
int delta = (d.quot == 1) ? 1 : 0;

ведь только что мы добились того, чтобы d.quot стало равным 0, оно никогда не сможет стать равным 1 )))
...
Рейтинг: 0 / 0
25.03.2015, 12:11
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916300
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
egorychс чего бы? d.quot целое ведь.
0 / 2 сколько будет?
...
Рейтинг: 0 / 0
25.03.2015, 12:29
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916302
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SashaMercuryкак бы её решали на языке С++ или С.
Я бы сначала проверил и отсёк краевые условия:
Код: sql
1.
2.
3.
4.
if (x==y) return 0;
if (x>0 && y<0) return -1;
if (x<0 && y>0) return -1;
if (y%x != 0) return -1;



Потом я бы воспользовался следующим алгоритмом:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
static int primaries[] = {2,3,5,7,...};

result = 0;
for (int i = 0; i<sizeof(primaries)/sizeof(int) && primaries[i]<sqrt(y); ++i)
{
   if (y%primaries[i] == 0)
   {
     y /= primaries[i];
     if (x%primaries[i] == 0)
       x /= primaries[i];
     else
       result += primaries[i];
     if (y == 1)
       return result;
   }
   return -1;
}


Тебе, как математику, должно быть очевидно как он работает.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
25.03.2015, 12:31
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916318
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
Dima Tegorychс чего бы? d.quot целое ведь.
0 / 2 сколько будет?нормально я затупил, качественно прошу прощения
...
Рейтинг: 0 / 0
25.03.2015, 12:42
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916434
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
А по здравому размышлению алгоритм сводится к следующему?
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
if (x==y) return 0;
if (x>0 && y<0) return -1;
if (x<0 && y>0) return -1;

int a = y/x;
int b = y%x;
if (b != 0) return -1;

static int primaries[] = {2,3,5,7,...};

result = 0;
for (int i = 0; i<sizeof(primaries)/sizeof(int) && primaries[i]<sqrt(a); ++i)
{
   if (a%primaries[i] == 0)
   {
     a /= primaries[i];
     result += primaries[i];
     if (a == 1)
       return result;
   }
}
return -1;
...
Рейтинг: 0 / 0
25.03.2015, 13:48
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916773
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ммм.... primes... вкуснятина.
...
Рейтинг: 0 / 0
25.03.2015, 16:50
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916816
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
maytonprimes... вкуснятина.
А без них в одну секунду не уложиться на верхнем конце диапазона.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
25.03.2015, 17:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916842
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Почитал условия. В принципе задача сводится к разложению частного двух чисел на простые множители, а затем эти множители надо сложить.

 
Мой вариант
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
	if(x == y) return 0;
	if(x == 0 || y % x != 0) return -1;
	int a = y/x;
	if (a <= 0) return -1;

	static int primaries[] = {2,3,5,7 ... до 10^9};

	int result = 0;
	int i = 0;
	while(a > 1) {
		if(a % primaries[i] == 0) {
			a /= primaries[i];
			result += primaries[i];
			i = 0;
		} else {
			i++;
			if(i >= sizeof(primaries)/sizeof(int)) return -2; // таблица primeries маленькая
		}
	}
	return result;

...
Рейтинг: 0 / 0
25.03.2015, 17:49
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916853
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima TМой вариант
А, чёрт, точно, я не учёл, что один множитель может повторяться.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
25.03.2015, 18:00
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916886
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima TМой вариант
А, чёрт, точно, я не учёл, что один множитель может повторяться.

еще не учел что всего один множитель может быть (sqrt(a) не в тему)
...
Рейтинг: 0 / 0
25.03.2015, 18:45
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916887
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Можно наверное из цикла выскочить раньше.
...
Рейтинг: 0 / 0
25.03.2015, 18:48
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916888
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry Sibiryakovя не учёл, что один множитель может повторяться.

Хотя я тоже лишнее написал:
Код: plaintext
1.
i = 0;


достаточно что i++ не выполняется.
...
Рейтинг: 0 / 0
25.03.2015, 18:49
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916892
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМожно наверное из цикла выскочить раньше.
Вроде нет. Крайние варианты (1,7) = 7 и (1,8) = 6
...
Рейтинг: 0 / 0
25.03.2015, 18:54
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917155
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryНапример, недавно я увидел код Дмитрия следующего вида
Код: plaintext
1.
2.
3.
	while (smth){
		smth do;
	}



И хотя ранее, я никогда не использовал такую стилистику в своём коде, мне понравилось, потому что я увидел как это выглядит. А теперь использую. Вот и сейчас захотел посмотреть :)
Это основы. Причем любого языка, а не только С. Три вида циклов: for(), while() и do ... while()
Если плохо понимаешь как они работают - потрать время на изучение.



Дима, да при чём тут основы с циклами, стилистика со скобками понравилась, я ведь написал
Ранее, меня беспокоил такой код
Код: plaintext
1.
2.
3.
4.
while(smth)
{
   smth do;//1 строка
}


но я увидел у тебя
Код: plaintext
1.
2.
3.
while(smth) {
   smth do;//1 строка
}


и мне понравилось


И да, я знаю что можно так
Код: plaintext
1.
2.
3.
while(smth) 
   smth do;//1 строка



но мне не нравится :)
...
Рейтинг: 0 / 0
26.03.2015, 01:41
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917156
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima T
SSБесконечного цикла, как мне кажется, быть не должно..
А если подумать головой? Не буду подсказывать, сам догадайся.


не должно быть бесконечного цикла никогда. Он может быть только если на входе 0, этот вариант отсекается
...
Рейтинг: 0 / 0
26.03.2015, 01:46
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917164
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Простых чисел порядка 80000, не очень удобно будет хранить их таким образом (в коде программы)
...
Рейтинг: 0 / 0
26.03.2015, 02:08
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917166
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
SashaMercuryПростых чисел порядка 80000, не очень удобно будет хранить их таким образом (в коде программы)

можно генерировать, это не проблема конечно
...
Рейтинг: 0 / 0
26.03.2015, 02:09
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917198
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДима, да при чём тут основы с циклами, стилистика со скобками понравилась, я ведь написал
Так и упоминул бы сразу про скобки, я про эту мелочь и не подумал, нафантазировал непонятно чего :)

Так код компактнее, меньше строк со скобками. Вопрос из серии "На вкус и цвет ...".

SashaMercuryИ да, я знаю что можно так
Код: plaintext
1.
2.
3.
while(smth) 
   smth do;//1 строка



но мне не нравится :)
И правильно, не надо так писать, накосячить легко, добавишь так строчку
Код: plaintext
1.
2.
3.
4.
while(smth) 
   smth do;//1 строка
   smth do2;//+1 строка


и визуально кажется что в цикл добавил, а реально за него.
Поэтому без скобок только так
Код: plaintext
1.
while(smth) smth do;


правда так дебагером отлаживать неудобно.
SashaMercuryне должно быть бесконечного цикла никогда. Он может быть только если на входе 0, этот вариант отсекается
Так и не понял чтоли? Если на входе 0, то твой цикл начнет выполнятся и зациклится, если не 0, то цикл не будет выполнятся. Т.к. у тебя на входе 0 быть не может (из-за предварительных проверок), то код в цикле никогда не выполнится. Зачем он тогда написан?
...
Рейтинг: 0 / 0
26.03.2015, 07:17
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917204
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercurySashaMercuryПростых чисел порядка 80000, не очень удобно будет хранить их таким образом (в коде программы)

можно генерировать, это не проблема конечно
Можно, только зачем? Если известно что они нужны, в итоге те же 80000 будут вычислены, просто при каждом запуске проги будет теряться время на этот бесполезный расчет.

Можешь скомбинировать для универсальности: первые брать из массива, как потребуется больше - считать.
...
Рейтинг: 0 / 0
26.03.2015, 07:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917231
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TТ.к. у тебя на входе 0 быть не может (из-за предварительных проверок), то код в цикле никогда не выполнится. Зачем он тогда написан?

Почему код в цикле никогда не выполнится ? Например 8/1=8. Цикл выполнится трижды 8->4, 4->2, 2->1
...
Рейтинг: 0 / 0
26.03.2015, 08:26
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917243
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Я кажется не то написал.. Там должно быть .rem, как у меня тогда до 8 теста программа дошла. Прошу прощение
...
Рейтинг: 0 / 0
26.03.2015, 08:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917244
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
А я думаю, что такое, что там не понятного в том цикле :D
...
Рейтинг: 0 / 0
26.03.2015, 08:33
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917252
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryЯ кажется не то написал..
Я на это и намекал :)

SashaMercuryкак у меня тогда до 8 теста программа дошла.
Отлаживать надо лучше. Придумывай нехорошие варианты. Смотри как отработает.
Вот мой набор:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
(1,1)=0
(-2,-6)=3
(1,8)=6
(2,5)=-1
(1,5)=5
(5,0)=-1
(0,5)=-1
(3,15)=5
(0,0)=0
(2,2)=0
(2,-2)=-1
...
Рейтинг: 0 / 0
26.03.2015, 08:40
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917273
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
	for (int i = 1; i < 90; ++i)
	{
		int res1=count_op_from_Dima(i, 1);
		int res2=count_op(i, 1);
		printf("%3i   %3i   %3i   %3i\n", i, res1, res2, res1 - res2);
	}


Мой алгоритм не оптимальный


 
1 0 0 0
2 2 2 0
3 3 3 0
4 4 4 0
5 5 5 0
6 5 5 0
7 7 7 0
8 6 6 0
9 6 9 -3
10 7 7 0
11 11 11 0
12 7 7 0
13 13 13 0
14 9 9 0
15 8 15 -7
16 8 8 0
17 17 17 0
18 8 11 -3
19 19 19 0
20 9 9 0
21 10 21 -11
22 13 13 0
23 23 23 0
24 9 9 0
25 10 25 -15
26 15 15 0
27 9 27 -18
28 11 11 0
29 29 29 0
30 10 17 -7
31 31 31 0
32 10 10 0
33 14 33 -19
34 19 19 0
35 12 35 -23
36 10 13 -3
37 37 37 0
38 21 21 0
39 16 39 -23
40 11 11 0
41 41 41 0
42 12 23 -11
43 43 43 0
44 15 15 0
45 11 45 -34
46 25 25 0
47 47 47 0
48 11 11 0
49 14 49 -35
50 12 27 -15
51 20 51 -31
52 17 17 0
53 53 53 0
54 11 29 -18
55 16 55 -39
56 13 13 0
57 22 57 -35
58 31 31 0
59 59 59 0
60 12 19 -7
61 61 61 0
62 33 33 0
63 13 63 -50
64 12 12 0
65 18 65 -47
66 16 35 -19
67 67 67 0
68 21 21 0
69 26 69 -43
70 14 37 -23
71 71 71 0
72 12 15 -3
73 73 73 0
74 39 39 0
75 13 75 -62
76 23 23 0
77 18 77 -59
78 18 41 -23
79 79 79 0
80 13 13 0
81 12 81 -69
82 43 43 0
83 83 83 0
84 14 25 -11
85 22 85 -63
86 45 45 0
87 32 87 -55
88 17 17 0
89 89 89 0
...
Рейтинг: 0 / 0
26.03.2015, 08:58
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917284
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryМой алгоритм не оптимальный
Ожидаемо, ты же только два простых числа взял (1 и 2), совпали только варианты где частное раскладывается на X или X*2^N, где X простое.
3*3 уже не обработалось.
...
Рейтинг: 0 / 0
26.03.2015, 09:08
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917296
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМожно наверное из цикла выскочить раньше.
Точно, можно, достаточно таблицы до sqrt(10^9) если не путаю

Саша допиливай идею :)
...
Рейтинг: 0 / 0
26.03.2015, 09:21
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917343
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TmaytonМожно наверное из цикла выскочить раньше.
Точно, можно, достаточно таблицы до sqrt(10^9) если не путаю

Саша допиливай идею :)

У меня осталось полчаса сегодня. Вечером компьютера не будет( Сейчас попробую
...
Рейтинг: 0 / 0
26.03.2015, 09:57
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917364
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Дополнил, а проверить не могу, сервер не работает у них, вероятно
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
#include <stdio.h>
#include <math.h>

int isPrime(int x)
{
	if (x == 1)    return 0;
	for (int i = 2; i <= (int)sqrt((float)x); ++i){
		if (x%i == 0)    return 0;
	}
	return 1;
}

int get_next_prime(int cur_pr)
{
	while (1){
		if (isPrime(++cur_pr))   return cur_pr;
	}
}

int count_op_from_Dima(int y, int x)
{
	if (x == y) return 0;
	if (x == 0 || y % x != 0) return -1;
	int a = y / x;
	if (a <= 0) return -1;

	int pr = 2;
	int result = 0;
	while (a > 1) {
		if (a % pr == 0) {
			a /= pr;
			result += pr;
		}
		else {
			pr = get_next_prime(pr);
		}
	}
	return result;

}


int main()
{
	int z, s;
	FILE* in = freopen("input.txt", "r", stdin);
	scanf("%i %i", &s, &z);
	fclose(in);
	FILE* out = freopen("output.txt", "w", stdout);
	printf("%i", count_op_from_Dima(z, s));
	fclose(out);
	return 0;
}

...
Рейтинг: 0 / 0
26.03.2015, 10:13
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917385
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
На 7 тесте time limit, хм. Уже нет времени отлаживать, завтра доделаю, мне пора выключать компьютер (
Спасибо :)
...
Рейтинг: 0 / 0
26.03.2015, 10:27
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917390
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДополнил
Коряво дополнил, посчитай (1, 982451653) и подумай как еще ускорить.
...
Рейтинг: 0 / 0
26.03.2015, 10:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917398
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
почитай про алгоритмы проверки на простое
http://habrahabr.ru/post/122538/
http://habrahabr.ru/post/133037/
...
Рейтинг: 0 / 0
26.03.2015, 10:38
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917412
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
допилил код Dima T
с таблицей целых чисел тест проходит
 
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
#include <fstream>
using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");
int n,s;

int count_primes(int n, int s)
{
    static int primaries[] = {2,3,5,7,11,13,17,19,23,29,
                              ...
                              31607,31627,31643,31649,31657,31663,31667,31687,31699,31721
                             };

    int c = 0;

    if(s==n)
    {
        //c = 0;
    }
    else if(n==0 || s==0 || s/n<0 || s%n)
    {
        c = -1;
    }
    else
    {
        s = s / n;

        int i=0;
        while(s > 1)
        {
            if(s % primaries[i] == 0)
            {
                s /= primaries[i];
                c += primaries[i];
                i = 0;
            }
            else
            {
                i++;
                if(i >= sizeof(primaries)/sizeof(int)) return c + s;
            }
        }
    }

    return c;
}

int main()
{
    cin>>n>>s;

    cout << count_primes(n, s);

}

...
Рейтинг: 0 / 0
26.03.2015, 10:46
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917560
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SashaMercuryНа 7 тесте time limit, хм.
Я же говорил, что без таблицы в одн секунду не уложиться. Не хочется хранить её прямо в
коде - ситай из внешнего файла если это позволено.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
26.03.2015, 12:38
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917569
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
int isPrime(int x)
{
	if (x == 1)    return 0;
	for (int i = 2; i <= (int)sqrt((float)x); ++i){
		if (x%i == 0)    return 0;
	}
	return 1;
}



Это неоптимально. При проверке на Prime можно сразу скипать чётные числа. Шаг делать равным 2.
А двойку проверить отдельно вне цикла.

Код: plaintext
1.
	for (int i = 3; i <= (int)sqrt((float)x); i+=2){



Это нужно выкинуть нафиг.
Код: plaintext
1.
sqrt((float)x)



Есть инкрементальный целочисленный расчёт квадратного корня. Есть просто целочисленный квадратный
корень.

Ищите в форуме мои посты 2-х годичной давности. Там генератор простых чисел обсуждался.

+
Если уже имеется вектор расчитанных простых то их можно использовать в качестве делителей.
...
Рейтинг: 0 / 0
26.03.2015, 12:43
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917631
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Без таблицы никак, иначе считать каждый раз. Тут хорошо расписана оптимизация генераторов. http://habrahabr.ru/post/122538/
 
Переписал оттуда генератор на С
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
#include <stdio.h>
#include <vector>

std::vector<int> primaries;

void fill_primaries(int max)
{
	primaries.clear();
	primaries.push_back(2);
	for(int i = 3; i <= max; i += 2) {
		int* k = &primaries[0];
		for(int j = primaries.size(); j > 0 && i % *k != 0; j--,k++) {
			if(*k * *k > i) {
				primaries.push_back(i);
				break;
			}
		}
	}
}

void  main(){
	fill_primaries(31623);
	for(int j = 0; j < primaries.size(); j++) printf("%d ", primaries[j]);
}


До миллиона за десятки мс генерит, если больше надо - тут алгоритмы посерьезнее http://habrahabr.ru/post/133037/
...
Рейтинг: 0 / 0
26.03.2015, 13:16
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918337
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Вы меня испугали. Я уже подумал что нужно больше отдыхать, если я так сильно ошибался когда пытался решить данную задачу без дополнительных затрат статической памяти. Но это оказалось не так. Вообще говоря, Кнут(если не ошибаюсь) пишет примерно следующее: если число вариантов перебора менее 10! то можно использовать перебор. В данном конкретном случае, мы имели дело с простыми числами в диапазоне . Согласитесь, это немного. Потеря производительности была на другом участке кода, ниже рефакторинг с оптимизациями касаемо поиска простых чисел (они не играют решающую роль, можно оставить их как и прежде), и изменением в алгоритме Дмитрия

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
#include <stdio.h>
#include <math.h>

//assume x>1
int isPrime(int x)
{
	for (int i = 3; i <= sqrtl((long double)x); i+=2){
		if (x%i == 0)    return 0;
	}
	if (x % 2 == 0)    return 0;
	return 1;
}

int get_next_prime(int cur_pr)
{
	if (cur_pr == 2)	return 3;
	while (1){
		cur_pr += 2;
		if (isPrime(cur_pr))	return cur_pr;
	}
}

int count_op_from_Dima(int y, int x)
{
	if (x == y) return 0;
	if (x == 0 || y == 0 || y % x != 0 || y / x < 0) return -1;
	int a = y / x;
	
	int res = 0;
	int pr = 2;
	while (a > 1 && pr<=sqrt((float)a)) {
		if (a % pr == 0) {
			a /= pr;
			res += pr;
		}
		else {
			pr = get_next_prime(pr);
		}
	}
	if (a > 0) res += a;
	return res;

}


int main()
{
	int z, s;
	FILE* in = freopen("input.txt", "r", stdin);
	scanf("%i %i", &s, &z);
	fclose(in);
	FILE* out = freopen("output.txt", "w", stdout);
	printf("%i", count_op_from_Dima(z, s));
	fclose(out);
	return 0;
}
...
Рейтинг: 0 / 0
27.03.2015, 06:39
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918340
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Не удержался C:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
//assume x>1
int isPrime(int x)
{
	for (int i = 3; i <= sqrtl((long double)x); i+=2){
		if (x%i == 0)    return 0;
	}
	return x % 2;
}
...
Рейтинг: 0 / 0
27.03.2015, 06:44
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918353
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Хотя если так подумать, это не изменения в алгоритме Дмитрия(ибо его алгоритм предназначен для таблицы простых числе куда может входить число а), а модификация алгоритма для решения задачи без статической таблицы
...
Рейтинг: 0 / 0
27.03.2015, 07:08
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918358
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
От моего алгоритма только каркас остался :) Еще была версия m_Sla 17433850

Это лишнее
Код: plaintext
1.
if (a > 0) res += a;


a всегда больше 0

и sqrtl((long double)x) не панацея: от того что точность повышаешь она идеальной не становится, нет гарантии что корень из 9 не получится 2.999999999999999 и приведется к 2, я бы так писал
Код: plaintext
1.
sqrt((float)x) + 1
...
Рейтинг: 0 / 0
27.03.2015, 07:40
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918362
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Я выше ссылки на статью про генераторы давал, не почитал? Там хорошая мысль была как корни не считать.
Это
Код: plaintext
1.
i <= sqrtl((long double)x)


равносильно этому
Код: plaintext
1.
i*i <= x


В принципе ничего гениального, но все считают корни.
...
Рейтинг: 0 / 0
27.03.2015, 07:52
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918388
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Да, сравнивать нет смысла, строчка лишняя. Можно сравнивать произведение, знаю об этом.
Ознакомился с информацией по ссылкам, спасибо :) но т.к. я этой проблемой глубоко не занимаюсь, и пока не планирую, не стал углубляться. Решето Эратосфена мне знакомо давно. Аткина, в общих чертах знал, сейчас посмотрел ещё раз )
...
Рейтинг: 0 / 0
27.03.2015, 08:47
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918485
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RWolf
Участник
Dima T,

более того, такой for вообще ересь — условие выхода из цикла считается заново каждую итерацию, при том, что оно не меняется.
...
Рейтинг: 0 / 0
27.03.2015, 10:00
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918539
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
RWolfболее того, такой for вообще ересь — условие выхода из цикла считается заново каждую итерацию, при том, что оно не меняется.
В целом согласен, но в данном случае корень тоже считается каждую итерацию, но наверно компилятор это оптимизирует.

В принципе цикл можно соптимизировать расчетом последовательности квадратов:
Код: plaintext
1.
2.
3.
4.
5.
x = 1;
x2 = 1;
while(x < ...) {
x2 += 2*x + 1;
x++;}
...
Рейтинг: 0 / 0
27.03.2015, 10:29
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918558
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RWolf
Участник
Dima T,

простой тест:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
int count_op(int z)
{
  int x=1;
  for (int i=0; i<sqrt(z);i++)
    x*=2;
  return x;
}



 
gcc -std=c99 -O2 -S 1.c .globl _count_op
.def _count_op; .scl 2; .type 32; .endef
_count_op:
LFB39:
.cfi_startproc
pushl %esi
.cfi_def_cfa_offset 8
.cfi_offset 6, -8
pushl %ebx
.cfi_def_cfa_offset 12
.cfi_offset 3, -12
subl $36, %esp
.cfi_def_cfa_offset 48
xorl %ebx, %ebx
movl $1, %esi
fildl 48(%esp)
fstpl 16(%esp)
jmp L4
.p2align 2,,3
L5:
sall %esi
incl %ebx
L4:
fldl 16(%esp)
fstpl (%esp)
call _sqrt
movl %ebx, 28(%esp)
fildl 28(%esp)
fxch %st(1)
fucompp
fnstsw %ax
testb $69, %ah
je L5
movl %esi, %eax
addl $36, %esp
.cfi_def_cfa_offset 12
popl %ebx
.cfi_restore 3
.cfi_def_cfa_offset 8
popl %esi
.cfi_restore 6
.cfi_def_cfa_offset 4
ret
.cfi_endproc

call _sqrt в каждой итерации, хотя, казалось бы, оптимизация включена.
...
Рейтинг: 0 / 0
27.03.2015, 10:40
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918582
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Понравилась идея SashaMercury с get_next_prime(), переделал немного свой генератор 17434730
 
Расчет следующего простого с кэшем
Заменил глобальный массив на static и добавил дописывание кэша по необходимости
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
#include <stdio.h>
#include <vector>

// следующее простое после x
int next_prime(int x)
{
	static std::vector<int> cache;
	static int max_prime = 0;
	if(max_prime == 0) {
		cache.push_back(2);
		cache.push_back(3);
		max_prime = 3;
	}
	if(x >= max_prime) { // нет в кэше
		for(int i = max_prime + 2; x >= max_prime; i += 2) {
			int* k = &cache[0];
			for(int j = cache.size(); j > 0 && i % *k != 0; j--,k++) {
				if(*k * *k > i) {
					cache.push_back(i);
					max_prime = i;
					break;
				}
			}
		}
		return max_prime;
	} else if(x < 2) {
		return 2;
	} else { // поиск в кэше
		int* min = &cache[0];
		int* max = &cache[cache.size() - 1];
		while(max - min > 1) {
			int* mid = min + (max - min) / 2;
			if (*mid > x) {
				max = mid;
			} else {
				min = mid;
			}
		}
		return *max;
	}
}

void  main(){
	int x = 0;
	for(int i = 0; i <100; i++) {
		x = next_prime(x);
		printf("%d ", x);
	}
	printf("%d\n", next_prime(-3));
}


До миллиона быстро генерит. Может кому пригодится. Я уже не раз качал таблицы, шаманил с форматированием чтоб в код вставить.
...
Рейтинг: 0 / 0
27.03.2015, 10:54
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38918617
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Только производная от квадратного корня имеет другой вид.
...
Рейтинг: 0 / 0
27.03.2015, 11:03
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919046
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
RWolfDima T,

простой тест:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
int count_op(int z)
{
  int x=1;
  for (int i=0; i<sqrt(z);i++)
    x*=2;
  return x;
}



 
gcc -std=c99 -O2 -S 1.c .globl _count_op
.def _count_op; .scl 2; .type 32; .endef
_count_op:
LFB39:
.cfi_startproc
pushl %esi
.cfi_def_cfa_offset 8
.cfi_offset 6, -8
pushl %ebx
.cfi_def_cfa_offset 12
.cfi_offset 3, -12
subl $36, %esp
.cfi_def_cfa_offset 48
xorl %ebx, %ebx
movl $1, %esi
fildl 48(%esp)
fstpl 16(%esp)
jmp L4
.p2align 2,,3
L5:
sall %esi
incl %ebx
L4:
fldl 16(%esp)
fstpl (%esp)
call _sqrt
movl %ebx, 28(%esp)
fildl 28(%esp)
fxch %st(1)
fucompp
fnstsw %ax
testb $69, %ah
je L5
movl %esi, %eax
addl $36, %esp
.cfi_def_cfa_offset 12
popl %ebx
.cfi_restore 3
.cfi_def_cfa_offset 8
popl %esi
.cfi_restore 6
.cfi_def_cfa_offset 4
ret
.cfi_endproc

call _sqrt в каждой итерации, хотя, казалось бы, оптимизация включена.


странно, z в теле цикла не меняется в данном конкретном случае. По хорошему должен оптимизировать. Может быть есть квалификатор обратный к volitile ?
...
Рейтинг: 0 / 0
27.03.2015, 14:03
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919050
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
maytonТолько производная от квадратного корня имеет другой вид.

Марк, можно подробнее причём тут производная, для особо одарённых :D
...
Рейтинг: 0 / 0
27.03.2015, 14:07
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919051
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
А откуда оптимизатору знать что sqrt - это чистая функция, которая зависит только от аргументов?
А без этого знания ни о каком предварительном вычислении не может быть и речи.
...
Рейтинг: 0 / 0
27.03.2015, 14:07
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919056
RWolf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RWolf
Участник
SashaMercury,

Просто компилятор не знает, что sqrt() не имеет побочных эффектов, и поэтому не может выкинуть лишние вызовы.
...
Рейтинг: 0 / 0
27.03.2015, 14:08
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919059
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly MoskovskyА откуда оптимизатору знать что sqrt - это чистая функция, которая зависит только от аргументов?
А без этого знания ни о каком предварительном вычислении не может быть и речи.

а нет оптимизаций во время выполнения программы ?
...
Рейтинг: 0 / 0
27.03.2015, 14:09
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919072
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
SashaMercuryа нет оптимизаций во время выполнения программы ?
Нет. А как бы это помогло? :)
...
Рейтинг: 0 / 0
27.03.2015, 14:16
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919077
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Можно оптимизатору помочь иногда
Код: plaintext
1.
2.
int max = sqrt(z);
for (int i=0; i<max;i++)


или так (если направление не важно)
Код: plaintext
1.
for (int i=sqrt(z); i>=0;i--)
...
Рейтинг: 0 / 0
27.03.2015, 14:19
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919089
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Anatoly MoskovskySashaMercuryа нет оптимизаций во время выполнения программы ?
Нет. А как бы это помогло? :)

Видимо никак.
Если бы компилятор знал о том что у этой функции нет побочных эффектов, и аргументы не меняются в теле цикла, он мог бы оптимизировать.

Впрочем, Дмитрий предложил хороший вариант, который будет применим и для других аналогичных ситуаций
...
Рейтинг: 0 / 0
27.03.2015, 14:26
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919233
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Думайте шЫрше.

Мы можем (грубо) заменить параболу на последовательность кусочно-линейных функций.
И это будет выигрыш. Главное чтоб эти кусочки были больше либо равны параболе.

Весь вопрос в выборе шага. Побочный эффект - парочка "лишних" делений. Которые на результат
не влияют.
...
Рейтинг: 0 / 0
27.03.2015, 15:41
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919262
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМы можем (грубо) заменить параболу на последовательность кусочно-линейных функций.
И это будет выигрыш. Главное чтоб эти кусочки были больше либо равны параболе.
В данном случае можно вообще таблицей в пару тысяч значений.

Вопрос будет ли оно быстрее умножения?

На своем генераторе затестил 17438916
заменил умножение в цикле
Код: plaintext
1.
2.
for(int j = cache.size(); j > 0 && i % *k != 0; j--,k++) {
	if(*k * *k > i) {


на корень перед циклом
Код: plaintext
1.
2.
3.
int i2= sqrt((float)i);
for(int j = cache.size(); j > 0 && i % *k != 0; j--,k++) {
	if(*k > i2) {


Умножение в цикле быстрее.
next_prime(10 000 000)
с умножением 741 мс
с корнем 851 мс
...
Рейтинг: 0 / 0
27.03.2015, 15:59
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919277
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
посчитал в разах:
корней 5`000`008
умножений 277`474`804

Т.е. если на расчет потребуется меньше 55 умножений, то выгодно. Теоретически должно взлететь.
...
Рейтинг: 0 / 0
27.03.2015, 16:07
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919409
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Прямые рисовать не стал, пошел другим путем, т.к. i у меня возрастает:
Код: plaintext
1.
2.
3.
4.
5.
int qi = 1;
for(int i = max_prime + 2; x >= max_prime; i += 2) {
	while(qi * qi < i) qi++; // ближайшее большее целое корня i
	for(int j = cache.size(); j > 0 && i % *k != 0; j--,k++) {
		if(*k > qi) {


Т.е. умножений стало на 270 млн. меньше. ИМХУ самый оптимальный вариант.
Ничего не изменилось, т.е. 270 млн. умножений занимают меньше 10 мс (дискретность таймера).


Интересный прикол, переключился в debug, такой код работает 1610 мс
Код: plaintext
1.
2.
3.
4.
5.
int qi = 1;
for(int i = max_prime + 2; x >= max_prime; i += 2) {
	//while(qi * qi < i) qi++; // ближайшее большее целое корня i
	for(int j = cache.size(); j > 0 && i % *k != 0; j--,k++) {
		if(*k * *k > i) {


а если while() разремить то 1550 мс, т.е. лишние циклы ускоряют программу

ХЗ кто помог, компилятор по другому регистры использовал или внутри проца какая-то оптимизация случилась. Затестил раз на десять. Стабильно проявляется в дебаге. Хорошо хоть в релизе нет.
...
Рейтинг: 0 / 0
27.03.2015, 17:47
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38919546
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Потестил в линуксах. Разницы никакой от сокращения количества умножений.

Побочный эффект: получился неплохой тест проца :)

В виндовсе i7 750 мс.
Линукс i3 1950 мс
Еще три виртуалки на разных хостингах 1100, 2275 и 5650 мс.
...
Рейтинг: 0 / 0
27.03.2015, 20:43
| Ответить | Цитировать | Написать  
76 сообщений из 76, показаны все 4 страниц
  все  
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]