How to make the conversion more faster?

Hi. I am trying to convert from decimal to Canonic Signed Digit(CSD). I took the code from this link: http://www.mathworks.com/matlabcentral/fileexchange/9730-canonical-signed-digits

This code takes the decimal input and provides CSD output in string form.

Now i am trying to apply this code for a matrix and took the idea from this link:

http://www.mathworks.com/matlabcentral/answers/30854-how-to-reduce-the-time

Following is the code:

C = [2.336 -1.900; 3.541 -0.219]; 
range = 5;
resolution = 15; 
k = 1;
CC = repmat('', numel(C), range+resolution); 
for i = 1 : numel(C)
  CC(k,1:(range + resolution )) = csdigit(C(i),range,resolution);
  k = k+1;
end

This code used many times by some other codes and the input matrix "C" may have thousands elements. So, if it is possible to reduce the time, it will help my research a lot.

[Oleg Komarov]

Your example code doesn't work.

After fixing it, almost 90% of the time is taken away by csdigit.

I recommend to recode that function.

[Shifat]

Ok. But i tried the example code and it's working.

How can i recode csdigit? Can you please give me any idea?

[Jan]

Please, Shifat, post some working code.

[Shifat]

Here is the code for csdigit. I just cut off unnecessary lines.

targetNum=num;

num=abs(num)/(2^(-resolution));

num=floor(num);

binNum=dec2bin(num,range+resolution);

digits = repmat('0', size(binNum));

%%replaced by-->digits= ('0'+0)*ones(size(binNum))

onesLoc=findstr(binNum,'1');

if ~isempty(onesLoc)

onesRun=find(diff(onesLoc)==1);

while ~isempty(onesRun)

onesPointer=find(diff(onesLoc)==1)+1;

addIn=onesLoc(onesPointer(end));

adder = repmat('0', size(binNum));

%%replaced by-->adder=('0'+0)*ones(size(binNum));

adder(addIn)=('1'+0);

%keep track of the additional digits

digits(addIn)=('-'+0);

binAdder=char(adder);

binNum=dec2bin(bin2dec(binNum)+bin2dec(binAdder),range+resolution);

onesLoc=findstr(binNum,'1');

onesRun=find(diff(onesLoc)==1);

if length(binNum)>length(digits)

digits=['0'+0,digits] % add any additional leading zero

end

end

end

digits(onesLoc)='+'+0;

if length(digits)<resolution

digits=[digits,('0'+0)*ones(1,resolution-length(digits))];

end

digits=char([digits(1:length(digits)-resolution),digits(length(digits)-resolution+1:end)]);

if targetNum<0 % flip representation if negative

digits=strrep(digits,'+','p');

digits=strrep(digits,'-','+');

digits=strrep(digits,'p','-');

end

Here is the code for loop:

C = [2.336 -1.900; 3.541 -0.219];

range = 5;

resolution = 15;

%k = 1;%%i removed 'k' because later i found that it is %unnecessary

CC = repmat('', numel(C), range+resolution);

for i = 1 : numel(C)

CC(i,1:(range + resolution ))=csdigit(C(i),range,resolution);

end

Answer 1

[Jan]

Your function would be faster with a pre-allocation. This:

CC = repmat('', numel(C), range+resolution);

does not pre-allocate CC, because replicating an empty string gives an empty string.

csdigit is not programmed efficiently. The exhaustively celebrated conversion from char to double to char to double to char is a waste of time. E.g. ('0'+0)*ones(size(binNum)) is suboptimal. repmat('0', size(binNum)) would be smarter. bin2dec and dec2bin are slow also, e.g. in bin2dec(char(neg)) * 2 ^ (-resolution). What does a multiplication by 2^-x do with a binary string?? Yes, this can be programmed much faster.

[EDITED] I'm running this code:

function Test(C)
range = 5;
resolution = 15; 
CC = repmat('', numel(C), range+resolution); 
for i = 1 : numel(C)
  CC(i, 1:(range + resolution )) = csdigit(C(i),range,resolution);
end

with these values:

C = floor(rand(100) * 64) / 32;

in Matlab 2009a/64. This needs 5.14 seconds.

The first steop is pre-allocation: repmat('') -> repmat(' '). Result: 4.06 seconds.

Insert a variable pow2res = pow2(resolution) and use them instead of all 2^-resolution and 2^resolution.

Then dec2bin and bin2dec can be replaced by these simplified versions *locally inside csdigit:

function s=dec2bin(d,n)
[f,e] = log2(d);
s=char(rem(floor(d*pow2(1-max(n,e):0)),2)+'0');

function x = bin2dec(s)
x = sum((s - '0') .* pow2(length(s)-1:-1:0), 2);

==> 2.08 seconds.

[Shifat]

I tried with 'repmat' by replacing ('0'+0)*ones(size(binNum)) with repmat('0', size(binNum)). But surprisingly, i found that repmat works slow.

C = rand (50,50);

%%%%run with csdigit

Elapsed time is 1.753776 seconds. %%With repmat

Elapsed time is 1.458614 seconds. %%With out repmat

[Oleg Komarov]

Timings should be computed repeatedly and then taken an average. Anyways, the bottlenecks are others, not the repmat.

Run your script in the profile to see which are the bottlenecks.

[Shifat]

I run the code for 10 times (both for with and with repmat separately) and then take the average.

[Oleg Komarov]

1000 trials:

repmat: 1.47

original: 1.52

[Shifat]

Ok. I did not run it for this long times. Probably for 1000 trials, repmat works faster.

[Jan]

I'm really impressed by your timings. All I get is

1. The warning: Some precision has been lost. Returned value is truncated!

2. A "Subscripted assignment dimension mismatch." error in the line:

CC(k,1:(range + resolution )) = csdigit(C(i),range,resolution);

Do I miss anything?

[Shifat]

Not really.

If the integer part of decimal input is grater than the 'range' in CSD form, than it will show the dimension mismatch error.

In that case, i have run the code again to see if the decimal input generated is with in the 'range'.

Answer 2

[Daniel Shub]

The easiest thing is probably to use a faster computer.

A quick look at csdigit doesn't reveal anything to me that is obviously multi-threaded. You could try replacing your for loop with a parfor loop. This could give you a speed up proportional to the number of cores. If you have access to a cluster, you can even get a bigger boost.

You could also strip all the error checks, and anything else that you do not need, from csdigit. It is probably not a big boost, but it may help.

You could convert csdigit to a mex and see if that buys you anything.

[Shifat]

Can you please give me any idea about mex? I am quite new in matlab. And what is parfor loop?

Answer 3

[Shifat]

Thanks to Jan Simon for the help. I have done the modification as suggested and used the following input:

   C = floor(rand(100) * 64) / 32;

I got:

   Elapsed time is 1.533428 seconds