Wikipedia

Wikipedia:Reference desk/Archives/Computing/2021 November 25

< Wikipedia:Reference desk‎ | Archives‎ | Computing
Computing desk
< November 24 << Oct | November | Dec >> Current desk >
Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.


November 25

edit

List of all divisors of an integer

edit

I need to get a list of all divisors of an integer (and do it a large number of times). What I am doing is factoring the integer and making an array of the prime factors and the power to which they appear in the number. Then I have a recursive routine where each level loops on the powers of a particular divisor, building up a product as it recurses, and adds the product to the list.

The problem is that on the average, getting the list of divisors is taking more than 5 times as much time as factoring. I'm looking for a faster way.

One thing I thought about is that maybe there is too much overhead in the recursive function - inside it only does a loop and a multiplication. The number of prime divisors is limited to nine or ten, so I could have that many nested loops rather than use a recursive procedure.

Does anyone have an idea for a faster way to get a list of divisors of an integer? Bubba73 You talkin' to me? 02:21, 25 November 2021 (UTC)[reply]

06:39, 25 November 2021 (UTC)2600:1700:D0A0:21B0:B8E9:FC33:43DF:4E7 (talk)
  • ExtendListOfKnownPrimesTo ( sqrt( num ))
  • CheckIfFactored( num, ListOfPrimes)
The trick is to keep a list of known primes, and then extend it when needed. The Sieve of Eratosthenes is simple to implement and extend - use an array of bools, with index [ (num-1) / 2 ]. Keep this array and the array of primes between calls to ExtendListOfKnownPrimesTo
LongHairedFop (talk) 12:06, 25 November 2021 (UTC)[reply]

Are you actually trying to enumerate the divisors, or just count them? Counting them is the Euler totient function. If you want to enumerate them, then you have to recursively loop through the distinct pk's from 0 to k, etc. But that should be pretty efficient. How large are these numbers? 2601:648:8202:350:0:0:0:69F6 (talk) 12:30, 25 November 2021 (UTC)[reply]

I need the actual list of divisors. As I stated above, I am recursively going through the prime factors, but that takes more than 5 times as long as factoring itself. I don't know the exact size of the numbers, but they get up to at least 13 digits, I think. Bubba73 You talkin' to me? 19:07, 25 November 2021 (UTC)[reply]
If you can keep the list in random access memory, there is a purely iterative process (two nested loops). Given the prime factorization, make a list of lists, one for each prime factor, of the proper powers of that prime. For example, for 1078 = 2×72×11 that list would be [[2], [7, 72], [11]] = [[2], [7, 49], [11]]. For the list of divisors, start with the singleton list L = [1]. For each list P in the list of lists, append to L a copy of L with each element multiplied by each p in P:
Start: L := [1].
P = [2]: L := [1] ++ [1×2] = [1, 2].
P = [7, 49]: L := [1, 2] ++ [1×7, 2×7, 1×49, 2×49] = [1, 2, 7, 14, 49, 98].
P = [11]: L := [1, 2, 7, 14, 49, 98] ++ [1×11, 2×11, 7×11, 14×11, 49×11, 98×11] = [1, 2, 7, 14, 49, 98, 11, 22, 77, 154, 539, 1078].
The resulting list is not sorted, but fast sorting algorithms can be found in most libraries. Note that you do not actually need to store the list of lists of powers; you can generate the powers with which to multiply on the fly.  --Lambiam 00:09, 26 November 2021 (UTC)[reply]
Thank you, I think that will work a lot better than the method I'm using. The divisors don't need to be sorted. I'll try it tomorrow. Bubba73 You talkin' to me? 05:01, 26 November 2021 (UTC)[reply]
It's actually a triply nested loop – for P in listOfLists / for p in P / for e in L.  --Lambiam 13:20, 26 November 2021 (UTC)[reply]
Further simplifications are possible. You can append the new products e × p immediately to the end of L; then, for each higher power, loop only over the part of L added just before:
First 7: L := [1, 2] ++ [1×7, 2×7] = [1, 2] ++ [7, 14] = [1, 2, 7, 14].
Second 7: L := [1, 2, 7, 14] ++ [7×7, 14×7] = [1, 2, 7, 14, 49, 98].
You can even fuse the factorization process with the loop over P, not storing any list of prime factors to start with. That will simplify the code; for the running time this will hardly make a difference.  --Lambiam 13:36, 26 November 2021 (UTC)[reply]
Yes, it actually uses three loops. I implemented it, except that I avoided the multiplications by 1 and there are no explicit lists except for the one that holds the list of divisors. In a small test, it is just about 3 times faster than the recursive method I was using. It might get better for larger (more typical) cases. The recursive method is OK for a few uses, but this is going to be used at least hundreds of millions of times and likely billions of times. Bubba73 You talkin' to me? 21:26, 26 November 2021 (UTC)[reply]
And one of the loops is on the power of the prime factor, which is 1 most of the time. I do the first power and then I check to see if the power is greater than 1. If it isn't, as it is most of the time, I avoid that loop. Bubba73 You talkin' to me? 22:00, 26 November 2021 (UTC)[reply]

