Why does Matlab's divisors function take so long when working on an ordinary integer?
3 次查看(过去 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
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
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
So divisors is a symbolic tool. It can handle a problem like this:
divisors(sym('12345678912314244564656654'))
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)
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
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
tic
factor(x)
toc
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Number Theory 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!