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

[gris]

Попил кофе в вот так попробовал
{n=3; s=5;
p=vector(n);
d=vector(s-1,i,i);\\ print("d ", d);
de=vector(s-1); for(i=1,n-1,de[i]=1);for(i=n,s-1,de[i]=2);
a=vector(n);
k=0;
forperm(de, dex,
j=0; for( i=1,s-1,if( dex[i]==1, j++; p[j]=d[i ]) ); p[n]=s;
\\print("p ",p);
a=vector(n); a[1]=p[1];for(i=2,n,a[i]=p[i]-p[i-1]); print("a ",a);
)}
a [1, 1, 3]
a [1, 2, 2]
a [1, 3, 1]
a [2, 1, 2]
a [2, 2, 1]
a [3, 1, 1]
То есть перемешивал индикаторный массив из единиц и двоек.
Упёрся в то, что
forperm([1,1,2,2],dex,print(dex))
Vecsmall([1, 1, 2, 2])
Vecsmall([1, 2, 1, 2])
Vecsmall([1, 2, 2, 1])
Vecsmall([2, 1, 1, 2])
Vecsmall([2, 1, 2, 1])
Vecsmall([2, 2, 1, 1])

а вот
forperm([1,1,0,0],dex,print(dex))
Vecsmall([1, 1, 0, 0])
и всё
Спасибо за советы. Мне главное не результат простенькой задачки, а изучение PARI

[wrest]

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

а вот
forperm([1,1,0,0],dex,print(dex))
Vecsmall([1, 1, 0, 0])
и всё

Надо доки читать , ибо

Цитата:

and if a is a small vector then p goes through the (multi)permutations lexicographically larger than or equal to a.

