Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
#1

Быстрая проверка натурального числа на простоту - C++

29.09.2012, 21:35. Просмотров 46232. Ответов 90
Метки нет (Все метки)

Часто возникает задача проверки натурального числа на простоту. При этом имеются вероятностные и детерминированные методы проверки. Здесь рассматриваются только детерминированные алгоритмы, дающие 100% ответ на вопрос о простоте.

Хорошо известно такое утверждение: если натуральное число n>1 не делится ни на одно простое число, не превосходящее http://www.cyberforum.ru/cgi-bin/latex.cgi?\sqrt{n}, то оно простое. В связи с этим получается самый простой способ проверки на простоту алгоритм

C++
1
2
3
4
5
6
7
8
9
10
11
int Prime(unsigned long a)
{
   unsigned long i;
   if (a == 2)
      return 1;
   if (a == 0 || a == 1 || a % 2 == 0)
      return 0;
   for(i = 3; i*i <= a && a % i; i += 2)
      ;
   return i*i > a;
}
В данном алгоритме из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\} отброшено 50% четных чисел, так как если число a не делится на 2, то нет смыла делить его на 4, 6 и т.д. Данный метод можно усовершенствовать и отбросить из множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\} больше чисел. Для этого выбирается некоторое число m, равное произведению простых чисел без степеней и рассматриваются только те элементы множества http://www.cyberforum.ru/cgi-bin/latex.cgi?\{2,3,...,\sqrt{n}\}, которые взаимно просты с m. Например, если m = 6 = 2*3, то из этого множества отбрасывается 66% элементов (ненужных проверок). В этом случае алгоритм будет быстрее предыдущего при больших n

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Prime(unsigned long a)
{
   unsigned long i, j, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0)
      return 0;
   bound = sqrt((double)a);
   i = 7; j = 11;
   while (j <= bound && a%i && a%j)
   {
       i += 6; j += 6;
   }
   if (j <= bound || i <= bound && a%i == 0)
      return 0;
   return 1;
}
Если m = 30 = 2*3*5, то такой алгоритм будет еще быстрее и отбрасывает уже 74% лишних элементов

C++
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
int Prime(unsigned long a)
{
   unsigned long i1, i2, i3, i4, i5, i6, i7, i8, bound;
   if (a == 0 || a == 1)
      return 0;
   if (a == 2 || a == 3 || a == 5 || a == 7 || a == 11 || a == 13 || a == 17 || a == 19 || a == 23 || a == 29)
      return 1;
   if (a%2 == 0 || a%3 == 0 || a%5 == 0 || a%7 == 0 || a%11 == 0 || a%13 == 0 || a%17 == 0 || a%19 == 0 || a%23 == 0 || a%29 == 0)
      return 0;
   bound = sqrt((double)a);
   i1 = 31; i2 = 37; i3 = 41; i4 = 43; i5 = 47; i6 = 49; i7 = 53; i8 = 59;
   while (i8 <= bound && a%i1 && a%i2 && a%i3 && a%i4 && a%i5 && a%i6 && a%i7 && a%i8)
   {
       i1 += 30; i2 += 30; i3 += 30; i4 += 30; i5 += 30; i6 += 30; i7 += 30; i8 += 30;
   }
   if (i8 <= bound ||
      i1 <= bound && a % i1 == 0 ||
      i2 <= bound && a % i2 == 0 ||
      i3 <= bound && a % i3 == 0 ||
      i4 <= bound && a % i4 == 0 ||
      i5 <= bound && a % i5 == 0 ||
      i6 <= bound && a % i6 == 0 ||
      i7 <= bound && a % i7 == 0)
         return 0;
   return 1;
}
Вот такие интересные наработки получились. У кого есть варианты, работающие быстрее, добавляйте.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2012, 21:35     Быстрая проверка натурального числа на простоту
Посмотрите здесь:
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
C++ Проверка числа на простоту
Проверка числа на простоту C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.10.2012, 14:41  [ТС]     Быстрая проверка натурального числа на простоту #21
Хотел применить теорию, которая помогла написать более быстрый алгоритм для проверки на простоту, к построению решета Эратосфена. Но ни тут то было, самая быстрая реализация имеет такой вид

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Eratosfen(char *a, long n)
{
    long i, j, bound = sqrt((double)n);
    a[0] = a[1] = 0; a[2] = 1;
    for(i = 4; i < n; i += 2)
        a[i] = 0;
    for(i = 3; i < n; i += 2)
        a[i] = 1;
    i = 3;
    while (i <= bound)
    {
        for(j = i << 1; j < n; j += i)
            a[j] = 0;
        i += 2;
        while (i <= bound && !a[i])
            i += 2;
    }
}
а попытка ускорить данный алгоритм с помощью рассматриваемых выше модулей дает обратный эффект. Это и понятно почему.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.10.2012, 11:14  [ТС]     Быстрая проверка натурального числа на простоту #22
Решето Эратосфена в таком варианте
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Eratosfen(char *a, long n)
{
    long i, j, d, bound = sqrt((double)n);
    a[0] = a[1] = 0; a[2] = 1;
    for(i = 4; i < n; i += 2)
        a[i] = 0;
    for(i = 3; i < n; i += 2)
        a[i] = 1;
    i = 3;
    while (i <= bound)
    {
        d = i << 1;
        for(j = 3 * i; j < n; j += d)
            a[j] = 0;
        i += 2;
        while (i <= bound && !a[i])
            i += 2;
    }
}
работает в два раза быстрее предыдущего. Для первых 100 000 000 натуральных чисел алгоритм укладывается в секунду!

