ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
25 сообщений из 402, страница 7 из 17
  7  все
Генератор простых чисел (до 10^9 за 5 сек)
    #38925361
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Убрал кастинг в твоём тесте. Быстрее стало.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
	double*   primeDouble = (double*)   malloc(TEST * sizeof(double));
        .....
	double s2 = 0;
	for(int i = 0; i < TEST; i++) {
		s2 += sqrt(primeDouble[i]);
	}
	printf("%f sqrt time %d msec\n", s2, now_msec() - t);



Код: plaintext
1.
2.
3.
4.
5.
Press any key to continue . . . 
start
-858523137 isqrt64 time 1914 msec
-858523137 isqrt32 time 805 msec
1025663660831.226200 sqrt time 406 msec
...
Рейтинг: 0 / 0
02.04.2015, 17:09
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925378
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonУбрал кастинг в твоём тесте. Быстрее стало.
Сейчас твои результаты пропорциональны моим. Похоже это твой компилятор "соптимизировал".

У меня в MSVC так вообще не компилируется. Пробовал (float) и (double) - скорость не меняется.
затестил так, скорость таже
Код: plaintext
1.
2.
3.
	float s2 = 0;
	for(int i = 0; i < TEST; i++) {
		s2 += sqrt((float)prime[i]);
...
Рейтинг: 0 / 0
02.04.2015, 17:20
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925389
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
По моему ... float на уровне калькуляций кроме экономии разрядной сетки не даёт вообще ничего.

Не пробовал просмотрель ассеблерный выход для float/double на предмет разницы?
...
Рейтинг: 0 / 0
02.04.2015, 17:26
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925393
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dima TУ меня в MSVC так вообще не компилируется.
Не заметил что у тебя double* primeDouble
затестил так, у меня никаких изменений.

затести так
Код: plaintext
1.
2.
double primed = prime[i];
s2 += sqrt(primed);


преобразование из int в double не может занимать столько же времени как вычисление корня. Явно глюк компилятора.
...
Рейтинг: 0 / 0
02.04.2015, 17:27
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925404
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНе пробовал просмотрель ассеблерный выход для float/double на предмет разницы?
Нет разницы. Отладчиком прошелся, значение передается в Сишный рантайм, а там проверки валидности и fsqrt.
Затестил оба, нет разницы в скорости. float еще и неточно посчитал.
...
Рейтинг: 0 / 0
02.04.2015, 17:36
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925416
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Флоат втопку. И пепел в море утопить.

Я закоммитил 1-й вариант своей тулзы. Работает она медленно. Зато сходу выдаёт итератор primes.

Делай

Код: plaintext
1.
$ svn update .
...
Рейтинг: 0 / 0
02.04.2015, 17:39
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925418
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
Revision: 10
Author: mayton
Date: Thursday, April 02, 2015 5:23:00 PM
Message:
Added 'PowerBruteForce' algorithm for 32-x bit computation architecture.

----
Added : /trunk/mayton/PBFA
Added : /trunk/mayton/PBFA/src
Added : /trunk/mayton/PBFA/src/pbfa.cpp
...
Рейтинг: 0 / 0
02.04.2015, 17:40
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925427
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
maytonЯ уже придумал как. Начальное приближение можно брать с предыдущей итерации.Ну тогда эта функция вообще не нужна, достаточно проверить, пора ли увеличить значение "с предыдущей итерации" на единицу :)
...
Рейтинг: 0 / 0
02.04.2015, 17:49
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925428
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Это и есть алгоритм Брезенхейма.
...
Рейтинг: 0 / 0
02.04.2015, 17:49
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925433
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Правда он создавался для рисования растровых кривых эллипсов и линий.
Но на курсе Графического моделирования нам рассказывали о параболе.
Следовательно я делаю вывод что есть и такая имплементация.
...
Рейтинг: 0 / 0
02.04.2015, 17:51
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925436
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЯ закоммитил 1-й вариант своей тулзы. Работает она медленно. Зато сходу выдаёт итератор primes.
Обновил. Чтоб не тормозила - поставь предел поменьше. 10-100 млн. чтоб максимум в 5 сек укладывалась.
Вектор быстрая штука, тестил с ним и без него - разница 20-30 мс на расчете до миллиарда. Добавлю тоже себе вариант с вектором.
...
Рейтинг: 0 / 0
02.04.2015, 17:53
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925437
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Хотя конечно смотря что тут подразумевалось под итерацией...
...
Рейтинг: 0 / 0
02.04.2015, 17:53
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925443
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonЯ закоммитил 1-й вариант своей тулзы. Работает она медленно. Зато сходу выдаёт итератор primes.
Обновил. Чтоб не тормозила - поставь предел поменьше. 10-100 млн. чтоб максимум в 5 сек укладывалась.
Вектор быстрая штука, тестил с ним и без него - разница 20-30 мс на расчете до миллиарда. Добавлю тоже себе вариант с вектором.
Не очень понял о каком пределе ты пишешь.

