function [s mbase]=dec2mbase(dec, v, base, check) % Convert decimal integers to multiple based (mbase) integers. % [S MBASE]=DEC2MBASE(D, V) returns an array of S and MBASE % as representation of D such that % D=S(:,1)*MBASE(1)+...S(:,end)*MBASE(end). % % Inputs: % DEC, an array of decimal integers. % % V, a vector of integers to regroup digits in a given BASE. % E.g., when BASE=2, V=[3 3 10] means that the 16 digits % of a binary number is grouped in to three groups with 3 digits % for the 1st and 2nd groups and 10 digits for the last group. % Note sum(V) should not be less than % ceil(log2(max(DEC))/log2(base)). % % BASE, an positive integer as the base for representation of DEC. % Its default value is 2. % % CHECK, a optional logical variable, defaulted to be true. When it is % TRUE, the program will check to see if % SUM(V)>= ceil(log2(max(DEC))/log2(BASE)) is true. If not so, % the function will give an error message. When the input % DEC is a long array, searching for its maximum value can be % costly. Users are therefore recommended to have an appropriate % vector V and set the optional CHECK to be false before % calling the function. % Outputs: % S, a matrix of size M by N where M is the length of DEC and N % is the length of V. % % MBASE, a vector of bases, with which you can recover the DEC, % by sum(S.*MBASE(ones(N,1),:),2). % % V, BASE and MBASE are related by % % MBASE=BASE.^(sum(V)-cumsum(V)) (eq.2) % % Example: let d=randi(2^16, 2, 1), which may turn out as % d =[59071;65234], calling [s mbase]=dec2mbase(d, [3 3 10]) % results in s =[ 7 1 703; 7 7 722] % and mbase = [8192 1024 1]. As can be verified, % sum(s.*mbase(ones(2,1),:),2) recovers the original d array. % % For more explanations, see inside of the function. See also MBASE2DEC % Explanation and Motivation: % As known well, an decimal integer, D, can be re-expressed as a % combinations of powers of a given base, B (which itself is a % positive integer) as follows, % % D=A0*B^(n)+A1*B^(n-1)+ ... + An*B^(0). (eq. 1) % % The coefficients [A0 A1 ... An] is called a representation in % B-base for the decimal integer D. When B is 2, % the coefficients will only consists of 0 and 1, known as binary % representation of D. % % That's we all have known very well, nothing new! And Matlab comes % with a pair of functions, DEC2BIN and BIN2DEC, to help you to % convert between decimal and binary numbers. % % What's special in this DEC2MBASE function is regrouping of eq. 1 % for efficiency consideration. Let's say you have a decimal integer % which can be represented in 16 digits of binary number (thus n is % 15 in eq. 1), and assume that the following regrouping will % make your applications more efficient (more on this later), % % D= (A0*B^2+A1*B^1+A2)*B^13 % + (A3*B^2+A4*B^1+A5)*B^10 % + (A6*B^10+A7*B^9+A8*B^8+A9*B^7+A10*B^6+A11*B^5+A12*B^4+ % A13*B^3+A14*B^2+A15*B^1+A16) % % i.e., you re-group them into three groups, each consists of 3, 3 % and 10 digits of binary numbers respectively. % % Now, the function DEC2MBASE will give you a 1x3 vector, with % % S(1)=A0*B^2+A1*B^1+A2; % S(2)=A3*B^2+A4*B^1+A5; % S(3)=A6*B^10+A7*B^9+A8*B^8+A9*B^7+A10*B^6+ % A11*B^5+A12*B^4+A13*B^3+A14*B^2+A15*B^1+A16 % % For example, for a decimal integer D=2^16-354=65082, its S=[7 7 670] % with MBASE=2.^[13 10 0]. If you sum(S.*MBASE,2), you will recover % 65082. % % When this kind of regrouping will give your application more % efficiency? Say, if you have a 16-layer binary tree, and you want to % search for some information through its leaves. You could search it % recursively through each of 16 layers as a C-programmer customarily % does. However, remember MATLAB is slow when comes iterations, % and is deadly slow when the number of layers is big such as 16. % Therefore you may very much want to vectorize your search. % Given that you are always constrained by computer memory as well, you % may then come up with a strategy of grouping the 16 layers into a few % groups and vectorize your search in each group. For the % example given above, the 16 layers is grouped into, 3, 3, and 10 % layers. You search the 8 nodes together (vectorization) in your % first group and find the 7th node containing the information % sub-tree. You then do the same for the second group and again find % its 7th node contains the destination of the information. You then % vectorize your search in your last group by search 1024 elements % together, and find the 670th leave node contains the information. % % For a better understanding of V, consider its two limit cases: % take an integer within 2^16 as an example, if V is set to be % V=ones(1,16), then the output S will be the same as from % calling the Mathworks's DEC2BIN except that S here is an % array of doubles not a string of characters; and in this case % MBASE will be 2^(15:-1:0). On the other hand, if V=16, the % output of S will be the same as DEC and MBASE=1. % % Wow, the documentation has gone long. Often I find that to document a % function takes more effort than to program the function itself. This % has been a blocking factor for me to publish more functions. Hopefully % you will prove that my effort is worthwhile. % % Enjoy! % % Zhigang Xu, 2009/Aug/24 if nargin<3, base=2; end if nargin<4, check=true; end if ~isa(dec, 'double'); dec = double(dec(:)); end if check d_max=max(dec); A=ceil(log2(d_max)/log2(base)); if sum(v)<A error(['SUM(V) should not be less than ' num2str(A)]) end end n=length(v); p=cumsum(v); p=p(end)-p; mbase=base.^p; b=base^v(n); q=fix(dec/b); s(:,n) =dec-q*b; dec = q; while any(dec) && n >1 n = n - 1; b=base^v(n); q=fix(dec/b); s(:,n) = dec-q*b; dec=q; end end
