From sources-request at octave dot org Mon May  2 10:23:43 2005
Subject:  Sub: Converting numbers to and from Fractional bases
From: "D Goel" <deego at gnufans dot org>
To: octave-sources at bevo dot che dot wisc dot edu
Date:  Mon, 02 May 2005 11:07:28 -0400

--=-=-=





Greetings

I couldn't find a treatment of fractional bases on google.  So, the
one below is my own treatment, and so I don't know how correct or
"official" it is.


The attached 3 programs convert a number from decimal to another base
and vice versa, except that the base can also be non-integer.


A representation [x y z . p q r s ... ]  in base b means that the
number is = x*b^2 + y*b^1 + z*b^0 + p*b^(-1) + ....

x,y,z,p,.... are called the allowed digits and are integers. For an
integer base b, the allowed digits range only from 0 to (b-1).  It is
easy to see that each number has a unique representation in this
scheme. Well, almost... The only single nonuniqueness is that
.999999999 ... is same as 1.0000000.  The latter is always the
preferred, or the "principal" representation.  In other words, make x
as large as possible before moving on to y.  We will use the same
algorithm below as well.


For a real (possible non-integer) base b, the allowed digits range
from 0 to ceil(b)-1.  Eveything else remains the same.  

Sometimes, we will find that multiple representations are possible.
For example, the number 1.0473.. (base 9.5) is the same as the number
.995.. (base 9.5).

In other words, .948.. (base 9.5) is equal to 1.0... (base 9.5).  And,
Numbers between .948 and .9999 can also be expressed as 1.000 to
1.053...  Indeed, .99999... is greater than 1.0.  Once again, just as
we did for integer bases, we call 1.000 and 1.053 as the preferred
"principal" representations.   In other words, assign as much as
possible to x before moving on to y.

The function fracbaseprincipal takes any number and converts it to its
principal form.


The number dec2fracbase converts a decimal to its representation in
base b.  The answer returned is always the principal form.  
Thus, if you try to express 4 in base 2, we have: 
octave>      dec2fracbase(4,2)
      {
  [1,1] =

    1  0  0

  [1,2] = 2
  [1,3] = 3
  [1,4] = 1
  [1,5] = 4
}

This, then, is our structure for representing a general number in base
b.

In this structure, The first part is the answer 1 0 0.  The next part,
2 indicates the base.  The third part 3 indicates that the decimal
lies at the end of the third digit, so that the answer is
100.0000000.....  The fourth part is 1 or -1 depending on the sign.
The fifth is an optional informational part, which indicates the
equivalent decimal representation.

In this structure, parts 2--5 are optional.  When absent, defaults are
assumed.  We already discussed the fifth part. If the fourth part,
sign is absent, it is taken to be 1.  If the third part, decimal
location is absent, it is assumed to be after the last digit.  If the
second part, base is absent, it is assumed to be a global variable,
fracbase, whose default value is 2.  Thus, most often, you will
specify just the number and the base, for example {[77],8}, to
represent a number 77(base 8).

If you omit the base too, it is assumed ==2, as discussed above, So,
for example, we know that {[1 0 0]} is equivalent to {[1 0 0], 2,
3,1,4}.  Let's try converting back to decimal:

octave:22> fracbase2dec({[1 0 0]})
ans = 4


As another example, let's convert 4 to base 2.5. We get:
{
  [1,1] =

    1  1  1  0  1  1  1  0  0  0  0  1  1  0  1  2  1  0 ...

  [1,2] = 2.50000000000000
  [1,3] = 2
  [1,4] = 1
  [1,5] = 4
}


We see that the base is 2.5 and the decimal lies after the 2nd place.
So, the answer reads:  11.10111.....

As one final example, let's convert 200 to base 16:

octave:28>       dec2fracbase(200,16)
ans =

{
  [1,1] =

    12   8

  [1,2] = 16
  [1,3] = 2
  [1,4] = 1
  [1,5] = 200
}

The answer is 12,8, which we often also write as C8. 

Of course, we want to keep our method general, applicable to arbitrary
bases (say, 18.5), and so we do not make use of letters A-F, which are
especially useful for base 16.

