Set-Based Solution
My first set-based solution has four main steps. First, it calculates the number of digits that the target base value will use. Next, for each target digit, it calculates the digit value (in decimal base).Third, it converts each target digit to the target base digit. And finally, it performs string concatenation to concatenate all digits to one target string.
Step 1 would be easy if T-SQL provided the necessary log functions. Mathematically, given the decimal value n, the number of digits required to express n in base b is FLOOR(LOGb(n)) + 1. T-SQL doesn't provide a log function with any base except natural log and log 10. To calculate the log in any given base (b) of any given value (n), you can use the following equation: LOGb(n) = LOGx(n)/LOG x(b), where x can be any value. Therefore, you can express LOGb(n) in T-SQL as LOG10(n)/LOG10(b). Although the mathematical expression is correct, the T-SQL expression might return incorrect values because the LOG10() function returns a float value, which is imprecise.
My tests produced incorrect results, especially when working with large values, so I had to find a different way to calculate the target number of digits. For this purpose, I created an auxiliary table called BasePowers and populated it with all supported powers of all bases up to base 36. Running the code in Listing 4 creates the table and populates it with data. You should expect overflow errors when running this code. The code in Listing 4 loops from base 2 through base 36, then in an inner loop raises each base by the powers 1, 2, 3, and so on until the script generates an overflow error. This error occurs once for each base, so you should expect 35 such errors. Such an overflow means that the result is outside the range of supported bigint values and therefore of no interest to us, since our solution supports conversions of values that fit in a bigint data type.
As an example of the information you can get from the BasePowers table, try running the following query:
SELECT pos, val FROM BasePowers
WHERE base = 16;
Table 4 shows the results of this query, which returns all powers of 16 that are less than or equal to the largest supported value in a big integer. Given a decimal value @n and a target base @b, the following code returns a row for each target base digit from the BasePowers table:
SELECT pos, val FROM BasePowers
WHERE base = @b AND val <= @n;
For example, for @n = 31 and @b = 16, this query returns two rows from BasePowers, one for each target base digit (pos = 1, val = 1) and (pos = 2, val = 16).
As a reminder, step 2 calculates the decimal value of each target digit in the new base. In other words, it breaks the whole decimal value into pieces corresponding to the individual target digits. For example, the solution code will convert the input decimal value 31 after applying all four steps to the base 16 value 1F. So, step 2 should first produce the decimal equivalent of each target digit—that is, first digit = 15 (decimal value of F hexadecimal) and second digit = 1 (decimal value of 1 hex). To calculate the decimal value representing a digit in position p, you use the following formula: dec_val = @n ÷ val % @b, where val (taken from the BasePowers table) is the power of @b for a digit in position pos. Note that I'm using integer division and modulo here. As an example, the decimal value representing the target base digit in position 1 is 15 (31 ÷ 1 % 16). The decimal value representing the target base digit in position 2 is 1 (31 ÷ 16 % 16). Here's the query that produces the decimal values representing all of the target base value's digits for an input decimal value @n and target base @b:
DECLARE @n AS bigint, @b AS int;
SET @n = 31; SET @b = 16;
SELECT pos, @n / val % @b FROM BasePowers
WHERE base = @b AND val <= @n;
Step 3 is supposed to convert the decimal representation of each target digit to the correct target base digit. You use the same technique I demonstrated in the iterative solution using the SUBSTRING() function and a string of 36 digits. Listing 5 shows how you merge the conversion technique and the preceding query to return the desired results for step 3—namely, the digit F in the postion and the digit 1 in the second. Now apply the same calculations to the values in T1 to get the breakdown of digits—for example, in base 36, as Listing 6 shows.
Now that you have all target digits and their positions, you just apply the fourth and final step, which is to concatenate the digits into one result string. You can apply string concatenation by using a pivoting technique. For information about performing string concatenation using pivoting, see my T-SQL 2005 Web columns from June 2004, "Pivot (or Unpivot) Your Data" (InstantDoc ID 42901), and July 2004, "Dynamic Pivoting" (InstantDoc ID 43140). Because you might need 63 digits to express the largest supported bigint value in the smallest base (2), you'll need 63 MAX(CASE...) expressions in the query's SELECT list. Listing 7 shows the (abbreviated) final solution. In Listing 7, I used base 36 as an example of generating the output that Table 1 shows.
Set-Based Solution with Optimized String Concatenation
Typically, a set-based solution is faster than the iterative alternative. In this case, the set-based solution is slower and significantly longer and more complicated than the iterative solution, mainly because of the string-concatenation technique that contains 63 MAX(CASE...) expressions. To find a fast solution that uses at least partially set-based techniques, I tried to optimize the string-concatenation part of the solution.
My third solution starts with the same query I used in the previous solution, which generates a result set that contains all target digits and their positions in separate rows before applying the pivot technique. You already know how to calculate the target number of digits. Now generate a string that contains as many zeros as the target number of digits:
DECLARE @r AS varchar(63);
SET @r = REPLICATE('0',
(SELECT MAX(pos) FROM
BasePowers
WHERE base = @b AND
val <= @n));
Next, use the STUFF() function as follows to "plant" the different digits in @r while scanning the rows that the previous solution's query returned:
SELECT @r = STUFF(@r, LEN(@r) -
pos + 1, 1, digit)
FROM (query_returning_digit
_breakdown) AS D
WHERE digit <> '0';
SELECT @r;
The use of STUFF() here is a bit tricky to follow. Try to visualize the breakdown of the base 36 digits for the input decimal value 3792919053113386084, as Table 5 shows. The result value has 12 target digits, so the code initializes @r with 12 zeros.
Now imagine the main piece of code containing the STUFF() function scanning the 12 rows that hold the digit position (pos column), and value (digit column). Regardless of the order in which SQL Server accesses these 12 rows, the STUFF() function replaces the zero in the correct position from the right (LEN(@r) – pos + 1) with the actual digit, and by the end of the scan, your code plants all digits.
Listing 8 shows the full implementation of this solution, creating the fn_dectobase() function. You use the function the same way you did with the iterative implementation I described earlier.
Set-Based Versus Iterative Conversions
My first idea when looking for solutions that convert a decimal value to a desired base was the iterative implementation I demonstrated. But because set-based solutions prove faster than iterative ones in most cases, I then tried to create a set-based solution. However, the first set-based solution I tried was slower, longer, and more complex, mainly because of the pivoting string-concatenation technique. In an effort to optimize the string concatenation, I used the STUFF() function. But even after I optimized the string concatenation, the iterative solution ran twice as fast as the optimized set-based solution.
Base conversions involve data formatting more than data manipulation, and set-based operations weren't designed to format data efficiently. This task needs an iterative approach, but T-SQL isn't strong in iterative operations. If you're not happy with the fastest (iterative) option I showed, you might want to perform the base conversions in the client application by using a programming language (e.g., Visual Basic—VB, C++, C#) designed for such activities.
All the solutions require a lot of complex logical manipulation. Whether or not you use the T-SQL implementations for base conversions, you might find that the logical manipulation and techniques I demonstrated here will help you with other tasks.