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

[Dmitriy40]

Vancho
PARI/GP и сам по себе не слишком быстрый (скорее откровенно медленный). И разумеется он будет терять скорость записи при увеличении количества цифр в числе.
Какие из цифр Вы считаете первыми непонятно. Если младшие, то их выделить просто (взятие остатка), если старшие, то чуть посложнее (скомбинировать целочисленный логарифм и возведение в степень с последующим делением).
Встроенных функций ограничения количества цифр в целых числах я не припоминаю. А преобразование числа в массив цифр и обрезка оного с любой стороны до любого размера - медленно.

PS. Если бы у меня стояла задача вычислить младшие N цифр всех степеней двойки, то я бы пожалуй считал сразу в десятичной системе, уж удвоение сделать в ней не так уж сложно - и точно быстрее преобразования длинного числа в десятичную форму. И не на PARI/GP, а на чём-то компилирующемся.
PPS. Для примера банальный цикл for(i=0,2^20,x=2^i%10^1000;x++) считался порядка 12 минут (и порядка 10 секунд до семнадцатой степени).

[Vancho]

Спасибо, у меня потребность намного проще просто из большого числа спереди кусок отрезать, длинной 3000 знаков и записать его в файл, остальное отбросить

для примера было так

2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576

стало так

2
4
8
16
32
64
128
256
512
102
204
409
819
163
327
655
131
262
524
104

Без перевода в строку то он быстренько в файлик накидывает, что pari/gp, что python, а вот при обрезке уже не так лётает.

В python с 2^500000 по 2^550000 несколько часов уходит, то есть, чтобы 50000 записать всего. Там циклом возвожу в степень, сразу кромсаю, кусок аппендом закидывают в список от туда уже в файл построчно. Причём этот с 50000 обрезанными 140 мегов весит, а если не обрезать все 8 гигов.

[wrest]

Vancho в сообщении #1422168 писал(а):

Там циклом возвожу в степень,

Зачем, если можно умножать аккумулятор на два и сохранять в аккумулятор?

У меня такая программа
? n=2^500000;for(i=1,50000,n=n+n;print(digits(n)[1..3]))
на компе с мобильным 4-ядерным процом 8-летней давности (мак-мини середина 2011) прокручивается примерно за час с четвертью.

[Dmitriy40]

Vancho
Ага, всё же старшие цифры. Ну тогда целочисленный логарифм, вычитание, возведение в степень и деление - и дадут старшие цифры. Вот такой тупой цикл for(i=1,2^17,y=2^i;e=logint(y,10);if(e<1000,x=y,x=y\10^(e-999))) (старшие 1000 цифр в x) отрабатывает за 70с, а до пятнадцатой степени за 2с.
Но вообще я бы сделал по другому: хранил бы две переменные, порог и на сколько делить, и по превышению порога домножал бы их обе на 10. Не нужен будет ни логарифм, ни степень, только умножение на два, сравнение и деление. Как-то так: pr=10^1000-1;d=1;for(i=0,2^17,x=2^i;if(x>pr,d*=10;pr=pr*10+9);x\=d). Это отрабатывает за 10с (и за 0.8с до $2^{15}$). И за 6 минут до $2^{20}$.
Скорость записи миллиона строк по килобайту проверять не интересно (и от языка она не сильно зависит).

wrest
Замена $2^i$ на умножение на 2 (или сдвиг влево на 1 бит) заметного выигрыша не даёт, основные тормоза очевидно в работе с длинными числами, а не в операции сдвига. И не просто не даёт выигрыша, а даже чуть медленнее! Где-то на 3%. Потому что интерпретатор, им выгоднее меньше более сложных встроенных операций.

UPD. Вот это for(i=500000,500500,print(i,":",digits(2^i)[1..1000])) отрабатывает за 30с, т.е. 50000 значений выведет минут за 50 (хоть 1000 цифр, хоть 3).

[wrest]