То есть если вы подаёте на вход forperm() не число, а вектор, то генерируются не все перестановки, а только стартовая и бОльшие (в лексикографическом смысле) чем стартовая (стартовая -- поданный на вход вектор).
То есть то же самое будет например со стартовой перестановкой [4,3,2,1]
? forperm([4,3,2,1],i,print(i))
Vecsmall([4, 3, 2, 1])
?
Чтобы получить ВСЕ перестановки [1,1,0,0] (которых будет 4!), можно попробовать так:
? v=[1,1,0,0];forperm(#v,i,print(vecextract(v,i)))
Но тогда туда попадут и совпадающие.
Чтобы получить только уникальные перестановки, можно попробовать так:
? v=[1,1,0,0];L=List();forperm(#v,i,listput(~L,vecextract(v,i)));listsort(~L,1);v1=Vec(L);print(v1)
[[0, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0], [1, 0, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0]]
?
Тут идея такая, что сначала набирается список из всех $n!$ перестановок, а потом удаляются повторяющиеся.

Работает и со стульями:
? v=["table","table","chair","chair"];L=List();forperm(#v,i,listput(~L,vecextract(v,i)));listsort(~L,1);v1=Vec(L);print(
v1)
[["chair", "chair", "table", "table"], ["chair", "table", "chair", "table"], ["chair", "table", "table", "chair"], ["table", "chair", "chair", "table"], ["table", "chair", "table", "chair"], ["table", "table", "chair", "chair"]]
?

[gris]

Индикация нулями! Получилось. Интересно с forsubset
Так что получается, что forperm для вектора с повторами одинаковые не выдаёт? Стартовая это предыдущая просто т лексикографически следующая строго больше?

[wrest]

gris
Вообще лучше сразу думать как правильно комбинаторную задачу формулировать в комбинаторных терминах (если задача комбинаторная, конечно).
Есть устоявшиеся термины типа сочетаний, перестановок, рамзещений и их вариаций (с повторениями/без). Иногда надо подсчитать их количество только, иногда надо ещё и сгенерировать.
По подсчету разных вариантов я делал даже тему «Комбинаторное двенадцатизадачие: раскладываем шары по урнам»
Ну и есть вот такая статья в Вики Двенадцатеричный_путь

-- 20.01.2023, 14:32 --

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

Так что получается, что forperm для вектора с повторами одинаковые не выдаёт?

Получается так, да.
Чтобы вышли все (неповторяющиеся) перестановки, можно делать ещё так:
? forperm(vecsort([1,1,0,0]),i,print(i))
Vecsmall([0, 0, 1, 1])
Vecsmall([0, 1, 0, 1])
Vecsmall([0, 1, 1, 0])
Vecsmall([1, 0, 0, 1])
Vecsmall([1, 0, 1, 0])
Vecsmall([1, 1, 0, 0])
?
То есть отсортировать входной вектор (тогда получаем что стартовая перестановка лексикографически наименьшая, но это надо бы проверять ещё на нечисловых данных).

[Iosafat]

Скажите пожалуйста, почему Пифагоровы тройки ищутся до 106, я же попросил программу искать до 101?

{i=0; n=2; r1=1; r2=101;
    for(a=r1, r2,
    for(b=r1, r2,
    for(c=r1, r2,
       if(a^n+b^n==c^n, i++;
         print(i, " | ", n, " | ", a,"²+",b,"²=",c "² | ", a^n,"+",b^n,"=",c^n)))))}

[gris]

ищутся до r2=101, а i=106 это количество найденных троек.
++ Тройки к тому же неотсортированные, поэтому их так много.

[Iosafat]

gris А, т.е. найденных строк получилось больше чем 101, значит все правильно, сообразил - СПАСИБО!

[gris]

Как лучше создать массив-индикатор натуральных чисел довольно большого порядка. Скажем, до десяти миллиардов. Ну типа
{p=vector( 10^1, i, !issquare(i) * (i%2!=0) )}
[0,0,1,0,1,0,1,0,0,0]
Ругается:
gp > p=vector(10^7,i,!issquare(i)*(i%2!=0))
*** vector: Warning: increasing stack size to 8000000.
*** vector: Warning: increasing stack size to 16000000.
*** vector: Warning: increasing stack size to 32000000.
*** vector: Warning: increasing stack size to 64000000.
*** _*_: Warning: increasing stack size to 100000000.
*** the PARI stack overflows !
current stack size: 100000000 (95.367 Mbytes)
\hint\ you can increase 'parisizemax' using default()

gp > p=vector(10^10,i,!issquare(i)*(i%2!=0))
*** at top-level: p=vector(10^10,i,!issquare(i)*(i%2!=0))
*** vector: overflow in t_INT-->long assignment.

[Iosafat]

gris Проблема с памятью? Предложите, чтоб кто-то просчитал. Обычно когда что-то не считается - считают по частям.

[Dmitriy40]

gris
Объявите вектор как vectorsmall, он вчетверо меньше памяти занимает (посмотреть размер занимаемого места можно функцией sizebyte()). Но далеко не все функции умеют с ними работать (foreach, select и много других не умеют).
Под x86/x32 каждый элемент вектора занимает 16 байтов, под x64 32 байта (4 машинных слова). А элемент vectorsmall равен машинному слову, 4 или 8 байтов.
Ну или выделите PARI гиг или два (а если винда x64 и памяти много, то до 2/3 физической). (UPD. Не работает, см. ниже.)

PARI очень плохо работает с типами данных маленького размера (меньше 32 или 64 бита в зависимости от версии винды и PARI). Я сколько ни боролся, нормального решения не нашёл, плюнул.

Ну в общем или да, считать чем-то другим, или по частям (кстати тогда можно и процент выполнения выводить и другую статистику счёта, не дожидаясь его завершения).

-- 22.01.2023, 20:15 --

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

*** vector: overflow in t_INT-->long assignment.

А вот это немного другая ошибка, не из-за нехватки памяти: PARI не может вычислить размер массива, эта величина не помещается в машинное слово (похоже у Вас версия PARI x32).

Ещё бывает совсем странная ошибка, когда размер вектора приближается снизу к 20млн элементов, то PARI (win32 версии) ошибается при внутреннем вычислении его размера:

? default(parisize,15*10^8);
  ***   Warning: new stack size = 1500000000 (1430.511 Mbytes).
? vectorsmall(17000000);
  ***   at top-level: vectorsmall(17000000)
  ***                 ^---------------------
  *** vectorsmall: overflow in lg().
  ***   Break loop: type 'break' to go back to GP prompt
break> break

? vectorsmall(16000000);
?

Для vector числа ровно те же.
Казалось бы при чём тут десятичный логарифм ...

[wrest]

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

Скажем, до десяти миллиардов. Ну типа

У меня для $10^7$ не ругается, только предупреждает:

(Оффтоп)

? p=vector(10^7,i,!issquare(i)*(i%2!=0));print(#p)
*** vector: Warning: increasing stack size to 16000000.
*** vector: Warning: increasing stack size to 32000000.
*** vector: Warning: increasing stack size to 64000000.
*** vector: Warning: increasing stack size to 128000000.
*** _*_: Warning: increasing stack size to 256000000.
10000000
? ##
*** last result computed in 1,937 ms.
?

Хватило 256 мегабайт...
P.S. Для $10^8$ хватает 2 гигабайт.

-- 22.01.2023, 21:21 --

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

Казалось бы при чём тут десятичный логарифм ...

Вы уверены что это он? Смотрели в исходники? Ибо в интерпретаторе lg() нет, это в библиотеке значит только.

-- 22.01.2023, 21:36 --

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

gp > p=vector(10^10,i,!issquare(i)*(i%2!=0))

Ну, тут вы, конечно, хватанули через край... Что вы будете делать с массивом такого размера, даже если создадите?

[Dmitriy40]

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

Вы уверены что это он?

Да мне пофиг где, главное что не даёт определить вектор большой длины (например 400млн элементов vectorsmall на 1.6ГБ). А сообщение об ошибке ясно указывает на lg().

А x64 PARI даёт:

? default(parisize,35*10^8);
  ***   Warning: new stack size = 3500000000 (3337.860 Mbytes).
? v=vectorsmall(400000000);
? #v
400000000
? sizebyte(v)
3200000008
?

Правда выполнение vectorsmall занимает секунд 10-15, но потом работа с вектором вроде с обычной скоростью.

[wrest]

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

А сообщение об ошибке ясно указывает на lg().

Да, но почему вы решили что это логарифм?
Доки по библиотеке говорят что
long lg(GEN z) returns the length (in longwords) of the root of z.
И
long lg(GEN x) returns the length of x in BITS IN LONG-bit words.

То есть это не логарифм, это функция связанная с размером занимаемой памяти. И root там выше это не арифметический корень...

[wrest]

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

То есть это не логарифм, это функция связанная с размером занимаемой памяти.

Да, и вот что пишут списке рассылке суппорта (2006 год!) http://pari.math.u-bordeaux.fr/archives ... 00005.html

Цитата:

PARI is trying to create a GEN object with length > 2^24 words [ e.g. a
vector with > 16777215 components ]

Так что да, вы правы и на 32-битных машинах размер числового вектора ограничен 16777215 элементами. Ну и пишут что чтобы этого не было, переходите на 64 бита.

Цитата:

> Is there any way to increase something to get around this? Are there
> serious penalties?

The easiest is to use a 64 bit machine.

В итоге, я думаю что имя lg() происхоит от length get и ошибка переполнения происходит как ей и положено, на этапе инициализации структуры (вектора), а именно на этапе вычисления его длины в словах.

[gris]

спасибо неравнодушным и радушным!
Да, у меня слабенький комп с windows32 и 4Гб оперативки .
Так что это чисто теоретический запрос. И он даже не решается битовыми массивами.
Размер индикаторного массива диктуется праймориалом и при 29# это уже больше 65 млрд.
Кстати, как коротко записать
n=2*3*5*7;

а используется массив для предварительного его довольно запутанного формирования, последующего анализа миллион раз и дальнейшего сдвига вдоль натуральных чисел с незначительными коррекциями.
Это приводит к сокращению в ??? раз решения проблем с гипотезами: АВС, Римана и ВТФ .
Меня привлекает иcключительно PARI