Differentiability of BitXor function

[matiasmorant]

in many programming languages there is a function of two variables called BitXor (which is also known as nim-sum, since it is used in solving de nim game) which represents each number as a string of its binary digits and then takes the Xor of each pair of terms, forming a new number.

For Example :

5*7= 1 0 1 * 1 1 1 (binary) =0 1 0 (binary) = 2

(where '*' is the BitXor operator)

and 2.5*1.5=10.1*1.1 (binary)=11(binary)=3


Ok. So let f(x)=c*x (where '*' is the BitXor operator and c a real number).

is f differentiable??

 

[HallsofIvy]

"BitXor" can be applied only to integers, not to general real numbers. Since the domain is discrete, the derivative cannot be defined and your question does not make sense.

 

[matiasmorant]

"BitXor" can be applied only to integers, not to general real numbers.

yes,I know that. but it's simple to see how to extend the function to all real numbers, that's why I gave the example 2.5*1.5=10.1*1.1(binary)=11(binary)=3. I don't see there is any problem in doing that, it seems pretty straight forward. we can call it the realbitxor function, or whatever.

here is a code for the 'RealBitXor' function, written for mathematica:

RealBitXor[x_, y_] := N[FromDigits[BitXor[First[#], Last[#]] &[
PadRight[
{ArrayPad[
First[RealDigits[Min[x, y],
2]], {Last[RealDigits[Max[x, y], 2]] -
Last[RealDigits[Min[x, y], 2]], 0}],
First[RealDigits[Max[x, y], 2]]}
]
], 2]/2^Length[First[PadRight[
{ArrayPad[
First[RealDigits[Min[x, y],
2]], {Last[RealDigits[Max[x, y], 2]] -
Last[RealDigits[Min[x, y], 2]], 0}],
First[RealDigits[Max[x, y], 2]]}
]]] - Last[RealDigits[Max[x, y], 2]]]

not very tidy, but well... and I didn't take the signs into account, but it's correct for positive real numbers.

if you graph the function f(x)=c*x, you will see that it is differentiable for some values of c; while it looks like a fractal for some others, which amazed me.


for the particular case where c=0; f(x)=x and f'(x)=1. obvious.
and for integer values of c, it seems to be differentiable by parts

 

[nickalh]

Between 0.0000 and 0.1111111...
we can only express 2^n numbers. The only numbers we can express exactly in binary have 2^n in the denominator. To be on the safe side, the precision for the domain should be several more digits (3 binary digits?) than the precision for taking the derivative. What you've done may work well.

I would trust a difference quotient, closely related to a derivative, more thoroughly. It is intended for discrete domains.

I only have WolframAlpha.com, not Mathematica, but I'm sure the pictures/fractals are cool.

 

[vladb]

yes,I know that. but it's simple to see how to extend the function to all real numbers, that's why I gave the example 2.5*1.5=10.1*1.1(binary)=11(binary)=3. I don't see there is any problem in doing that, it seems pretty straight forward. we can call it the realbitxor function, or whatever.

It's an interesting idea. However, you need some additional work to make the definition consistent.
For example, 1.000... and 0.1111... (in binary) both represent the same real number (1).
Then 1.000... xor 0.111... = 1.111... = 2,
but 0.111... xor 0.111... = 0.000 = 0, which is a contradiction.

 

[nickalh]

0.1111... = 1.0 ??
The regular decimal system has the same issue. Considering computers don't store an infinite number of digits whether decimals or binary, this shouldn't be a major issue.

 

[vladb]

0.1111... = 1.0 ??
The regular decimal system has the same issue. Considering computers don't store an infinite number of digits whether decimals or binary, this shouldn't be a major issue.

I see your point, but I was considering the original question as a mathematical one (with the programming part just to confirm/disprove OP's hypothesis). Notions of continuity and differentiability don't make much sense to me when working with numbers represented by computers.

 

[D H]

0.1111... = 1.0 ??
The regular decimal system has the same issue. Considering computers don't store an infinite number of digits whether decimals or binary, this shouldn't be a major issue.

This is a huge issue, and it destroys the concept of differentiability of this function. A function that is nowhere continuous (and this one is) is not differentiable.

That 0.111...₂ = 1.0₂ introduces a huge ambiguity in the definition of this function. Example: What is c*x, where * is our "real bit xor" operator, for c=1/3, x=1/4? In binary, c is 0.01(01)... An ambiguity exists for x: do we represent it as 0.01 or 0.001(1)... ? We need to pick a rule for terminating binary numbers so that our function is well-defined. There are two possibilities:

• Use the terminating representation for x.
  With this choice, c*x=0.01(01)...*0.01=0.0001(01)...=1/12₁₀.
• Use the repeating representation for x.
  With this choice, c*x=0.01(01)...*0.001(1)...=0.01(10)...=5/12₁₀.

With regard to differentiability, it doesn't really matter which choice is made. The function is discontinuous at x=1/4. A number slightly less than 1/4 will have a representation that starts with 0.0011, so 1/3 bitxor (1/4-ε) is approximately equal to 5/12. A number slightly greater than 1/4 will have a representation that starts with 0.0100, so 1/3 bitxor (1/4-ε) is approximately equal to 1/12. Make epsilon approach zero and those "approximately equal to" become exact. There is a discontinuity at x=1/4. Similarly, there is a discontinuity at every number that has a terminating binary representation. Since the set of numbers with a terminating binary representation is a dense subset of the reals, this function is nowhere continuous.