Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 23 24 25 26 27 28 [29] 30 31 32   вперед  Ctrl
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2128
Barlone
Длинная история на английском с кучей матана: https://www.maa.org/sites/default/files/pdf/upload_library/2/Rice-2013.pdf

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

Но там же, хоть авторы и настаиваю на разнице между эллипсами и эллиптическим кривыми, приводится общая формула y2=ax3+bx2+cx+d, из которой при a=c=0, b=-1 и d=1 получаем очевидный частный случай. Хотя в общем - да, это совсем не круг и не эллипс.

А вообще подумалось - вот так надо писать учебники, а не тот сухостой из галиматьи для любителей зубрить наизусть орфографический словарь языка индейцев мяу-мяу. Здесь всё просто и понятно, а если заинтересуют детали - очевидно, что перечитать из институтского курса математики и, самое главное - нахрена оно надо, в отличии от никому ненужных мяу-мяу.
21 мар 19, 13:30    [21839526]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2128
mayton
Забавно. Фукция Эйлера хотя и шумит как дирихле, но достаточно ярко рисует
скопления значений вокруг y=x, y=x/2 ...e.t.c. Думаю что ее с некоторой вероятностью
можно не считать а угадывать.

Там ещё наблюдается шаблон из "уголков", что-то вроде y=x переходящее в y=const и y=const переходящее в y=-x.
21 мар 19, 13:36    [21839535]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Забавно. Фукция Эйлера хотя и шумит как дирихле, но достаточно ярко рисует
скопления значений вокруг y=x, y=x/2 ...e.t.c. Думаю что ее с некоторой вероятностью
можно не считать а угадывать.
Если не трудно, не напомните для картинки что есть х, что y, и что за функция (х)?

Для любой картинки особенно важными являются пограничные зоны.

Сверху - почти четкая прямая, а что может быть снизу?
Там тоже прослеживается некоторая очень редкая точечная линия.
21 мар 19, 15:30    [21839739]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
По горизонтали x.
По вертикали - функция Эйлера от x.
21 мар 19, 17:00    [21839874]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Дарю сорцы.

(буква фи - настоящая. Так и скомпилировано. Спасибо Скале. Позвляет)
  /**
    * Euler's function
    *
    * @param n
    * @return
    */
  def φ(n: Long): Long = {
    var result = 1
    for(i <- 2L to n)
      if (gcd(i,n) == 1)
        result = result + 1

    result
  }


Тут главная процедура. Она просто рисует.

+
import java.awt.Color
import java.awt.image.BufferedImage
import java.io.FileOutputStream
import mayton.primes.PrimeLib._

import javax.imageio.ImageIO

object EulerSpace {

