Print a specific value in the infinite Walsh matrix

4

The Walsh matrix is an interesting fractal matrix with the property that every single value in a Walsh matrix has a value of either -1 or 1. Additionally, the size of a Walsh matrix is always a power of 2.

Because each Walsh matrix is identical to the top-left quarter of the immediately higher-order Walsh matrix, we can create a generalized "infinite Walsh matrix" by considering the limit of the sequence of Walsh matrices of order N, as N goes to infinity. From here on, we will call this infinite generalization the Walsh matrix.

Your task is to build a program that takes the coordinates of a location in the Walsh matrix and returns the value that occurs there.

Your program will accept two integers x and y as input (in any form you choose), and output the value that appears in the x+1th row of the y+1th column of the Walsh matrix. For example, the input

2 5

will return 1, as the 3rd row in the 6th column of the Walsh matrix has a value of 1. The input

6 4

will return -1, as the 7th row in the 5th column of the Walsh matrix has a value of -1. The input

2834719 394802

will return -1, as the 2384720th row of the 394803rd column has a value of -1.

The shortest code to do this in any language wins.

Joe Z.

Posted 2014-02-14T19:51:26.243

Reputation: 30 589

5I quickly figured out a procedure for determining the value of any cell. Problem is, it only gives the correct answer half of the time. :) – DavidC – 2014-02-14T20:26:11.813

2print "0 ± 1" – Doorknob – 2014-02-14T22:05:00.823

@DavidCarraher, it seems that if you output 1 you'll do better than 50%. – Peter Taylor – 2014-02-15T09:27:24.530

1@Peter Taylor, Great idea, and your solution even saves a few characters. – DavidC – 2014-02-15T13:56:51.340

@PeterTaylor Of course, the limit as you go to infinity is still 50%. – Joe Z. – 2014-02-15T14:34:30.233

1Please add a minimal description of the matrix so that the problem makes sense when wikipedia is down. – Sparr – 2019-10-15T04:37:12.370

Answers

4

GolfScript (18 15 14 bytes)

~&2base-1\0-,?

Takes input space-separated; outputs to stdout. Thanks to Howard for pointing out that the space in the 15-char solution was removable.

The way I reasoned to this solution is quite simple. Take the highest set bit of x|y: this tells you the size of the smallest Walsh matrix which contains the relevant index. Then clearing that bit in both x and y drops us down to the top-left quadrant, and we need to multiply by -1 if we were previously in the bottom-right quadrant: i.e. if the bit was set in both x and y. By induction down the bit sequence, we just need to count the number of bits set in x&y.

Peter Taylor

Posted 2014-02-14T19:51:26.243

Reputation: 41 901

Of course it is much shorter to write ~&2base-1\0-,?. – Howard – 2014-02-15T11:11:07.143

2

Python 2 - 42 bytes

print(-1)**bin(input()&input()).count("1")

This takes the two coordinates as separate lines on standard input and writes the answer to standard output.

The algorithm is this:

  1. For coordinates X and Y, find X & Y, the bitwise AND of their values.
  2. Count the number of 1 bits in X & Y. This is the number of times the requested coordinate is in the bottom right quadrant of a level of the matrix.
  3. If the count is odd, the result is -1. If the count is even, the result is 1.

This should work for any positive integer coordinates (including large ones that need more than 32 bits).

Blckknght

Posted 2014-02-14T19:51:26.243

Reputation: 701

1

Forth (gforth), 44 bytes

: f and 1e 63 for s>d 2* 1+ s>f f* 2* next ;

Try it online!

The function takes two word-sized unsigned integers (64 bits on TIO). It returns -1 or 1 on the floating-point stack and leaves a garbage 0 on the main stack.

The algorithm follows Blckknght's submission, but the task made me explore LOTS of possibilities for writing Forth programs - from bit shift, divmod, single-to-double conversion to abusing floating-point stack. (The TIO link has several alternative definitions of f which all work, but are longer than the main answer.)

How it works

: f ( u1 u2 -- -1e_or_1e )  \ Takes two integers and returns a float 1 or -1
  and 1e                    \ Bitwise and(=N), then put a 1(=R) on the FP stack
  63 for                    \ Repeat 64 times... (TIO gforth has 64-bit cells)
    s>d                       \ Sign-extend single N to double
                              \ In effect, 0 is pushed if MSB is zero, -1 otherwise
    2* 1+ s>f f*              \ Change 0_or_-1 to 1_or_-1, cast to float and multiply with R
    2*                        \ Shift N left once
  next                      \ End loop
  ;                         \ End function

Bubbler

Posted 2014-02-14T19:51:26.243

Reputation: 16 616

0

x86_64 machine language for Linux, 17 bytes

0x00:  48 21 F7          and    rdi, rsi
0x03:  F3 48 0F B8 C7    popcnt rax, rdi
0x08:  FF C0             inc    eax
0x0a:  24 01             and    al, 1
0x0c:  01 C0             add    eax, eax
0x0e:  FF C8             dec    eax
0x10:  C3                ret    

Same algorithm as @Blckknght's answer.

Try it online!

ceilingcat

Posted 2014-02-14T19:51:26.243

Reputation: 5 503