2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 38, 39, 40, 41, 42, 43, 44 ... 54  След.

А вам пакет PARI/GP интересен?
Да 83%  83%  [ 58 ]
Нет 6%  6%  [ 4 ]
Не уверен(а) 11%  11%  [ 8 ]
Всего голосов : 70
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение20.01.2023, 13:05 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Попил кофе в вот так попробовал
{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 :-)

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение20.01.2023, 13:14 


05/09/16
11972
gris в сообщении #1578051 писал(а):
а вот
forperm([1,1,0,0],dex,print(dex))
Vecsmall([1, 1, 0, 0])

и всё

Надо доки читать :mrgreen: , ибо
Цитата:
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"]]
?

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение20.01.2023, 13:24 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение20.01.2023, 14:19 


05/09/16
11972
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])
?

То есть отсортировать входной вектор (тогда получаем что стартовая перестановка лексикографически наименьшая, но это надо бы проверять ещё на нечисловых данных).

 Профиль  
                  
 
 Пифагоровы тройки
Сообщение21.01.2023, 05:41 
Аватара пользователя


21/01/23

159
Запорожье
Скажите пожалуйста, почему Пифагоровы тройки ищутся до 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)))))}

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение21.01.2023, 09:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 СПАСИБО!
Сообщение21.01.2023, 10:00 
Аватара пользователя


21/01/23

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

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение22.01.2023, 17:54 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Как лучше создать массив-индикатор натуральных чисел довольно большого порядка. Скажем, до десяти миллиардов. Ну типа
{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.

 Профиль  
                  
 
 Брат
Сообщение22.01.2023, 18:37 
Аватара пользователя


21/01/23

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

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение22.01.2023, 20:01 
Заслуженный участник


20/08/14
11640
Россия, Москва
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 числа ровно те же.
Казалось бы при чём тут десятичный логарифм ... :facepalm:

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение22.01.2023, 21:09 


05/09/16
11972
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 писал(а):
Казалось бы при чём тут десятичный логарифм ... :facepalm:

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

-- 22.01.2023, 21:36 --

gris в сообщении #1578298 писал(а):
gp > p=vector(10^10,i,!issquare(i)*(i%2!=0))

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

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение22.01.2023, 23:18 
Заслуженный участник


20/08/14
11640
Россия, Москва
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, но потом работа с вектором вроде с обычной скоростью.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение23.01.2023, 09:10 


05/09/16
11972
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 там выше это не арифметический корень...

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение23.01.2023, 10:17 


05/09/16
11972
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 и ошибка переполнения происходит как ей и положено, на этапе инициализации структуры (вектора), а именно на этапе вычисления его длины в словах.

 Профиль  
                  
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение23.01.2023, 11:51 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 804 ]  На страницу Пред.  1 ... 38, 39, 40, 41, 42, 43, 44 ... 54  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group