Добавлено через 1 час 56 минут
С подачи от valeriikozlov более быстрый алгоритм:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Eratosfen(char *a, long n)
{
    long i, j, d, bound = sqrt((double)n);
    a[0] = a[1] = 0; a[2] = 1;
    for(i = 4; i < n; i += 2)
        a[i] = 0;
    for(i = 3; i < n; i += 2)
        a[i] = 1;
    i = 3;
    while (i <= bound)
    {
        d = i << 1;
        for(j = i * i; j < n; j += d)
            a[j] = 0;
        i += 2;
        while (i <= bound && !a[i])
            i += 2;
    }
}
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
28.10.2012, 22:47     Быстрая проверка натурального числа на простоту #23
не знаю на сколько актуально, но этот оптимизированный алгоритм можно загнать на GPU =) с лишь откидыванием четных чисел я получил скорость в проверки 10млрд делителей/ секунду. Число порядка 10^19 в худшем случае проверяет около 100-120ms.

Добавлено через 11 минут
Thinker, а ты еще что нить придумал ? вот конкретный тест:
digit 2305843009213693951
is simp 0
time 150.121 ms
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
29.10.2012, 09:07  [ТС]     Быстрая проверка натурального числа на простоту #24
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, а ты еще что нить придумал ? вот конкретный тест:
digit 2305843009213693951
is simp 0
time 150.121 ms

Не по теме:

судя по всему, мои алгоритмы очень медленны для очень больших чисел. Вот в этой теме
Как проверить является ли число простым
всплыл более быстрый алгоритм AKS

AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
29.10.2012, 23:25     Быстрая проверка натурального числа на простоту #25
Thinker, я так понял алгоритм никто не написал на с++? Просто тот же перебор можно оптимизировать для видеокарты и он будет работать с бешеной скоростью ю, пока достиг проверки 15млрд делителей/сек

