|
In this article I described a simple algorithm which can be used to convert an arbitrary long number with base X to a number with base Y. The implementation assumed that all digits have an equal base, which suffices in most cases. In this article we will make small modifications in order to allow for number conversions where both the source and the destination number of the conversion may have different bases for each digit. I decided to implement this algorithm and write about it, because I needed it for my own experiments -- I wanted to play around with an idea I have had. For those of you who are interested, I'll write about my experiments in a subsequent article. :)
Although cases are rare in which the digits of a number have different bases they occur from time to time. Oh yes, "time" -- this is a good example for such a use case. Suppose you have an integer representing a timespan in milliseconds and you want to calculate the number of milliseconds, seconds, minutes, hours, days, and weeks of that timespan. Of course, you can easily do the necessary calculations "by hand", but it also works more or less out-of-the-box with our simple algorithm. All we have to do is to modify it such that for each digit in question an arbitrary number base can be used.
Before we start to extend the algorithm let's have a quick look at the original code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| def incNumberByValue(digits, base, value):
# The initial overflow is the 'value' to add to the number.
overflow = value
# Traverse list of digits in reverse order.
for i in reversed(xrange(len(digits))):
# If there is no overflow we can stop overflow
# propagation to next higher digit(s).
if not overflow:
return
sum = digits[i] + overflow
digits[i] = sum % base
overflow = sum / base
def multNumberByValue(digits, base, value):
overflow = 0
# Traverse list of digits in reverse order.
for i in reversed(xrange(len(digits))):
tmp = (digits[i] * value) + overflow
digits[i] = tmp % base
overflow = tmp / base
def convertNumber(srcDigits, srcBase, destDigits, destBase):
for srcDigit in srcDigits:
multNumberByValue(destDigits, destBase, srcBase)
incNumberByValue(destDigits, destBase, srcDigit) |
As you can see all three functions have parameters for passing in the number base. The number base is used for each digit calculation within the functions 'incNumberByValue' and 'multNumberByValue' and we need a way to parameterize the base value for each digit. This can easily be achieved by passing in a function which returns the digit base given a digit index. So we don't pass the number base directly anymore, but we pass in a function pointer. (This is a nice example for the Strategy design pattern, by the way.)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| def incNumberByValue(digits, baseFn, value):
# The initial overflow is the 'value' to add to the number.
overflow = value
# Traverse list of digits in reverse order.
for i in reversed(xrange(len(digits))):
# If there is no overflow we can stop overflow
# propagation to next higher digit(s).
if not overflow:
return
tmp = digits[i] + overflow
digitBase = baseFn(i, len(digits))
digits[i] = tmp % digitBase
overflow = tmp / digitBase
def multNumberByValue(digits, baseFn, value):
overflow = 0
# Traverse list of digits in reverse order.
for i in reversed(xrange(len(digits))):
tmp = (digits[i] * value) + overflow
digitBase = baseFn(i, len(digits))
digits[i] = tmp % digitBase
overflow = tmp / digitBase
def convertNumber(srcDigits, srcBaseFn, destDigits, destBaseFn):
for i in xrange(len(srcDigits)):
multNumberByValue(destDigits, destBaseFn, srcBaseFn(i, len(srcDigits)))
incNumberByValue(destDigits, destBaseFn, srcDigits[i]) |
That's pretty much it. You now have a generic solution which is flexible enough to handle both standard cases with equal digit bases as well as rare cases with distinct digit bases.
Let's use this code to do the timespan calculation mentioned at the beginning of this article. We need two digit base strategies. One for numbers with equal digit bases and one for a number with predefined digit bases. The former is necessary because we want to provide the number of milliseconds of a timespan as a decimal number, and the latter because we need different digit bases for a timespan expressed in milliseconds, seconds, minutes, hours, and so on:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| def getConstantDigitBase10(digitIndex, digitsLen):
return 10
def getTimeDigitBase(digitIndex, digitsLen):
if digitIndex == digitsLen - 1:
# milliseconds
return 1000;
if digitIndex == digitsLen - 2:
# seconds
return 60
if digitIndex == digitsLen - 3:
# minutes
return 60
if digitIndex == digitsLen - 4:
# hours
return 24
if digitIndex == digitsLen - 5:
# days
return 7
# weeks
return 10000000000 |
We use a big number base for the weeks digit, because we don't want to get more digits. We could also introduce a year digit, but then we would have to deal with leap years and leap seconds… Having said that let's concentrate on our calculation. If we wanted to know how much milliseconds, seconds, minutes etc. the timespan 9876543210ms represents we just needed to do this:
1
2
3
4
5
| >>> srcDigits = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> destDigits = [0, 0, 0, 0, 0, 0]
>>> convertNumber(srcDigits, getConstantDigitBase10, destDigits, getTimeDigitBase)
>>> print(destDigits)
[16, 2, 7, 29, 3, 210] |
This result tells us that the timespan 9876543210ms means 16 weeks, 2 days, 7 hours, 29 minutes, 3 seconds, 210 milliseconds. And, of course, this works the other way round, too:
1
2
3
4
5
| >>> srcDigits = [16, 2, 7, 29, 3, 210]
>>> destDigits = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
>>> convertNumber(srcDigits, getTimeDigitBase, destDigits, getConstantDigitBase10)
>>> print(destDigits)
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0] |
While the previously shown code works well, there is also an inconvenience which you may already have noticed. Using the previously shown approach we need to write a strategy function for each number/digit base we want to support. Python and some other programming languages allow for applying the currying technique. We can use this technique to create a factory function which in turn returns a function pointer to a function configured for a specific use case. Let's have a look at the following factory function:
1
2
3
4
5
6
7
8
9
10
11
12
13
| def createDigitBaseFromListFn(digitBases):
numDigitBases = len(digitBases)
def getDigitBaseFromList(digitIndex, digitsLen):
baseIndex = digitsLen - digitIndex - 1
return digitBases[baseIndex] if baseIndex < numDigitBases else 10000000000
# Return the "configured" function.
return getDigitBaseFromList
def createConstantDigitBaseFn(base):
def getConstantDigitBase(digitIndex, digitsLen):
return base
# Return the "configured" function.
return getConstantDigitBase |
With the help of these generic factory functions we can now simply do our conversions without the necessity to write custom digit base strategies:
1
2
3
4
5
| >>> srcDigits = [9876543210]
>>> destDigits = [0, 0, 0, 0, 0, 0]
>>> convertNumber(srcDigits, createConstantDigitBaseFn(10000000000), destDigits, createDigitBaseFromListFn([1000, 60, 60, 24, 7]))
>>> print(destDigits)
[16, 2, 7, 29, 3, 210] |
Note that this code avoids to provide the number 9876543210 as a comma separated list of base 10 digits by converting from a number whose digit base is 10000000000 for every digit which, in fact, means we get a number with only one digit having value 9876543210.
|
|
