Простенькая задача:
дано два N-числа a и b, определить, есть ли такое N-число c, что a*a+b*b=c*c. Как можно проще всего (в смысле чтоб работало как можно быстрее) это сделать и можно ли это сделать не используя sqrt, а то он считается очень долго?
В принципе задачу можно переформулировать:
дано N-число z, нужно выяснить, есть ли у него целочисленный квадр. корень c. Но мне почему-то кажется, что частный случай z=a*a+b*b, то есть что z это сумма квадратов, можно как-то использовать...

theone
А зачем это все? Пифагоровы тройки можно искать по формуле (p^2-q^2)^2+(2*p*q)^2=(p^2+q^2)^2, где p и q натуральные, p>q.

Проверять число на квадратность можно по-разному, но чтобы было быстрее операции сопроцессора, придется постараться.

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

Добавлено спустя 1 минуту, 56 секунд:
а такжк ещё можно попробовать поискать соотношения сторон треугольника по формулам Виета

theone


Если не использовать sqrt, то, наверное, только перебором:

c будет больше max(a,b)
c будет не больше max(a,b)*sqrt(2)

Вот в этом промежутке от max до 1,41*max и нужно искать пересечение функции f(C)=C^2-const с нулем, где const=A^2+B^2. Методов для перебора немало существует. Один из них, вроде бы, метод золотого сечения.

А может все же проще и быстрее через sqrt ?
Поищи инфу о том, как различные компиляторы/интерпретаторы считают sqrt. Попробуй то же самое реализовать, только с точностью до десятых (больше и не нужно -- числа то натуральные ищутся)

vor

Любопытно, и как использовать эту устрашающую формулу ?

xKVtor
Подставить какие-нибудь p, q - получатся a, b, c (это то, что в скобках).
Например, если p=2, q=1 будет a=p^2-q^2=3, b=2pq=4, c=p^2+q^2=5.

А вот все ли решения получаются таким способом - забыл.

Взял наугад p=33 q=32 -- работает!!!

Правда, для нахождения p & q из a & b (которые заданы в условии) потребуется решить квадратное уравнение. А чтобы его решить, необходимо как минимум два раза извлечь квадратный корень. Получается, что этот вариант не лучше, чем просто с=sqrt(a*a+b*b)

Думаю быстрее сопроцессорной инструкции fsqrt не получится

Помню реализовывал sin один раз через ряды - скорость получилась такая же как обычный sin() у BC3.1. Но самым шустрым был вызов sin у сопроцессора


числа a и b могут быть какими? Понятно, что натуральными. Я имею в виду диапазон (отрезок), в который они попадают

Очень похоже на правду.

Накатал тут на досуге программулину, реализующую описанный мною алгоритм, и сравнил результаты с sqrt.

Без использования сопроцессора результат лучше (38 секунд против 44 секунд).
С использованием сопроцессора результат гораздо хуже (38 секунд против 4 секунд). Подозреваю, что моему алгоритму не помогут никакие оптимизации.

vor
Да, мне нужно найти все пифагоровы тройки (ну или хотя бы их количество), т.е. тройки (a,b,c), удовлетворяющие уравнению a*a+b*b=c*c, при 1<a<b<c<=1000000. И чтобы все это считалось за 5-10сек.
Формула твоя находит не все тройки (напр., по ней нельзя найти тройку (9,12,15)).
CHRONOS
По-подробнее если можно...
xKVtor
Насчет перебора - была у меня такая мысля, только за верхнюю границу для c я думал брать a+b, а насчет sqrt(2)*b даже как-то и не подумал. Теперь думаю брать за верхнюю границу I=min{a+b;sqrt(2)*b}, т.к. при 2*b>5*a (приблизительно) лучше брать a+b, а при 2*b<5*a - sqrt(2)*b.
Только не знаю, как делать поиск. Я знаю только бинарный поиск, а он при диапазоне N=I-b-1 в худшем (т.е. в большинстве) случае будет делать logN по основанию 2 шагов, а при больших диапазонах это многовато...

Это, наверно, слишком круто для меня ...

all
Попробую реализовать бинарный поиск и сравню по скорости с sqrt. Но мне кажется что кардинально ничего не изменится. Может у кого-нибудь есть мысли, как оптимальнее всего решить вышеописанную заадчу (про тройки). Может как-то можно откидывать какие-то пары (a,b), для которых точно не найдется нужного c?

theone
Эта тройка производный случай тройки [3/4/5] --> [3*3/3*4/3*5] таких троек можно миллион наплодить [x*3/x*4/x*5]

Отсюда следует вывод: желательно ввести оптимизацию -- предварительно проверять пары a и b на наибольший общий делитель. Хотя, достаточно просто на общий делитель. Если найдется хотя бы один, то такую пару чисел можно не обсчитывать и переходить к следующей.

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

Общий делитель считается быстрее, чем кв. корень???
Сомневаюсь... Возьмем тот же алгоритм Евклида... неприятно и долго...

Добавлено спустя 3 минуты, 17 секунд:

вообще коли на то пошло, что из любой тройки [a;b;c] можно получить бесконечно много троек [a*x;b*x;c*x]
Док-во:
(a*x)^2+(b*x)^2=(a^2+b^2)*x^2=c^2*x^2=(c*x)^2

Уже 2 дня обсуждения, и всё равно не уверен, что нужно theone - то ли нахождение с (по a и b) - как способ нахождения пифагоровых троек, то ли поиск всех пифагоровых троек как способ нахождения с.
Если всё-таки ищутся пифагоровы тройки, а формула позволяет сгенерировать все тройки ( с учётом дополнительной генерации домножением), то искать общие делители незачем. Можно сначала наплодить прямо по формуле (и p<1000, и q<1000), а потом для
не самых больших c (для тех с, которые в двое, втрое меньше 1000000) намножить ещё - только надо повторы пресечь.
Проблема - в каком порядке все эти тройки хранить. Пока наилучшим вариантом представляется по порядку возрастания c.

Root
А может стоит попробовать не искать общий делитель для двух чисел a и b, а самостоятельно конструировать их из простых чисел.
Каждое число есть ни что иное, как произведение некоторых простых чисел, возведенных каждое в определенную степень.

Пример:

b= Pn^Bn * P(n-1)^B(n-1) * ... * P2^B2 * P1^B1
a= Pn^An * P(n-1)^A(n-1) * ... * P2^A2 * P1^A1

Pk - простые числа;
Ak,Bk - степени, в которые их возводят;
n - номер максимального натурального числа в диапазоне N (в нашем случае: N=1 000 000)

должны выполняться условия:

a<b
a<N
b<N
Ak*Bk=0 (одна из степеней обязательно должна быть нулевой, иначе числа будут иметь общий делитель)

Проблемы:

1.(главная) Необходимо найти ВСЕ простые числа в исследуемом промежутке (в нашем случае -- от 0 до миллиона)
2. надо потом эти числа где то хранить (в нашем случае них будет под сотню тысяч)
3. надо так же найти место и для хранения индексов Ak и Bk -- это еще 2 массива, таких же огромных, как и предыдущем пункте
4. числа а и b не берутся по-порядку, а их необходимо конструировать, затрачивая на это вычислительные ресурсы и время; сам алгоритм описывать не буду -- как-нибудь в другой раз (проще прогу написать)

Достоинство:

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

Остальные тройки можно будет "наплодить"

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

я на олимпиаде развлекался: тоже надо было что-то с простыми числами считать. Так написали прогу, генерирующую список п.ч., а потом просто в массив запихали. Скорость была - супер! (зачем считать? просто выберем элемент из заранее просчитанного массива) Но расход памяти был неприятным

зачем считать каждый раз? один раз посчитать и набить в прогу....

Такое и с sqrt можно сделать (если нормализовать в относительные еденицы - cn=c/b, bn=b/b=1 an=a/b), то можно достаточно плотно составить
таблицу cn=sqrt(1+an) - =f(an), и тогда с=cn*b (с какой-то погрешностью). Начинать надо с an=1/708 (sqrt(1/500000)).

Заглянул в книжку - действительно, все тройки a,b,c , не имеющие общего делителя больше 1, получаются из формулы. И этим способом будет во много раз быстрее, чем перебором.

Добавлено спустя 3 минуты, 58 секунд:
Dometer

Хранить не обязательно. Можно найти одну и домножать, пока она не выйдет за пределы 10^6. Но тогда они не будут упорядочены. Хранить в памяти можно, если не под DOS. Их около 10^6 и будет. (очень приблизительно)

Результаты:
С бинарным поиском ничего хорошего не получилось: при lim=30000 (1<a<b<c<=lim) после всех оптимизация 42 сек. против 9 сек. Причем 9 сек. было на почти самом примитивном алгоритме:

Так что поиск - гиблое дело...

Зато при использовании формулы при таком же lim=30000 программа работает примерно 0.6 сек. Теперь ее нужно еще максимально оптимизировать. Теперь основной вопрос: как быстрее всего проверить, являются ли два числа взаимно простыми?. На всякий случай вот "черновой" код (считает только кол-во троек), может кто-то знает C++ и сможет еще оптимизировать:

cntr - кол-во пифагоровых троек.
При lim=30000, cntr=42686
При lim=100000, cntr=161436
При lim=1000000, cntr=1980642 (worktime=624 sec.)
vor

Но не только такие тройки. В общем случае по формуле (p^2-q^2)^2+(2*p*q)^2=(p^2+q^2)^2, p<q, p,q из N, где a=p^2-q^2, b=2*p*q, c=p^2+q^2, находятся тройки следующих типов:
1) ВСЕ простые тройки [a;b;c] (a,b,c взаимно простые <=> НОД(a,b,c)=1)
2) ВСЕ тройки вида [k*a;k*b;k*c], где a,b,c взаимно простые, а k-квадрат N-числа (напр. [4a;4b;4c], [9a;9b;9c], [16a;16b;16c])
3) НЕКОТОРЫЕ тройки вида [l*b;l*a;l*c], где l - N-число, [a;b;c] - простая тройка. Напр. [8;6;10], [24;10;26], ...
xKVtor,Root,Dometer,vor
пока еще не въехал в вашу идею, завтра подумаю...

Я (и не только я) предлагаю найти все "простые", а остальные получить домножением.
Простая тройка получается из взаимно простых p,q.

По коду:
1. Зачем проверять, что меньше - p или q, если q от p+1?
2. Зачем проверять p,q на простоту?

Я бы сделал так: в двойном цикле (как здесь) проверяем p,q на взаимную простоту - по алг. Евклида, потом считаем тройку a,b,c и добавляем к счетчику троек сразу lim/c , учитывая кратные. Всё!

vor

да, ступил я...

Если в моем алгоритме убрать эту проверку, то он будет работать немного медленнее, т.к. если p и q не взаимно простые, то дальше проверять уже ничего не нужно (т.к. этот вариант уже учитывался). При этом проверять p и q на взаимную простоту проще, чем a и b (они больше, к тому же их сначала надо посчитать).

Во-первых, что за алгоритм Евклида?
Во-вторых, то что p и q взаимно простые, еще не значит, что получаемая из них тройка еще не учитывалась. Например, при p=1, q=3 (взаимно простые) получаем тройку [8;6;10]=[6;8;10], а эта тройка уже учитывалась, как кратная тройке [3;4;5].

Не верно: p=1,q=3 - тройка [6;8;10] - не простая...

Дык, я весь свой предыдущий пост посявятил предложению, как этого можно достигнуть.

Возможно, выгоднее не брать по-порядку p и q, и не проверять потом их на взаимную простоту, а самим генерировать (конструировать) по описанному мною способу. Выполнение условия Ak*Bk=0 как раз и обеспечивает взаимную простоту полученных чисел.

Элементарные примеры:

Пример #1:

Имеем ряд простых чисел:

p4=7; p3=5; p2=3; p1=2- простые числа;

Сгенеерируем q и p:

a4=2; a3=0; a2=1; a1=0 - степени этих простых чисел для генерации q;
b4=1; b3=1; b0=1; b1=0 - степени этих простых чисел для генерации p;

Получим:

q=7^2 * 5^0 * 3^1 * 2^0=49*3=147
p=7^1 * 5^1 * 3^1 * 2^0=49*3=210

Числа не являются взаимно простыми, т.к. не все условия Ak*Bk=0 выполнены: a2*b2=1<>0

Пример #2:

p4=7; p3=5; p2=3; p1=2- простые числа;

Сгенеерируем q и p:

a4=1; a3=0; a2=0; a1=3 - степени этих простых чисел для генерации q;
b4=0; b3=1; b0=1; b1=0 - степени этих простых чисел для генерации p;

Получим:

q=7^1 * 5^0 * 3^0 * 2^3=56
p=7^0 * 5^1 * 3^1 * 2^0=15

Числа являются взаимно простыми, т.к. все условия Ak*Bk=0 выполнены и общих делителей, соответственно, нет.

ЗЫ: В моем предыдущем посте очепятка:Конечно же: не натурального, а простого.

Добавлено спустя 5 часов, 26 минут, 3 секунды:
Хороший вопрос, я бы тоже с удовольствием узнал ответ на него


Ну, ты тут и наколбасил !

Попробуем разобраться и разложить все по полочкам...

Для начала определимся с используемой формулой. Возьмем за основу вариант, изложенный во втором посте:

(p^2-q^2)^2+(2*p*q)^2=(p^2+q^2)^2 (*)

где:

p и q -- натуральные,

Обозначим для удобства составные части формулы:

a=p^2-q^2 (**)
b=2*p*q (***)
c=p^2+q^2 (****)

Естественно: a,b,c -- натуральные числа. Из этого факта и из (**) вытекает еще одно важное условие:

p>q (*****)

Еще одно немаловажное условие, заданное в первом посте этой ветки:

0<a<b<c<limit=N (******)

Если речь пойдет о разных тройках, то для обозначения их элементов (a,b,c, а так же p и q) будем использовать индексы.

Продолжим.

Во-первых, [8;6;10] и [6;8;10] формально совершенно разные тройки, т.к. значения входящих в них чисел находились по разным формулам и на основе различных оснований p и q. Формально на основе условия (******) первую тройку мы вообще не должны учитывать.

Неверно. На основе p=3,q=1 (раз уж условились, что p>q) получается тройка [8;6;10], а не [6;8;10], которая получается из тройки, в основе которой p=2,q=1.

В процессе размышлений над этим вопросом родились две элементарные теоремы.

Теорема #1:

Если тройка a1,b1,c1 получена на основе взаимно простых натуральных чисел q1,p1, то не существует другой тройки чисел a2=k*a1, b2=k*b1, c2=k*c1 (k-натуральное число), которая была бы составлена на основе натуральных и взаимно простых чисел q2,p2.

Доказательство: {от противного}

Допустим существует такое k, что основания получившейся тройки q2,p2 являются нат-ми и взаимно простыми. Тогда:

a2=k*a1=k*(p1^2-q1^2)=(sqr(k)*p1)^2-(sqr(k)*q1)^2
b2=k*b1=2*(sqr(k)*p1)*(sqr(k)*q1)
c2=k*c1=(sqr(k)*p1)^2+(sqr(k)*q1)^2

Переобозначим:

sqr(k)*p1=p2
sqr(k)*q1=q2

a2=p2^2-q2^2
b2=2*p2*q2
c2=p2^2+q2^2

Видно, что p2 и q2 не что иное, как основание новой тройки. Причем:

1. если sqr(k) - не натуральное число, то p2 и q2 -- не натуральные
2. если sqr(k) - натуральное число, то p2 и q2 имеют общий множитель=sqr(k) и следовательно не являются взаимно простыми.

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

Теорема #2:

Если тройка a1,b1,c1 получена на основе натуральных взаимно-простых чисел q1 и p1, то существует такое число k, что основание q2,p2 новой тройки a2=k*b1, b2=k*a1, c2=k*c1 так же будет натуральным числами (а при k=2 и удачном стечении обстоятельств еще и взаимно простыми)

Доказательство:

a2=p2^2-q2^2==k*b1=k*(2*p1*q1)
b2=2*a2*b2==k*a1=k*(p1^2-q1^2)
c2=p2^2+q2^2==k*c1=k*(p1^2+q1^2)

[c2(+)a2]:

(p2^2+q2^2)+(p2^2-q2^2) == k*(p1^2+q1^2) + k*(2*p1*q1)
2*p2^2 == k*((p1+q1)^2)

p2=sqr(k/2)*(p1+q1)

[c2(-)a2]:

(p2^2+q2^2)-(p2^2-q2^2) == k*(p1^2+q1^2) - k*(2*p1*q1)
2*q2^2 == k*((p1-q1)^2)

q2=sqr(k/2)*(p1-q1) [напомню: p>q]

Пусть k=2*z^2.
Получаем, что при любом натуральном z основанием q2,p2 второй тройки будет натуральное число.
А при k=2 (z=1) числа q2,p2 имеют неплохие шансы на то, чтобы быть взамно простыми.#

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

Добавлено спустя 1 час, 2 минуты, 56 секунд:
Еще один момент (пока не лег )

Поскольку от нас требуется, чтобы a<b, то можно попробовать узнать, каким образом это условие повлияет на подбор q и p.
a<b
p^2-q^2<2*p*q
(p^2+q^2-2*p*q)-2*q^2<0
(p-q)^2<2*q^2
Поскольку p>q и q>0, то:
p-q<sqr(2)*q

p<q*(sqr(2)+1) (*******) - это необходимое условие подбора q и p, обеспечивающее a<b.

Примеры (из ранее рассмотренных):

p=2,q=1 => 2<(~1.41+1)~2.8 - условие выполнено, a<b [3;4;5]
p=3,q=1 => 3>(~1.41+1)~2.8 - условие не выполнено, a>b [8;6;10]