Generating floats from integers

Question

I wanted to make an algorithm that is a counter-example of Cantor's diagonalization argument. Given an integer, this Python code will produce a unique rational number. Fed the sequence of positive and negative integers as inputs, it will eventually produce all the floats.

Given infinitely long integers, I speculate that it produces infinitely long fractional numbers, forming a bijection with the real numbers. In my unpopular question on math.stackexchange, I learned that this is not a demonstration of the reals being countable (failing to be a counter-example to Cantor's argument) because the infinitely-long integers aren't integers. I won't pretend to fully understand that. Nevertheless, here's my code that produces a sequence of fractional numbers.

Try it: https://www.online-python.com/UGLMlWjy8v

import math

def r_impl(i):
    if i == 0:
        return 1
    x = (int(math.log(i, 2)) >> 1) + 1
    r = 1 << (x << 1) - 1
    if i < r:
        i <<= 1
        i -= r 
    i += 1
    return i / (1 << x)

def r(i):
    if i == 0:
        return 0
    if i > 0:
        return r_impl(i - 1)
    return -r_impl(-i - 1)
    
for i in range(-65, 65):
    print(f"int: {i} -> real: {r(i)}")

The size of the printed table can be configured in the last part of the code.

As the input integer increases, the algorithm walks increasingly large regions of the real number line with increasingly fine steps. The int math.log portion determines the pass that the input belongs to. The pass x has a region from (0 to 2ˣ], and 4ˣ steps. The steps count increases faster than the region so that the magnitude and precision can both grow. There are other ways to produce floats from integers, for instance setting the mantissa and exponent of a float directly, or this, but this is a method I hadn't seen before.

Finally, here are the notes from my design process using (mostly) binary notation.

s(d) = {1/(10^d) ... (10^(10d))/(10^d)} - s(d - 1)

1/1 | 1/10 ... 100/10 | 1/100 ... 10000/100 | 1/1000 ... 1000000/1000 | 1/10000 ... 100000000/10000 

d is the number of divisor zeros (number of digits - 1)

x   denominator     number of fractions   number of unique fractions    fractions
0   1               1 (1)                 1 (1)                         1/1
1   10              100 (4)               11 (3)                        1/10 (10/10) 11/10 100/10
2   100             10000 (16)            1100 (12)                     1/100 (10/100) 11/100 ((100/100)) 101/100 (110/100) 111/100 (1000/100) 1001/100 1010/100 1011/100 1100/100 1101/100 1110/100 1111/100 10000/100
3   1000            1000000 (64)          110000 (48)
4   10000           100000000 (256)       11000000 (192)
x   10^x            10^(10x)              u(0) = 1, u(x) = 100^x - 100^(x - 1)

Answer 1

Some of your variable names could use work. r being a function in one place and a variable in a different function elsewhere is confusing. i isn't too bad because it's a counter in a range, although r_impl changing i makes it confusing (i being different between r and r_impl is also a bit misleading, but not as bad). I'm going to change that i to numerator and rename the others:

• x -> input_pass
• r (the function) -> rational_of
• r_impl -> positive_rational_of
• r (the variable) -> threshold (?)

You could use a bit of documentation. Normally, the hard part is actually writing it down. You already did that, so you might as well put it in your function. I'll also add in type hinting.

math.log(i,2) could be math.log2(i). Even better, int(math.log(i, 2)) == i.bit_length() - 1 (see int.bit_length()). This also lets you no longer import math. (Before I saw int.bit_length a few minutes ago, I was going to suggest consider finding the bit_length on your own.)

I prefer //2 and *2 to >>1 and <<1, but that may be a personal preference, so I'll leave that alone.

The if i > 0: ... could be simplified down to return math.copysign(positive_rational_of(abs(i) - 1),i). That's one line of code instead of three, although introducing math.copysign and abs is not necessarily a simplification. I guess I'm back to importing math, so I'll throw in math.ldexp(x,-i)==x/(1<<i) (see math.ldexp).

The if i==0: return 1 comes from when the original i is ±1. This means that if we change the if i==0: return 0 to account for i==±1, then we don't need the return 1 case.

When generating a countable sequence, it's nice to be able to start the sequence and have it go however long you need, which is precisely the job description of a generator. This would also let us create a sequence that would never stop, should some algorithm want that.

As Richard Neumann pointed out, there's only a finite set of floats available (Python automatically handles arbitrarily big integers, so you don't have to worry about that). It would be good to figure out at what point you'll run into that limit, and document it. On the other hand, I doubt you'd be interested in letting it run that long.

Notes about the math: I would interpret "infinitely long integer" to mean an infinitely long sequences of digits. There are indeed an uncountable number of these, and they can be put into a one to one correspondence with the real numbers. Your algorithm, however, is only taking regular integers and giving regular rational numbers. My guess is that you would say that after an infinite amount of time, we would get infinitely long integers. But we would need to say that integer such-and-such would happen at time such-and-such, and we can't have an indeterminate "infinitely far in the future". In fact, your algorithm is giving dyadic rationals (those whose denominator is a power of two). To put that another way: at no point will your algorithm give the rational number 1/3, let alone an irrational number. You can actually apply Cantor's diagonal argument to your output: start writing down the binary form of the numbers that you get that are between 0 and 1, and Cantor's argument will show how to find a number that is not in your list.

import itertools
import math
from typing import Iterator

def positive_rational_of(i:int) -> float:
    '''
    1<<(2*input_pass) rationals from (0,1<<input_pass]
    With denominator 1<<input_pass, we'll have 1<<(2*input_pass-1) different numerators.
    '''
    input_pass:int = ((i.bit_length() - 1) >> 1) + 1
    threshold:int = 1 << (input_pass << 1) - 1
    numerator:int = i
    if numerator < threshold:
        numerator <<= 1
        numerator -= threshold
    numerator += 1
    return math.ldexp(numerator,-input_pass)

def rational_of(i:int) -> float:
    if -1 <= i <= 1:
        return i
    return math.copysign(positive_rational_of(abs(i) - 1),i)

def rational_sequence(N) -> Iterator[float]:
    yield 0
    if math.isfinite(N):
        integer_sequence = range(1,N)
    else:
        integer_sequence = itertools.count(1)
    for i in integer_sequence:
        yield rational_of(i)
        yield rational_of(-i)

if __name__=='__main__':
    for rational in rational_sequence(65):
        print(f"real: {rational}")