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

2 ビュー (過去 30 日間)
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?
  1 件のコメント
the cyclist
the cyclist 2022 年 11 月 30 日
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.

サインインしてコメントする。

回答 (1 件)

John D'Errico
John D'Errico 2022 年 11 月 30 日
編集済み: John D'Errico 2022 年 11 月 30 日
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.
  3 件のコメント
Steven Lord
Steven Lord 2022 年 12 月 1 日
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.

サインインしてコメントする。

製品


リリース

R2022a

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by