mersenneforum.org Pari gp Command divisors() ?
 Register FAQ Search Today's Posts Mark Forums Read

 2018-02-25, 15:08 #1 Godzilla     May 2016 2×34 Posts 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
2018-02-25, 15:47   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by Godzilla 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.

 2018-02-25, 15:53 #3 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32×101 Posts 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
2018-02-25, 16:00   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by danaj 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

2018-02-25, 16:25   #5
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts

Quote:
 Originally Posted by science_man_88 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.

 2018-02-25, 16:33 #6 Godzilla     May 2016 2×34 Posts 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.
2018-02-25, 17:08   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts

Quote:
 Originally Posted by Godzilla 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

2018-02-25, 17:14   #8
Godzilla

May 2016

16210 Posts

Quote:
 Originally Posted by science_man_88 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.

2018-02-25, 17:20   #9
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by Godzilla 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.

 2018-02-25, 17:26 #10 Godzilla     May 2016 2×34 Posts 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
2018-02-25, 17:31   #11
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by Godzilla 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 ?

 Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 1 2016-01-24 01:41 firejuggler Prime Sierpinski Project 2 2012-01-10 17:14 Random Poster Math 1 2008-12-15 01:14 stpascu Factoring 1 2006-10-16 16:31 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