И ... это опенсорц. Закоммить свои изменения в мой файл. И я вобщем-то не буду против если это не крашит приложение.
...
Рейтинг: 0 / 0
02.04.2015, 17:55
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925505
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
ребята, вы ведь понимаете, что топик не может заканчиваться не на простом числе страниц? ;))
...
Рейтинг: 0 / 0
02.04.2015, 18:37
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925519
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я нарисовал табличку для тестов и для оценки плотности распределения primes.

Selection from 2 to..Primes detectedAll to primes ratio10025 0.251000 168 0.16810000 1 229 0.1229100000 9 592 0.095921000000 78 498 0.07849810000000 664 579 0.0664579100000000 5 761 455 0.057614551000000000 50 847 534 0.050847534
...
Рейтинг: 0 / 0
02.04.2015, 18:45
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925534
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonНе очень понял о каком пределе ты пишешь.
И ... это опенсорц.
Понятно что могу поправить. Я к тому что какой смысл полминуты считать, все-равно долго. Топик с того и начался что я не мог дождаться пока мой перебор насчитается :)

egorychребята, вы ведь понимаете, что топик не может заканчиваться не на простом числе страниц? ;))
Верно подмечено, теперь цель 11-я, после 13-й туго будет, присоединяйся

Но тут у нас есть оптимизатор - mayton если что имеет права лишнее почистить, т.е. подравнять страницы.
...
Рейтинг: 0 / 0
02.04.2015, 18:53
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925535
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Сашик раскурит СВН и я подчищу.
...
Рейтинг: 0 / 0
02.04.2015, 18:58
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925537
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TПонятно что могу поправить. Я к тому что какой смысл полминуты считать, все-равно долго. Топик с того и начался что я не мог дождаться пока мой перебор насчитается :)
Просто мы решаем разные задачи.

Я искал оптимальные способы хранения расчитанных primes на диске
чтобы факоризировать сверх-длинные целые.

А ты хотел чтобы Эратосфен до 2 млрд считался за несколько секунд. Но это другая задача.
...
Рейтинг: 0 / 0
02.04.2015, 19:01
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925538
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЯ нарисовал табличку для тестов и для оценки плотности распределения primes.
Ты формулу распределения давал n/ln(n)

Чем дальше, тем формула точнее предсказывает. На лярде по формуле 48254942, на 5% не совпало.

Табличка полезна для контроля точности вычислений. Если совпало, то остается проверить что все найденные простые (взаимно поделив друг н друга) и можно утверждать что генератор корректно работает. По хорошему какой-то экспресс-тест надо изобрести, т.к. делить не быстро.
...
Рейтинг: 0 / 0
02.04.2015, 19:02
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925542
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Формула - асимтотична. На малых величинах она вообще вихляется чудовищно.
...
Рейтинг: 0 / 0
02.04.2015, 19:04
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925547
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Но она полезна в другом. У меня был план - хранить расчитанные primes в бинарных файлах
специально оптимизированных по размеру (каждое число укладывалось в несколько бит).
И индексировать для последовательного от min до max итератора по файлу.

Но эта задея до сих пор у меня не взлетела именно из-за капризного характера самих
primes. Их невозможно оценить по стат-показателям. Они - постоянно плывут.
Дельта между primes плывёт. Плывёт разрядность. Причём постоянно в сторону
усложнения архитектур.

Пожалуй n/ln(n) это единственное что стационарно. Хоть какая-то точка отсчёта
в этом океане хаоса.

Вобщем старик Ландау хихикает в своём гробу глядя на мои потуги.
...
Рейтинг: 0 / 0
02.04.2015, 19:08
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925551
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonПросто мы решаем разные задачи.

Я искал оптимальные способы хранения расчитанных primes на диске
чтобы факоризировать сверх-длинные целые.
Готовь диски, всё будет. max_prime(uint64_t x) посчитаем. Точнее уже есть заготовка, просто не доделал, поэтому не выложил. Сначала с Сашей отвлекся на Аткина (не зря, получили ориентир по скорости), потом с наведением порядка и заливкой разбирался.

Я привык решать вопросы последовательно. Начали с начала - иду той же последовательностью. Начинал с Эратосфена, тут причесал - выложил. Самое вкусное оставлено на десерт.

Тут еще мысль с оптимизацией шага цикла недоделана.

maytonА ты хотел чтобы Эратосфен до 2 млрд считался за несколько секунд. Но это другая задача.
Он будет считаться за 100 мс. Порвем Аткина. Есть мысли. Потерпи :)
...
Рейтинг: 0 / 0
02.04.2015, 19:15
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925603
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
mayton, откомпилировал твой исходник, с ходу не получилось, MSVC 2008 не понял. Пришлось поправить
Код: plaintext
1.
2.
//#include <stdint.h>
typedef unsigned long long uint64_t;



Вывод в консоль это жесть. Завешивает RDP-терминал наглухо. Ладно хоть до миллиона указал, не долго считалось :)

 
Статистика ожидаемая, пытаюсь с ней боротьсяKey[3] = 7 %, hits = 49999
Key[5] = 5 %, hits = 33331
Key[7] = 4 %, hits = 26660
Key[11] = 3 %, hits = 22846
Key[13] = 3 %, hits = 20754
Key[17] = 2 %, hits = 19148
Key[19] = 2 %, hits = 17999
Key[23] = 2 %, hits = 17039
Key[29] = 2 %, hits = 16271
Key[31] = 2 %, hits = 15669
Key[37] = 2 %, hits = 15154
Key[41] = 2 %, hits = 14692
Key[43] = 2 %, hits = 14290
Key[47] = 2 %, hits = 13935
Key[53] = 2 %, hits = 13584
Key[59] = 1 %, hits = 13230
Key[61] = 1 %, hits = 12904
Key[67] = 1 %, hits = 12630
Key[71] = 1 %, hits = 12321
Key[73] = 1 %, hits = 12052
Key[79] = 1 %, hits = 11823
Key[83] = 1 %, hits = 11533
Key[89] = 1 %, hits = 11283
Key[97] = 1 %, hits = 11004
...
Рейтинг: 0 / 0
02.04.2015, 20:11
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925643
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Обновись снова. Я не знал что ты будешь компилировать с _DEBUG
...
Рейтинг: 0 / 0
02.04.2015, 21:06
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38925645
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonПросто мы решаем разные задачи.
Зафиксировал недоделанную next_prime64(). Она рабочая, но не оптимизированная под последовательности, не x64, считает только до 2^32.
Но как считает:
Код: plaintext
1.
next_prime64(4200000000);


результатprime 4200000037 time 0
Смотри nextprime.cpp

С разрядностью разбираюсь. Остальная оптимизация позже.
...
Рейтинг: 0 / 0
02.04.2015, 21:06
| Ответить | Цитировать | Написать  
25 сообщений из 402, страница 7 из 17
  7  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Генератор простых чисел (до 10^9 за 5 сек)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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