Ranajoy Saha

Ranch Hand

Posts: 105

2

posted 1 year ago

Hi, everyone

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

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

Piet Souris

Rancher

Posts: 1980

67

Campbell Ritchie

Marshal

Posts: 55717

163

posted 1 year ago

Have added code tags to your matrices, using the Text option in the dropdown list. I think it makes it look better, but the widths of the characters are irregular, so I had to remove some spaces.

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

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?
Ranajoy Saha

Ranch Hand

Posts: 105

2

posted 1 year ago

Following Piet Souris suggestion, what I did was created an H(2) matrix and wrote a code to fill any square matrix with the values of H(2). Then, what I did was to invert the outputs as soon as the last matrix is to be inserted.

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?

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?

Ranajoy Saha

Ranch Hand

Posts: 105

2

Ranajoy Saha

Ranch Hand

Posts: 105

2

posted 1 year ago

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), ...

*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]

Campbell Ritchie

Marshal

Posts: 55717

163

posted 1 year ago

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), ...

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 1 year ago

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.

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

Ranch Hand

Posts: 1142

9

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 1 year ago

Clarification: I mean is there a

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

Marshal

Posts: 55717

163

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 1 year ago

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?

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

Ranch Hand

Posts: 1142

9

posted 11 months ago

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?

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?

Campbell Ritchie

Marshal

Posts: 55717

163

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 11 months ago

Since I think I've come up with the best way to calculate the values in a Hadamard matrix, I'll pose the question:

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?

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?

Piet Souris

Rancher

Posts: 1980

67

posted 11 months ago

I remember that a recursive solution was very easy and elegant, and that I next tried to devise a non-recursive formula that, given x and y coordinates, directly lead to either H1 or !H1. (and H1 is the given starting situation). But that turned out to be so complex that I soon gave up. It's much more difficult than coming up with a formula for say the Fibonacci series, with only n as variable. I even tried to prove some full induction formula, but in vain.

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

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

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 11 months ago

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?

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?

Piet Souris

Rancher

Posts: 1980

67

posted 11 months ago

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.

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.

Ryan McGuire

Ranch Hand

Posts: 1142

9

posted 11 months ago

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.

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.

Piet Souris

Rancher

Posts: 1980

67

posted 11 months ago

hi Ryan,

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?

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?

Ryan McGuire

Ranch Hand

Posts: 1142

9

Piet Souris

Rancher

Posts: 1980

67

posted 11 months ago

Thanks for the inspiration, and what a lovely formula. Have a cow, truly deserved!