Добавлено через 12 часов 1 минуту
Thinker, я придумал как ускорить этот алгоритм, произведя заранее подготовку, то есть имея какие то данные в виде таблицы в файле например, которые можно просчитать 1 раз и сохранить. В общем как ты писал, если исключить из проверки все четные числа и каждое 3е, то получим, что надо проверить всего 33% делителей. Я решил проверить на сколько уменьшится этот процент, если к примеру мы исключим по больше числе. В итоге получил такой расчет: при исключении всех простых чисел до 10 000 (а их 1228) получаем, что на больших числах нам надо проверить около 6,6% оставшихся, то есть можно ускорить в 5 раз! (теоритически). А период повторения этих чисел - их произведение = 808157282. То есть нужно получить все оставшиеся числа в промежутке от k (где k - первое число, которое не делится по модулю на 1228 простых) до k + 808157282. Судя по расчетам их около 53 млн - при размере u_int64 = 8 байт это занимает порядка 420 мб. Остается только получить эти числа =) ну или посчитать на сколько можно уменьшить данное количество.
ValeryS
Модератор
6550 / 5016 / 463
Регистрация: 14.02.2011
Сообщений: 16,722
29.10.2012, 23:38     Быстрая проверка натурального числа на простоту #26
Цитата Сообщение от AEXks Посмотреть сообщение
то есть имея какие то данные в виде таблицы в файле например,
Я не помню предлагал или нет
предварительно рассчитываем простые числа до 2^32 и записываем их в файл
это 16 гигабайт интов на самом деле меньше мы же не все туда будем записывать а только простые
можно создать файл для чисел 2^16 это 260 кБ (важна идея)
а потом при расчете если число попадает в диапазон берем из таблицы(из файла)
а если больше, то делим на делители из файла( т.е) делим только на простые числа
этим мы выбрасываем и кратные 2 и кратные 3 5, 7, 11 .......
скорость должна возрасти, хотя не просчитывал не знаю
основная работа ляжет на создание файла ( но это один раз)
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 09:10     Быстрая проверка натурального числа на простоту #27
ValeryS, а что, если у нас число например порядка 10^19 = 2^19 * 5^19 и кончатся делители из файла?_)
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 09:35  [ТС]     Быстрая проверка натурального числа на простоту #28
AEXks, я уже ходил этим путем, прочитайте пост 16 этой темы. прироста в скорости нет. прирост в скорости начинается, если числа ОЧЕНЬ большие
При этом я рассматривал очень большие значения m, а чем ближе m к корню из тестируемого числа, тем больше убирается составных тестируемых чисел. например, если http://www.cyberforum.ru/cgi-bin/latex.cgi?m = \sqrt{a}, то остаются только простые тестируемые числа в роли потенциальных делителей. но реализация этого всего не позволяет добиться быстрой скорости, поэтому индийские ученые (AKS) пошли другим путем.

Дело же в чем. Мы же все равно фиксирует этот модуль m, а тестируемые числа могут быть сколь угодно большими, так и так возникнет процент лишних проверок с использованием составных делителей. да и реализовать это эффективно с массивами не удается.

ValeryS, такой алгоритм подойдет только для чисел из фиксированного диапазона, но не для произвольного числа.
ValeryS
Модератор
6550 / 5016 / 463
Регистрация: 14.02.2011
Сообщений: 16,722
30.10.2012, 10:34     Быстрая проверка натурального числа на простоту #29
Цитата Сообщение от AEXks Посмотреть сообщение
у нас число например порядка 10^19 = 2^19 * 5^19 и кончатся делители из файла?
это меньше чем 2^64 ???
Цитата Сообщение от Thinker Посмотреть сообщение
такой алгоритм подойдет только для чисел из фиксированного диапазона, но не для произвольного числа.
при использовании таблицы простых чисел до 2^32
можно проверять числа до 2^64
если этого мало то можно создать большую таблицу