Вот в 30 раз быстрее (моего предыдущего кода):
? z=500000;n=2^z;k=log(2)/log(10);for(i=1,50000,n=n+n;e=(z+i)*k;x=floor(e-2);print(n\10^x))
Логарифм в цикле считать не надо, там жо линейно все, степень двойки мы и так сами знаем, просто на коэффициент умножить её. В коде выше этот логарифм (нецелый) это e

-- 24.10.2019, 01:13 --

Vancho
Такшта ваши несколько часов, похоже, сократились до нескольких минут
Dmitriy40
Там все-тки стартовая степень-то полмиллиона, а не единица... Протаймить лучше с ней, наверное.

-- 24.10.2019, 01:31 --

Vancho
Да, кстати, я не знаю как он там устроено в операционных системах, но запись в файл должна быть асинхронная (чтобы не делать её за 50000 операций)
Посмотрите описание filewrite вместо write

[Dmitriy40]

wrest
Практически без потери скорости можно упростить до: k=log(2)/log(10);for(i=500000,550000,print(2^i\10^floor(max(i*k-1000,0)))).
Кстати Вы про max забыли и короткие числа у вас выводятся неправильно (дополняются нулями справа).

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

Там все-тки стартовая степень-то полмиллиона, а не единица... Протаймить лучше с ней, наверное.

Я протаймил весь диапазон до $2^{20}$, получилось 6 минут. Причём для 1000 цифр, а не трёх. Ваш код в тех же условиях (1000 цифр) для $i=0..2^{17}$ выполняется за 15с, мой за 10с.

-- 24.10.2019, 02:07 --

Сравнение вариантов:

? z=500000;n=2^z;k=log(2)/log(10);for(i=1,50000,n=n+n;e=(z+i)*k;x=floor(e-1000);x=(n\10^x))
time = 1min, 21,184 ms.
? z=500000;n=2^z;k=log(2)/log(10);for(i=1,50000,n=n+n;e=(z+i)*k;x=floor(max(e-1000,0));x=(n\10^x))
time = 1min, 20,997 ms.
? k=log(2)/log(10);for(i=500000,550000,x=(2^i\10^floor(max(i*k-1000,0))))
time = 1min, 21,792 ms.
? pr=10^(logint(2^500000,10)+1);d=max(1,pr\10^1000);for(i=500000,550000,x=2^i;if(x>=pr,d*=10;pr*=10);x\=d)
time = 17,379 ms.

Для сравнения, на ассемблере без особых оптимизаций весь диапазон до $2^{20}$ считается за 22с (вместо 6 минут на PARI/GP), а с оптимизацией под AVX2 меньше трёх секунд.

[wrest]

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

Замена $2^i$ на умножение на 2 (или сдвиг влево на 1 бит) заметного выигрыша не даёт, основные тормоза очевидно в работе с длинными числами, а не в операции сдвига.

Да, действительно. Такие умные компиляторы\интерпретаторы...

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

Сравнение вариантов:

То есть, меньше минуты.
Да, у меня тормозной планшет пробегает ваш код всего за 4 минуты. А если отрезать не 1000 старших цифр, а только 3, то за 14 секунд.
Грандиозно.

[wrest]

Vancho
В общем, на ноутбуке программа ув. Dmitriy40 записывает файл с 50000 числами (от $2^{500000}$ до $2^{550000}$), обрезанными до первых (старших) 1000 значащих цифр за 35 секунд, по одному числу на строку, и получается файл ок. 50 мегабайт.
Текст:
pr=10^(logint(2^500000,10)+1);d=max(1,pr\10^1000);for(i=500000,550000,x=2^i;if(x>=pr,d*=10;pr*=10);write("C:/temp/digits.txt",x\d))

[Vancho]

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

Vancho
В общем, на ноутбуке программа ув. Dmitriy40 записывает файл с 50000 числами (от $2^{500000}$ до $2^{550000}$), обрезанными до первых (старших) 1000 значащих цифр за 35 секунд, по одному числу на строку, и получается файл ок. 50 мегабайт.
Текст:
pr=10^(logint(2^500000,10)+1);d=max(1,pr\10^1000);for(i=500000,550000,x=2^i;if(x>=pr,d*=10;pr*=10);write("C:/temp/digits.txt",x\d))

