интерактивный курс: введение в программирование на PARI/GP

[wrest]

Dmitriy40 в сообщении #1637834 писал(а):

Заметьте что 144*5e6=720e6, в 10 раз меньше 7ГБ!

А... да, 0,7ГБ отъелось на 5 млн. чисел порядка $10^{44}$. Но претензии к управлению размером стека остаются
parisize = 8000000, primelimit = 500000
? nf=Map()
%1 = Map([;])
? for( i=1, 5000000, mapput(nf,random(10^22)*10^22+random(10^22),0) );
? sizebyte(nf)
%3 = 719999816
? sizebyte(nf)/#nf+0.
%4 = 143.99996320000000000000000000000000000
?

[gris]

Как можно коротко записать/вычислить число вида
n=(((((13^3-7)^3-7)^3-7)^3-7)^3-7)^3-7;
с k парами скобок? Что-то типа рекурсивной процедуры?
Я придумал только
n=13; k=7; for( i=1,k-1, n=n^3-7);

[Dmitriy40]

Забавный непрактичный вариант:
fold((x,y)->x^3-y,[13,7,7,7,7,7,7,7]);

[gris]

Dmitriy40, спасибо!
Уже применил в своих корыстных целях в виде
n=fold((x,y)->x^3-7*y,[13,9,19,19,9]);
Работает! Надо изучить.

[Dmitriy40]

Забавно работает сравнение:

? Mod(2,3)==5
%1 = 1

Т.е. равно. По модулю.
Я раньше думал что сравнивается лишь числитель (т.е. эквивалентно lift(Mod(2,3))==5).

[maxal]

Dmitriy40 в сообщении #1649812 писал(а):

Я раньше думал что сравнивается лишь числитель (т.е. эквивалентно lift(Mod(2,3))==5).

Сравнение a==b в PARI/GP всегда вычисляется через сравнение разности a-b с нулем. Здесь мы имеем:

? Mod(2,3) - 5
%1 = Mod(0, 3)

Т.е. тип t_INT приводится к t_INTMOD, а не наоборот.
И, кстати, называть значение вычета "числителем" (как и его модуль "знаменателем") не принято.

-- Thu Aug 22, 2024 19:58:24 --

wrest в сообщении #1637205 писал(а):

Изготовление вектора [коэффициентов] из полинома:
? vector(#P,i,polcoef(P,#P-i))
%3 = [1, 5, 3, 4]

Можно просто Vec(P) или Vecrev(P) в зависимости от того, с какого конца хочется начинать перечислять коэффициенты.

-- Thu Aug 22, 2024 20:03:30 --

gris в сообщении #1637800 писал(а):

Вопрос: Нельзя ли в forvec применять переменные вектора? Типа
forvec( s=[[1,222],[i1,224],[i2,226]], ...)
То есть изящно сделать
for( i1=1,222, for( i2=i1+1,224, for( i3=(i2+1,226, ... )))

Для этого у forvec() есть третий параметр flag:

? ?forvec
forvec(X=v,seq,{flag=0}): v being a two-component vectors of length n, the sequence is evaluated with X[i] going from v[i][1] to v[i][2] for i=n,..,1 if flag is zero or omitted. If flag = 1 (resp. flag = 2), restrict to increasing (resp. strictly increasing) sequences. As a shortcut, v being a vector of nonnegative integers allows to loop over representatives of Z^n/vZ^n.

Так как вы хотите, чтобы индексы суммирования были упорядочены строго, то ставим флаг равным 2:

forvec( s=[[1,222],[1,224],[1,226]], ..., 2 )

[gris]

Спасибо. Вот ещё вопрос: Возведение в натуральную степень и по модулю.
2 ^ 12 = 1 mod(3); gp > 3^21%43 = 42
Беда в том, что показатели степени очень большие и при вычислении напрямую overflow in lg(). Я такую штуку "изобрёл" .
Как я представляю(a%md)^n=a%md^nи остаток можно считать постоянно при возведении в степень. То есть вначале формируется вектор из степеней в с показателем $2^i$ с применением модуля, а потом всё перемножается:

{ n=76871;    p=12450785994384756536;    md=37; 
   pd=digits(p,2);
   pd=Vecrev(pd);
   vp=vector(#pd);
   vp[1]=n%md;
   for( i=2,#vp,vp[i]=vp[i-1]^2%md);
   m=1;for(i=1,#vp, if(pd[i],m=m*vp[i]%md) );
   printf("%d ^ %d = %d mod(%d)\n",n,p,m,md); }

76871 ^ 12450785994384756536 = 34 mod(37)

Считается мгновенно и памяти не просит.
Но я думаю, что есть для этой цели специальные короткие команды. Где почитать? И при обычном возведении происходит какая-то оптимизация процесса? Dmitriy40 Спасибо.

[Dmitriy40]

gris
Не надо ничего изобретать, есть уже готовое:

? Mod(76871,37)^12450785994384756536
%1 = Mod(34, 37)

А если действительно хочется узнать как оно так быстро и просто вычисляется, то смотрите алгоритмы быстрого возведение в степень по модулю. Но в PARI их применять не потребуется.