вообще мне трудно решать,поскольку не могу представить прикладную задачу для применения таких больших простых чисел
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 10:59     Быстрая проверка натурального числа на простоту #30
ValeryS, окей , задача состоит в взломе ключа RSA , длина которого как минимум 1000бит , так что тут даже не обойтись простой арифметикой, а вообще это все нужно для криптографии в том числе.
Thinker, Вы исходите из производительности одного ядра процессора, но на видеокарте это будет выглядеть по другому. Надо думать в этом направлении. И чем больше мы исключаем чисел, тем фактически большее количество делителей можно проверить за секунду. Пока, исключив только 2 и 3 я смог добиться проверки 16,6 млрд делителей в секунду. то есть 1,6 * 1010 / сек. Теперь по теоретическом расчету для проверки 232 делителей уйдет 232 / 1,6 * 1010 = 0,26 секунд. ( Что на практике так и есть, так как в 64 битное число можно как раз записать 20ти значные числа.)
ValeryS, То есть по рассуждениям выше не нужно ничего городить) числа 264 проверяются в худшем случае за 260ms , и в принципе можно считать , что для таких числе задача решена.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 20:58  [ТС]     Быстрая проверка натурального числа на простоту #31
AEXks, если зафиксировать модуль m, то в этом случае сложность алгоритма будет http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt{n}), где n - исследуемое число. Поэтому есть ли смысл идти в этом направлении. Вы же прекрасно понимаете, что в ассимметричных шифрах используются ОЧЕНЬ большие числа, а если речь об эллиптических кривых, то там совсем принцип другой. Изначально моя цель была, действительно, улучшить широко используемый алгоритм проверки на простоту, но при общих равных условиях (при активном одном ядре), третий алгоритм из первого поста получился самым удачным. Другие алгоритмы, которые я здесь не выкладывал, уступают относительно (условной) сложности реализации и скорости. Да, при больших числах скорость медленно начинает расти относительного третьего алгоритма, но сложность остается http://www.cyberforum.ru/cgi-bin/latex.cgi?O(\sqrt{n}), поэтому я эту затею бросил.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:01     Быстрая проверка натурального числа на простоту #32
Thinker, а есть ли другие точные алгоритмы при меньшей сложности? так как скорость просчета на _int64 быстр, то нужно как то попробовать реализовать деление по модулю двух _int64 , _int64 на максимум _int64 . Я уже написал мысли по этому поводу.. там нужны битовые операции, а именно я не знаю есть ли функции вычисляющие номер самого старшего значимого бита.
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:08  [ТС]     Быстрая проверка натурального числа на простоту #33
Тот же AKS, но им не интересовался. Мне интересно было применить некоторые познания из теории чисел на практике и, отчасти, это сделать удалось. Ваша идея с GPU очень интересна, но не понятно как Вы это реализовали.
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:25     Быстрая проверка натурального числа на простоту #34
Thinker, в каком плане не понятно ? могу выложить код функции обработчика и ядра =) обсудим
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:30  [ТС]     Быстрая проверка натурального числа на простоту #35
Цитата Сообщение от AEXks Посмотреть сообщение
Thinker, в каком плане не понятно ?

Не по теме:

я просто не работал программно с GPU

AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:38     Быстрая проверка натурального числа на простоту #36
Тут все просто: так как мы выкинули 2ки и 3ки то зачем нам их проверять? из-за этого получается две последовательности чисел, которую мы и задаем. на GPU мы имеем много нитей, которые выполняют "свой" код. По этому мы берем и выполняем параллельно проверку сразу нескольких делителей. Этот код заточен на проверку сразу массива чисел, но я тут проверял всегда одно =)

C++
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
57
58
59
__global__ void is_simple(ulong *arr, ulong *info, int idx, ulong sqr, ulong shift, ulong count)
{
    int thIdx = blockIdx.x * blockDim.x + threadIdx.x;
    ulong x;
    
    if(thIdx % 2 == 0)
        x = 3 * thIdx + 5;
    else
        x = 3 * (thIdx - 1) + 7;
    
    ulong temp = arr[idx];
    ulong rez = 1;
    
    for(ulong i = 0; i < count; ++i)
    {       
        rez = rez xor ((temp % x) == 0);
        x += shift; 
    }
    info[thIdx] = rez;
}
 
