Simple operations with symbolic variables

14 views (last 30 days)
Hello everybody,
I'm new to Matlab. I would like to ask if anyone knows what's the time complexity of the addition / subtraction operations with symbolic variables.
Example:
syms a b
A = a^2*b^2+a^3*b^3
B = a^2*b^2+a*b
I would like to know what's the time complexity of this simple operation:
A - B = a^3*b^3 - a*b
I'm not sure about how Matlab calculates it.
(note that each variable has no given value).
Thank you!
  5 Comments
Walter Roberson
Walter Roberson on 2 Mar 2017
Unfortunately using tic and toc to measure algorithm complexity is tricky.
For example, the algorithm complexity of
for k =1:n
H(k) = 1;
end
is O(n). But if you code that and test with tic toc, you will find that the time is O(n^2) or worse, because of the way that MATLAB handles expanding arrays (notice that I did not preallocate, which is a matter irrelevant to algorithm complexity)

Sign in to comment.

Accepted Answer

Walter Roberson
Walter Roberson on 22 Feb 2017
The time complexity of symbolic operations is unspecified, undocumented, and subject to change between versions.
Time complexity of addition and multiplication is usually talked about abstractly as if addition of any two numbers takes the same time independently of the values of the numbers, and if multiplication of any two numbers takes the same time independently of the values of the numbers -- and time complexity calculations equate the two times, as if the time to add two numbers is the same as the time to multiply two numbers. For the purposes of what "time complexity" computes, it is irrelevant that the time to do an addition is not the same as the time to do a multiplication as long as the time for the multiplication is a constant multiple of the time to do addition. 18 cycles (for example) instead of 3 cycles (for example) is not important as long as the implementation is some constant multiple 18/3 or 68/9 or whatever it happens to be for the implementation.
However, implementations of symbolic values need to deal with the fact that values are not constant length -- the space required to represent the number 3 might be different than the space required to represent 33 (as would be the case for binary coded decimal, BCD), or the space required to represent 333 (which exceeds the value representable in an 8 bit byte.) Because of this factor, the time required for additions or multiplications are not constant but instead depend upon value.
For addition of two groups of blocks of values such that each block represents an integer (e.g. , if you broke an integer up into bytes, then you each integer would be represented by a group of bytes and you would have two such groups to add two numbers), the traditional "long form" method is to add the lowest two corresponding blocks, detect carry, add the next two corresponding blocks together with the carry from the first set, detect carry from that, add the next two corresponding blocks together with the carry, and so on. This requires time proportional to the number of blocks in a group.
But consider that if there were no carries that if you had the hardware resources you could add each pair of corresponding blocks simultaneously. Then you have to do fix-up for the carries, and the fix-up might trigger a carry, and so on. Can this approach save you anything in the long run? It turns out that there are algorithms that can add in parallel and propagate carry faster than linearly. And that starts to matter if you just happen to be using a processor that has SIMD (Single Instruction, Multiple Data) class of instructions that can accelerate performance. Therefore, the time complexity of addition of variable-length values depends upon the size of the values and upon the available instruction set and upon the quality of implementation.
Worst case for addition of variable length objects is that the time taken is proportional to log() of the the larger value.
Extended precision multiplication is more complicated. Going back in my memory several decades, I seem to recall that worst case would be proportional to the product of the logs of the two values, but I could be wrong. I suggest you examine John D'Errico's Variable Precision Integer (VPI) File Exchange Contribution.
All of this leads to situations where the Time Complexity of a symbolic algorithm can potentially be improved by techniques such as re-centering, to reduce the values used so that the extended precision operations take less time, even though that might appear to increase the operation count, because the assumption that multiplication takes a constant factor more time than addition is no longer valid.
  3 Comments
Ben Radu
Ben Radu on 24 Feb 2017
Thank you very much, Walter Roberson, for your very helpful and detailed answer.

Sign in to comment.

More Answers (1)

Vandana Rajan
Vandana Rajan on 22 Feb 2017
Hi,
To understand how much time a particular MATLAB code takes to execute, you can use the 'tic' and 'toc' functions.
https://in.mathworks.com/help/matlab/ref/tic.html
You may also go for MATLAB profiler to track execution time.
https://in.mathworks.com/help/matlab/ref/profile.html
  6 Comments
Walter Roberson
Walter Roberson on 24 Feb 2017
Documentation of the internal rules would not necessarily help much. I mentioned above a symbolic math package in which the ordering depends upon which version was seen first in the session: that package explicitly documents that fact and explicitly documents that given two equivalent expressions, the one that is chosen is the one that has the lower address (pointer). As the user has no control over the address something is placed at, this mostly acts to document that you cannot fight the system and cannot rely on the order of terms because it could change any time. It is good to know explicitly that taking shortcuts will probably fail, as it keeps you from wasting time trying to reverse-engineer rules, but really the same thing can be accomplished by just saying "These are internal matters, don't count on them" without documenting what happens in any given release.

Sign in to comment.

Community Treasure Hunt

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

Start Hunting!

Translated by