I'm interested in an efficient Python-implementation of the so-called 'interleaving function' f which takes two numbers a, b in (0,1) and interleaves their decimal digits, i.e.
f(a,b) := 0.a1 b1 a2 b2 a3 b3 ... where a = 0.a1 a2 a3... and b = 0.b1 b2 b3... are the decimal representations of a,b.
Mathematically speaking, the function f is a one-to-one map from (0,1)x(0.1) to (0,1).
Can you suggest how to efficiently implement this map in Python so as to preserve it being one-to-one?
For an efficient implementation one needs to make sure to achieve two things: minimal asymptotic complexity in terms of big O notation and efficient computational operators, avoiding repeated or otherwise unnecessary calculation.
Given the problem, it is unlikely that it could be solved with an algorithm that is less than linear on the length of the input numbers. In terms of operators, given that we work with decimal formatting, it would be difficult that we could benefit from some bit-wise (binary) computations. Thus we're probably best with general mathematical operations.
Using float
A first naive implementation would attempt executing the function on floating point numbers:
However, a simple test shows a problem - inherently limited precision of floating point arithmetic which distorts already at the 16-17th digit after the floating point:
Using Decimal
A common way to overcome the precision problem is to use decimal.Decimal, the python implementation of fixed-point decimal arithmetic:
This seems to work better for b, but unfortunately, it also leads to imprecision at about the same digit in the result. This imprecision is also signalled by the Inexact flag in the context after the calculation:
Using str
Another approach which should not impose limits due to precision (and which you have brought up yourself) is to do syntactical processing with strings:
remove traling 0 if present
The algorithm doesn't do validation, so it remains to you to decide what you might want to add. Yet, testing this gives the desired precision:
...but what can one do with the resulting string? Maybe convert it into a Decimal again? Depends how you want to use the outcome.