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