А, как в этом коде регулировать диапазон, если менять i=500000,550000 на i=4096, 1048576 нули начинает записывать. Или например i=500000,700000 скорость записи падает. Или надо по 100000 отшагивать на каждую запись

10^(logint(2^100000,10)+1);d=max(1,pr\10^1000);for(i=100000,200000
10^(logint(2^200000,10)+1);d=max(1,pr\10^1000);for(i=200000,300000
10^(logint(2^300000,10)+1);d=max(1,pr\10^1000);for(i=300000,400000
10^(logint(2^500000,10)+1);d=max(1,pr\10^1000);for(i=500000,600000
10^(logint(2^600000,10)+1);d=max(1,pr\10^1000);for(i=600000,700000

И d=max(1,pr\10^1000) только на длину отреза влияет? Можно любое значение ставить 10 или 50 или 2000,3000?

[Dmitriy40]

Vancho
Для изменения начального числа NNN его надо подставить в два места: в logint(2^NNN,10) и в for(i=NNN,SSS,. SSS - конечное число (включительно).
Для изменения количества записываемых старших цифр KKK это количество надо подставить в d=max(1,pr\10^KKK).
Можно упростить настройку сделав её в начале строки:
NNN=4096;SSS=5500;KKK=1000;pr=10^(logint(2^NNN,10)+1);d=max(1,pr\10^KKK);for(i=NNN,SSS,x=2^i;if(x>=pr,d*=10;pr*=10);write("C:/temp/digits.txt",x\d))

[wrest]

Vancho в сообщении #1422329 писал(а):

А, как в этом коде регулировать диапазон,

Вот вам функция:

(Оффтоп)

Vancho_14229_315(n_start,n_quantity,n_digits,s_filename)={
my(pr=10^(logint(2^n_start,10)+1),d=max(1,pr\10^n_digits),x);
for(i=n_start,n_start+n_quantity-1,x=2^i;if(x>=pr,d*=10;pr*=10);write(s_filename,x\d));
print("finished");
}

n_start - число, показатель степени с которой начинать
n_quantity -- число, количество строк которые записать в файл
n_digits -- число, количество старших цифр которое оставить (или меньше если число маленькое)
s_filename -- строка, имя файла куда все записать

Запускать например так:
Vancho_14229_315(500000,1000,3,"C:/temp/digits.txt")
Означает: начать с числа $2^{500000}$, всего вычислить $1000$ степеней двойки, оставить $3$ старших цифры в каждой вычисленной степени, записать обрезанные числа построчно в файл с именем "C:\temp\digits.txt"

Если не будет работать - сообщайте :)

[Soul Friend]

Имеется матрица M[i,j] с числами в десятичной системе, но надо их вывести в двоичном виде. Как это сделать?

[dmd]

Soul Friend

? m=[4,2,3,6;32,7,9,11]
%1 =
[ 4 2 3  6]

[32 7 9 11]

?
? binary(m)
%2 =
[         [1, 0, 0]    [1, 0]       [1, 1]    [1, 1, 0]]

[[1, 0, 0, 0, 0, 0] [1, 1, 1] [1, 0, 0, 1] [1, 0, 1, 1]]

[Soul Friend]

dmd
Спасибо.

[Soul Friend]

Надо проверить число $n$, что оно не является суммой каких либо элементов вектора $A$.
Есть ли для этого готовая функция на PARI/GP, если нет - то, как это реализовать ?
$n \neq (k_1 + ... + k_i) $
где $k_x$ - элементы множества $A$.
Пример:
$A=\{3, 5, 7\}$
$n=17$
$n \neq (3+5)$
$n \neq (5+7)$
$n \neq (3+7)$
$n \neq (3+5+7)$
Элементы множества в суммировании не повторяются.