Version 13 of base conversion

Updated 2011-12-02 04:55:19 by SEH

See Also: Converting an integer to a base 2 string, Binary representation of numbers, Based numbers


rvb A general base-conversion procedure for arbitrary length string representations of numbers with integer and/or fraction.

 #=============================================================================
 # PROC    : baseconvert
 # PURPOSE : convert number in one base to another base
 # AUTHOR  : Richard Booth
 # DATE    : Fri Jul 14 10:40:50 EDT 2006
 # ---------------------------------------------------------------------------
 # ARGUMENTS :
 #   % base_from
 #       original base (expressed in base 10)
 #   % base_to
 #       base to convert number to (expressed in base 10)
 #   % number
 #       number expressed in base_from (must have form int.fra, int, or .fra)
 # RESULTS :
 #   * returns number expressed in base_to
 # EXAMPLE-CALL :
 #{
 #  set num16 [baseconvert 10 16 3.1415926535]
 #}
 #=============================================================================
 proc baseconvert {base_from base_to number} {
     set number [string tolower $number]
     if {![regexp {([0-9a-z]*)\.?([0-9a-z]*)} $number match sint sfra]} {
         puts "baseconvert error: number \"$number\" is not in correct format"
         return ""
     }
     set map 0123456789abcdefghijklmnopqrstuvwxyz
     set i -1
     foreach c [split $map ""] {
         incr i
         set D2I($c) $i
         set I2D($i) $c
     }
     set lint [string length $sint]
     set lfra [string length $sfra]
     set converted_number 0
     if {$lint > 0} {
         set B {}
         foreach c [split $sint ""] {
             lappend B $D2I($c)
         }
         set aint ""
         while {1} {
             set s 0
             set r 0
             set C {}
             foreach b $B {
                 set v [expr {$b + $r*$base_from}]
                 set b [expr {$v/$base_to}]
                 set r [expr {$v%$base_to}]
                 incr s $b
                 lappend C $b
             }
             set B $C
             set aint "$I2D($r)$aint"
             if {$s == 0} {break}
         }
         set converted_number $aint
     }
     if {$lfra > 0} {
         set s [expr {int(1.0*$lfra*log($base_from)/log($base_to))}]
         set B {}
         foreach c [split $sfra ""] {
             set B [linsert $B 0 $D2I($c)]
         }
         set afra ""
         for {set j 0} {$j < $s} {incr j} {
             set r 0
             set C {}
             foreach b $B {
                 set v [expr {$base_to*$b + $r}]
                 set r [expr {$v/$base_from}]
                 set b [expr {$v%$base_from}]
                 lappend C $b
             }
             set B $C
             set afra "$I2D($r)$afra"
         }
         append converted_number .$afra
     }
     return $converted_number
 }

a small test script for baseconvert:

 set fmt "%-10s (base %-2d)  =>  %-10s (base %-2d)"
 foreach number {12ff.abb 122. 125 .222 0.222 0.22 0.2 0.1} {
    puts [format $fmt $number 16 [baseconvert 16 10 $number] 10]
    puts [format $fmt $number 16 [baseconvert 16 8  $number] 8]
    puts [format $fmt $number 16 [baseconvert 16 2  $number] 2]
 }

glennj Here's a simpler implementation, but integer values only

    namespace eval baseconvert {
        variable chars "0123456789abcdefghijklmnopqrstuvwxyz"
        namespace export baseconvert
    }
    proc baseconvert::dec2base {n b} {
        # algorithm found at http://www.rosettacode.org/wiki/Number_base_conversion#Python
        variable chars
        expr {$n == 0 ? 0
              : "[string trimleft [dec2base [expr {$n/$b}] $b] 0][string index $chars [expr {$n%$b}]]"
        }
    }
    proc baseconvert::base2dec {n b} {
        variable chars
        set sum 0
        foreach char [split $n ""] {
            set sum [expr {($sum * $b) + [string first $char $chars]}]
        }
        return $sum
    }
    proc baseconvert::baseconvert {num basefrom baseto} {
        dec2base [base2dec $num $basefrom] $baseto
    }

rvb A related problem is sampling a multi-dimensional grid.

Lars H: Hmm... That's a rather antiquated way to do it, though. If you really want all points in the grid, then it is easier to construct it as the Cartesian product of a list of lists.

rvb Friendly jabs aside, my point was that counting in any particular base is like climbing a multidimensional grid (or even the geometric analogue, to a lightheaded antiquarian.) However, the Cartesian product of a list of lists approach, which I tried with the recursive procedure, is very elegant.

 #=============================================================================
 # PROC    : gridsample
 # PURPOSE : uniformly sample a normalized hypercube
 # AUTHOR  : Richard Booth
 # DATE    : Tue Jul 18 11:19:10 EDT 2006
 # ---------------------------------------------------------------------------
 # ARGUMENTS :
 #   % ndiv
 #       number of divisions of the normalized hypercube
 #       (each independent variable range is [-1, 1])
 #   % nind
 #       number of independent variables
 # RESULTS :
 #   * returns list of (normalized) samples
 # EXAMPLE-CALL :
 #{
 #  set samples [gridsample 5 2]
 #}
 #=============================================================================
 proc gridsample {ndiv nind} {
     if {$nind < 1 || $ndiv < 1} {
         return {}
     }
     set samples {}
     set base [expr $ndiv+1]
     set npts [expr pow($base, $nind)]
     for {set i 0} {$i < $npts} {incr i} {
         set sample {}
         set v $i
         for {set j 0} {$j < $nind} {incr j} {
             set w [expr int($v/$base)]
             set r [expr $v - $base*$w]
             set v $w
             lappend sample [expr {2.0*$r/$ndiv-1}]
         }
         lappend samples [join $sample]
     }
     return $samples
 }

a test script for gridsample:

 set nind 3
 set ndiv 6
 set samples [gridsample $ndiv $nind]

 puts "sample A B C"
 set iexpt -1
 foreach sample $samples {
     puts "[incr iexpt] [join $sample]"
 }

MJ - for conversion of large integers to hex the above proc is fairly slow (probably because it doesn't take advantage of Tcl 8.5 large integer support).

The proc below is much faster.

 # needs Tcl 8.5 for large integer support
 proc hex {num} {
   set res {}
   set hex_list {0 1 2 3 4 5 6 7 8 9 A B C D E F}
   while {$num / 16 != 0} {
      set rest [expr {$num%16}]
      set res [lindex $hex_list $rest]$res
      set num [expr {$num/16}]
   }
   set res [lindex $hex_list $num]$res
 }

 % time {baseconvert 10 16  25543398472347234723447294729472384329374982742984729472347247729472984264726487264284628462846274628462846284628462846284623874623874623784623486248726487642846} 100
 879291.28 microseconds per iteration
 % time {hex  25543398472347234723447294729472384329374982742984729472347247729472984264726487264284628462846274628462846284628462846284623874623874623784623486248726487642846} 100
 4507.07 microseconds per iteration

SEH 20111201 --

For hex conversion: format %llx $num

 % time {hex  25543398472347234723447294729472384329374982742984729472347247729472984264726487264284628462846274628462846284628462846284623874623874623784623486248726487642846} 100
 1867.9400000000001 microseconds per iteration

 % time {format %llx  25543398472347234723447294729472384329374982742984729472347247729472984264726487264284628462846274628462846284628462846284623874623874623784623486248726487642846} 100
 19.329999999999998 microseconds per iteration

rvb Replaced with faster (30x to 40x) list-based code. Previous baseconvert was very slow mainly because exprs were not {}'d (see Tcl Performance).

For what it's worth, here's a formula calculator for baseconvert formula calculators:

  ForCalc basecalc {
    basea   "base A"                 {}    10   b
    baseb   "base B"                 {}    16   a
    numa    "Number in base A"       {}    10.0 b
    numb    "Number in base B"       {}    a.0  a
  } {
    a {
      set basea [expr int($basea)]
      set baseb [expr int($baseb)]
      set numa  [baseconvert $baseb $basea $numb]
    }
    b {
      set basea [expr int($basea)]
      set baseb [expr int($baseb)]
      set numb  [baseconvert $basea $baseb $numa]
    }
  } -title "base conversion"