How to make the conversion more faster?

1 view (last 30 days)
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:
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.
  4 Comments
Jan
Jan on 11 Mar 2012
Please, Shifat, post some working code.
Shifat
Shifat on 11 Mar 2012
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

Sign in to comment.

Accepted Answer

Jan
Jan on 11 Mar 2012
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.
  7 Comments
Jan
Jan on 11 Mar 2012
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
Shifat on 11 Mar 2012
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'.

Sign in to comment.

More Answers (2)

Daniel Shub
Daniel Shub on 11 Mar 2012
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.
  1 Comment
Shifat
Shifat on 11 Mar 2012
Can you please give me any idea about mex? I am quite new in matlab. And what is parfor loop?

Sign in to comment.


Shifat
Shifat on 12 Mar 2012
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

Products

Community Treasure Hunt

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

Start Hunting!