Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу 1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 22 апр 2019, 18:35 
Не в сети
Начинающий
Зарегистрирован:
22 апр 2019, 17:54
Сообщений: 14
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Здравствуйте!

Мне по работе требуется запрограммировать алгоритм решения неопределенного уравнения 2-го порядка:

a⁢x² + b⁢x⁢y + c⁢y² + d⁢x + e⁢y + f = 0

... с нулевым коэффициентом при xy. Подбирая в сети что-то подходящее, наткнулся на такой ресурс:

Generic two integer variable equation solver,

который завис на первом же примере:

-2 * x^2 + 76759502 * x + 8 * y^2 - 2301002776 * y + 49328368 = 0,

имеющем как минимум решение при y = 320436 и x = 19189151.

Обстоятельства моего положения таковы, что можно обсуждать финансовую сторону вопроса. Не являясь профессиональным математиком, я запрограммировал метод, который сам же и разработал, я называю его линейной интерполяцией, когда на интересуемом участке подбираются точки соотношения x и y в виде целого натурального числа. Однако, вдруг затерзали сермяжные подозрения, а не изобретаю ли я велосипед...

Буду признателен за ответы.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 22 апр 2019, 18:59 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
03 апр 2012, 19:13
Сообщений: 13534
Откуда: Москва
Cпасибо сказано: 1290
Спасибо получено:
3616 раз в 3175 сообщениях
Очков репутации: 678

Добавить очки репутацииУменьшить очки репутации
А почему такие коэффициенты огромные?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 22 апр 2019, 19:13 
Не в сети
Начинающий
Зарегистрирован:
22 апр 2019, 17:54
Сообщений: 14
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Вообще-то они маленькие. Могу пояснить, почему они именно такие "маленькие-большие". Это предельно максимальные, при которых я могу проверять работоспособность своей программы при помощи калькулятора Windows. Рабочие коэффициенты представляются сотнями десятичных знаков.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 22 апр 2019, 21:21 
Не в сети
Гений
Зарегистрирован:
02 фев 2017, 00:21
Сообщений: 615
Cпасибо сказано: 7
Спасибо получено:
184 раз в 163 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
[math]\begin{array}{l}
A{x^2} + B{y^2} + Cx + Dy + E = 0\\
A\left( {{x^2} + \frac{C}{A}x + \frac{{{C^2}}}{{4{A^2}}}} \right) + B\left( {{y^2} + \frac{D}{B}y + \frac{{{D^2}}}{{4{B^2}}}} \right) + E - \left( {\frac{{{C^2}}}{{4A}} + \frac{{{D^2}}}{{4B}}} \right) = 0\\
A{\left( {x + \frac{C}{{2A}}} \right)^2} + B{\left( {y + \frac{D}{{2B}}} \right)^2} = \frac{{{C^2}}}{{4A}} + \frac{{{D^2}}}{{4B}} - E\\
z = x + \frac{C}{{2A}}\,\,\,\,\,\,\,t = y + \frac{D}{{2B}}\,\,\,\,\,\,\,K = \frac{{{C^2}}}{{4A}} + \frac{{{D^2}}}{{4B}} - E\\
A{z^2} + B{t^2} = K
\end{array}[/math]


Если [math]A[/math] и [math]B[/math] имеют разные знаки, то дальше ищите про уравнения Пелля - для них дан исчерпывающий метод их решения, причем элементарный. Если же у них одинаковые знаки, то тут нужно серьезно заниматься изучением этого класса, сходу его найти не могу.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю underline "Спасибо" сказали:
kda
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 22 апр 2019, 23:16 
Не в сети
Начинающий
Зарегистрирован:
22 апр 2019, 17:54
Сообщений: 14
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Знаки коэффициентов при вторых степенях x и y разные.

Знаете, у меня сейчас очень странное ощущение. Наверное, потому что слово "элементарно" приходилось слышать часто. Вместе с тем люди, которым мы предлагали приличные контракты за конкретное годное для программирования решение для A = -2 и B = 8 как-то терялись в неизвестном направлении...

Надо посмотреть. Странно, что управнение Пелля я отверг практически с самого начала... А тут очевидная манипуляция, к нему приводящая. Уважаемый, Вы бы не исчезали далече, еще нужно оценить годность для встраивания в программный продукт "элементарного метода решения", который еще в свою очередь требуется поискать. Вдруг там какая-нибудь засада. Я с конкретной темой уже больше трех лет, правда по программной, а не математической части, всякое бывало.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 22 апр 2019, 23:49 
Не в сети
Последняя инстанция
Зарегистрирован:
08 апр 2015, 12:21
Сообщений: 7567
Cпасибо сказано: 229
Спасибо получено:
2751 раз в 2539 сообщениях
Очков репутации: 473

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю michel "Спасибо" сказали:
kda
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 23 апр 2019, 12:58 
Не в сети
Начинающий
Зарегистрирован:
22 апр 2019, 17:54
Сообщений: 14
Cпасибо сказано: 3
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
michel писал(а):
Вообще говоря, это уже не уравнения Пелля возникают, если приведенные дроби не являются целыми числами. Похоже, что это гораздо более трудная задача, что-то я не видел готовых алгоритмов решения подобных уравнений.


