Why does Matlab's divisors function take so long when working on an ordinary integer?

Matlab takes 25 seconds to find the sets of divisors for 1000 integers. The user submitted function divisor() -- no s at the end, available in the File Exchange, can find the sets of divisors for 10,000 integers in less than one second. Why can't the built-in divisors function recognize that the parameter given to it is an integer within a range that can be handled in the expeditious manner, and do so?

[the cyclist]

It might be easier to help with this if you actually posted the two code snippets you are comparing, so that we could offer suggestions.

Answer 1

[John D'Errico]

You ALWAYS. ALWAYS. ALWAYS need to consider the arguments for a function. Does it work in double precision, or as a sym? Don't forget that compared to a double precision operation, a symbolic numerical call effectively makes a snail look blazingly fast. However, there are tradeoffs, as the symbolic tool is far more capable.

help divisors

--- help for sym/divisors ---

 DIVISORS Divisors of an expression.
    DIVISORS(S), where S is a SYM, returns the divisors of S.
    If S is integer or rational, only the nonnegative divisors are returned;
    if S is nonconstant, only divisors free of constant factors are returned.
    DIVISORS(S, VARS) returns the divisors of S, such that all factors not 
    containing vars are considered constant, and divisors containg them are omitted.
 
    Examples:
 
       divisors(sym(6)) is
       [1, 2, 3, 6]
 
       divisors(x^2-1) is 
       [1, x - 1, x + 1, (x - 1) * (x + 1)]
 
       divisors(x^2*y*z^2, [x y]) is
       [1, x, x^2, y, x*y, x^2*y]
 
    See also SYM/FACTOR.

    Documentation for sym/divisors
       doc sym/divisors

    Other uses of divisors

       double/divisors    single/divisors

So divisors is a symbolic tool. It can handle a problem like this:

divisors(sym('12345678912314244564656654'))

ans = 

But as you see in the help, it also works on symbolic expressions that are not just numbers. Any code that works on double precision numbers will completely fail on that integer of course, as it is too large for a double.

SHOULD it have been written differently, and check the arguments, so if you pass in a double precision argument, it would work in double precision? Actually, it does look like divisors returns a double result, when you pass in a double as input.

divisors(144)

ans = 1×15

1 2 3 4 6 8 9 12 16 18 24 36 48 72 144

But I'd bet that it uses the sym/factor tool to factor the input. And that code must be slower.

As a check, I wrote a tool a zillion years ago to compute the divisors of a number. It does work in double precision for the operation, IF the number can be factored as a double using double/factor.

aliquotparts(144)
ans =
     1     2     3     4     6     8     9    12    16    18    24    36    48    72

(Note that it was written to return only the proper divisors of a number. So it does not return the number itself in that list.)

timeit(@() aliquotparts(144))
ans =
   7.3956e-05
   
timeit(@() divisors(144))
ans =
     0.009169

So my code is considerably faster.

But, is there a reason why you are asking us this question? We did not write it. So ask the author. But I might guess the target of this code was perceived to be mainly for factoring symbolic expressions, and the author decided the use of it to provide the factors of small integers specifically was not the main reason for being of that code.

But how do I know? How can anyone who is not the author know? Remember that code from TMW is code that should have passed through some sort of peer review there, from their own team on the symbolic toolbox, probably based on requirements from that team. The code was written as it was written. If you think it should operate differently, then submit a feature request to the MathWorks. Answers is not the correct vehicle for a feature request though.

[Steven Lord]

But as you see in the help, it also works on symbolic expressions that are not just numbers.

Here is one such example.

syms x
f = expand((x+1)*(x-2))

f = 

divisors(f)

ans = 

With greater flexibility can come greater complexity.

[Charles Kluepfel]

I do not know of a way of contacting the author of divisors(). I was trying to reach out to get the code to test if the input argument was a double (or uint64, etc.) and if so use a speedier algorithm. That would be a lot easier than expecting someone new to Matlab to know there is the alternative divisor() in the File Exchange, and it seems ridiculous that MathWorks would rely on File Exchange to provide this.

[Steven Lord]

I do not know of a way of contacting the author of divisors().

If you're referring to the function from Symbolic Math Toolbox, please contact Technical Support directly using the Contact Support link under the Get Support heading at the end of this page.

Note that we don't recommend modifying functions that are provided by MathWorks. In this particular case you won't be able to usefully modify the symbolic divisors function because the implementation of the main algorithm in divisors is part of the core symbolic engine for which we do not provide source code.

Note that if your goal is to use this for something like factoring products of primes for cryptographic purposes, your idea to "test if the input argument was a double (or uint64, etc.) and if so use a speedier algorithm" likely won't help you achieve that goal except in "toy" problems. Generally for "real world" problems the numbers involved are much larger than flintmax (and most are greater than realmax and so are represented in double precision as Inf.)

But if you're just interested in factorizing doubles, consider using the factor function in MATLAB. This doesn't give you exactly the same list as divisors does, but it may satisfy your needs.

x = 2^23-1

x = 8388607

tic
factor(x)

ans = 1×2

47 178481

toc

Elapsed time is 0.026189 seconds.