I currently have a big-num implementation based on rational numbers (with repeating digits) that stores the following (in binary):
Some examples (Expressed as <int>.<frac>(<repeating-frac>)):
2.5 (base 10): 10.1 (base 2)2.1 (base 10): 10.0(0011) (base 2)2.5(3) (base 10): 10.(1000) (base 2)I can convert from base 10 (or any base) to base 2 (which is how the big-num is actually stored on disk) with the following procedure:
For the integer part, simply keep dividing it (string division) by 2 until it's 0.
In this case, the remainders after each division encode the number.
For the fractional part, keep multiplying (string multiplication) by 2 until it's either 0, or in a loop.
In either case, the "remainder" / overflow of the multiplication encodes the fractional parts.
The problem arises when converting from base 2 to base 10 (or any other base). I have the following procedure currently:
Get the integer part fine by reversing the process and multiplying by 2 and adding the remainders of all digits.
Get the pure fractional (non-repeating) part by adding the "remainder" / overflow and dividing by 2
However, for the repeating fractional part, I'm at a loss on how to start. When decoding the integer or pure fractional, I start with the value at 0, since the encoding procedures end with the value at 0. However, for the repeating fractional part, the end value is not 0, so I can't start at 0 and expect to get the same value out.
I don't want to store this stop number because I know that, for e.g., 0.0(0011) (base 2) maps uniquely and unambiguously to 0.1 (base 10). The same is true of any digit combination. They should all map to a unique decimal (or any other base) equivalent.
Given this, I don't want to waste space storing the end value, since there must be a way to get back to the original value.
So how can I go from a base 2 encoding (with repeating digits) to a base N encoding (possibly with repeating digits)
If a generic base isn't possible, I'm only really interested in bases 8, 10 and 16, of which 8 and 16 are trivial, as they are powers of 2, so 10 is the only other base I really care about converting to from base 2.
As it turns out, the answer was relatively simple: We simply need to perform the same algorithm as when converting from base N to base 2, but instead of dividing / multiplying a string of base N by 2, we instead divide / multiply a string of base 2 by N.
Here is the same algorithm as in the question, now generic for base N:
For the integer part, simply keep dividing it by N until it's 0.
In this case, the remainders after each division encode the number in base N.
For the fractional part, keep multiplying by N until it's either 0, or in a loop.
In either case, the "remainder" / overflow of the multiplication encodes the fractional parts in base N.
Now this does complicate the actual implementation, as string division / multiplication by 2 is significantly easier than binary division / multiplication by N, so maybe it's possible to implement it using only string operations, as the original decoding algorithm in the question did for integers and non-repeating fractionals, but that would likely require a lot more work than using binary operations.