Немного о факторизации / Программирование

ReSQL.ru

Мобильная версия Контакт Правила FAQ Помощь

Гость

Войти | Регистрация | Профиль | Очистить

Новые сообщения | Избранное

Форумы | Пользователи | Статистика | Мод. лог | Поиск

Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Немного о факторизации

25 сообщений из 163, страница 3 из 7

все

Немного о факторизации

#39911126

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov,
неправильно понимаешь
я то проверил, всё что написал, всё верно.

согласен?

...

Рейтинг:

0 / 0

06.01.2020, 13:16

| Ответить | Цитировать | Написать

Немного о факторизации

#39911130

Gennadiy Usov

Гость

kealon(Ruslan)

Gennadiy Usov,
неправильно понимаешь
я то проверил, всё что написал, всё верно.
согласен?

Всё проверил, только одно забыл:
как завершается наш пример - число 45 и р = 61.

Где последние расчёты, где получаемые множители?

...

Рейтинг:

0 / 0

06.01.2020, 13:41

| Ответить | Цитировать | Написать

Немного о факторизации

#39911221

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov,

а я обещал их найти?

...

Рейтинг:

0 / 0

06.01.2020, 20:42

| Ответить | Цитировать | Написать

Немного о факторизации

#39911230

Gennadiy Usov

Гость

kealon(Ruslan)

Gennadiy Usov,
а я обещал их найти?

А проверка своего метода 22053148 ?

Как известно:
мужик сказал, ...

Или метод 22053148 никуда не годится?

...

Рейтинг:

0 / 0

06.01.2020, 21:30

| Ответить | Цитировать | Написать

Немного о факторизации

#39911240

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov,

у меня всё сходится

2^14 | _{p2 = 1500

31^14 | _{p2 = 3089

[1500 * 3089] | _{p2 = 855

Код: plaintext
1.
2.
3.
75 1109 1514 855
136 2157 1672 855
197 471 3154 855
258 698 2736 855
....

насчёт слева: "дай итератор степенной, гуляющий по числам < p" ..., есть ????}}}

...

Рейтинг:

0 / 0

06.01.2020, 22:32

| Ответить | Цитировать | Написать

Немного о факторизации

#39911286

Gennadiy Usov

Гость

Составил программу факторизации с помощью метода с использованием непрерывных дробей.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
Исходное 11111 = 41*271.

Перебираю разные простые числа вместо 41 и всё получается.
А на числе 13 - не получается. Интересно!

И на числах 23, 53, 73,...

Что-то мне подсказывает,
что не "проходят" числа, у которых последняя цифра 3.

Хотя прошло 11 * 283.

...

Рейтинг:

0 / 0

07.01.2020, 07:58

| Ответить | Цитировать | Написать

Немного о факторизации

#39911429

Gennadiy Usov

Гость

Нашел у себя ошибку: не до конца прочитал условие алгоритма.

Если не получилось, то надо продолжать (следующий прогон). И всё.

Взял за основу перебор нечётных числ от 3 до 100 (первое число) и число 257 (второе число).

Обычно множители находятся за 1 - 2 прогона.

Множитель 13 найден за 14 прогонов, 71 - за 40 прогонов, 73 - за 14 прогонов, 83 - за 48 прогонов, 97 - за 53 прогона.
А на 89 - программа зависла - очень много прогонов... (в результате не хватает места для одного из массивов)

...

Рейтинг:

0 / 0

07.01.2020, 20:02

| Ответить | Цитировать | Написать

Немного о факторизации

#39911480

Gennadiy Usov

Гость

Продолжаю исследования метода с использованием непрерывных дробей.

Взял за основу перебор нечётных числ от 3 до 255 (первое число) и число 257 (второе число).

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

Если количество прогонов ограничить числом 100000 (!), то получается,
что невозможно найти множителей (кроме 1 и произведения двух чисел) для произведения двух чисел,
когда первое число:
89, 139, 151, 181, 197, 211, 229, 239, 251

...

Рейтинг:

0 / 0

08.01.2020, 09:45

| Ответить | Цитировать | Написать

Немного о факторизации

#39911726

Gennadiy Usov

Гость

Немного подумал и "проскочил" 89.

Например, для числа 167 необходимо 36 прогонов и здесь "фигурируют" числа в районе Е+200.

...

Рейтинг:

0 / 0

08.01.2020, 19:19

| Ответить | Цитировать | Написать

Немного о факторизации

#39911854

Gennadiy Usov

Гость

Составил программу факторизации с помощью метода с использованием квадратичных форм.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf

Формулы похожие на формулы непрерывных дробей.

Было бы интересно объединить эти два метода,
однако при применении этих методов повторяются числа, по которым нельзя найти множители.

Например, при переборе нечётных чисел от 3 до 1000 (первое число) и для числа 257 (второе число)
не находятся множители по двум методам для чисел:
113, 191, 193, 313, ... и т.д.

...

Рейтинг:

0 / 0

09.01.2020, 09:21

| Ответить | Цитировать | Написать

Немного о факторизации

#39911861

kealon(Ruslan)

Участник

Откуда: Нижневартовск

Сообщения: 4 020

Рейтинг: 0 / 0

Gennadiy Usov

это равноценные методы
что имеется ввиду?

...

Рейтинг:

0 / 0

09.01.2020, 09:42

| Ответить | Цитировать | Написать

Немного о факторизации

#39911917

Gennadiy Usov

Гость

kealon(Ruslan)

Gennadiy Usov

Составил программу факторизации с помощью метода с использованием квадратичных форм.
Было бы интересно объединить эти два метода,
однако при применении этих методов повторяются числа, по которым нельзя найти множители.

Например, при переборе нечётных чисел от 3 до 1000 (первое число) и для числа 257 (второе число)
не находятся множители по двум методам для чисел:
113, 191, 193, 313, ... и т.д.

это равноценные методы
что имеется ввиду?

Методы не равноценны, потому что у каждого из них свой перечень "неопределяемых множителей".
Эти два перечня имеют некоторое пересечение.

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

...

Рейтинг:

0 / 0

09.01.2020, 11:41

| Ответить | Цитировать | Написать

Немного о факторизации

#39912710

Gennadiy Usov

Гость

Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.

...

Рейтинг:

0 / 0

11.01.2020, 07:39

| Ответить | Цитировать | Написать

Немного о факторизации

#39912726

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy Usov

Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.

Насколько я помню, в таких случаях умножают число на маленькие простые: 30623*2, 30623*3, ... И при этом может найтись множитель, не равный этому маленькому простому - то есть множитель исходного числа.

...

Рейтинг:

0 / 0

11.01.2020, 10:49

| Ответить | Цитировать | Написать

Немного о факторизации

#39912734

Gennadiy Usov

Гость

Barlone

Gennadiy Usov

Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.

Спасибо!

Помогло 2 и 23, дальше из простых не смотрел.

...

Рейтинг:

0 / 0

11.01.2020, 11:26

| Ответить | Цитировать | Написать

Немного о факторизации

#39912746

Gennadiy Usov

Гость

Проверка показала,
что для каждого простого числа, на которое умножается искомое число,
существует свой перечень не определяемых чисел.

Эти перечни могут пересекаться, а могут и не пересекаться.

...

Рейтинг:

0 / 0

11.01.2020, 12:35

| Ответить | Цитировать | Написать

Немного о факторизации

#39914531

Gennadiy Usov

Гость

При составлении алгоритмов всегда было интересно:
какие операции на ПК выполняются быстрее?
А если вместо одного возведения в квадрат выполнять несколько сложений?
и т.д.

Сделал тест на питоне в виде цикла от 1 до 10000000.

Сам цикл (чистый) занимает 0,59 сек.
Если в цикле одно сложение (2**100-1) + (2**101-1), то время работы 1,23 сек.
Если в цикле одно умножение (2**100-1) * (2**101-1), то время работы 1,56 сек.
Если в цикле одно действие по остатку (2**100-1) % (3**20), то время работы 3,17 сек.

...

Рейтинг:

0 / 0

15.01.2020, 19:12

| Ответить | Цитировать | Написать

Немного о факторизации

#39914550

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Усов. Бросай свои числа. Go-go решать задачи.

https://www.sql.ru/forum/1321195/zadacha-s-korobkami-iz-vetki-pro-terver

...

Рейтинг:

0 / 0

15.01.2020, 19:58

| Ответить | Цитировать | Написать

Немного о факторизации

#39914862

Barlone

Участник

Сообщения: 1 506

Рейтинг: 0 / 0

Gennadiy Usov

Программа это хорошо. Но еще неплохо бы понимать теорию, почему он вообще работает. Почему в первом цикле должна встретится квадратная форма? Почему во втором цикле должна встретиться неоднозначная форма, и почему из ее коэффициентов можно найти делитель?

...

Рейтинг:

0 / 0

16.01.2020, 15:30

| Ответить | Цитировать | Написать

Немного о факторизации

#39914888

Gennadiy Usov

Гость

Barlone

Gennadiy Usov

Программа это хорошо.
Но еще неплохо бы понимать теорию, почему он вообще работает.
Почему в первом цикле должна встретится квадратная форма?
Почему во втором цикле должна встретиться неоднозначная форма, и
почему из ее коэффициентов можно найти делитель?

Каждый из методов кто-то разработал и составил перечень операций.
Методы работают не для всех чисел, но для многих чисел работают, и то хорошо.
Влезать в теорию алгоритма пока нецелесообразно, поскольку не понятно: а зачем?

Осталось понять: а как эти методы применить, если применять.
Если применять, то можно влезать в алгоритмы.

Или это остаётся экзотикой.

...

Рейтинг:

0 / 0

16.01.2020, 16:02

| Ответить | Цитировать | Написать

Немного о факторизации

#39924035

Gennadiy Usov

Гость

Решил продолжить исследования 22060146 времени работы операций на ПК (Питон):

Получились коэффициенты:
сложение - 12
умножение - 12
остаток по модулю - 24
корень квадратный - 55
по-битовое определение единичек в числе - 8

...

Рейтинг:

0 / 0

07.02.2020, 19:13

| Ответить | Цитировать | Написать

Немного о факторизации

#39925395

Gennadiy Usov

Гость

Работаю в Питоне.

Заметил, что программа "ошибается" при делении на 2 для чисел около 10^18.

398222426974351438
199111213487175712

Что посоветуете?

...

Рейтинг:

0 / 0

11.02.2020, 20:27

| Ответить | Цитировать | Написать

Немного о факторизации

#39925442

exp98

Участник

Сообщения: 2 390

Рейтинг: 0 / 0

Gennadiy Usov

Заметил, что программа "ошибается" при делении на 2 для чисел около 10^18. 398222426974351438 199111213487175712 Что посоветуете?

Это разве не эффект double? 15-16 точных цифр ...

...

Рейтинг:

0 / 0

12.02.2020, 00:12

| Ответить | Цитировать | Написать

Немного о факторизации

#39925446

mayton

Участник

Откуда: loopback

Сообщения: 53 422

Рейтинг: 2 / 0

Gennadiy Usov

Python пытается вывести тип данных из текста который ты лупишь.
Смотри. Ввожу просто разные числа. Разной длины. И с десятичной точкой и без.

Код: python

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

Python 2.7.17 (default, Nov  7 2019, 10:07:09) 
[GCC 7.4.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> type(1.1)
<type 'float'>
>>> type(1)
<type 'int'>
>>> type(100000)
<type 'int'>
>>> type(100000000000000000000)
<type 'long'>
>>> type(10000000000000000000000000000000000000000000000000)
<type 'long'>
>>> 
>>> type(long(1))
<type 'long'>

Если выводимый тип - неудачен - то дальше вся цепочка вычислений будет нехорошей.
Типы данных - это самая первая наука которую учат на уроках информатики.
И контроль за ними должен быть предельно жёстким.

Как только ты объявляешь переменную - ты должен знать какие числа в ней будут лежать.
Целые или вещественные. И если целые то какой максимальный диспазон надо обеспечить.

В последней строке я попытался Питону объявить что единичка имеет тип long.

...

Рейтинг:

0 / 0

12.02.2020, 00:58

| Ответить | Цитировать | Написать

Немного о факторизации

#39925460

Gennadiy Usov

Гость

У меня Python 3.7.4.
И в нём нет "long".

Пробую дальше.

Вместо / поставил // и получилось.
И результат становится int (как положено).

То есть:
не int (a/2),
a a // 2

Хотя // должен отбрасывать дробные части, ещё уменьшая целое число.
В справочниках: "Получение целой части от деления"

...

Рейтинг:

0 / 0

12.02.2020, 06:44

| Ответить | Цитировать | Написать

25 сообщений из 163, страница 3 из 7

все

Форумы / Программирование [игнор отключен] [закрыт для гостей] / Немного о факторизации

Цитировать

Написать

Автор*:

Ввести пароль для входа

Тема*:

Сообщение

Данное сообщение тематическое

Сообщение содержит картинки или видео 18+

Автор:

ВНИМАНИЕ! На данном подфоруме действуют строгие правила. Удостоверьтесь, что ваше сообщение соответствует им!

Форум или тема закрыты для гостей. Необходима авторизация!

Загрузить последнюю сохраненную версию

Вложение:

Вставить как галерею

Максимальный размер вложений: 4,0 МБ, аудио/видео: 8,0 МБ. Картинки большего размера ужимаются, если возможно.

Введите код, изображенный на картинке. Если код нечитаемый, кликните картинку, чтобы загрузить другой вариант.

Отправляя сообщение, я выражаю свое согласие с правилами форума и принимаю пользовательское соглашение.

Читали тему (0):

Читали форум (0):

Пользователи онлайн (0):

start [/forum/topic.php?fid=16&msg=39912726&tid=1339626]:	0ms
get settings:	10ms
get forum list:	14ms
check forum access:	4ms
check topic access:	4ms
track hit:	146ms
get topic data:	10ms
get forum data:	2ms
get page messages:	61ms
get tp. blocked users:	1ms
others:	232ms

total:	484ms