-7
\$\begingroup\$

Write a function that, given N >= 0, finds the Nth number in a standard Gray code.

Example input:

1
2
3
4

Example output:

1
3
2
6

Additional reference

\$\endgroup\$

closed as off-topic by Dennis, Fors, ProgramFOX, Kyle Kanos, Martin Ender Jul 3 '14 at 13:52

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions without an objective primary winning criterion are off-topic, as they make it impossible to indisputably decide which entry should win." – Dennis, Fors, ProgramFOX, Kyle Kanos, Martin Ender
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ This isn't much of a challenge, IMHO \$\endgroup\$ – Hasturkun Dec 4 '11 at 16:36
  • 1
    \$\begingroup\$ Welcome to CodeGolf.SE! According to our FAQ, every challenge is expected to have a objective winning criteria. If you mean "shortest code" you should tag [code-golf] instead of [code-challenge], otherwise you need to be explicit. \$\endgroup\$ – dmckee Dec 4 '11 at 23:59
  • \$\begingroup\$ According to your linked source, the first graycode is 0, not 1. How do you measure the speed? Based upon what did you accept Ilmari Karonen's answer? \$\endgroup\$ – user unknown Dec 9 '11 at 0:05
3
\$\begingroup\$

Perl, 7 chars

$_^$_/2

This is an expression that returns the Gray code, given the input in $_. You can use it on the command line with the -n switch:

perl -nE 'say $_^$_/2'

or use it in a map:

perl -E 'say for map $_^$_/2, 1 .. 10'
1
3
2
6
7
5
4
12
13
15

If you specifically want a function, I can do that too (in 20 chars):

sub g{$_[0]^$_[0]/2}

Edit: Since this challenge is now tagged , let me include the equivalent C preprocessor macro, which should be about as fast as this can be done:

#define g(i) ((i)^(i)>>1)

A faster solution, if one exists, is likely to require hand-optimized assembly code. Even then, a good optimizing C compiler may be hard to beat. Looking at the disassembly of the benchmark code below, it seems gcc compiles this into three Intel assembly instructions:

 8048428:       89 c2                   mov    %eax,%edx
 804842a:       d1 ea                   shr    %edx
 804842c:       31 c2                   xor    %eax,%edx

This (a register copy, a shift and an XOR) is about what I'd expect any decent compiler to produce. Of course, a good compiler might also be able to interleave the operations with surrounding code to improve pipelining. (In the benchmark, the inner loop is tight enough that there's not much room for that.)

Testing just how fast this is can be a bit tricky, since we need to make sure the compiler won't just optimize away the Gray code calculation, or even the entire testing loop. Here's a piece of code that sums up all unsigned 32-bit integers eight times over, either in Gray code order or, if NOGRAY is defined, in normal binary order. Obviously, the output should be zero in either case, but at least gcc isn't smart enough to realize that.

#include <inttypes.h>
#include <stdio.h>

#ifdef NOGRAY
#  define g(i) (i)
#else
#  define g(i) ((i)^(i)>>1)
#endif

int main (void) {
    uint32_t k, i, n = 0;
    for (k = 0; k < 8; k++) {
        for (i = 1; i != 0; i++) n += g(i);
    }
    printf("%lu\n", (unsigned long) n);
    return 0;
}

On my 2.2GHz AMD Athlon 64 X2 CPU, compiled with gcc 4.4.3 with -O3 for i486-linux-gnu, running this code takes about 46.9 seconds, compared to about 31.2 second with NOGRAY defined. That gives about 15.7 seconds for 235−8 Gray code calculations, which comes down to about 0.457 nanoseconds, or almost exactly one CPU cycle per calculation.

However, it's worth noting that that's the marginal cost of including the Gray code calculation in the loop. The total time to execute the benchmark loop (which includes two adds and a conditional jump in addition to the three lines of assembly I showed above) is about 1.365 nanoseconds, or three cycles per iteration.

\$\endgroup\$
  • \$\begingroup\$ a) It's not a code golf. b) How fast is it? \$\endgroup\$ – user unknown Dec 9 '11 at 0:02
  • 2
    \$\begingroup\$ a) It wasn't fastest-code either when I posted this answer, that tag was added later. b) About as fast as it can be done in Perl, which is to say, probably many times slower than the equivalent code in C. \$\endgroup\$ – Ilmari Karonen Dec 9 '11 at 0:12
  • \$\begingroup\$ Yes, but it was never marked as code-golf, so your headline is a bit misleading. And I would like to measure the speed of your code to compare it to mine - but I would have to write the timing-code myself, or use a single invocation, measured by time. Still I had to write the main-method myself. \$\endgroup\$ – user unknown Dec 9 '11 at 1:51
  • \$\begingroup\$ A good compiler could auto-vectorize that and produce 4 (SSE) or 8 (AVX2) Gray codes per iteration. \$\endgroup\$ – Peter Cordes Dec 18 '16 at 0:33
2
\$\begingroup\$

Golfscript, 4 chars

.2/^
\$\endgroup\$
  • \$\begingroup\$ @Taylor: please don't get me wrong, I'm not looking for gray code for given N, but looking for N-th number in gray code list. (check the edit section) \$\endgroup\$ – mohammad shamsi Dec 5 '11 at 4:35
  • \$\begingroup\$ @mohammadshamsi, it's in no way clear what difference you're intending to draw. \$\endgroup\$ – Peter Taylor Dec 5 '11 at 7:02
  • \$\begingroup\$ a) It's not a code golf. b) How fast is it? \$\endgroup\$ – user unknown Dec 9 '11 at 0:02
  • 2
    \$\begingroup\$ @userunknown, a) See Ilmari's comment. b) As fast as possible in GolfScript. c) This was primarily a protest answer against a "code challenge" which can be done efficiently in 4 characters. \$\endgroup\$ – Peter Taylor Dec 9 '11 at 7:19
  • \$\begingroup\$ For protesting, I would suggest a) downvoting b) commenting and c) vote to close the question. 2.) See my comment to Ilmari's comment. \$\endgroup\$ – user unknown Dec 9 '11 at 9:01
0
\$\begingroup\$

scala:

It's not a code-golf!

However - if you like to golf:

def g(n:Int)=n^(n/2)

20 chars, according to my set of natural numbers.

But since speed matters, I produce a compilable form:

object Graycode extends App {

  def graycode (n: Int) = n^(n/2)

  def test (max: Int) {
    var i = 0
    val start = System.nanoTime ()
    while (i < max) { 
      graycode (i) 
      i += 1
    }
    val stop = System.nanoTime ()

    val diff = (stop-start)*1.0 / (1000*1000*1000)
    println ("Time: " + diff + "s\tn: " + max + "\tspeed: " + max * 1.0/diff + " /s")  
  }

  override def main (args: Array[String]) = {
    var max = args(0).toInt 
    val graycode = Graycode
    graycode.test (max)
  }
}

You can compare it against your solution this way:

scala Graycode 1000000000
Time: 23.882410496s n: 1000000000   speed: 4.1871820274066865E7 /s

About 4 million ints per second on my machine. If I comment out the call to graycode, I get as speed: 7.683713972447292E8 /s, so it is not mainly the time used to loop, which is measured above.

Of course your absolute times will vary, but you may compare it to measurements of your code. Please provide measurement methods with your solutions too.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.