🔒 Locked

an interesting function

Started by capn_midnight Jan 19, 2005 at 5:59 PM 2 replies 500+ views

Original Post

404

Jan 19, 2005 at 5:59 PM

while fiddling around with binary numbers and gray code, I derived a simple function for converting binary numbers to gray code numbers g(b) = b XOR (b>>1) recursively calling g(b) eventually returns b again. The number of recursive calls m is 2ⁿ where n is the largest integer value such that 2^(2^n) is less than b. So that would be floor(log₂log₂b). I just think that going from the binary number to the gray code number is really simple (one call of g(b)) and using the same function you could get back to the binary number (eventually). Anyone else having fun with mathness? [Edited by - capn_midnight on January 19, 2005 6:54:58 PM]

reiko

Jan 19, 2005 at 6:21 PM

Isn't the number of calls required such that g(b) = b equal to 2 ^ floor (log₂ b) , not floor (log₂log₂b) ?

capn_midnight

Author

404

capn_midnight

Jan 19, 2005 at 6:53 PM

Quote:
Original post by posit
Isn't the number of calls required such that g(b) = b equal to 2 ^ floor (log₂ b) , not floor (log₂log₂b) ?

actually, I did mistype, but it's 2^{1+floor(log₂log₂b)}

[Edited by - capn_midnight on January 19, 2005 7:53:42 PM]

capn_midnight

Author

404

capn_midnight

Jan 19, 2005 at 7:06 PM

Here is the code I used to verify my answer. Unfortunately, the range of numbers that require 32 calls is [65536, 4294967296), with 64 calls thereafter.

#include <iostream>using namespace std;int gray(int i){	return i^(i>>1);}int dist(int g){	int k=0;	int j=g;	do{		j=gray(j);		++k;	}while(g!=j);	return k;}int main(){	int m=0;	for(unsigned int i = 0; i <= 65536 ; ++i){		unsigned int j=i;		int k=dist(i);		if(dist(i+1)!=k){			cout<<i<<": "<<dist(i)<<": "<<m<<endl;			m=1;		}		else{			m++;		}	}	return 0;}

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.