интерактивный курс: введение в программирование на 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 их применять не потребуется.

[gris]

Сильно упрощённая модель. Задан цикл по вектору и вектор, который обязательно появляется в этом цикле. Надо предсказать, на каком шаге.
Несложно делается, но нет ли волшебной палочки?
Строится вспомогательный вектор из числа шагов для изменения на единицу i-ой позиции в очередном векторе перебора.
При небольшой доработке можно из любой системы счисления переводить в десятичную!

wd=[[1,2],[1,3],[1,17],[1,22]];
f=[2,3,7,22];
nw=#wd;
wpk=vector(nw);wpk[nw]=1;
forstep(i=nw-1,1,-1,wpk[i]=wpk[i+1]*wd[i+1][2] );
print(vecsum(vector(nw-1,i,(f[i]-1)*wpk[i] ) )+f[nw]);

k=0;
forvec(v=wd,k++;if(v==f, break)); print(k)

2024
2024

[genk]

$\mathsf{}$Здравствуйте. Впервые столкнулся с такой проблемой:если в программе много переменных,можно ли в PARI индексировать их обычным образом,вроде $x_i$ (конечно,индекс будет каким-то образом писаться в одной строке с буквой x1,x2,...).И как тогда,например,в цикле for присваивать значения этим переменным типа $\mathsf{for(i=1,30,x_i=...)}$?

[Dmitriy40]

genk
Индексированные переменные это и есть вектор (массив): x=vector(100); x[53]=123+x[13]; for(j=1,#x, x[j]=j*prime(j) ).
Кстати если нет зависимости значений друг от друга, то присвоение можно делать прямо в момент объявления: x=vector(100,j, j*prime(j)). Можно и с зависимостями, но придётся вычисление сделать через if с проверкой индексов.

[genk]

Dmitriy40
Спасибо,предельно ясно.

[Ende]

Выделена тема «Сверхъестественные пифагоровы тройки до 100 разрядов»

[genk]

Здравствуйте.Меня интересует такой вопрос:может ли PARI вычислять базис Грёбнера в $\mathbf{Q[x_1,x_2,\dots,x_n]}$ для идеала,порожденного многочленами f_1,f_2,\dots,f_k? С одной стороны,есть простой алгоритм(например,Бухбергера),который вроде бы "по плечу" такому продвинутому калькулятору.Но я не нашел подходящей функции(не будешь же проверять полсотни функций в разделе "Общие числовые поля",начинающиеся с ideal... Поиск по функциям,в названии которых есть часть basis или grobner тоже ничего не дал.Или я что-то пропустил?

[Dmitriy40]

В версии 2.17 от 30 сентября наконец сделали праймориал:
"allow n# for the primorial of n (product of primes <= n)"
Зато forprime испортили, в ней баги полезли.