2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Уравнения Пелля без иррациональных чисел
Сообщение03.10.2018, 07:07 


16/08/05
1146
Предлагаю к обсуждению статью Norman Wildberger "Pell’s equation without irrational numbers". Хотелось бы воспроизвести метод в pari/gp и проверить на составных $D$, что у меня пока не получается, т.к. не всё понимаю в статье. Самое интересное - равносильна вычислительная трудоёмкость факторизации составных $D$, или нет.

 Профиль  
                  
 
 Re: Уравнения Пелля без иррациональных чисел
Сообщение03.10.2018, 09:01 
Заслуженный участник


16/02/13
4105
Владивосток
Пробежал глазами — вроде ж всё просто, не? Делаем вектор, подвергаем левым/правым преобразованиям в зависимости от, пока не получим исходный, ну и так далее. Что именно непонятно?

 Профиль  
                  
 
 Re: Уравнения Пелля без иррациональных чисел
Сообщение07.10.2018, 22:10 


16/08/05
1146
Проинтерпретировалось в коде так:
Код:
njw(d)=
{
L= [1,0;1,1]; R= [1,1;0,1];
A= [1,0;0,-d]; Q= A; N= 1;
while(1,
  a= Q[1,1]; b= Q[1,2]; c= Q[2,2];
  t= a+2*b+c;
  if(t<0, Q= R~*Q*R; N= N*R, Q= L~*Q*L; N= N*L);
  if(Q==A, break())
);
return(N[,1]~)
};


Проверка:
Код:
? #
   timer = 1 (on)
?
? \r njw.gp
?
? njw(2)
%2 = [3, 2]
?
? njw(7)
%3 = [8, 3]
?
? njw(61)
%4 = [1766319049, 226153980]
?
? njw(991)
%5 = [379516400906811930638014896080, 12055735790331359447442538767]
?
? pell=njw(8616460799);
time = 1,357 ms.
?
? gcd(pell[1]-1,8616460799)
%7 = 96079
?
? factorint(8616460799)
%8 =
[89681 1]

[96079 1]


Кто-нибудь может прокомментировать пункт 8.Speeding up the algorithm, или что можно подкрутить, чтоб ускорить этот алгоритм?

 Профиль  
                  
 
 Re: Уравнения Пелля без иррациональных чисел
Сообщение09.12.2018, 14:31 


16/08/05
1146
На русском по теме от А.В. Спивак: видео и книжка "Арифметика-2" (Библиотечка Квант, с.75).
Моя реализация в Геогебре.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group