[Sharky]

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

Дано: M -- любое целое положительное число и не обязательно является точным квадратом.
Задача: Представить sqrt(M) в виде дроби X/Y, решение которой есть квадратный корень M

На помощь в решении приходит уравнение Пелля. Однако, если M не является точным квадратом то существует бесконечное множество решений.. нужно найти самое простое.

[Sharky]

Вот брошюра про уравнения Пелля с некоторыми теоремами и доказательствами (на русском языке).

[Sharky]

Вот еще ссылки на англ. языке:

[Зарегистрироваться?]'s_equation
[Зарегистрироваться?]. html
[Зарегистрироваться?]

[DoubleZero]

Сообщение от Sharky писал вс, 06 мая 2007 12:39

Дано: M -- любое целое положительное число и не обязательно является точным квадратом.
Задача: Представить sqrt(M) в виде дроби X/Y, решение которой есть квадратный корень M

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

[Sharky]

Сообщение от DoubleZero писал вс, 06 мая 2007 13:15

В чем тогда проблема?

Представить его максимально приближенным к точному, произвести расчет за минимальное время и получить малые значения (X,Y).

[tigra_7]

Sharky, а поточнее можно?

Сообщение от Цитата:

Представить sqrt(M) в виде дроби X/Y, решение которой есть квадратный корень M

Нужен просто алгоритм, или есть ограничения на количество операций или что-то ещё?

P.S. Да, а другие книжки от НМУ у тебя есть?

P.P.S Вот тут вспомнил про итерационную формулу Герона : X_(n+1)=0.5(X_n+a/X_n). X_n->sqtr(a) Причем сходится очень быстро.

[Sharky]

Сообщение от tigra писал вс, 06 мая 2007 20:34

Нужен просто алгоритм, или есть ограничения на количество операций или что-то ещё?

В принципе нужен _быстрый целочисленный_ алгоритм для произвольного m не превышающего 2^127-1...

Сообщение от tigra писал вс, 06 мая 2007 20:34

P.S. Да, а другие книжки от НМУ у тебя есть?

Тебе сюда, наверное: [Зарегистрироваться?]

[tigra_7]

Спасибо за ссылку.

Сообщение от Цитата:

В принципе нужен _быстрый целочисленный_ алгоритм для произвольного m не превышающего 2^127-1...

То есть такое жёсткое требование : именно целые, рациональные не подходят ?Просто тот алгоритм Герона, который я предложил очень быстрый и везде используется для (калькуляторы по сути по нему считают).

[Sharky]

Сообщение от tigra писал вс, 06 мая 2007 21:14

То есть такое жёсткое требование : именно целые, рациональные не подходят ?Просто тот алгоритм Герона, который я предложил очень быстрый и везде используется для (калькуляторы по сути по нему считают).

Все что я не знал -- уже забыл.. а то что знал -- забыл еще раньше.. (c)
По-твоему алгоритм Герона может разложить sqrt(m) на x/y не используя уравнение Пелля? Интересно, каким образом?

P.S. вообще-то я думал, что калькуляторы используют полиномный метод.. или я не прав?

[tigra_7]

Пролистал книжку, потом посмотрел на алгоритм Герона как оказалось те же яйца если требовать рациональность для x_1. Сейчас под вечер уже туго соображаю, но завтра утром напишу все свои толковые мысли.

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