baseconv.frink

View or download baseconv.frink in plain text format


// Base conversion routine due to Schoenhage
// This is a recursive divide-and-conquer algorithm which divides the number
// into approximately equal-sized halves and concatenates the parts together.
// See Knuth, Vol. 2, Answers to Exercises (4.4) Question 14.

// This was the prototype for speeding up base conversions in Frink for
// platforms that have only ridiculously slow base conversion routines for
// large numbers (like any of Sun's JVMs.)  The internal implementation in
// Frink detects the JVM being used, and if it's Sun's, uses this algorithm
// instead of their native algorithm for large numbers.

// JVMs like Kaffe, which use the horribly fast GMP libraries, don't need this.
// This algorithm must be close to GMP's, because it doesn't slow down their
// base conversion *too* much.

// This sample omits two important points which are needed to make it work:
// 1.) The lower half of the number needs to be zero-padded when concatenating.
//
// 2.) You don't want to recurse all the way down into single digits.  The
//     final implementation should choose a lower size for numbers
//     (say, the size of an int or long) and use the system's built-in base
//     conversion algorithms on numbers smaller than that.

baseconv[U] :=
{
   b = bitLength[U]   // Find length of number in binary digits
   n = bitLength[b]   // Find length *of length* in binary digits
                      // (this is like taking approx log2, but fast)

   V = 10^2^(n-3)     // Find a value of V that splits this in approx. half.
                      // such that V is a power of 10^(2^k) and k is a
                      // well-chosen integer that splits the number in about
                      // half.
                      // 
                      // The method for finding k here was found to work
                      // empirically well and only requires knowing the bit
                      // lengths of a number (which is easy given that we
                      // store in base 2) 
   
   U0 = U mod V       // Divide the number into 2 approximately equal-sized
                      // halves (this is lower half)
   
   U1 = U div V       // Truncating divide, leaves upper half of number
   
   println[baseconv[U0] + baseconv[U1]]  // Concatenate halves recursively
                                         // (leading zero padding is needed in
                                         // practice.)
}


View or download baseconv.frink in plain text format


This is a program written in the programming language Frink.
For more information, view the Frink Documentation or see More Sample Frink Programs.

Alan Eliasen was born 17645 days, 8 hours, 28 minutes ago.