void is_simple_arr(ulong *in_arr,ulong *out_arr, int dim_arr, float *time)
{
    dim3 blocks(60000);
    dim3 threads(256);
    int coef = 3;
    ulong *devArr,*devInfo;
    cudaEvent_t start,stop;
    
    cudaEventCreate(&start);
    cudaEventCreate(&stop); 
    
    cudaMalloc((void**)&devArr, dim_arr * sizeof(ulong));
    cudaMalloc((void**)&devInfo, blocks.x * threads.x * sizeof(ulong));
    
    device_ptr<ulong> for_reduction(devInfo);
    cudaMemcpy(devArr, in_arr, dim_arr * sizeof(ulong), cudaMemcpyHostToDevice);
    ulong red_rez;
    
    cudaEventRecord(start, 0); 
    for(int i = 0; i < dim_arr; ++i)
    {
        ulong sq = sqrt(in_arr[i]) + 1;
        if(in_arr[i] % 2 != 0 && in_arr[i] % 3 != 0)
        {
            is_simple<<< blocks, threads >>>(devArr, devInfo, i, sq, blocks.x * threads.x * coef, sq/(blocks.x * threads.x * coef) + 1);
            red_rez = reduce(for_reduction, for_reduction + blocks.x * threads.x,999,thrust::minimum<ulong>());
            out_arr[i] = red_rez;           
        }
        else
        {
            out_arr[i] = 0;
        }
    }
    
    cudaEventRecord(stop, 0);
    cudaEventSynchronize(stop);
    cudaEventElapsedTime(time,start, stop);
}
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:50  [ТС]     Быстрая проверка натурального числа на простоту #37
Занятно) Ну, можно некоторые моменты переделать. вместо
C++
1
if(thIdx % 2 == 0)
написать
C++
1
if(!(thIdx & 1))
вместо
C++
1
if(in_arr[i] % 2 != 0)
написать
C++
1
if(in_arr[i] & 1)
вместо
C++
1
ulong sq = sqrt(in_arr[i]) + 1;
написать
C++
1
ulong sq = sqrt(in_arr[i]);
но все это мелочи.
может Вам попробовать третий алгоритм так переделать?
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 21:53     Быстрая проверка натурального числа на простоту #38
это какой именно? я чет прочитав все что тут было написано так и не понял чем они особо отличаются?
Thinker
Эксперт C++
4223 / 2197 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
30.10.2012, 21:56  [ТС]     Быстрая проверка натурального числа на простоту #39
скоростью отличаются. третий алгоритм из поста 1, как минимум, в два раза быстрее чем первый алгоритм. Но это для чисел из диапазона от 2 до 10^8. А при росте чисел прирост скорости будет существенно расти.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.10.2012, 22:14     Быстрая проверка натурального числа на простоту
Еще ссылки по теме:
Проверка на простоту числа C++
Проверка числа на простоту (нужны комментарии) C++
C++ Проверка на простоту числа - исправить ошибки в коде
C++ Робота с динамической памятью, проверка числа на простоту
Проверка цифр натурального числа C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
AEXks
24 / 3 / 1
Регистрация: 28.10.2012
Сообщений: 35
30.10.2012, 22:14     Быстрая проверка натурального числа на простоту #40
Thinker, а ну да, вы собственно и воспользовались тем, что период последовательности числе будет равен произведению выкинутых. Я написал тестовую прогу для вычисления всего этого и вот что у меня вышло:
число выкинутыхпериод количество оставшихся чисел в периоде процент оставшихся всего
1 1 1 50%
2 8 6 33%
3 8 30 26%
4 48 210 22%
5 480 2310 20%
6 576030.030 19%
7 92.160510.510 18%
8 1.658.8799.699.690 17%
   
Таблица растет очень быстро и не ясно как вводить в начале все эти числа. Поясню: для старта проверки на GPU если мы выкинули например 7 чисел, то нужно их каким то образом сообщить конвееру, чтобы 92160 нитям досталось по числу, и потом мы уже к ним прибавляем так называемый shift, равный периоду (в примере 510 510). собственно инициализировать нужно всего один раз. НО так как число то маленькое для GPU (MAX_ULONG) то я думаю из-за чтений из памяти произойдет даже замедление. Так что надо придумывать для длиной арифметики. А все таки как определить номер старшего бита числа, кроме как
C++
1
2
3
4
5
for( ; dig != 0; )
{
     dig >>= 1;
     ++sum;
}
Yandex
Объявления
30.10.2012, 22:14     Быстрая проверка натурального числа на простоту
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru