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

Откуда: Нижневартовск
Сообщений: 6017
Gennadiy Usov,
неправильно понимаешь
я то проверил, всё что написал, всё верно.

согласен?
6 янв 20, 13:16    [22053999]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov,
неправильно понимаешь
я то проверил, всё что написал, всё верно.
согласен?
Всё проверил, только одно забыл:
как завершается наш пример - число 45 и р = 61.

Где последние расчёты, где получаемые множители?
6 янв 20, 13:41    [22054006]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

а я обещал их найти?
6 янв 20, 20:42    [22054201]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov,
а я обещал их найти?
А проверка своего метода 22053148?

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

Или метод 22053148 никуда не годится?
6 янв 20, 21:30    [22054215]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

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


2^14 | p2 = 1500
31^14 | p2 = 3089


[1500 * 3089] | p2 = 855


75	1109	1514			855
136 2157 1672 855
197 471 3154 855
258 698 2736 855
....

насчёт слева: "дай итератор степенной, гуляющий по числам < p" ..., есть ????
6 янв 20, 22:32    [22054255]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

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

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

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

Хотя прошло 11 * 283.
7 янв 20, 07:58    [22054351]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

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

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

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

Множитель 13 найден за 14 прогонов, 71 - за 40 прогонов, 73 - за 14 прогонов, 83 - за 48 прогонов, 97 - за 53 прогона.
А на 89 - программа зависла - очень много прогонов... (в результате не хватает места для одного из массивов)
7 янв 20, 20:02    [22054618]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Продолжаю исследования метода с использованием непрерывных дробей.

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

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

Если количество прогонов ограничить числом 100000 (!), то получается,
что невозможно найти множителей (кроме 1 и произведения двух чисел) для произведения двух чисел,
когда первое число:
89, 139, 151, 181, 197, 211, 229, 239, 251
8 янв 20, 09:45    [22054746]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Немного подумал и "проскочил" 89.

Например, для числа 167 необходимо 36 прогонов и здесь "фигурируют" числа в районе Е+200.
8 янв 20, 19:19    [22055111]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

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

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

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

Сообщение было отредактировано: 9 янв 20, 09:22
9 янв 20, 09:21    [22055318]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
kealon(Ruslan)
Member

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

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

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

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

  • это равноценные методы
  • что имеется ввиду?
9 янв 20, 09:42    [22055333]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
kealon(Ruslan)
Gennadiy Usov
Составил программу факторизации с помощью метода с использованием квадратичных форм.
Было бы интересно объединить эти два метода,
однако при применении этих методов повторяются числа, по которым нельзя найти множители.

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

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

Поэтому объединение этих методов позволит несколько уменьшить количество чисел,
для которых нельзя найти множителей при использовании одного из методов.
9 янв 20, 11:41    [22055439]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.
11 янв 20, 07:39    [22057027]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

Откуда:
Сообщений: 1402
Gennadiy Usov
Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.
Насколько я помню, в таких случаях умножают число на маленькие простые: 30623*2, 30623*3, ... И при этом может найтись множитель, не равный этому маленькому простому - то есть множитель исходного числа.

Сообщение было отредактировано: 11 янв 20, 10:50
11 янв 20, 10:49    [22057052]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Gennadiy Usov
Если взять число 113 х 271 = 30623,
то имеем бесконечный цикл из только 5-6 чисел.
Насколько я помню, в таких случаях умножают число на маленькие простые: 30623*2, 30623*3, ... И при этом может найтись множитель, не равный этому маленькому простому - то есть множитель исходного числа.
Спасибо!

Помогло 2 и 23, дальше из простых не смотрел.
11 янв 20, 11:26    [22057064]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

Эти перечни могут пересекаться, а могут и не пересекаться.
11 янв 20, 12:35    [22057089]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

Сделал тест на питоне в виде цикла от 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 сек.

Сообщение было отредактировано: 15 янв 20, 19:21
15 янв 20, 19:12    [22060146]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Усов. Бросай свои числа. Go-go решать задачи.

https://www.sql.ru/forum/1321195/zadacha-s-korobkami-iz-vetki-pro-terver
15 янв 20, 19:58    [22060189]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Barlone
Member

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

Формулы похожие на формулы непрерывных дробей.
Программа это хорошо. Но еще неплохо бы понимать теорию, почему он вообще работает. Почему в первом цикле должна встретится квадратная форма? Почему во втором цикле должна встретиться неоднозначная форма, и почему из ее коэффициентов можно найти делитель?
16 янв 20, 15:30    [22060725]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Barlone
Gennadiy Usov
Составил программу факторизации с помощью метода с использованием квадратичных форм.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
Формулы похожие на формулы непрерывных дробей.
Программа это хорошо.
Но еще неплохо бы понимать теорию, почему он вообще работает.
Почему в первом цикле должна встретится квадратная форма?
Почему во втором цикле должна встретиться неоднозначная форма, и
почему из ее коэффициентов можно найти делитель?
Каждый из методов кто-то разработал и составил перечень операций.
Методы работают не для всех чисел, но для многих чисел работают, и то хорошо.
Влезать в теорию алгоритма пока нецелесообразно, поскольку не понятно: а зачем?

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

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

Сообщение было отредактировано: 16 янв 20, 16:04
16 янв 20, 16:02    [22060778]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

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

Получились коэффициенты:
сложение - 12
умножение - 12
остаток по модулю - 24
корень квадратный - 55
по-битовое определение единичек в числе - 8
7 фев 20, 19:13    [22075768]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
Работаю в Питоне.

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

398222426974351438
199111213487175712

Что посоветуете?
11 фев 20, 20:27    [22077871]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
exp98
Member

Откуда:
Сообщений: 2446
Gennadiy Usov
Заметил, что программа "ошибается" при делении на 2 для чисел около 10^18. 398222426974351438 199111213487175712 Что посоветуете?
Это разве не эффект double? 15-16 точных цифр ...
12 фев 20, 00:12    [22077935]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
mayton
Member

Откуда: loopback
Сообщений: 48022
Gennadiy Usov
Работаю в Питоне.

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

398222426974351438
199111213487175712

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

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

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.
12 фев 20, 00:58    [22077941]     Ответить | Цитировать Сообщить модератору
 Re: Немного о факторизации  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 2204
У меня Python 3.7.4.
И в нём нет "long".

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

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

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

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

Сообщение было отредактировано: 12 фев 20, 06:45
12 фев 20, 06:44    [22077962]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 2 [3] 4 5   вперед  Ctrl      все
Все форумы / Программирование Ответить