Can I ask what you are trying to do? Do you have an example number? Btw I got confused about the totient function earlier: please ignore what I said about it. Yes you are probably better off generating the divisors on the fly than building a list in memory. 2601:648:8202:350:0:0:0:69F6 (talk) 20:43, 27 November 2021 (UTC)[reply]

Bubba73, if the number of divisors is "reasonable" (small enough to loop through), then the number of distinct prime factors won't be too large, so if you really want fast code, you can generate nested loops (even with chunks of straight line code) directly with something like GNU lightning. 2601:648:8202:350:0:0:0:69F6 (talk) 10:32, 28 November 2021 (UTC)[reply]

Reply to both: I need to get a list of the divisors of numbers to apply a theorem, and do it within my existing program. The numbers that are to have their divisors listed are generated inside the program. I don't have an example at hand so I don't normally see them, but I can get some. The number of divisors of one of these numbers can be in the thousands. This is to be done hundreds of millions or billions of times.
The method Lambiam told me about is a bit more than twice as fast as the recursive method I was using. Bubba73 You talkin' to me? 23:31, 28 November 2021 (UTC)[reply]
  • This is a summary of a run that took 1 hour on an old i7 (running on one core):
    • 150,379,012 numbers factored to get a list of their divisors
    • Largest number factored, n = 31,950,157,798,650
    • Largest number of divisors = 5,376 (for n=9,276,007,540,800). Bubba73 You talkin' to me? 01:02, 29 November 2021 (UTC)[reply]
Those two numbers are both very easy to factor, and 5376 divisors is not a lot to enumerate. Is the bottleneck actually factoring rather than enumerating the factors? Are you asking how to factor numbers in the range of 2**40 or so? I like the Pollard rho method as being fairly simple to implement compared with fancier methods, while being much faster than trial division. How are you generating these numbers you are factoring? What programming language are you using? 2601:648:8202:350:0:0:0:69F6 (talk) 11:15, 29 November 2021 (UTC)[reply]
On the tests I've done with some slight refinements to Lambian's first method, listing the divisors takes around 2x as long as factoring (a little more or a little less, depending). My old recursive method was taking over 5 times as long. The numbers to factor are generated within the program - they come up as denominators in Egyptian fractions. I don't know how big they will be in advance, but on that last test, the largest was close to 245, but they are going to get bigger (but certainly well under 260. I've used Pollard's rho method, but I'm using Shank's method. With Pollard's method, you have to square numbers, and they get larger than 264. In Shank's method, the intermediate numbers don't get much larger, so I can keep them under 64 bits, so it is well-suited for this range of numbers. I'm using Object Pascal/Delphi. Bubba73 You talkin' to me? 04:31, 30 November 2021 (UTC)[reply]
Is it a secret which theorem you are applying to the list of divisors?  --Lambiam 14:11, 29 November 2021 (UTC)[reply]
No secret theorem, it is theorem 4 here]. Bubba73 You talkin' to me? 20:22, 29 November 2021 (UTC)[reply]
I expect the time needed to generate the list, given the factorization, is roughly linear in the length ℓ of the list. To apply Theorem 4 you next need to find a pair d1, d2 of divisors obeying specific requirements. As there are O(ℓ2) pairs of divisors, I expect that step to take quadratic time. If there are few factors, the factorization step should dominate, and if there are many different factors, the quadratic step should dominate. Therefore it appears to me that not a whole lot can be gained by optimizing the process of generating the list of divisors.  --Lambiam 00:52, 30 November 2021 (UTC)[reply]
I'm (sort of) avoiding quadratic time when comparing pairs of divisors because part of the theorem is that the sum of the two divisors must be a multiple of the numerator (call it n), so I store the value of the divisor mod n. Then I group the divisors that are congruent to 1 mod n and group the ones that are congruent to n-1 mod n - then match between the two groups. That is quadratic, but on a much smaller list. Bubba73 You talkin' to me? 02:26, 1 December 2021 (UTC)[reply]

The following is not optimized at all, but it seems pretty fast:

Haskell code
import           Data.List (group, tails)

factors :: Int -> [Int]
factors n = go n (2:[3,5..]) []
    where
      go n ccs@(c:cs) acc
          | c*c > n = [n]
          | n`rem`c == 0 = c : go (n`quot`c) ccs (c:acc)
          | otherwise = go n cs acc

divisors :: Int -> [Int]
divisors n = go $ group (factors n)
    where
      go [] = [1]
      go (fs:fss) =
          [d*t | gs <- tails fs, let t = product gs, d <- go fss]

n0 = 31950157798650
n = 9276007540800

main = print (check n) where
    check n = (length (divisors n), all ok (divisors n))
    ok d = n`rem`d == 0

2601:648:8202:350:0:0:0:69F6 (talk) 17:48, 29 November 2021 (UTC)[reply]

A smart Haskell compiler might recognize that the recursive functions are actually linear folds, the functional equivalent of tail recursion, which can be implemented by iteration.  --Lambiam 00:52, 30 November 2021 (UTC)[reply]
Right, the factorization routine is written that way (with an accumulation parameter) specifically to enable that optimization. It is a functional programming idiom. I may be missing something but I think that the divisors routine doesn't optimize that way. It really does have to recurse through a tree of divisors. On the other hand, because of lazy evaluation, neither routine (post-edit, below) has to expand a whole list of results into memory before the rest of the program can consume them. If you don't use Haskell, give it a try sometime ;). learnyouahaskell.com is a good place to start. Edit: I rearranged the factorization function to also generate the factor list lazily, like in a right fold. 2601:648:8202:350:0:0:0:4F12 (talk) 03:44, 30 November 2021 (UTC)[reply]
  • I still don't understand what you are trying to do with theorem 4 (find 2-term 1/x+1/y representations of particular fractions? Which ones?). But looking at the theorem, you shouldn't need to generate all the pairs of divisors since you can prune a lot before you start. E.g. the requirement that the two divisors be coprime, given one divisor you immediately eliminate a lot of possibilities for the other. The other conditions let you get rid of even more. I didn't look closely at the proofs, but it might be possible to "unwind" the proofs of theorems 3 and 4 to let you retrieve the divisors directly from the factorization, instead of having to search through the pairs of them. 2601:648:8202:350:0:0:0:4F12 (talk) 08:55, 30 November 2021 (UTC)[reply]
I'm using both of those conditions, and I avoid having to take the GCD, but there might be a better way. Bubba73 You talkin' to me? 02:30, 1 December 2021 (UTC)[reply]
I've not encountered the phrase "Egyptian fractions" before, however I recognise them as before betting shops were automated settlers used them to decompose the odds to make the arithmetic easier. 92.23.218.99 (talk) 15:52, 30 November 2021 (UTC)[reply]
See Egyptian fraction. Bubba73 You talkin' to me? 02:27, 1 December 2021 (UTC)[reply]
GCD is very fast compared to factorization or enumerating the divisors: Euclidean algorithm. It's a built-in in Haskell ;). 2601:648:8202:350:0:0:0:4F12 (talk) 04:28, 1 December 2021 (UTC)[reply]
I know, I've had it programmed into my library of math routines for 40 years. But in this case I'm avoiding it. Bubba73 You talkin' to me? 06:52, 1 December 2021 (UTC)[reply]

Type of DVD player that plays Region 1 & NTSC discs

edit

Does my UK DVD player have to depend on the type of player (e.g. Sony, Philips, Toshiba or Liteon) that plays region 1 and NTSC DVDs? 81.152.221.231 (talk) 21:40, 25 November 2021 (UTC)[reply]

Do a web search for multi region dvd player and region free DVD player. Repeat but with blue ray player instead of DVD player (blue ray players play DVDs). 05:51, 26 November 2021 (UTC)2600:1700:D0A0:21B0:7013:8442:84B6:D144 (talk)
Retrieved from "https://en.wikipedia.org/w/index.php?title=Wikipedia:Reference_desk/Archives/Computing/2021_November_25&oldid=1096457017"