mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory > PARI/GP

Reply
 
Thread Tools
Old 2018-02-25, 15:08   #1
Godzilla
 
Godzilla's Avatar
 
May 2016

2×34 Posts
Default Pari gp Command divisors() ?

Good evening,
I wanted to ask if the program parigp is faster to find the divisors of an even number, with the command divisors(), compared to an odd number with the command factor() or is it the same? thank you
Godzilla is offline   Reply With Quote
Old 2018-02-25, 15:47   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by Godzilla View Post
Good evening,
I wanted to ask if the program parigp is faster to find the divisors of an even number, with the command divisors(), compared to an odd number with the command factor() or is it the same? thank you
These commands aren't even the same, factor only finds prime factors, divisors lists all divisors.
science_man_88 is offline   Reply With Quote
Old 2018-02-25, 15:53   #3
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

divisors is a bit slower than factor. Given the same size inputs, either one is slower (on average) on odds vs. evens. So it seem the question boils down to which one has the larger impact. Like sm88 said, the question is a bit odd and sounds like the XY Problem, but as asked:

An experiment:
Code:
? s=0; forstep(n=10^11+0,10^11+3*10^6,2,s+=length(factor(n))); s
time = 13,207 ms.
3000002
? s=0; forstep(n=10^11+0,10^11+3*10^6,2,s+=length(divisors(n))); s
time = 16,280 ms.
58547739
? s=0; forstep(n=10^11+1,10^11+3*10^6,2,s+=length(factor(n))); s
time = 17,275 ms.
3000000
? s=0; forstep(n=10^11+1,10^11+3*10^6,2,s+=length(divisors(n))); s
time = 18,658 ms.
20901346
says that at this size, odds win. At this size it is faster to do either operation on evens.

Repeating this using 10^9 says factor wins -- at that size the overhead of divisors vs. factors outweighs the extra time factoring.

In my program, divisors first does a factor then constructs the divisors. I'm curious how Pari/GP does it. Looks like divisors_init calls absZ_factor(n) so it does the same thing, albeit in a more roundabout way (it handles more types, and might have more efficient iterators).

Last fiddled with by danaj on 2018-02-25 at 15:55
danaj is offline   Reply With Quote
Old 2018-02-25, 16:00   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by danaj View Post
divisors is a bit slower than factor. Given the same size inputs, either one is slower (on average) on odds vs. evens. So it seem the question boils down to which one has the larger impact. Like sm88 said, the question is a bit odd and sounds like the XY Problem, but as asked:

An experiment:
Code:
? s=0; forstep(n=10^11+0,10^11+3*10^6,2,s+=length(factor(n))); s
time = 13,207 ms.
3000002
? s=0; forstep(n=10^11+0,10^11+3*10^6,2,s+=length(divisors(n))); s
time = 16,280 ms.
58547739
? s=0; forstep(n=10^11+1,10^11+3*10^6,2,s+=length(factor(n))); s
time = 17,275 ms.
3000000
? s=0; forstep(n=10^11+1,10^11+3*10^6,2,s+=length(divisors(n))); s
time = 18,658 ms.
20901346
says that at this size, odds win. At this size it is faster to do either operation on evens.

Repeating this using 10^9 says factor wins -- at that size the overhead of divisors vs. factors outweighs the extra time factoring.

In my program, divisors first does a factor then constructs the divisors. I'm curious how Pari/GP does it. Looks like divisors_init calls absZ_factor(n) so it does the same thing, albeit in a more roundabout way (it handles more types, and might have more efficient iterators).
Factor allows you to factor more than just integers and lets you set a limit, factorint at last check doesn't allow a limit to be placed.

Last fiddled with by science_man_88 on 2018-02-25 at 16:00
science_man_88 is offline   Reply With Quote
Old 2018-02-25, 16:25   #5
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
Factor allows you to factor more than just integers and lets you set a limit, factorint at last check doesn't allow a limit to be placed.
divisors operates on multiple types as well. I didn't notice any time difference for this test (simple integers, no additional arguments) of factorint vs factor.

Both factor and divisors operating on integers this size could be sped up 2-4x if it was particularly desired.
danaj is offline   Reply With Quote
Old 2018-02-25, 16:33   #6
Godzilla
 
Godzilla's Avatar
 
May 2016

2×34 Posts
Default

Tanks for the reply SS88 and Danaj ,

my question is to verify operations with highly composite numbers.
I explain very quickly: p1 * p2 = n * 20 = HCN highly composite number.

101*3 = 303 * 20 = 6060
Code:
(12:31) gp > divisors(6060)
%2 = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60, 101, 202, 303, 404, 505, 606, 1010, 1212, 1515, 2020, 3030, 6060]
Than :

6060/60=101 An odd prime factor always corresponds to an even divisor.
6060/2020=3 An odd prime factor always corresponds to an even divisor.
Godzilla is offline   Reply With Quote
Old 2018-02-25, 17:08   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by Godzilla View Post
Tanks for the reply SS88 and Danaj ,

my question is to verify operations with highly composite numbers.
I explain very quickly: p1 * p2 = n * 20 = HCN highly composite number.

101*3 = 303 * 20 = 6060
Code:
(12:31) gp > divisors(6060)
%2 = [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60, 101, 202, 303, 404, 505, 606, 1010, 1212, 1515, 2020, 3030, 6060]
Than :

6060/60=101 An odd prime factor always corresponds to an even divisor.
6060/2020=3 An odd prime factor always corresponds to an even divisor.
So you've noticed odd * even= even
science_man_88 is offline   Reply With Quote
Old 2018-02-25, 17:14   #8
Godzilla
 
Godzilla's Avatar
 
May 2016

16210 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
So you've noticed odd * even= even
I believe that, the divisors () command is faster than factor () command, because divisors() does not check if a number is prime.
Godzilla is offline   Reply With Quote
Old 2018-02-25, 17:20   #9
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts
Default

Quote:
Originally Posted by Godzilla View Post
I believe that, the divisors () command is faster than factor () command, because divisors() does not check if a number is prime.
All depends on details of implementation there are any number of ways to check conditions like issquarefree.
science_man_88 is offline   Reply With Quote
Old 2018-02-25, 17:26   #10
Godzilla
 
Godzilla's Avatar
 
May 2016

2×34 Posts
Default

I noticed that every even number corresponds to an odd number, for example the even number 60 always corresponds to 3.

43*3=129*20=2580
2580/60=43
Godzilla is offline   Reply With Quote
Old 2018-02-25, 17:31   #11
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by Godzilla View Post
I noticed that every even number corresponds to an odd number, for example the even number 60 always corresponds to 3.

43*3=129*20=2580
2580/60=43
I'm guessing you've watched the numberphile video ?
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Question about Mersenne divisors paulunderwood Miscellaneous Math 1 2016-01-24 01:41
Looking for fermat divisors, n=90-120 firejuggler Prime Sierpinski Project 2 2012-01-10 17:14
Density of Mersenne divisors Random Poster Math 1 2008-12-15 01:14
odd divisors of Mersenne-like, question stpascu Factoring 1 2006-10-16 16:31
Number of divisors of n? Citrix Math 10 2006-02-08 04:09

All times are UTC. The time now is 00:55.


Thu Dec 2 00:55:44 UTC 2021 up 131 days, 19:24, 1 user, load averages: 0.66, 0.86, 0.84

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.