# Simple operations with symbolic variables

11 views (last 30 days)

Show older comments

Ben Radu
on 22 Feb 2017

Commented: Walter Roberson
on 2 Mar 2017

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
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)

### Accepted Answer

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

Walter Roberson
on 22 Feb 2017

The algorithms for parallel sorts baffle me; understanding time complexity of multi-threading can be tough.

I have not seen any clear evidence that the MuPAD kernel uses parallel processing for ordinary operations. Possibly in some of the library functions like numeric ODE.

### More Answers (1)

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
on 24 Feb 2017

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!