This was the introduction to the representation/theory.  For more
details, see the doc of dec2fracbase. 







DG                                 http://gnufans.net/
--

--=-=-=
Content-Type: application/octet-stream
Content-Disposition: attachment; filename=fracbase2dec.m

function [result] = fracbase2dec (inp)

  ## Copyright (C) 2005 and onwards D. Goel
  ##
  ## This file is NOT (yet) part of Octave.
  ##
  ## This is free software; you can redistribute it and/or modify it
  ## under the terms of the GNU General Public License as published by
  ## the Free Software Foundation; either version 2, or (at your option)
  ## any later version.
  ##
  ## This software is distributed in the hope that it will be useful,
  ## but WITHOUT ANY WARRANTY; without even the implied warranty of
  ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  ## General Public License for more details.
  ##
  ## You should have received a copy of the GNU General Public License
  ## along with Octave; see the file COPYING.  If not, write to the Free
  ## Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  ## 02111-1307, USA.
  ##
  ## -*- texinfo -*-  at deftypefn {Function File} {} name_of_function
  ## ( at var{arg1}, @var{arg2}) Does foo bar. If @var{arg1} is not
  ## specified it defaults to 0, 8 or 16 depending on Keywords:  at end
  ## deftypefn  at seealso{function1, function2, function3}
  ##
  ## Author: D. Goel <deego at gnufans dot org> Created: 01 May 2005
  ## Adapted-By:
  ##
  ##
  ##
  ##  function [result] = fracbase2dec (inp)
  ##
  ##  See the function dec2fracbase for documentation.
  ##
  ## If the base is not supplied as part of inp, we use the value of the
  ## global variable fracbase

  global fracbase=2;


  global fracbase=2;

  if isnumeric(inp);
    result=inp;
  elseif iscell(inp);
    len=length(inp);
    repr=inp{1};
    if len>=2;
      base=inp{2};
    else 
      base=fracbase;
    endif

    if len>=3;
      dec=inp{3};
    else
      dec=length(repr);
    endif

    if len>=4;
      sign=inp{4};
    else 
      sign=1;
    endif


    res=0;
    for ii=1:length(repr);
      res=res+repr(ii)*base^(dec-ii);
    endfor
    result=sign*res;
  else
    error("input Not cell nor number?")
  endif
endfunction




--=-=-=
Content-Type: application/octet-stream
Content-Disposition: attachment; filename=dec2fracbase.m

function [result error] = dec2fracbase (num, base, numit) 


  ## Copyright (C) 2005 and onwards D. Goel
  ##
  ## This file is NOT (yet) part of Octave.
  ##
  ## This is free software; you can redistribute it and/or modify it
  ## under the terms of the GNU General Public License as published by
  ## the Free Software Foundation; either version 2, or (at your option)
  ## any later version.
  ##
  ## This software is distributed in the hope that it will be useful,
  ## but WITHOUT ANY WARRANTY; without even the implied warranty of
  ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  ## General Public License for more details.
  ##
  ## You should have received a copy of the GNU General Public License
  ## along with Octave; see the file COPYING.  If not, write to the Free
  ## Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  ## 02111-1307, USA.
  ##
  ## -*- texinfo -*-  at deftypefn {Function File} {} name_of_function
  ## ( at var{arg1}, @var{arg2}) Does foo bar. If @var{arg1} is not
  ## specified it defaults to 0, 8 or 16 depending on Keywords:  at end
  ## deftypefn  at seealso{function1, function2, function3}
  ##
  ## Author: D. Goel <deego at gnufans dot org> Created: 01 May 2005
  ## Adapted-By:
  ##
  ##
  ##
  ##  function [result error] = dectobasemy (num, base, numit)
  ##
  ##
  ##
  ##
  ## Convert any decimal NUM to any BASE.  The BASE may be fractional or
  ## even NEGATIVE, yet should still be REAL.   NUMIT is the max num of
  ## iterations before we cope out the remaining part as the error. The
  ## error is expressed as a decimal.  The RESULT is expressed as a
  ## cell. The fourth part of this cell is the num 1 or -1, expressing
  ## the overall sign.  The third part of this cell is a vector. The
  ## third part of this cell is the location of the decimal WITH
  ## reference from the LEFT.
  ##
  ##
  ## For example, if base were 2, then 5 in base 2 would be expressed as
  ## {1, [1 0 1], 3}.  1 indicates the overall sign.  4 indicates that
  ## the decimal lies AFTER the 3rd digit, (which, of course, there
  ## isn't any).  When this number if zero, this means that the decimal
  ## lies after the 0th digit, which means before the first digit. This
  ## number, thus, can also be negative.
  ##
  ##
  ##If base were 16, then 15 would be expressed as {1,[15],1}. We just
  ##used 15, we do not use any special notations like A-F, since we want
  ##to keep the method very general.
  ##
  ##
  ##
  ## Theory: In integer bases, any num has a unique num representation.
  ## This representation is unique upto just one "nonuniqueness" --
  ## .999999999999... is 1, an the latter is always the preferred form.
  ##
  ## In fractional bases, say 2.3, the integers used are 0,1,2.  This
  ## number (3) is more than 2.3, so there CAN be multiple
  ## representations, but we define a principal representation: If there
  ## are 2 equivalent but different representations {a_n} and {b_n},
  ## then a_n should have the largest possible numbers to the left,
  ## viz., If k is the largest k such that a_k> b_k, and m is the
  ## largest m such that b_m>a_m, if any, then k>m.  A k should always
  ## exist. Or, in other words, when constructing the representation, we
  ## tkase out the largest chunk we can at each decimal stage before
  ## going to the decimal on the right.
  ##
  ## The method we learnt for converting any base 10 to base N in school
  ## starts out from the right -- we compute the least significant part
  ## first. That works in practice because of a special property of
  ## integer bases.  But in principal, for a general base, one needs
  ## start out from the left.
  ##
  ## For fractional bases of the form N+f, when 0<f<=1, the integers
  ## used in the representation are 0..N.
  ##
  ## ERROR is the remaining remainder, if any.
  ##
  ## We also return numused and  baseused as the 3rd and the 4th
  ## arguments. They refer to the actual number and base used in the
  ## calculation, respectively.
  ##
  ## Representation:  A decimal number in any base is represented by a
  ## cell of several entries. The entry is a sign, this is 1 or
  ## -1. The second entry is a row vector representing the actual digits
  ## in the base b representation.
  ##
  ## For example, the pricipal representation of 2.3 in its own base
  ## 2.3, is (10.00000000), but an equivalent representation is
  ## (2.0110112010010..)
  ##
  ##  BTW, to convert an arbitrary representation to its principal form,
  ##  run fracbase2dec on it, followed by dec2fracbase, which is what
  ##  `fracbaseprincipal' does.  Also, in the principal repr. form, the
  ##  base is always positive. 
  ##
  ##
  ##
  ## The second entry is the base b.
  ##
  ## The fifth entry, which is optional and is never to be taken as
  ## authoritative, is the decimal equivalent.
  ##
  ## Thus, you can construct representations by hand.
  ##
  ## The aim is that all functions that accept a frac2base form should
  ## also accept regular numbers since those are just their base10
  ## forms. One example of such a function is fracbase2dec, feed it a
  ## number and you get it right back.
  ## 
  ## Once again, here is the final summary of the order of the entries
  ## we ended up choosing:
  ## First entry is the representation, for example, [1 0 0] for 4 in
  ## base 2.
  ## Second entry is the base, for example, 2.  If missing, we use the
  ## value of the global fracbase.
  ##
  ## Third, entry, if present, means the location of the decimal from
  ## the left in the representation.  If not present, it is assumed to
  ## be on the far right, and hence ==3, for the above example. 
  ## The fourth entry, if present, is the overall sign. If absent, it is
  ## 1.
  ## The fifth entry is entirely optional and should affect no math in
  ## any function.  It
  ## is the decimal equivalent of the numbner. 
  ##
  ## if the base is <1, the whole thing becomes meaningless.  In a
  ## principal representation, the base can never be <1.  If YOU supply
  ## us a base <1, we can only assume that you want the input number
  ## represented in decreasing powers of the base, which is equivalent
  ## to expressing the inverse of the number in the decreasing powers of
  ## the inverse of the base.  That is what we shall do in that case.
  ##
  ## If the base is not supplied, we use the value of the global
  ## variable fracbase
  ##
  ## The answer is always returned in the principal form.

  global fracbase=2;

  if nargin<2;
    base=fracbase;
  endif


  if nargin<3;
    numit="";
  endif

  if not(isnumeric(numit));
    numit=100;
  endif
  
  if length(numit(:))>1;
    numit=numit(1);
  endif


  if length(num(:))>1;
    num=num(1);
  endif

  if length(base(:))>1;
    base=base(1);
  endif

  if abs(base)<=1;
    error("Base must be greater than 1")
  endif

  if imag(base)!=0
    error("Base should not have an imaginary part.")
  endif

  sign=1;

  if num<0; 
    sign=-sign;
    num=num*(-1);
  endif

  if base<0; 
    sign=-sign;
    base=-base;
  endif

  blog=log(base);
  ## First find kmax and fix it.  This will help us with the decimals. 
  kmax=floor(log(num)/blog);
  
  ## This may have had rounding errors when numlog in reality was an
  ## exact multiple of blog, but taking logs produced rounding errors,
  ## so ALWAYS  check one higher.
  if (base^(kmax+1))<=num;
    disp("Warning: initial False Log condition met:")
    disp(base);
    disp(kmax);
    disp("");
    kmax=kmax+1;
  endif
  dec=kmax+1;;
      
  ## Now that we have the decimal condition fixed, we can proceed with
  ## the rest of the algorithm:
  
  
  ## number of iterations.
  it=0;
  repr=[];  ## representation.
  remainder=num;
  k=kmax;

  while ((remainder>0)&&(it<numit))
    basek=base^k;
    newpos=floor(remainder/basek);
    remainder=remainder-basek*newpos;
    repr=[repr newpos];
    k--;
  endwhile

  if remainder<0;
    disp("Warning: Negative remaider:")
    disp(remainder)
    disp("");
  endif
    
  ## Now if not enough zeros on the right, add some, well, add only upto
  ## numit zeros... viz. not too many zeros, but enough for usual
  ## day-to-day representations, like 4--> 100 in base 2.
  dec1=dec;
  if (length(repr))<dec1;
    if (dec-length(repr))<numit;
      repr=[repr zeros(1,dec-length(repr))];
    endif
  endif
  
  result={repr,base,dec,sign,num};

  
endfunction 

--=-=-=
Content-Type: application/octet-stream
Content-Disposition: attachment; filename=fracbaseprincipal.m

function [result] = fracbaseprincipal (num)
  ## Copyright (C) 2005 and onwards D. Goel
  ##
  ## This file is NOT (yet) part of Octave.
  ##
  ## This is free software; you can redistribute it and/or modify it
  ## under the terms of the GNU General Public License as published by
  ## the Free Software Foundation; either version 2, or (at your option)
  ## any later version.
  ##
  ## This software is distributed in the hope that it will be useful,
  ## but WITHOUT ANY WARRANTY; without even the implied warranty of
  ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  ## General Public License for more details.
  ##
  ## You should have received a copy of the GNU General Public License
  ## along with Octave; see the file COPYING.  If not, write to the Free
  ## Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  ## 02111-1307, USA.
  ##
  ## -*- texinfo -*-  at deftypefn {Function File} {} name_of_function
  ## ( at var{arg1}, @var{arg2}) Does foo bar. If @var{arg1} is not
  ## specified it defaults to 0, 8 or 16 depending on Keywords:  at end
  ## deftypefn  at seealso{function1, function2, function3}
  ##
  ## Author: D. Goel <deego at gnufans dot org> Created: 01 May 2005
  ## Adapted-By:
  ##
  ##
  ##
  ##  function [result] = fracbaseprincipal (num)
  ##
  ## See doc of dec2fracbase. If the base is not supplied as part of
  ## num, we use the value of the global variable fracbase

  global fracbase=2;

  global fracbase=2;

  if isnumeric(num);
    res=num;
  elseif iscell(num)
    base=abs(num{2});
    res=dec2fracbase(fracbase2dec(num),base);
  endif
    
  result=res;
  
endfunction 

--=-=-=--