2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 9, 10, 11, 12, 13, 14, 15 ... 54  След.

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


20/08/14
11709
Россия, Москва
Aether
Первый цикл - проверяемое число, с шагом 2 чисто для ускорения (чётные числа не подходят по определению).
Присваивание t=x просто инициализирует временную переменную (текущий остаток) для внутренних циклов проверки числа, чтобы не изменить в процессе переменную цикла.
Вектор обнулил для сброса списка делителей.
Второй цикл - проверка делимости на соответствующее число Мерсенна начиная с наибольшего, оно вычисляется и сохраняется в m.
Цикл while - делит (нацело) текущий остаток (в t) на текущее число Мерсенна и расширяет список (вектор) делителей пока текущий остаток ему кратен (t%m==0 вычисляет остаток от деления и проверяет его на 0, а "\" - целочисленное деление).
В итоге t будет равно 1 только если проверяемое число состоит из произведений чисел Мерсенна (в любой положительной степени каждое).
Правда доказать это утверждение я не могу, но как и привести контрпример.

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


13/02/17

317
Varanasi
Спасибо, разобрался. Думаю, что код можно ускорить, вычисляя наибольшее число Мерсенна для некоторой области, а не задавая его вручную сразу для всех 100000, так происходит много ненужных сравнений и делений.

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


20/08/14
11709
Россия, Москва
Дык я примерно так и сделал, выставив руками наибольшую степень двойки. Ну а что она больше реально необходимой - не сильно портит, ведь для каждой лишней выполняется фактически одно деление (t%m) и всё, остальное намного быстрее.
Добавление лишнего if(t>=m, ... перед while для пропуска делений если текущий остаток меньше числа Мерсенна ускоряет некритично.
Попробовал предвычислить все числа Мерсенна перед первым циклом - ускорило несущественно.
В общем нет смысла усложнять, значительного ускорения не получается.

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


13/02/17

317
Varanasi
Кстати, а как посмотреть и сравнить скорость исполнения кодов?

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


20/08/14
11709
Россия, Москва
Aether в сообщении #1194916 писал(а):
Кстати, а как посмотреть и сравнить скорость исполнения кодов?
После выполнения программы дать команду ## - покажет время выполнения последней команды (или всей последней запущенной программы) в мс.
Правда я выше сравнивал "на глаз". :-)

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


13/02/17

317
Varanasi
Что-то 0 мs выдает даже при $10^6$ значений. Как-то неправильно.

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


20/08/14
11709
Россия, Москва
Да, неправильно. Но тогда не знаю. Раньше работал и другой способ, а потом вдруг перестал без причины.
Но вообще с PARI/GP о скорости простых вычислений говорить бессмысленно, у меня счёт до $10^5$ занимал 1.7с, до $10^6$ считалось 21с, а программка на дельфи без оптимизаций за полторы минуты насчитала всё до 2млрд.

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


13/02/17

317
Varanasi
У меня новые вопросы. Затеял построить функцию Мёбиуса на натуральном ряду. Для этого необходимо числам, имеющим в факторизации степени простых больше 1 присвоить 0, не имеющим в факторизации степеней простых больше 1, присвоить 1, если количество чисел в факторизации четное и -1, если нечетное. (Прошу не выкладывать готовое решение или выкладывать под спойлер)

Функция factor(n) выдает в качестве результата матрицу из k строк и 2-х столбцов. Чтобы проверить, содержит ли факторизация степени факторов >1, необходимо иметь доступ ко 2-му столбцу матрицы, содержащему степени факторов.

Вопрос, как получить доступ кзначениям 2-го столбца, если матрица задавалась неявно, а формировалась как результат функции factor? Т.е. переменные по которым пробегают индексы матрицы неопределены. Как например извлечь значение из третьей строки второго столбца матрицы?

-- 24.02.2017, 17:50 --

Кажется разобрался, присваиваем переменной m матрицу факторизации: m=factor(n), далее с помощью функции v=matsize(m) определяем её размер, который выдается в виде вектора и который мы сохраняем в переменной v. Первое значение v - количество строк. Далее извлекаем k= v[1] и строим цикл длины k в котором обращаемся к каждой ячейке второго столбца матрицы и сравниваем его с 1: m[k,2]==1. Если все значения 1 - значит факторизация числа не содержит высших степеней, если есть значение больше 1 или !=1, значит содержит высшие степени.

Теперь осталось "самую малость" - воплотить это в работающий код.

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


20/08/14
11709
Россия, Москва
Обрисую интересный вариант проверки вектора на "все единицы" (если меньше 1 значений быть не может) без явных циклов:
Код:
v=[...]; if(vecmax(v) == 1, ...)

Получить строку или столбец матрицы в вектор можно примерно так:
Код:
v=m[1,]; v=m[,1]

И тогда проверка что число раскладывается на простые множители в степенях не выше 1:
Код:
if(vecmax(factor(x)[,2]) == 1, ...)
Красота!

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


11/01/06
5702
Aether в сообщении #1195040 писал(а):
Затеял построить функцию Мёбиуса на натуральном ряду.

Всё уже построено: moebius(n)

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


13/02/17

317
Varanasi
Что-то не заладилось у меня с кодом (

Код:
for(n=1,100, m=factor(n); k=matsize(m)[1]; z=0; for(i=1,k, if(m[k,2]==1, z=z+1)); if(z==k, print(n,"=+-1"), print(n,"=0")))


Пропускает некоторые нули

-- 24.02.2017, 19:03 --

maxal в сообщении #1195094 писал(а):
Всё уже построено: moebius(n)


Спасибо, но раз уж начал, то надо доделать, тем более - это важный опыт работы с матрицами и векторами.

-- 24.02.2017, 19:04 --

Dmitriy40 в сообщении #1195093 писал(а):
И тогда проверка что число раскладывается на простые множители в степенях не выше 1:


Ага, спасибо, учту.

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


20/08/14
11709
Россия, Москва
Aether в сообщении #1195101 писал(а):
Что-то не заладилось у меня с кодом (
Код:
... if(z==k, print(n,"=+-1)); print(n,"=0"))
Наверное забыли двойную кавычку в первом print.
И второй print выполняется всегда - это так и задумано? Может быть он должен выполняться только если не выполнился первый и тогда следует поместить его в ветку else оператора if?

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


13/02/17

317
Varanasi
Все-равно, пропускает некоторые нули, хотя и не выводит значения дважды.

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


20/08/14
11709
Россия, Москва
В if(m[k,2]==1 индекс должен быть не k, а i.

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


13/02/17

317
Varanasi
Вот блин, а я уже всю голову сломал, спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 809 ]  На страницу Пред.  1 ... 9, 10, 11, 12, 13, 14, 15 ... 54  След.

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



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

Сейчас этот форум просматривают: Bing [bot]


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

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