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

Владимир2012 Возьмем скажем Microsoft. У них GUID в применении скажем к COM это не просто уникальный ключ,
но и ссылка к одной или нескольким веткам реестра /в котором хранятся дополнительные данные об
UNIQ/.
Подход /как по мне/ - правильный.
Так вот сделать архитектуру нашего UNIQ гибкую и расширяемую
/может быть даже завязанную с некой базой UNIQs (но ни как не привязанной к реестру)/.
Не надо мешать в одну кучу ключи и связанные с ними данные, GUID для COM это именно уникальный ключ конкретного класса, а ветка в реестре - место хранения метаданных этого класса. Никто GUID`ы в реестре хранить не заставляет. COM изобретение MS, решили они хранить в реестре в ветке с именем по GUID - их право, от того что ты изобретешь свое хранилище подход MS никак не поменяется.

Проблема именно в размерах: ID придумано именно для уменьшения размеров, для компактного хранения данных. Чтобы диапазон допустимых значений незначительно превосходил количество требуемых. Если бы с размерами проблем не было, то делай 128 бит (хоть самодельным алгоритмом) и забудь про все остальные проблемы.
...
Рейтинг: 0 / 0
13.04.2015, 10:52
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38934589
Владимир2012
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир2012
Участник
Dima TСмысл? Цель какая?Чтобы затем этот GUID можно было использовать и в WWW, ...
Кроме того если далее GUID использовать по примеру Microsoft и иметь доступ к его метаданным,
то он будет подобен URL.
Проще говоря это будет "URL" к объекту.
Т.е. зная GUID объекта можно получить мета данные по нем /к примеру об книге, товаре, .../.
При этом нам не нужно будет разрабатывать ни какие вэб сервисы ...
...
Рейтинг: 0 / 0
13.04.2015, 11:34
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38934683
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Владимир2012 А что если UNIQ /наш аналог GUID/ будет переменной длины.
Т.е. в нем скажем 0-й бит 1-го байта имеет значение:
== 0 - UNIQ фиксированной длины;
== 1 - UNIQ переменной длины;

С точки зрения БД - всё равно. Строки и псевдо-числа (Number) хранятся в виде последовательностей символов.

128-битность может быть интересна в тех сферах где основная вычислительная нагрузка падает именно
на сравнения 128-битных целых. Но я таких не знаю. К примеру все современные файловые системы NTFS/Zfs
в качестве основного вычислимого типа используют uint64_t. Это покрывает все потребности роста ФС на десятки
лет в будущее.

Представить себе объёмы измеряемые 128 битами не просто невозможно. Это неслыханно. Это астрономически
огромное число. Мы можем его попробовать сравнить с секундами возраста вселенной или количеством атомов вещества.
Чтобы хотя-бы обладать порядком сравнения.
...
Рейтинг: 0 / 0
13.04.2015, 12:22
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38934686
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Владимир2012Dima TСмысл? Цель какая?Чтобы затем этот GUID можно было использовать и в WWW, ...
Кроме того если далее GUID использовать по примеру Microsoft и иметь доступ к его метаданным,
то он будет подобен URL.
Проще говоря это будет "URL" к объекту.
Т.е. зная GUID объекта можно получить мета данные по нем /к примеру об книге, товаре, .../.
При этом нам не нужно будет разрабатывать ни какие вэб сервисы ...
В такой постановке как сгенерить GUID дело десятое. По сути ты предлагаешь сделать каталог всего на свете, чтобы потом просто на него ссылаться или брать необходимую инфу. Придумать его структуру и правила хранения - не проблема. Даже RFC написать можно. Только это 0,01% от решения всей задачи. Кто будет наполнять этот каталог и следить за актуальностью? Вот в чем проблема.

Все придумано до нас: у товаров есть EAN у книг ISBN.
Придумано потому что это выгодно и оправдывает затраты на "придумывание" и главное на поддержание придуманного в рабочем состоянии.

Так что оставшиеся 99,99% твоей задачи придумать как доказать владельцу объекта (например производителю товара) что ему выгодно зарегистрироваться в твоей системе и поддерживать в актуальном состоянии информацию о своих объектах.

PS Ты не первый с подобными идеями, хотя по размаху яндекс.маркет убогая поделка по сравнению с твоими замыслами :)
...
Рейтинг: 0 / 0
13.04.2015, 12:24
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38934697
Владимир2012
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Владимир2012
Участник
Dima TВсе придумано до нас: у товаров есть EAN у книг ISBNВот в этом и изюминка.
Будет предложен унифицированный подход к созданию meta данных об объекте.

PS: Разница в том, что подход "EAN у книг ISBN" порождает неимоверное количество разных сущностей.
Что в свою очередь как "ком" тянет за собой другие проблемы.
...
Рейтинг: 0 / 0
13.04.2015, 12:29
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38934731
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
В внедрением протокола Ipv6. Разрядную сетку IP адреса получателя и отправителя не просто удвоили.
А учетверили. Я думаю что перегнули палку. Админам трудно запоминать даже приблизительно Ipv6
адреса. Специально для этого была придумана "сжатая" нотация с двоеточиями (":") чтобы скипать
длинные последовательности нулей (капец рациональность) в пустых пока еще диапазонах.
Трудно будет также фиксировать сложные правила файрвола. Индивидуальные блокировки e.t.c.
Еще сложнее будет хранить мета-базы данных трафика.

Думаю что с 128 битами явно поспешили. Не было поэтапного развития. Дай бох планета земля
доживёт до новых потребностей в расширении адреса.
...
Рейтинг: 0 / 0
13.04.2015, 12:46
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38934737
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercuryПоздравляю! :)
Привет лентяй. А ты собираешся нас порадовать кодингом?
...
Рейтинг: 0 / 0
13.04.2015, 12:48
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38934771
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonВ внедрением протокола Ipv6. Разрядную сетку IP адреса получателя и отправителя не просто удвоили.
А учетверили.
maytonПредставить себе объёмы измеряемые 128 битами не просто невозможно. Это неслыханно. Это астрономически
огромное число. Мы можем его попробовать сравнить с секундами возраста вселенной или количеством атомов вещества.
Чтобы хотя-бы обладать порядком сравнения.
Каждой молекуле по IP-шнику дали, а мы тут за какие-то несчастные GUIDы. Надо IP-шники раздавать на все случаи жизни
...
Рейтинг: 0 / 0
13.04.2015, 13:05
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38935278
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Дима. Please review.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
Revision: 33
Author: mayton
Date: Monday, April 13, 2015 7:39:00 PM
Message:
Fixes MinGW compiller warning : 'this decimal constant is unsigned only in ISO C90'
----
Modified : /trunk/DimaT/header.h


+ надо-бы написать краткие аннотации или в Help или в каментах что каждая утилита делает.
...
Рейтинг: 0 / 0
13.04.2015, 19:42
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38935386
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TКаждой молекуле по IP-шнику дали, а мы тут за какие-то несчастные GUIDы. Надо IP-шники раздавать на все случаи жизни
А смысл? IP надо раздавать устройствам которые хотя-бы пингуются и светят в мир на 80 порту
хоть какой-то веб-мордой. А так - тривиальные клиенты спокойно сидят за proxy, nat и не жужжат.
И внешний адрес им нужен как зайцу 5-е колесо.
...
Рейтинг: 0 / 0
13.04.2015, 23:47
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38935679
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Решил порассуждать о некоторых частных случаях факторизации. Припустим есть
некое длинное целое A которое является результатом произведения 2х достаточно
больших простых чисел (X,Y). Почему двух? Ну... согласно криптографическим протоколам.
Вобщем таковы начальные условия.

Какими должны быть эти (X,Y). Ну... предположительно они должны быть достаточно
большими чтобы исключать "перебор" решетом primes или таблице или базой.
Исходим из предположения что A имеет астрономически-высокую разрядность (512 бит
максимум) и разрядная сетка обычно задейстована на 80-100%. Тогда
искомые (X,Y) которые удовлетворят уравнению



Или



находятся на кривой типа гипербола которая проходит через точки:

(1,A), (x1,y1), (y1,x1), (A,1).

которые имеют целочисленное решение. А все остальные (xi,yi) по сути
не имеют целого решения xy=1 по определению. Потому-что такова постановка.

Где-бы следовало искать точку (xi,yi) ? По всей видимости не в окрестности
(1,A) или (A,1) где решение находится перебором. И не в окрестности

(xc,yc)=((SQRT(A),SQRT(A)) где число трудно но всё-таки можно искать от центра симметрии.

А скорее всего искомые (x,y) лежат между (xc,yc) и (A/ymaxprime,ymaxprime) и (xmaxprime,A/maxprime)
где *maxprime это максимум последовательности простых чисел которые у нас есть и которые
легко и удобно извлекаются и имеют единичную оценку сложности алгоритма проверки делимости в
рамках нашей решаемой задачи.

Уф... написал. Чуть позже нарисую поясняющую картинку.
...
Рейтинг: 0 / 0
14.04.2015, 11:11
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38935711
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
maytonГде-бы следовало искать точку (xi,yi) ? По всей видимости не в окрестности
(1,A) или (A,1) где решение находится перебором. И не в окрестности

(xc,yc)=((SQRT(A),SQRT(A)) где число трудно но всё-таки можно искать от центра симметрии.
Ага, метод Ферма
maytonА скорее всего искомые (x,y) лежат между (xc,yc) и (A/ymaxprime,ymaxprime) и (xmaxprime,A/maxprime)
где *maxprime это максимум последовательности простых чисел которые у нас есть и которые
легко и удобно извлекаются и имеют единичную оценку сложности алгоритма проверки делимости в
рамках нашей решаемой задачи.
Вообще-то чтобы получить N-битный RSA ключ, берется пара нечетных случайных N/2-битных чисел A и B, каждое из которых тестируется по Миллеру-Рабину по нескольким основаниям. Никто не стремится специально доказать их простоту. Да, еще неплохо проверить, что A-1 и B-1, а также A+1 и B+1 содержат большие простые множители.
...
Рейтинг: 0 / 0
14.04.2015, 11:32
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38935736
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
ОК. Спасибо Барлон. У меня уже целый список чего почитать.
...
Рейтинг: 0 / 0
14.04.2015, 12:03
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38936305
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДима. Please review.
+ надо-бы написать краткие аннотации или в Help или в каментах что каждая утилита делает.
Поправил варнинги.
Думаю надо там поудалять лишнее. Промежуточные версии наверно никому не интересны.
Оставить next_prime32.h next_prime64.h и сделать одну primegen.cpp собрав туда все полезное. Удаляю?

primegen.cpp почти сделал (осталось добавить многопоточность). Считает по заданному диапазону и сохраняет найденные в файл. Если файл не задавать, то просто количество считает, т.е. тест на скорость.
Можешь потестить.
...
Рейтинг: 0 / 0
14.04.2015, 17:43
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38936311
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Да. Я думаю что 32х битные версии для сообщества не представляют
интереса. Кому надо под легаси-железо - сам поправит и пересоберёт.

Я грохну PBFA-32bit няшную шнягу.
...
Рейтинг: 0 / 0
14.04.2015, 17:46
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38936415
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonДа. Я думаю что 32х битные версии для сообщества не представляют интереса.
Не совсем согласен. С математической точки зрения они бесполезны, но с практической - они просто быстрее. 8 байт дольше читается чем 4, пусть ускорение не в 2 раза, но 10-15% времени x32 экономит.
...
Рейтинг: 0 / 0
14.04.2015, 19:25
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38936577
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я понял твою мысль. На уровне storage имеет смысл сохранить кеши vector<uint32>, vector<uint64>.
...
Рейтинг: 0 / 0
14.04.2015, 23:30
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38938689
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
kealon(Ruslan)
Участник
mayton,

ещё вот такая мысль возникла

все простые числа >2 можно представить в виде только одним способом при a=b+1
a^2-b^2 =(a-b)(a+b)

числа
при к>0 всегда не простые

и вот интересно, какова доля простых чисел в рядах
...
Рейтинг: 0 / 0
16.04.2015, 21:57
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38938892
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Barlone
Участник
Народ считает факториалы с использованием решета Эратосфена.
...
Рейтинг: 0 / 0
17.04.2015, 10:31
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38938948
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Просмотрел бегло. Оригинально. Они посчитали что затраты на хранение и генерацию дерева целых
будут слишком малы (т.к. порядок числа под факториалом обычно мал).

Но кому нужен точный расчёт факториала? Пожалуй только в задачах доказательства теорем
или схождений рядов им подобных.
...
Рейтинг: 0 / 0
17.04.2015, 11:18
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #38939212
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Добавил многопоточность в primegen.cpp. Правда при запуске в многопоточном варианте он только скорость померяет. В файл запись не стал делать, слишком много кода получится и хранить надо где-то, чтобы последовательно в файл писать.
...
Рейтинг: 0 / 0
17.04.2015, 13:54
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39012652
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Чортов сорсфорж. Упал нафик

https://sourceforge.net/p/primegen/code/
...
Рейтинг: 0 / 0
21.07.2015, 18:33
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39151177
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Со ссылкой на хабр http://habrahabr.ru/post/275541/

Еще одно простое число найдено.



Эти чортовы ботаны не спят ночей и мучают процессор и видяшку
чтобы получить свои 3000 условных енотов и потешить своё самолюбие!
...
Рейтинг: 0 / 0
20.01.2016, 10:24
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39151189
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonЭти чортовы ботаны не спят ночей и мучают процессор и видяшку
чтобы получить свои 3000 условных енотов и потешить своё самолюбие!
Есть от них польза, косяк в интеловском проце нашли :)
...
Рейтинг: 0 / 0
20.01.2016, 10:35
| Ответить | Цитировать | Написать  
Генератор простых чисел (до 10^9 за 5 сек)
    #39151201
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dima TmaytonЭти чортовы ботаны не спят ночей и мучают процессор и видяшку
чтобы получить свои 3000 условных енотов и потешить своё самолюбие!
Есть от них польза, косяк в интеловском проце нашли :)
Ну чтож.. остаётся только развести руками и обругавшись спросить как
они (Intel) там вообще тестируют новые модели процессоров?

Бох с ними с простыми числами. Хотя-бы прогнали регресс по DDIV, экспонентам
и элементарной математике.

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


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