Add two real numbers ... probably

Question

The problem statement here is pretty simple, take two real numbers on the range [0,1) as input and output their sum, with probability 1.

The catch here is that there are a lot of real numbers. There are in fact so many real numbers that it is impossible to fit all of them into any finite data type. As such, any way to input real numbers has to be potentially infinite, and any algorithm that handles arbitrary real numbers cannot consume all of the input.

For this challenge you will input (and output) real numbers as lazy sequence (e.g. stream, generator, lazy list, function) of bits, representing their binary expansion. You can assume that the input will be normalized and will not end in an infinite repetition of 1.

Even with this special input format it isn't possible to add any two real numbers. Any potential algorithm can be tricked into an infinite loop.

So instead we are going to settle for almost working. To "work" on a pair of inputs your program needs to be able to output any bit of the output in finite time. For example, if you output a generator I should be able to read to the 5th bit without the program getting stuck in a loop. Your answer needs to work with probability 1, meaning that the measure of the set of inputs which your program does work needs to have measure 1. The behavior for which the program doesn't work is undefined it can loop forever give an incorrect answer etc. so long as these cases themselves have measure zero.

This is code-golf the goal is to minimize the size of your source code as measured in bytes.

Examples

Here are some examples of rational numbers being added. You do not need to support any of these specific numbers.

1/3  = 0.01010101010101010...
+
1/5  = 0.00110011001100110...
=
8/15 = 0.10001000100010001...

3/8  = 0.011000000000000000...
+
3/16 = 0.001100000000000000...
=
9/16 = 0.100100000000000000...

17/95    = 0.001011011100111101111110101001110001001011011100111101111110101...
+
3/13     = 0.001110110001001110110001001110110001001110110001001110110001001...
=
506/1235 = 0.011010001110001100101111111000100010011010001110001100101111111...

Answer 1

Python, 75 bytes

def f(*I,n=0):
 for a,b in zip(*I):yield from[a,*n*[1^a]][:-(n:=1+n*(a^b))]

Attempt This Online!

Takes two iterables and returns one.

How?

Count bits that differ between the inputs without outputting anything until an equal bit is encountered. Output this bit followed by counter times its complement. Reset counter and start over.

Answer 2

Rust, 222 199 bytes

|a:Box<dyn Iterator<Item=usize>>,b:Box<dyn Iterator<Item=usize>>|a.zip(b).scan(0,|z,(e,f)|Some(if e==f{let q=*z;*z=0;(e..=e).chain((1-e..2-e).cycle().take(q)).collect()}else{*z+=1;vec![]})).flatten()

Attempt This Online!

Just the type declaration of a iterator is already longer than some of the answers here :(

Answer 3

Javascript, 103 104 105 bytes

function*g(a){for(;;){for(i=0;(A=a.next().value)!=a.next().value;)i++;yield*[A,...Array(i).fill(+!A)]}}

More nicely formatted:

function*g(a){
    for(;;){
        for(i=0;(A=a.next().value)!=a.next().value;) i++;
        yield A;
        yield* Array(i).fill(+!A)
    }
}

Expects a generator function which yields the bits of the numbers to be added, interleaved.

Answer 4

Charcoal, 21 bytes

ＦＮ≔⁺ＮＮθＮηＷ⁻ηＮＮηＩ﹪⁺θη²

Try it online! Link is to verbose version of code. Takes input as n (1-indexed) and in interactive mode will prompt for interleaved input bits until it knows what value the nth output bit is but on TIO you just have to provide enough bits (if there aren't enough you'll see a prompt but the program will just halt). Explanation:

ＦＮ≔⁺ＮＮθ

Input n pairs of bits but only keep the sum of the last pair.

ＮηＷ⁻ηＮＮη

Input further pairs of bits until two match.

Ｉ﹪⁺θη²

Add the matching bit to the sum from earlier and reduce modulo 2.

Answer 5

R, 62 60 bytes

Edit: -2 bytes thanks to pajonk

{t=0
\(x,y){u=t
t<<-`if`(x-y,t+1,0)
if(x==y)c(x,rep(!x,u))}}

Attempt This Online!

Port of loopy walt's Python approach.

Function that accepts sequential pairs of bits from the two numbers to be added as input to successive calls, and gives output when it can, otherwise outputs nothing. So the full output is the concatenated output of successive calls.
Input corresponds to the bits after the binary point, output begins with a single bit before the binary point, followed by all bits after the binary point (since we need to one more bit in case the two input numbers add-up to greater-than one).

Unfortunately my maths isn't good enough to determine when an infinite number of infinitely-small values sum to a finite value or to zero, so I'm blindly trusting that this approach is valid...