Dmitriy40Спасибо, что откликнулись. Вот это сильно обнадеживает:
Для не слишком больших чисел, скажем до
![$10^{19..38}$ $10^{19..38}$](https://dxdy-04.korotkov.co.uk/f/7/b/d/7bd004727e7c787590fc36e8926bda3a82.png)
, извлечение целочисленного квадратного корня не проблема, не быстро, но миллионы в секунду вполне реально (например до
![$10^{19}$ $10^{19}$](https://dxdy-01.korotkov.co.uk/f/4/d/d/4ddc019143f8a983383ad5c37907412482.png)
корень извлекается 15 млн.раз/с), это у меня уже давно написано.
Мне нужно аккуратно прикинуть, насколько велики будут коэффициенты решаемых квадратных уравнений, если исходить из границы
![$10^9$ $10^9$](https://dxdy-01.korotkov.co.uk/f/0/6/5/065159456ed4c790e33155c119a0726f82.png)
. Надеюсь уложиться в Ваши размеры. Позже я напишу подробное изложение алгоритма; он в самом деле крайне примитивный, ничего общего с (действительно) очень сложным алгоритмом отыскания целых точек на эллиптической кривой общего вида. А сейчас выложу код на Maple, чтобы Вы могли чисто визуально (а может, и содержательно) понять, что с точки зрения математики здесь все примитивно.
Используются две вспомогательные процедуры. Первая находит целую часть квадратного корня из натурального
![$N$ $N$](https://dxdy-04.korotkov.co.uk/f/f/9/c/f9c4988898e7f532b9f826a75014ed3c82.png)
:
Код:
FloorSqrt:=proc(N)
local x,x_next;
if N=0 then return 0 end if;
x:=iquo(N+1,2); x_next:=iquo(x+iquo(N,x),2);
while x>x_next do
x:=x_next; x_next:=iquo(x+iquo(N,x),2)
end do;
return x
end proc:
Вторая решает квадратные уравнения
![$at^2+bt+c=0$ $at^2+bt+c=0$](https://dxdy-03.korotkov.co.uk/f/2/9/8/2981c93abc68f70147777e3f060cb40782.png)
с целыми коэффициентами в целых числах:
Код:
solve_int:=proc(a,b,c)
local S,d,d2;
if a=0 and b=0 then return {} end if;
if a=0 then if irem(c,b)=0 then return {-c/b} else return {} end if end if;
S:={};
d:=b^2-4*a*c;
if d>=0 then d2:=FloorSqrt(d);
if d2^2=d then
if irem(-b+d2,2*a)=0 then S:=S union {(-b+d2)/2/a} end if;
if irem(-b-d2,2*a)=0 then S:=S union {(-b-d2)/2/a} end if;
end if;
end if;
return S;
end proc:
Ну и, собственно, сама программа:
Код:
runge:=proc(H)
local S,m,Q,k,res,x,y;
S:={[0,-1]};
m:=1+floor(evalf(abs(H)^(1/4)));
Q:=floor(evalf(m/(m^2-2)+sqrt((m+abs(H))/(m^2-2)+2/(m^2-2)^2)));
for k from -m to m do
res:=solve_int(k^2-2,2*k,H-k+1);
for x in res do S:=S union {[x,-k*x-1]} end do
end do;
for x from 1 to Q do
res:=solve_int(x,1,-2*x^3+H*x+1);
for y in res do S:=S union {[x,y]} end do
end do;
for x from -Q to -1 do
res:=solve_int(x,1,-2*x^3+H*x+1);
for y in res do S:=S union {[x,y]} end do
end do;
return S
end proc:
По существу, здесь решается две порции квадратных уравнения (выделены вертикальными пробелами), причем вторая порция --- это исходное уравнение, решаемое относительно
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
(а
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
в роли параметра, который перебирается в заранее вычисленных границах от
![$-Q$ $-Q$](https://dxdy-01.korotkov.co.uk/f/0/2/e/02e7597581801b2a16be4bd34fc3476682.png)
до
![$Q$ $Q$](https://dxdy-02.korotkov.co.uk/f/1/a/f/1afcdb0f704394b16fe85fb40c45ca7a82.png)
, исключая
![$x=0$ $x=0$](https://dxdy-01.korotkov.co.uk/f/8/4/3/8436d02a042a1eec745015a5801fc1a082.png)
). Первая порция квадратных уравнений зависит от вспомогательного параметра
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
(который перебирается в заранее вычисленных границах от
![$-m$ $-m$](https://dxdy-04.korotkov.co.uk/f/f/5/1/f51155c92690d7dfbf249973199e536f82.png)
до
![$m$ $m$](https://dxdy-01.korotkov.co.uk/f/0/e/5/0e51a2dede42189d77627c4d742822c382.png)
), а неизвестным в уравнении является
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
(по известному
![$k$ $k$](https://dxdy-03.korotkov.co.uk/f/6/3/b/63bb9849783d01d91403bc9a5fea12a282.png)
и найденному корню
![$x$ $x$](https://dxdy-04.korotkov.co.uk/f/3/3/2/332cc365a4987aacce0ead01b8bdcc0b82.png)
затем вычисляется
![$y$ $y$](https://dxdy-02.korotkov.co.uk/f/d/e/c/deceeaf6940a8c7a5a02373728002b0f82.png)
).
Если бы Вы заменили мои вульгарно написанные (с точки зрения программирования; математически они корректны) вспомогательные процедуры Вашими оптимизированными, можно было бы покуситься на рекорд.