2014 dxdy logo

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

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




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

 
 
 
 Re: Уравнения Пелля без иррациональных чисел
Сообщение03.10.2018, 09:01 
Пробежал глазами — вроде ж всё просто, не? Делаем вектор, подвергаем левым/правым преобразованиям в зависимости от, пока не получим исходный, ну и так далее. Что именно непонятно?

 
 
 
 Re: Уравнения Пелля без иррациональных чисел
Сообщение07.10.2018, 22:10 
Проинтерпретировалось в коде так:
Код:
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 
На русском по теме от А.В. Спивак: видео и книжка "Арифметика-2" (Библиотечка Квант, с.75).
Моя реализация в Геогебре.

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group