 |
|
|
 
|
|
Задача на квадратичные иррациональности, вычисление периода бесконечной дроби 
| xctepx |
|
|||
 Новичок Профиль Группа: Участник Сообщений: 23 Регистрация: 24.12.2005 Репутация: нет Всего: нет |
Помогите с такой задачей :
"Представить квадратичную иррациональность в виде бесконечной периодической дроби". Здесь кв. иррациональность = (A + B * Sqrt©) / D. Проблема состоит в том, что надо реализовать быстрый способ нахождения периода, т.к. пользуясь стандартным (когда вычисляешь сам), прога зависает. В системе Mathematica реализована функция ContinuedFraction, которая раскладывает квадратичную иррациональность в дробь с периодом в 3000 чисел буквально в 3-5 секунд! Там в доке говорится, что использовался модифицированный метод Лемера. Если кто-нибудь знает что-то по этому поводу, большая просьба ответить. Заранее благодарен. |
|||
|
||||
Загрузка ...
| MBo |
|
|||
|
Бывалый  Профиль Группа: Участник Сообщений: 234 Регистрация: 10.6.2002 Репутация: 5 Всего: 18 |
Хм... Иррациональные числа непредставимы точно в виде периодической дроби.
Может, речь идет о цепной дроби типа a0 +1/(1+a1/(1+a2/(...))) ? |
|||
|
||||
| xctepx |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 23 Регистрация: 24.12.2005 Репутация: нет Всего: нет |
Да, именно о ней. И проблема состоит в том, как быстро вычислить период. (Остальное уже сам сделал)
|
|||
|
||||
| drkot |
|
|||
 Ищущий Профиль Группа: Завсегдатай Сообщений: 1042 Регистрация: 5.5.2006 Репутация: нет Всего: 8 |
А самто искать пытался?
-------------------- Ошибка не становится истиной по причине широкого распространения, как и Истина не становится Ошибкой из-за того, что никто её не видит. |
|||
|
||||
| nostromo |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 194 Регистрация: 23.3.2006 Репутация: 5 Всего: 10 |
Цепные дроби и уравнение Пелля (и будет счастье).
http://www.mccme.ru/mmmf-lectures/books/bo...book.14.pdf.zip http://www.mccme.ru/mmmf-lectures/books/bo...book.13.pdf.zip --------------------
На пыльных тропинках далеких планет останутся наши следы. |
|||
|
||||
| esperant0 |
|
|||
 Опытный Профиль Группа: Участник Сообщений: 714 Регистрация: 20.5.2005 Репутация: 4 Всего: 14 |
если не секрет, как уравнение пеля связанно с определением периода цепной дроби:? -------------------- Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть. |
|||
|
||||
| nostromo |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 194 Регистрация: 23.3.2006 Репутация: 5 Всего: 10 |
Уравнение Пелля (p^2 - n* q^2 == 1) по сути и есть квадратическая иррациональность. Решить уравнение Пелля --- значит найти некоторое приближение к sqrt{n}, причем эффективный алгоритм связан с построением цепной дроби.
Известно также, что цепная дробь является периодической тогда и только тогда, когда она является представлением квадратической иррациональности. В методичках все есть... --------------------
На пыльных тропинках далеких планет останутся наши следы. |
|||
|
||||
| xctepx |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 23 Регистрация: 24.12.2005 Репутация: нет Всего: нет |
Большое спасибо! Но мой вопрос состоял в том, что нужен БЫСТРЫЙ поиск соответствующей бесконечной периодической цепной дроби!
|
|||
|
||||
| nostromo |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 194 Регистрация: 23.3.2006 Репутация: 5 Всего: 10 |
Почитайте указанные книжки внимательнее.
Если я все равильно понял, Ваше выглядит так: A+B*sqrt(D), и можно предложить примерно следующий алгоритм: 1. Ищем решение уравнения Пелля для числа B^2 * D (строим цепную дробь для числа B * sqrt(D)). Эффективный алгоритм построения цепной дроби --- это алгоритм "вытягивания носов" в брошюре о цепных дробях. 2. Найденное решение уравнения Пелля гарантирует, что найден период соответствующей цепной дроби. Это следует из рекурсивных соотношений для решений уравнения Пелля. 3. Прибавляем к цепной дроби константу A и получаем ответ. --------------------
На пыльных тропинках далеких планет останутся наши следы. |
|||
|
||||
| xctepx |
|
|||
|
Новичок Профиль Группа: Участник Сообщений: 23 Регистрация: 24.12.2005 Репутация: нет Всего: нет |
Ещё раз большое спасибо за ответ! Уже всё готово! И работает!
|
|||
|
||||
|
|
| Правила форума "Алгоритмы" | |
|
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
| 0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Алгоритмы | Следующая тема » |
[ Время генерации скрипта: 0.0490 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |