# baseconv.frink

``` // 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.) } ```