Доброго времени суток!
У нас есть несколько пар чисел, являющихся решениями квадратичного сравнения:
$%x_i=a_i+np_i, \space\space n \in ℕ$%
$%y_i=b_i+np_i, \space\space n \in ℕ$%
и отрезок $%[Down; Up]$%

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

(Мой вариант: если $%(\space [floor((Up-x_i)/p-(Down-x_i)/p) \ne0]\space OR \space[floor((Up-y_i)/p-(Down-y_i)/p) \ne 0]\space)$%, то попадает.
и мне кажется, что он долог и ненадежен.)
(я не знаю, как в латексе сделать округление вниз, поэтому написал floor)
Заранее спасибо всем откликнувшимся!

задан 11 Авг '13 20:32

изменен 12 Авг '13 18:13

У Вас в условии существенно, что $%n$% -- именно натуральное число? Или любое целое тоже бы подошло?

В том условии, которое Вы выписали в конце, фигурируют два числа, и между ними -- логическая связка "или". Там, наверное, какие-то неравенства имелись в виду, или я что-то не разобрал?

(11 Авг '13 20:59) falcao

именно натуральные числа.
да, там следующим образом: либо левая скобка не ноль, либо правая не ноль. ну или обе не ноль. поправил еще: добавил округление вниз.

(11 Авг '13 21:35) miramentis
10|600 символов нужно символов осталось
1

Любой из алгоритмов (формул), предложенных выше (в описании задачи, ответе @falcao и коментариях к нему) будет работать в разы быстрее, чем само вычисление корней сравнения, если использовать операцию целочисленного деления вместо дробного с последующим округлением вниз. Не знаю, в паком мат. пакете или на каком языке Вы производите вычисления, но такое там обязательно есть. Так что по этому поводу можно не беспокоиться.

ссылка

отвечен 24 Авг '13 18:08

10|600 символов нужно символов осталось
0

Для упрощённого случая, когда имеется одна арифметическая прогрессия вида $%a+np$%, я бы поступил так. Сначала находим наибольшее целое $%n$%, для которого $%a+np\le u$%. Это не что иное как число $%n=\lfloor\frac{u-a}{p}\rfloor$%. Далее проверяем, верны ли неравенства $%n\ge1$% и $%d\le a+np$%. Если оба они верны, то одно из чисел прогрессии попадает в отрезок $%[d;u]$%; верно и обратное.

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

ссылка

отвечен 12 Авг '13 21:03

Я правильно понимаю, что речь идёт об одном и том же квадратичном сравнении по модулю степеней одного и того же простого числа? Насколько велика при этом длина отрезка $%[d;u]$%? Если она не слишком большая, то можно проверить эти числа поочерёдно. Если же это долго, можно найти наибольшее $%k$%, для которого $%p^k$% попадает в отрезок, а потом применять метод половинного деления. То есть брать показатель примерно $%k/2$%, если $%k$% не годится, а потом искать показатель между $%0$% и $%k/2$%, или между $%k/2$% и $%k$% -- в зависимости от исхода.

(12 Авг '13 22:47) falcao

вы все правильно понимаете.
отрезок может быть разным: от ~1500 до ~250000.
ну... как бы вам сказать... именно это наибольшее $%k$% мне и нужно найти =)
поиск начинается с $%k=1$% и до тех пор, пока корень попадает в отрезок. как только перестал попадать - нашли нужное $%k$%

(13 Авг '13 1:31) miramentis

я вообще хотел конкретизировать задачу и поставил вопрос - что у меня не получается

(13 Авг '13 14:50) miramentis

Я так понимаю, что проверка попадания числа в отрезок для данного фиксированного показателя степени не составляет труда и делается при помощи нахождения целой части. И тогда можно не проверять по отдельности каждое число $%i$%, воспользовавшись методом половинного деления. Чем не годится такой алгоритм? Он слишком медленный получается?

(13 Авг '13 15:17) falcao

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

(13 Авг '13 21:18) miramentis
1

А что если сделать так: взять алгоритм решения квадратичного сравнения из Вашего предыдущего вопроса, и применить его к нахождению корней из заданного отрезка. Тогда сначала решаем сравнение по модулю $%p$% и находим серии вида $%\pm x_0+pk$%, где $%k$% целое. Записываем неравенства вида $%d\le\pm x_0+pk\le u$%, после чего получаются границы для $%k$%. При этом длина отрезка $%[d;u]$% уменьшается примерно в $%p$% раз. Далее решаем сравнение по модулю $%p^2$%, где всё сводится к линейному сравнению по модулю $%p$% после подстановки. То есть этот алгоритм должен работать быстро.

(13 Авг '13 23:26) falcao

да, отличный вариант. спасибо большое за ответ!

(21 Авг '13 11:35) miramentis
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×573

задан
11 Авг '13 20:32

показан
708 раз

обновлен
24 Авг '13 18:08

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru