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

[VAL]

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

По идее, должно идти последовательно и не проверять второе если уже невыполнено первое, но я программистам не доверяю и всегда пишу вложенные if.

Неоднократно проверял. Вложенные if ничуть не быстрее одного if с многими &&

[Dmitriy40]

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

По идее, должно идти последовательно и не проверять второе если уже невыполнено первое, но я программистам не доверяю и всегда пишу вложенные if.

И зря, в доке прямо сказано что считается именно ровно слева направо до первого выполненного условия, чтобы можно было применять условия типа if(x!=3 && a/(x-3)>0, ...) или if(j<=#v && v[j]>0, ...). А вложенные if могут быть чуточку медленнее (разбирать отдельный оператор вместо лексемы). Хотя чтобы это заметить ... Сомневаюсь. Зато с длинным условием писанины меньше и логика яснее.

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

Как считается If c || нескольких условий? Они по очереди проверяются до первого выполнения?

Да, слева направо до первого выполненного, это гарантировано. И для ||, и для && (до первого невыполненного).

-- 30.10.2022, 17:18 --

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

Это тормозит?

Не знаю что "это". Но обычно тормозит любой добавленный оператор (потому что PARI/GP интерпретатор и каждый раз разбирает код заново). Причём иногда настолько сильно, что оказываются неприменимы стандартные методы оптимизации (типа выноса постоянных вычислений из циклов). Т.е. иногда добавление вроде бы ускоряющего оператора приводит наоборот к замедлению. Я где-то показывал несколько таких примеров. И заранее не угадаешь что пересилит, замедление от лишнего оператора или ускорение от сокращения операций внутри цикла.

[Dmitriy40]

Вот один из примеров, что быстро нашёлся:

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

Иллюстрация насколько к PARI/GP неприменимы обычные методы оптимизации, в данном случае исключение хвостовой рекурсии:

[gris]

Напугало:
{print(floor(6-30/5));print(floor(6-10*0.6))}
0
-1

[wrest]

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

Напугало:

Ну второе у меня равно -2.350988701644575016 E-38 (количество знаков стоит по умлочанию) если печатать без округления. Целочисленная (и рациональная) арифметика там точная, рациональные числа хранятся в виде несократимой дроби (можно вынуть числитель и знаменатель этой дроби функциями numerator(x) и denominator(x) соответственно). Ну а как только вы ставите десятичную точку, всё становится плавающим, а не точным :) Или если используете иррациональные функции типа синуса или корней. Так что целые, рациональные и вещественные числа - это разные типы там.
Запустите например
print(1/9);print(1/9+0.0)

[Dmitriy40]

gris
Очень далеко не любое дробное десятичное число можно точно представить в формате с плавающей точкой (сколько бы бит там ни было в мантиссе), потому такие числа почти всегда неточные. Хотите точных вычислений - используйте целые или рациональные числа, исключительно. Ещё можно аккуратно округлять дробные числа до целых, но нужно каждый раз внимательно смотреть в какую сторону их округлять в конкретном месте кода, и строго до любых вычислений с ними.

[gris]

Да это неудачная попытка "оптимизации" ограничения для вложенного цикла:
for (k=0, 15*N, for (m=0, floor(3*N-k*3/5),...
А ведь Dmitriy40 предупреждал...
Вовремя опомнился. Буду осторожен.

[gris]

Ещё вопросы, если можно.
Сделал монте-карло по перестановкам элементов вектора $(1,2,3,4,5,6)$. Когда-то делал полный перебор перестановок, но в каких-то скриптах и там всё по-другому. А нет ли в PARI чего-нибудь этакого?

{S=vector(6); 
for ( k=1,200000, 
  for ( i=1,6, S[i]=i);
  for ( i=1,5, j=6-random(7-i); D=S[i];S[i]=S[j];S[j]=D);
)}

Нужно ли делать инициализацию массива каждый раз или пусть переставляется? Как делать СВОП элементов массива? $[S[n],S[m]]=[S[m],S[n]]$ почему-то не работало. Ну и вообще, как лучше и просто генерировать перестановку?

+ 22:26
Dmitriy40
wrest
Спасибо! Буду пробовать.
Хотелось скажем генерировать случайные перестановки из большого количества элементов. Я делал последовательными транспозициями всех позиций с начала до конца с последующими. Вроде бы получается равновероятно.

[Dmitriy40]

Есть специальный цикл по всем перестановкам: forperm. Примеры запуска есть в документации к PARI. Ну или вот:

? forperm([1,2,3],r, print(r); );
Vecsmall([1, 2, 3])
Vecsmall([1, 3, 2])
Vecsmall([2, 1, 3])
Vecsmall([2, 3, 1])
Vecsmall([3, 1, 2])
Vecsmall([3, 2, 1])
?

Но для получения всех перестановок надо непременно указывать массив в возрастающем порядке! Достаточно применить к нему оператор Set() (только он и дубли удалит):

? forperm([2,3,1],r, print(r); );
Vecsmall([2, 3, 1])
Vecsmall([3, 1, 2])
Vecsmall([3, 2, 1])
? forperm(Set([2,3,1]),r, print(r); );
Vecsmall([1, 2, 3])
Vecsmall([1, 3, 2])
Vecsmall([2, 1, 3])
Vecsmall([2, 3, 1])
Vecsmall([3, 1, 2])
Vecsmall([3, 2, 1])
?

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

for ( i=1,6, S[i]=i);

Можно сделать проще и быстрее: S=vector(6,i,i);

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

$[S[n],S[m]]=[S[m],S[n]]$ почему-то не работало.

Работает:

? S=[1,2,3,4,5]
[1, 2, 3, 4, 5]
? n=1;m=4;[S[n],S[m]]=[S[m],S[n]]
[4, 1]
? S
[4, 2, 3, 1, 5]
?

-- 03.11.2022, 22:12 --

Кажется я не вполне понял что хотелось ...

[wrest]

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

Ну и вообще, как лучше и просто генерировать перестановку?

numtoperm(n, k)
Generates the k-th permutation (as a row vector of length n) of the numbers 1 to n. The number k is taken modulo n!, i.e. inverse function of permtonum. The numbering used is the standard lexicographic ordering, starting at 0.

-- 03.11.2022, 22:46 --

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

Хотелось скажем генерировать случайные перестановки из большого количества элементов.

Случайная перестановка из n элементов:
x(n)=numtoperm(n,random(n!))
Но для большого количества (десятки тысяч) элементов может не подойти. Насколько надо большое?

[gris]

Учёл советы при генерации k штук перестановок-беспорядков вектора $(1,2,...,n)$:
{n=22; k=12;
for(ik=1,k,
S=vector(n,i,i);
for(i=1,n-1, j=n-random(n-i); [S[i],S[j]]=[S[j],S[i]]);
print(S);
)}
Как лучше генерировать беспо перестановки без неподвижных элементов? Размер вектора меньше тысячи.

[wrest]

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

Как лучше генерировать беспо перестановки без неподвижных элементов? Размер вектора меньше тысячи.

Мне кажется, что у вас уже все нормально. Спецфункции для генерации случайного беспорядка нет, а значит всё равно нужен цикл по всем элементам.
Единственное, если явно указать что вектор содержит маленькие числа (т.е. 32 битные если ваш pari 32 битный или 64битные если pari 64 битный), это ускоряет перебор:
? n=22;k=1000000;for(ik=1,k,S=Vecsmall(vector(n,i,i));for(i=1,n-1,j=n-i;[S[i],S[j]]=[S[j],S[i]]));
? ##
*** last result computed in 12,964 ms.
? n=22;k=1000000;for(ik=1,k,S=vector(n,i,i);for(i=1,n-1,j=n-i;[S[i],S[j]]=[S[j],S[i]]));
? ##
*** last result computed in 20,915 ms.
Т.е. миллион беспорядков длиной 22 каждый генерируется за 20 секунд, а миллион беспорядков из маленьких чисел за 13 секунд.
Ещё почти две секунды можно выиграть если вынести инициализацию начальной перестановки за внешний цикл:
? n=22;k=1000000;v=Vecsmall(vector(n,i,i));for(ik=1,k,S=v;for(i=1,n-1,j=n-i;[S[i],S[j]]=[S[j],S[i]]));
? ##
*** last result computed in 11,254 ms.

[wrest]

gris
Ещё я проверил такой подход. Генерируем случайную перестановку и проверяем является ли она беспорядком, и если нет, то генерируем пока не сгенерируем беспорядок.
Но оказалось, что чтобы сгенерировать $n$ беспорядков надо сгенерировать $ne$ случайных перестановок, и экономия сходит на нет (т.е. получаются те же 11 секунд).

? n=22;k=1000000;for(ik=1,k,until(a,S=numtoperm(n,random(n!));a=1;for(i=1,n,if(S[i]==i,a=0;break))));
? ##
*** last result computed in 10,487 ms.

[wrest]

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

Вроде бы получается равновероятно.

Это кстати вопрос Вот numtoperm(n,random(n!)) точно даёт случайную перестановку (равновероятно выбирает одну из всех возможных).

[gris]

Попробовал полный перебор по всем 10-значным (без ведущих нулей) натуральным числам с разными цифрами.
{S=Vecsmall(vector(10));D=Vecsmall(vector(10,i,10^(10-i)));kt=0;
forperm([0,1,2,3,4,5,6,7,8,9],S,
if (S[1]!=0,M=0;for(i=1,10,M=M+S[i]*D[i]);kt++;);
);
print(kt);
}
3265920
А как быстро записывать скалярное произведение векторов или ещё как переводить вектор из цифр в число?
Кстати, отметил такую фичу
{S=1;s=2;Ss=3;sS=4; print(S,s,Ss,sS)}
1234
и ещё ошибся с vecsmall. Где критичен регистр букв?
Насчёт (псевдо)случайности потока перестановок задумался.