5

I'm writing a compiler in Java and needed a gensym function. I decided that I would just try to generate unique 64 bit integers and convert them to base 36 strings. I jotted down a recursively defined function to generate the sequence. When I tested it in C, the sequence up to $n=2^{20}$ contained no duplicates. So now I'm curious if it's possible to determine, without occupying my computer for the next two weeks, if the function is a one-to-one correspondence on $[0,2^{64})\rightarrow[0,2^{64})$. The function is defined like this:

$f(0)=1$

$f(1)=3$

$\forall n > 1, f(n)=\mathord{\sim}f(n - 1) \verb|^| (37 \cdot f(n - 2))$

To be clear, the tilde is bitwise complement, and the caret is bitwise xor.

I was a math major in college but it's been a while since I've really done this sort of thing and I'm just not sure how to tackle this. Anyway, first question, so, sorry if I was little too verbose.

mvw
  • 34,562
James Bolden
  • 51
  • How tightly does the bitwise complement bind in this? Is it (~f(n-1))^... or ~(f(n-1)^...) ? – Q the Platypus Aug 01 '16 at 00:24
  • The former. (~f(n-1))^... – James Bolden Aug 01 '16 at 00:24
  • Actually it doesn't matter – Q the Platypus Aug 01 '16 at 00:27
  • What is wrong with $f(i) = i$? Guessing a function that you hope is a permutation of ${ i \mid 0\le i \le 2^{64}-1}$ and then asking if you were right on MSE is absurd. (And do you really think you could test your guess in 2 weeks?) – Rob Arthan Aug 01 '16 at 00:41
  • Well, that's true. There's nothing really wrong with just using a counter. It was an aesthetic (and, perhaps, frivolous) choice.

    (And no, I don't think I could. Granted it only took about twenty minutes to test up to $2^{20}$ by caching the result of each call, and that's without any threading, or really much thought at all about optimization.)

     – James Bolden Aug 01 '16 at 00:49
  • Just as an aside, I wasn't asking if the function actually is a one-to-one correspondence, just if it could be determined, analytically, whether or not it is. Also, I thought about it a little bit and you're obviously quite right that two weeks was an absurdly terrible guess. Then, later on, I thought about it quite a bit more and realized that I don't even have words for how bad of a guess two weeks was. – James Bolden Aug 01 '16 at 08:33
  • FWIW, I think this is a reasonable question to ask. By the way, is $\cdot$ multiplication modulo $2^{64}$ (i.e. unsigned int multiplication)? – cody Aug 04 '16 at 22:01
  • @cody yes, that seems to be the case in both my test language (C) and Java, which the algorithm is intended for.

    Also, just a thought, but what I think gave me so much difficulty even getting started figuring this out is that as a math major I wasn't taught much of anything regarding bitwise operations. So when I looked at the general form of the algorithm, I couldn't come up with any kind of term substitution.

     – James Bolden Aug 05 '16 at 04:49

0 Answers0