Recently I came across this problem in the book "Introduction to Programming in JAVA An Interdisciplinary Approach" under creative examples. I know the properties of Hadamard matrix. Like, they are all square matrices. H(1) consists of a single row and column with the value T. And in general if we have H(N) then we can create H(2N) by defining the matrix as 1st row [H(N) H(N)] and second row [H(N) -H(N)]. So whenever an user enters a the value for N, I assume it to be a power of 2. and declare a NXN matrix, whose first element H[0][0] is true. But then how do I populate the array from that point. I need help in understanding the approach to this program.

For reference here is the complete question,

Hadamard matrix. The N-by-N Hadamard matrix H(N) is a boolean matrix with the remarkable property that any two rows differ in exactly N/2 entries. (This property makes it useful for designing error-correcting codes.) H(1) is a 1-by-1 matrix with the single entry true, and for N>1, H(2N) is obtained by aligning four copies of H(N) in a large square, and then inverting all of the entries in the lower right N-by-N copy, as shown in the following examples (with T representing true and F representing false, as usual).

Write a program that takes one command-line argument N and prints H(N). Assume that N is a power of 2.

Regards,

Ranajoy

I think you should explain the algorithm behind creating the matrix. Once you have the algorithm written out in a nice simple form it shoulld be easy to convert to code.

By the way: Have you considered changing each row to a number? Regard a T as the bit set (=1) and a false a a 0. That way you can change each row to an

`int`or

`long`depending on its size. Does that help at all?

Basically the code goes as follows.

This is the display() method.

This code has some problem. Here are some of the outputs.

Everything goes all right till 4. but when I enter 8, the code ends up giving me this.

How should I correct this issue? Where am I going wrong?

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

That is exactly what you are looking for. An algorithm written out nice and simply, so you can implement it. Of course the algorithm starts with the magic word recursion. Recursion isn't quite witchcraft, but if you want a happy life, don't try to work out how recursion works. Just trust that it does workJunilu Lacar wrote:. . . To get H(8), . . . to get H(4), . . . To get H(2), ...

Junilu Lacar wrote:I would try to use some recursion. To get H(8), fill first three quadrants with H(4), then invert H(4) to get the fourth quadrant. Recursively, to get H(4), you'd fill first three quadrants with H(2), then invert H(2) to get the fourth quadrant. To get H(2), ...

Orrr....

You could write write a recursive method to return just a single boolean. Conveniently, H(N)[X, Y] is the same for all N where X and Y are reasonable (i.e. X,Y < N)

Disclaimer: This is toally untested code.

Now just fill in any size array you want.

Ryan McGuire wrote:Orrr... Is there a way to calculate a given array value from just the indexes? For instance, without working the entire H(128) matrix out, I would bet that H(128)[42, 95] is T. Can anyone confirm or refute that?

Clarification: I mean is there a

**non-recursive**way to calculate a given array value.

Campbell Ritchie wrote:There probably is. You will have to search for algorithms.

Search for? Figure the algorithm out your own darn self. It's just a bunch of Ts and Fs in a fairly regular pattern. How hard can it be?

Ryan McGuire wrote:

Campbell Ritchie wrote:There probably is. You will have to search for algorithms.

Search for? Figure the algorithm out your own darn self. It's just a bunch of Ts and Fs in a fairly regular pattern. How hard can it be?

I think this thread could be moved over to Programming Diversions. It's easy enough that it should be gettable, but it's hard enough to support multiple plans of attack AND provide some nice aha moments along the way. Could some kind Sheriff move this there if you agree?

Given the definition of Hadamard matrices in the OP, what's the best (easy to program, low memory reqs, fast to execute, etc) way to...

1. Determine a single value without necessarily calculating the entire matrix? e.g. What is H512[344][285]?

2. Print out the entire matrix.

Is the answer to part 2 just answering part 1 over and over?

If you have such a direct formula, then I would love to see it.

Piet Souris wrote:If you have such a direct formula, then I would love to see it.

Rather than give out (what I think is) the answer, let me ask...

1. For a given H(n), there are four copies of H(n/2). Where is H(n/2) used as-is and where is it inverted (i.e. XORed)? More secifically, is there a way to characterize where the copy of H(n/2) is inverted from just the indexes? (Something like, "if x and y are both prime numbers, invert H(n/2).")

2. Once you answer that for H(n) and H(n/2), how does that relate to H(n/2) and H(n/4), etc.

3. Is there an easy way to describe how many times H(1)[0][0] gets XORed to arrive at all the other values?

H512(345, 261) =( 512 ^([261 / n!] (floor function) % 2 == 0) && H1(1,1)

Do you have such a function? I do not need to know it, but if you do I'll have another try.

Piet Souris wrote:Anyone who has a recursive solution knows this reasoning. That''s not the problem. I am looking for a non recursive formula without any ifs and whiles, just a plain simple formula like:

H512(345, 261) =( 512 ^([261 / n!] (floor function) % 2 == 0) && H1(1,1)

Do you have such a function? I do not need to know it, but if you do I'll have another try.

Yes, I do. It cheats just a little in that it's not 100% O(1). However, the source code is nice and short because it uses a method in one of the standard Java classes.

yes, it is indeed very simple and almost O(1). Also in H(n, x, y, startBoolean) it is remarkable that the value does not depend on n, the order of the Hadamard. And I used a method from a standard class too. Now, what is the chance that we have the same? Shall I send you a PM?

With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime. |