2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 19, 20, 21, 22, 23, 24, 25 ... 52  След.

А вам пакет PARI/GP интересен?
Да 82%  82%  [ 56 ]
Нет 6%  6%  [ 4 ]
Не уверен(а) 12%  12%  [ 8 ]
Всего голосов : 68
 
 Re: интерактивный курс: введение в программирование на PARI/GP
Сообщение23.10.2019, 23:07 
Заслуженный участник


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

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

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


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

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

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 гигов.

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


05/09/16
11468
Vancho в сообщении #1422168 писал(а):
Там циклом возвожу в степень,

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

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

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


20/08/14
11067
Россия, Москва
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).

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


05/09/16
11468
Вот в 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
Такшта ваши несколько часов, похоже, сократились до нескольких минут :mrgreen:
Dmitriy40
Там все-тки стартовая степень-то полмиллиона, а не единица... Протаймить лучше с ней, наверное.

-- 24.10.2019, 01:31 --

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

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


20/08/14
11067
Россия, Москва
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 меньше трёх секунд.

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


05/09/16
11468
Dmitriy40 в сообщении #1422174 писал(а):
Замена $2^i$ на умножение на 2 (или сдвиг влево на 1 бит) заметного выигрыша не даёт, основные тормоза очевидно в работе с длинными числами, а не в операции сдвига.

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

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


05/09/16
11468
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))

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


23/10/19
3
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?

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


20/08/14
11067
Россия, Москва
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))

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


05/09/16
11468
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"

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

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


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

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


16/08/05
1146
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]]

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


12/10/16
637
Almaty, Kazakhstan
dmd
Спасибо.

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


12/10/16
637
Almaty, Kazakhstan
Надо проверить число $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)$
Элементы множества в суммировании не повторяются.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 771 ]  На страницу Пред.  1 ... 19, 20, 21, 22, 23, 24, 25 ... 52  След.

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



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

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


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

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