Вот именно. Но в моем случае можно схимичить. Программный курсор, положение которого отображают коэффициенты D, E и F, можно "двигать" самыми разными способами. Правда реализация допускает только одно направление движения - вперед, до полного обнуления коэффициента D. Там и конец поиска (вершина параболы f(x)). Пример работы метода MoveNext(),реализующего 1 итерацию прямого перебора:

-2 * x^2 + 76759502 * x + 8 * y^2 - 2301002776 * y + 49328368 = 0, y0 = 320436
-2 * x^2 + 76759382 * x + 8 * y^2 - 2301002760 * y + 51108860 = 0, y1 = 320435
-2 * x^2 + 76759262 * x + 8 * y^2 - 2301002744 * y + 52885768 = 0, y2 = 320434

Другими словами, можно рассчитать величину движения, добиваясь "правильных" дробей. В принципе, я так и делаю, научив программу мгновенно переходить к точкам целых соотношений k = x / y + z. И мы были весьма рады, добившись вместо 320436 итераций прямого перебора на конкретном примере не более 1 тыс. "тычков" в подобные точки, пока не обнаружили, что "покрытие одного тычка" стремительно скукоживается при увеличении разрядности. Гораздо быстрее, чем мы ожидали. Вот что значит не держать в штате профессионального математика...

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 23 апр 2019, 13:39 
Не в сети
Гений
Зарегистрирован:
02 фев 2017, 00:21
Сообщений: 615
Cпасибо сказано: 7
Спасибо получено:
184 раз в 163 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
michel
В чистом виде - да. Но можно и до него довести, немного доработав напильником. В крайнем случае, решение в рациональных можно добыть, умножив еще на[math]A^{2}B^{2}[/math]

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 23 апр 2019, 13:44 
Не в сети
Гений
Зарегистрирован:
02 фев 2017, 00:21
Сообщений: 615
Cпасибо сказано: 7
Спасибо получено:
184 раз в 163 сообщениях
Очков репутации: 21

Добавить очки репутацииУменьшить очки репутации
kda
Так-то нужно заняться этим. Существенных проблем, пока, не вижу. О диофантовых я осведомлен немного поверхностно, нужно порыться в литературе, но в будни мне не до этого. Может, в выходные скажу немного конкретнее.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Диофантовы уравнения с 2 неизвестными
СообщениеДобавлено: 23 апр 2019, 14:45 
Не в сети
Мастер
Зарегистрирован:
08 янв 2016, 15:28
Сообщений: 225
Cпасибо сказано: 2
Спасибо получено:
26 раз в 24 сообщениях
Очков репутации: 2

Добавить очки репутацииУменьшить очки репутации
Я в прошлом году пытался изобрести вычислительный программный алгоритм для следующей задачи:
имеется число m, которое может быть сколь угодно большим
Требуется разложить число m по основанию другого произвольного числа n с помощью полинома степени d:
m = n[math]^{d}[/math] + a[math]_{d-1}[/math]n[math]^{d-1}[/math] + .... + a[math]_{0}[/math]

Основное требование - сумма коэффициентов a[math]_{0}[/math], ... , a[math]_{d-1}[/math] должна быть минимальна,
эти коэффициенты могут быть равны нулю

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

Я думаю, что кто-то уже наступал на эти грабли

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу 1, 2, 3  След.  Страница 1 из 3 [ Сообщений: 30 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Диофантовы уравнения

в форуме Теория чисел

Anashkin V

2

272

21 дек 2020, 01:11

Диофантовы уравнения

в форуме Алгебра

Petja234

19

697

27 май 2021, 11:57

Диофантовы уравнения

в форуме Теория чисел

lenka44_44

7

636

12 сен 2018, 22:10

Диофантовы уравнения

в форуме Геометрия

mdauletiyarov

5

171

05 ноя 2022, 07:17

Преобразовать диофантовы уравнения

в форуме Алгебра

gtdd1962

6

420

18 янв 2016, 10:43

Подгонка суммы или диофантовы уравнения

в форуме Дискретная математика, Теория множеств и Логика

stmnf

2

412

02 фев 2019, 06:01

Два уравнения с тремя неизвестными

в форуме Теория чисел

s_e_r_g

4

306

08 авг 2019, 21:18

Решение Линейного уравнения с 3 неизвестными

в форуме Линейная и Абстрактная алгебра

LIAL

10

1784

29 янв 2016, 10:38

Система из одного уравнения с тремя неизвестными

в форуме Интересные задачи участников форума MHP

one man

8

279

24 янв 2023, 21:05

Диофантовы пятерки

в форуме Теория чисел

s_e_r_g

17

537

16 апр 2022, 12:29


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved