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

[gris]

wrest, скрипт, конечно. Вывод только для контроля.
По 5788765_10 = [5,8,5,4,5,13]_16: [0,4,5,8,13] По условию, переписанная в _k запись числа должна содержать не менее l цифр. В противном случае она дополняется ведущими нулями. У нас получилось шесть цифр, а надо минимум семь. Добавляем ноль в множество. Если уже был, то не страшно. Кстати, это позволяет предотвратить ситуацию с нулём:
0_10 = []_6: [0] Ему возвращается положенная по справедливости цифра.

[wrest]

gris
А, ну тогда все хорошо. Лишнего нет, всё по делу.

[gris]

Вот ещё дурацкая задачка.
На вход подаются десятичные натуральные числа от $0$ до $2^l-1$, которые преобразуются в двоичное число длины $l$, в котором по заданному правилу переставляются цифры, что в конце концов преобразуется в десятичное число.

{ln=12;
vc=[3,6,5,7,1,11,9,12,2,4,8,10];
foreach( [0,1,13,24,577,4000],n,
  vd=digits(n,2); printf("%5d: %d\n ",n,vd);
  vd1=vector( ln,i, if (vc[i]>#vd, 0, vd[vc[i]]) );
  printf("      %d to %d\n", vd1,fromdigits(vd1,2) );
)}
    0: []
       [0,0,0,0,0,0,0,0,0,0,0,0] to 0
    1: [1]
       [0,0,0,0,1,0,0,0,0,0,0,0] to 128
   13: [1,1,0,1]
       [0,0,0,0,1,0,0,0,1,1,0,0] to 140
   24: [1,1,0,0,0]
       [0,0,0,0,1,0,0,0,1,0,0,0] to 136
  577: [1,0,0,1,0,0,0,0,0,1]
       [0,0,0,0,1,0,0,0,0,1,0,1] to 133
 4000: [1,1,1,1,1,0,1,0,0,0,0,0]
       [1,0,1,1,1,0,0,0,1,1,0,0] to 2956

Вот как то так вроде бы работает. Перестановка задаётся вектором vc одна на все числа.Предполагается, что всё задано корректно.
Нет ли более простого подхода?

[Dmitriy40]

Для перестановки вектора или матрицы есть vecextract. Как раз по списку номеров элементов.

[gris]

Спасибо. Вот ещё сделанное на коленке.
Надо получить все векторы длиной m с элементами от 1 до k

{k=6;m=3;
n=k^m-1;
for( i=0,n,
  d=digits(i,k);
  v=vector( m, i, if( i>#d, 1, d[i]+1) );
  print(v);
)}
[1, 1, 1], [2, 1, 1], [3, 1, 1], [4, 1, 1], [5, 1, 1], [6, 1, 1],
[2, 1, 1], [2, 2, 1], [2, 3, 1],     ...     , [6, 6, 5], [6, 6, 6]

Вот бы каким-то флагом получить digits с обязательными ведущими нулями до постоянной длины.
типа digits5 (389)=[0,0,3,5,9];

+++ 16:35 Спасибо! Ещё больше полюбилforvec

[Dmitriy40]

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

Надо получить все векторы длиной m с элементами от 1 до k

forvec(x=vector(m,i,[1,k]), print(x))

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

Вот бы каким-то флагом получить digits с обязательными ведущими нулями до постоянной длины.

digitsN(x,k,n)=my(r=digits(x,k)); if(#r<n, r=concat(vector(n-#r),r)); return(r);

[Dmitriy40]

Как интересно: оказывается ограничение на размер памяти, которое allocatemem и default(parisize) и default(parisizemax), не влияет на размеры списков и хештаблиц (Map):

? default(parisize)
%1 = 4000000
? default(parisizemax)
%2 = 0
? m=Map();
? for(i=1,10^6,mapput(m,i,i%257))
? sizebyte(m)
%5 = 67984452

При ограничении в 4М хештаблица непринуждённо заняла 68М.

[Dmitriy40]

Ещё интересное наблюдение: нулевые значения векторов занимают меньше места:

\\gp64:
? for(i=-3,3,x=[i];print(i,":",sizebyte(x));)
-3:40
-2:40
-1:40
0:32
1:40
2:40
3:40
? for(i=-3,3,x=vector(1000,k,i);print(i,":",sizebyte(x));)
-3:32008
-2:32008
-1:32008
0:24008
1:32008
2:32008
3:32008
? x=vector(1000,k,k%2);print(sizebyte(x));
28008
? x=matrix(100,100);print(sizebyte(x));
241608
? x=matrix(100,100,i,j,1);print(sizebyte(x));
321608
? x=matrix(100,100,i,j,(i+j)%2);print(sizebyte(x));
281608

\\gp32:
? for(i=-3,3,x=[i];print(i,":",sizebyte(x));)
-3:20
-2:20
-1:20
0:16
1:20
2:20
3:20

С одной стороны хорошо, экономия памяти, с другой стороны видимо тратится дополнительное время на изменение размеров элементов. И тогда если большинство элементов будут не нулевыми, то выгоднее инициализировать вектора (и матрицы) сразу ненулевыми значениями. Правда разница если и будет, то лишь на многомиллионных векторах.

[wrest]

gris
Изготовление полинома из вектора [коэффициентов]
? v=[1,5,3,4]
%1 = [1, 5, 3, 4]
? P=Pol(v,x)
%2 = x^3 + 5*x^2 + 3*x + 4
?
Изготовление вектора [коэффициентов] из полинома:
? vector(#P,i,polcoef(P,#P-i))
%3 = [1, 5, 3, 4]
Ну а дальше читать тут: https://pari.math.u-bordeaux.fr/dochtml ... eries.html

P.S. Ой, а вопрос то пропал. Ну ладно, не пропадать же ответу

[gris]

wrest, спасибо за ответ. Я просто устыдился того, что не подготовился к вопросу и удалил его Буду читать FM по вашему совету и наверняка ещё спрошу более конкретнее .

[gris]

gp > polrootsreal(Polrev(primes(2)))
[-0.6666666666666666666666666667]

gp > polrootsreal(Polrev(primes(2434)))
[-0.9960369895432265521556781771]

gp > polrootsreal(Polrev(primes(2435)))
[]

polrootsreal(Polrev(primes(2437)))
[-0.9966912680420351022436326790, -0.9965933340278384751512797067]

gp > polrootsreal(Polrev(primes(2481)))
[-0.9969186916238192378345112206, -0.9964288608776514354529335606]
сегодня вдруг увидел и проверил.
кстати, можно решать квадратные уравнения
polrootsreal(Pol([1,-5,6]))
[2.000000000000000000000000000, 3.000000000000000000000000000]

[gris]

Набираю векторы длиной в 100 000 из 45-значных не обязательно различных чисел.
Хочу найти повторы. Хотя бы обнаружить их наличие. Вот:
print(#v, " / ", #Set(v))
100000 / 100000
Параллельно идёт набор 4-значных чисел и там
100000 / 1035
При увеличении количества до 200 000 время возрастает в 4 раза, а повторов нет. При увеличении до миллиона (в 10 раз) время увеличивается совершенно непропорционально, хотя памяти выделяется достаточно, но всё валится. Причём ещё до преобразования вектора в множество.
Может быть сбрасывать этот массив на диск, а потом повторы искать? Или другой метод?

[Dmitriy40]

gris
Использовать Map(): добавлять элементы с mapput() с любым значением, лучше нулевым. Если итоговый размер меньше количества добавленных элементов - были повторы. Можно даже их подсчитать если в значении хранить количество повторов и перед добавлением проверять есть ли такой элемент mapisdefined() и если есть, то класть в него значение на 1 больше имеющегося.
Занимает в несколько раз больше места чем массив, но десяток миллионов элементов в память влезут.
Операции #, foreach работают, обращение по индексу нет. Всегда сортирован по возрастанию ключа.

[gris]

Спасибо!

nf=Map();
k=0; 
fin  = fileopen("1.txt");
while(str = filereadstr(fin), k++;
   nn=eval(str); 
   mapput(~nf,nn,0);
);  
fileclose(fin);
print(k," / ",#nf);

3000000 / 2999959
time = 35,131 ms.

Убедился, что 41 строка повторяется. Это успокоило

[Dmitriy40]

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

   mapput(~nf,nn,0);

Работает и без ~.

Подсчитать количество повторений каждой строки (заменить mapput() на):

qq=0; mapisdefined(nf,nn,&qq); mapput(nf,nn,qq++);

Вывести только повторяющиеся строки:

foreach(nf,m, if(m[1][2]>1, print(m[1][1]," x ",m[1][2]); ); );

Здесь m[1][1] это ключ (nn), m[1][2] это значение (qq).

-- 30.04.2024, 00:31 --

Да, и nn=eval(str); делать не обязательно, ключ может быть и строкой (и массивом и вообще любым объектом). Разве что nn будет занимать заметно меньше места чем str ...