Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 7 [8] 9 10   вперед  Ctrl      все
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Эх, опять промахнулись... 3317044064679887385961981 - вот тут уже 43 надо.
А вот и нет!

Здесь s = 2.
При s = 1 одни 1 и (n - 1) до 42.
А при s = 0 при 2 сразу составное!
Не понял, это как?
>>> a=3317044064679887385961981
>>> pow(2,a//4,a)
806966215798523717614900
>>> pow(2,a//2,a)
3317044064679887385961980
тут не видно, что составное
3 окт 19, 17:26    [21986094]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Будем категоризировать числа на "простые", "составные" и "неизвестные"?

Это было-бы честно в данном топике.
3 окт 19, 17:30    [21986099]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Что-то у меня сомнения, не наврал ли я в спешке где-то в алгоритме... Надо перепроверить еще раз
3 окт 19, 17:39    [21986109]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov
Здесь s = 2.
При s = 1 одни 1 и (n - 1) до 42.
А при s = 0 при 2 сразу составное!
Не понял, это как?
>>> a=3317044064679887385961981
>>> pow(2,a//4,a)
806966215798523717614900
>>> pow(2,a//2,a)
3317044064679887385961980
тут не видно, что составное
Вот мои расчёты по s = 0 (справа - основание степени, слева - s)

(0, 806966215798523717614900L, 2)
(0, 1L, 3)
(0, 3317044064679887385961980L, 4)
(0, 1L, 5)
(0, 806966215798523717614900L, 6)
(0, 806966215798523717614900L, 7)
(0, 2510077848881363668347081L, 8)

Уже при основании степени 2 видно, что остаток не равен ни 1, ни (n - 1).
А раз этот остаток не равен, то исходное число - составное.
3 окт 19, 17:50    [21986125]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
пропущено...
Не понял, это как?
>>> a=3317044064679887385961981
>>> pow(2,a//4,a)
806966215798523717614900
>>> pow(2,a//2,a)
3317044064679887385961980
тут не видно, что составное
Вот мои расчёты по s = 0 (справа - основание степени, слева - s)

(0, 806966215798523717614900L, 2)
(0, 1L, 3)
(0, 3317044064679887385961980L, 4)
(0, 1L, 5)
(0, 806966215798523717614900L, 6)
(0, 806966215798523717614900L, 7)
(0, 2510077848881363668347081L, 8)

Уже при основании степени 2 видно, что остаток не равен ни 1, ни (n - 1).
А раз этот остаток не равен, то исходное число - составное.
Чего?
13 - 1 = 22*3
Берем основание 2, 23 = 8, это не 1 и не 12 по модулю 13. 13 - составное число?
3 окт 19, 19:39    [21986221]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Barlone
Что-то у меня сомнения, не наврал ли я в спешке где-то в алгоритме... Надо перепроверить еще раз
Разобрался. Небольшая неточность, которая не влияет на результат проверки. Неканонично получилось, результат возведения в степень поделен пополам, но и сравнивается с единицей, а не с 2. Вобщем, можно не исправлять.
3 окт 19, 19:51    [21986234]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Чего?
13 - 1 = 22*3
Берем основание 2, 23 = 8, это не 1 и не 12 по модулю 13. 13 - составное число?
Уговорил. Будет 56.
Тем более, что log = 56.

Я забыл, что по алгоритму сначала (s - 1), а потом (s - 2) и т.д. А не наоборот.
3 окт 19, 19:55    [21986238]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Barlone
Barlone
Что-то у меня сомнения, не наврал ли я в спешке где-то в алгоритме... Надо перепроверить еще раз
Разобрался. Небольшая неточность, которая не влияет на результат проверки. Неканонично получилось, результат возведения в степень поделен пополам, но и сравнивается с единицей, а не с 2. Вобщем, можно не исправлять.
Да, а вот с квадратным корнем надо что-то сделать. 2^1023 еще лезет, а 2^1024 говорит "OverflowError: int too large to convert to float"
3 окт 19, 19:59    [21986239]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Ну теперь вот так:
import math

def jacobi(a, n):
    assert(a > 0 and n % 2 == 1)
    a %= n
    t = 1
    while a != 0:
        while a % 2 == 0:
            a = a // 2
            r = n % 8
            if r == 3 or r == 5:
                t = -t
        a, n = n, a
        if a % 4 == 3 and n % 4 == 3:
            t = -t
        a %= n
    if n == 1:
        return t
    else:
        return 0

def pair2(a, d, n):
    return ((a[0] * a[0] + n - 2) % n, (a[0] * a[1]) % n)
        
def pairmul(a, b, d, n):
    x = (a[0] * b[0] + d * a[1] * b[1]) % n
    if x % 2 == 0:
        x = x // 2
    else:
        x = (n + x) // 2
    y = (a[0] * b[1] + b[0] * a[1]) % n
    if y % 2 == 0:
        y = y // 2
    else:
        y = (n + y) // 2
    return (x, y)

def pairpow(a, m, d, n):
    r = (2, 0)
    while m != 0:
        if m % 2 == 1:
            r = pairmul(r, a, d, n)
        a = pair2(a, d, n)
        m = m // 2
    return r

def isprime(n):
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    if n == 3:
        return True
    if n % 3 == 0:
        return False
    if n == 5:
        return True
    if n % 5 == 0:
        return False

    q = n.bit_length()
    if q < 1023:
        m = int(math.sqrt(n))
        if m * m == n:
            return False
    else:
        m = n >> (q // 2)
    k = (m + n // m) // 2
    while k != m:
        m, k = k, (m + n // m) // 2
    if m * m == n:
        return False
    
    p = 3
    d = p * p - 4
    j = jacobi(d, n)
    while j == 1:
        p = p + 1
        d = p * p - 4
        j = jacobi(d, n)

    if j == 0:
        return False

    if pow(d, n // 2, n) != n - 1:
        return False

    a = pairpow((p, 1), (n + 1) // 2, d, n)

    if a[1] != 0:
        return False
    if a[0] != 2 and a[0] != n - 2:
        return False
    return True
    

for i in range (1,3999,2):
    if (isprime(pow(2,1024)+i)):
        print(i)
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
3 окт 19, 20:12    [21986247]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Barlone
пропущено...
Разобрался. Небольшая неточность, которая не влияет на результат проверки. Неканонично получилось, результат возведения в степень поделен пополам, но и сравнивается с единицей, а не с 2. Вобщем, можно не исправлять.
Да, а вот с квадратным корнем надо что-то сделать. 2^1023 еще лезет, а 2^1024 говорит "OverflowError: int too large to convert to float"
У меня то же самое.

Либо без корня (я не использую корень на больших числах), либо "делить" на части и перемножать.
3 окт 19, 20:45    [21986274]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.

1 мин. 48 сек.
3 окт 19, 20:50    [21986276]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Gennadiy Usov
Barlone
Ищем простые от 2^1024 - нашлись 2^1024 + (643, 1081, 2113, 2715, 3711)
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.

1 мин. 48 сек.
У меня секунд за 15 те же.
3 окт 19, 21:19    [21986280]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
Наконец послушали специалиста. Вы уж там разбирайтесь, но так скоропалительно, а то быстро 30 страниц набежит типа "о-опс, ошибка", "блин, снова ошибся", "ёлы-палы, поспешил" ... ну вы помните. И мой вопрос затеряется, и никто не ответит((

А вопрос у меня сбоку от ваших проблем. Почему остановились на 2^2k ? и диапазон 100тыс хиленький.

Мог бы кто-нибудь найти кол-во простых в след-х дипаз-х (для сравнения с оценкой, к-рую я давал 2-3 дня назад):
2^p	диапазон	оценка
50	1000000	28021,35
100	1000000	14218,81
2048	200000	140,79
4096	500000	176,05
4096	1000000	352,10
8192	500000	88,04
8192	1000000	176,08
Попутно интересно отработать модные теперь эвристики для погрешности оценки. Это чтобы не вычислять типа 1/(Ln x - 2) для больших x и т.п.

Интересно посмотреть насколько относительная погрешность апроксимируется величиной sqrt(1/f(x)), где f(x) есть кол-во простых в диапазоне. И тогда абсолютная погрешность sqrt(f(x)).
Вообще я догадываюсь, что далеко не всегда так будет, но на нашем скудном материале даже различие 70 и 79 примерно на границе такой погрешности (прикидывал на бумажке, без калькулятора).
А тоя смотрю, как после p=1024 относит-я погр-ть скакнула в 1000 раз для p=2K(2024)

Ну и сами диапазоны в будущем хочется подлиннее.
3 окт 19, 21:27    [21986281]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
exp98, чтобы такие диапазоны обсчитывать, надо бы с питона на что-то более быстрое перейти.
4 окт 19, 05:14    [21986369]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
Gennadiy Usov
Ещё 5335, 5793, 5947, 7015, 7447, 7935, 8953, 8995, 9855.
1 мин. 48 сек.
У меня секунд за 15 те же.
С предварительным делением на малые множители или нет?

И ПК у меня старенький.
4 окт 19, 05:59    [21986375]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
exp98
Наконец послушали специалиста.
Почему остановились на 2^2k ? и диапазон 100тыс хиленький.
Попутно интересно отработать модные теперь эвристики для погрешности оценки. Это чтобы не вычислять типа 1/(Ln x - 2) для больших x и т.п.
Интересно посмотреть насколько относительная погрешность апроксимируется величиной sqrt(1/f(x)), где f(x) есть кол-во простых в диапазоне. И тогда абсолютная погрешность sqrt(f(x)).
Вообще я догадываюсь, что далеко не всегда так будет, но на нашем скудном материале даже различие 70 и 79 примерно на границе такой погрешности (прикидывал на бумажке, без калькулятора).
А тоя смотрю, как после p=1024 относит-я погр-ть скакнула в 1000 раз для p=2K(2024)
Ну и сами диапазоны в будущем хочется подлиннее.
Что нам даёт погрешность от "специалиста"?

Вот и sqrt после p=1024 не работает, и "скакнула" скорость после p=1024.
И всё.

Есть формула количества, а есть расчёты.
Уточняем формулу или уточняем расчёты?

У одного 70, у другого 79, а что у "специалиста" - неизвестно.
И что это даёт?
Наверное не формулу, а что-то другое
4 окт 19, 06:28    [21986380]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Barlone
exp98, чтобы такие диапазоны обсчитывать, надо бы с питона на что-то более быстрое перейти.
Обсчитали, и что это даст?

Будем прыгать и радоваться, что посчитали около 2^(какое-то)?
Кого сейчас этим удивишь, когда существуют мощные компьютеры.

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

Чтобы сравнивать алгоритмы, надо считать не время, а считать раунды.

Ведь формулы везде одинаковы, что у нас, что в Африке.
Только каждый их по разному применяет

Раунды не зависят ни от языка, ни от ПК.
4 окт 19, 06:39    [21986381]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
mayton
Member

Откуда: loopback
Сообщений: 42918
Gennadiy Usov
Чтобы сравнивать алгоритмы, надо считать не время, а считать раунды.

Почти правильно. Я добавлю что надо считать не время а некие элементарные мат-операции
которые надо выполнить чтобы достичь результата. И оценить как эти операции растут
от объема данных.

Обычно - нелинейно. И есть также заблуждение о том что умножение занимает единицу времени.
Для длинных целых чисел умножений зависит квадратично от разрядной сетки числа.
Это тоже надо учитывать. Как - не знаю но надо.

Если всё правильно оценить - получим асимптоматику.
4 окт 19, 11:16    [21986538]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9486
Gennadiy Usov
Чтобы сравнивать алгоритмы, надо считать не время, а считать раунды.
"Сколько времени придётся ждать?" - это я понимаю.
"Сколько раундов будет сделано?" - не понимаю, да и какая мне разница???
4 окт 19, 11:22    [21986543]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
Gennadiy Usov
Что нам даёт погрешность от "специалиста"? ... Уточняем формулу или уточняем расчёты?
Вам - ничего, мне - удовольствие.
Каждый косит свой газон. Да вы и свои рассчёты не торопились ещё недавно уточнять, что изменилось вдруг?

Не принц, конечно, но что есть,то есть, за сколько мне вам отдаться?
4 окт 19, 11:44    [21986576]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
exp98
Member

Откуда:
Сообщений: 1846
Basil A. Sidorov, я не вдаюсь в подробности, видимо это некая агрегированная прмежуточная величина алгоритма. Возможно пропорциональная вычислительной сложности этого модуля. Щас речь не о пользователях.
4 окт 19, 11:47    [21986583]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Basil A. Sidorov
Gennadiy Usov
Чтобы сравнивать алгоритмы, надо считать не время, а считать раунды.
"Сколько времени придётся ждать?" - это я понимаю.
"Сколько раундов будет сделано?" - не понимаю, да и какая мне разница???
Почитайте про тест Миллера-Рабина
https://ru.wikipedia.org/wiki/Тест_Миллера_—_Рабина
Там всё написано про раунды.

Главная трудность работы тестов простоты - это количество раундов.
Этим количеством увеличивают вероятность получения нужного числа случайным образом.
4 окт 19, 15:06    [21986817]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Basil A. Sidorov
Member

Откуда:
Сообщений: 9486
Gennadiy Usov
Главная трудность работы тестов простоты - это количество раундов.
Этим количеством увеличивают вероятность получения нужного числа случайным образом.
Я читал. Вопрос был другой.
4 окт 19, 15:11    [21986824]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
А вот интересная задача (по поводу определения раундов)

import math
a1= math.sqrt(1000000000000000000000001)//1
a2 = math.sqrt(1000000000000000000000000000000000000000000001)//1
print (a1, a2)

И печать результатов:

(1000000000000.0, 3.1622776601683792e+22)

Вот почему одно число целое, а другое число вещественное?
4 окт 19, 15:59    [21986879]     Ответить | Цитировать Сообщить модератору
 Re: Эвристический алгоритм (формула, тест простоты) для определения простых чисел  [new]
Barlone
Member

Откуда:
Сообщений: 1348
Что-то у меня на диапазоне 200000 с 22048 нашлось 151 число. Черт возьми, надо было их вывести, а не просто посчитать.
4 окт 19, 16:09    [21986889]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 3 4 5 6 7 [8] 9 10   вперед  Ctrl      все
Все форумы / Программирование Ответить