Download or view 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.)
}
Download or view 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 19971 days, 5 hours, 9 minutes ago.