  def main(args: Array[String]): Unit = {

    val SIZE = 512
    val PIXEL = 4

    val HACKY = "d2b21e"
    val DARKLEAVE = "17420f"

    val image = new BufferedImage(SIZE, SIZE, BufferedImage.TYPE_INT_RGB)

    val g2d = image.createGraphics

    g2d.setColor(Color.WHITE)
    g2d.fillRect(0,0,512,512)

    for(x <- 0 until 512) image.setRGB(x, 512 - &#966;(x), 0x00000000)

    ImageIO.write(
      image,
      "PNG",
      new FileOutputStream(s"out/euler-space-${SIZE}x${SIZE}.png"))

  }


}

Исходники gcd я уже публиковал.
22 мар 19, 22:46    [21841366]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Ну вот это φ - и есть буква фи. Странно что не отрисовалась.
22 мар 19, 22:47    [21841368]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Забавно. Фукция Эйлера хотя и шумит как дирихле, но достаточно ярко рисует
скопления значений вокруг y=x, y=x/2 ...e.t.c. Думаю что ее с некоторой вероятностью
можно не считать а угадывать.
Здесь прослеживаются 3 линии:
под 45 градусов - это простые числа
под 22 градуса - это простые числа, умноженные на 2
под 33 градуса - это простые числа, умноженные на 3
и т.д.
23 мар 19, 05:58    [21841504]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
mayton
Я не помню где была ссылка на оригинальный калькулятор но вот этот https://planetcalc.ru/3754/
определяет оба числа как простые.
Нашел факторизатор до 60 знаков
https://ru.numberempire.com/numberfactorizer.php
24 мар 19, 10:27    [21841916]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2128
Gennadiy Usov
Нашел факторизатор до 60 знаков

Шустро считает. До ~2180. Если дальше квадратичная зависимость, что 2360 посчитает в 4 раза медленнее. 21440 в 64 раза (что явно не реально). А если кубическая, то...
24 мар 19, 13:02    [21841987]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Хм. Похоже его сознательно ограничили. Чтоб всякие дилетанты вроде нас не занимались
ерундой. И не грузили чужое железо глупыми вычислениями.
24 мар 19, 14:32    [21842037]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1347
alex55555
Gennadiy Usov
Нашел факторизатор до 60 знаков

Шустро считает. До ~2180. Если дальше квадратичная зависимость, что 2360 посчитает в 4 раза медленнее. 21440 в 64 раза (что явно не реально). А если кубическая, то...
Нет известных алгоритмов факторизации с полиномиальной от количества бит сложностью. Для лучших известных алгоритмов примерная оценка - удвоение времени работы на каждые +12 бит. Так что 2360 - это в 215 раз дольше, а 21440 - дольше в 2105 раз
24 мар 19, 19:01    [21842205]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
В задачах факторизации ищутся множители для очередного целого числа.

В задачах криптографии ищутся простые числа.

А есть ли задачи, в которых надо найти очень большое составное число?
25 мар 19, 07:09    [21842383]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 14090
Gennadiy Usov
А есть ли задачи, в которых надо найти очень большое составное число?

Эта задача легко решается: перемножай простые пока не получишь составное нужного размера.
25 мар 19, 08:13    [21842402]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Dima T
Gennadiy Usov
А есть ли задачи, в которых надо найти очень большое составное число?

Эта задача легко решается: перемножай простые пока не получишь составное нужного размера.
А если формула?

Не зависящая от простых чисел?
25 мар 19, 08:48    [21842415]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
alex55555
Member

Откуда:
Сообщений: 2128
Barlone
Нет известных алгоритмов факторизации с полиномиальной от количества бит сложностью.

Да, забыл, что количество нужно в степень вставлять.
25 мар 19, 11:19    [21842538]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Мне кажется Барлон подытожил наш топик.

Может пора его закрыть? Что еще высасывать из грязного пальца?
25 мар 19, 11:36    [21842553]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5341
Barlone,

а есть какие-то методы факторизации с переводом к другому кольцу вычетов?
25 мар 19, 13:50    [21842754]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
Нашел интересное простое число:

160000000000000000000000000000000009
25 мар 19, 13:54    [21842763]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1836
И ещё одно

1600000000000000000000000000000000000000000000000009
25 мар 19, 13:56    [21842766]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Криптография не дружит с десятичной системой. Поэтому для нас это число - не более чем
забавный факт.
25 мар 19, 13:59    [21842769]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1347
kealon(Ruslan)
Barlone,

а есть какие-то методы факторизации с переводом к другому кольцу вычетов?
Эллиптические кривые?
25 мар 19, 14:01    [21842772]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Barlone
Member

Откуда:
Сообщений: 1347
только это не кольцо
25 мар 19, 14:07    [21842778]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
Dima T
Member

Откуда:
Сообщений: 14090
mayton
Что еще высасывать из грязного пальца?

А как же рекорд 21832949 ?
25 мар 19, 14:11    [21842783]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
mayton
Member

Откуда: loopback
Сообщений: 42897
Dima T
mayton
Что еще высасывать из грязного пальца?

А как же рекорд 21832949 ?

Да ну ево. Тема исжевана.
25 мар 19, 14:14    [21842789]     Ответить | Цитировать Сообщить модератору
 Re: Пятничная задачка. Алгоритм Эратосфена  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 5341
Barlone
kealon(Ruslan)
Barlone,

а есть какие-то методы факторизации с переводом к другому кольцу вычетов?
Эллиптические кривые?
всё таки не то
я имею ввиду со сменой кольца вычетов
например, разложение n=a*b, а вот взять другое полностью нам известное кольцо и как-то привести задачу к нему

пусть возьмём простое p > n*n/2

q>1 удовлетворяющее [n^(-1)|p] * [q^2 - 1] < n/4. будет дискретным корнем
25 мар 19, 14:30    [21842810]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 23 24 25 26 27 28 [29] 30 31 32   вперед  Ctrl
Все форумы / Программирование Ответить