insert data into matrix

[wawan]

hello all i have big problem here,
I want to build a matrix that have rules like this:
1. first value is 1.[1]
2. then replicate [1] become two array, the first array is [11] and second array is inverdted [1-1].
3. the rule is repeated for the two array above,the first array become [1111]&[11-1-1]the second array become [1-11-1]&[1-1-11].
[11 1 1]
[11-1-1]
[1-11-1]
[1-1-11]

4. so the matrix have long power of 2. and if the user input n long, i must generate n long matrix with condition, if and only if n=power of 2 (k); were k=positif integer

thanks wiro

[Anon]

Your description is a bit confusing, and, I think, inconsistent, but it sounds like you're asking about Hadamard matrices.

This is my first cut at the code. It can no doubt be improved

function hadamard($n=0){

if($n==0) return array(array(1));

$matrix=hadamard($n-1);

$newmatrix=array();
foreach($matrix as $row)
{ $newmatrix[]=array_merge($row,$row);
}
foreach($matrix as $row)
{ $nrow=array();
foreach($row as $term)
{ $nrow[]=-$term;
}
$newmatrix[]=array_merge($row,$nrow);
}
return $newmatrix;
}

[Anon]

Prolly faster:

hadamard($n=0)
{
for($x=0;$x<(1<<$n);$x++)
for($y=0;$y<(1<<$n);$y++)
{
$h[$x][$y]=0;
for($i=0;$i<$n;$i++) if($x&$y&(1<<$i)) $h[$x][$y]++;
$h[$x][$y]=($h[$x][$y]&1?-1:1);
}
return $h;
}

[wawan]

Hey body...that's good answer, but could u tell me, where is the different(faster) in u'r scripts

[Anon]

The big bottleneck in the is that it's recursive: if you're computing hadamard(5), you end up with PHP having to keep track of five entire functions-in-progress, with all their local variables and so forth. That can get expensive; luckily it's almost right at the start, so there's little "in progress" at that point, but PHP still has to do all the work involved with calling a user-defined function. The first approach also uses array_merge() a couple of times, which means more function-call overhead.

I also half-suspect that foreach looping over array indices is a wee bit slower than ordinary for loops. In the second all there's nothing fancier than some increments and a few bit-operations.

'Course, all this is probably academic until the matrices get really big. In which case a bit of memory conservation might be in order:

hadamard($n=0)
{
$one=1;
$mone=-1;
for($x=0;$x<(1<<$n);$x++)
for($y=0;$y<(1<<$n);$y++)
{
$h[$x][$y]=0;
for($i=0;$i<$n;$i++) if($x&$y&(1<<$i)) $h[$x][$y]++;
$h[$x][$y]=($h[$x][$y]&1?$mone:$one);
}
return $h;
}

The difference between this one and the previous is that the previous requires 2⁽²ⁿ⁾ locations in memory to store lots of 1's and -1's, while this one only stores a single 1 and a single -1 and just points to those as necessary.

Plus, I just felt like doing it again, only smarter 🙂

[wawan]

thanks Grumbler...
i'll try find smarter too...🙂

[Anon]

'Cos I could, I quickly wrote a version that's kinda intermediate between the two. It still uses the recursive construction, but doesn't use array_merge.

function hadamard($n=0)
{
if($n==0) return array(array(1));

$m=hadamard($n-1);
$tn=1<<($n-1);
for($x=0; $x<$tn; ++$x)
for($y=0; $y<$tn; ++$y)
{
$h[$x][$y]=$m[$x][$y];
$h[$x][$y+$tn]=$m[$x][$y];
$h[$x+$tn][$y]=$m[$x][$y];
$h[$x+$tn][$y+$tn]=-$m[$x][$y];
}
return $h;
}

Memory consumption of this would be the same as the first, O(2^(2n)).

[wawan]

it seems that u have a good mathematic back gound....
Have u ever use Hadamard matrix for any application?

[Anon]

More like the foreground... :-)

(Practical applications of) Hadamard matrices have come up a couple of times in my experience.

One use is in image processing, where it appears as an image transform, where you can have a Hadamard Transform just as you can have a Fourier Transform for identifying periodic components in an image, or a Cosine Transform (used in things like JPEG compression).

The other use is in designing error-correcting codes. Say you wish to encode a message consisting of four-bit words 0000..1111. One method would be to assign to each word a row from hadamard(4), which means each word of the message gets encoded as a sequence of 16 bits.
The important feature is that each row in the matrix differs by exactly 8 bits from any other row in the matrix - so four bits in the codeword have to be corrupted before it becomes indecipherable. Compare this with sending the original four-bit words unencoded, where a single error would not just make the word unreadable, but - worse - make it get read incorrectly.

[wawan]

Hey..that great experience...Man
And thanks again....for help me solve the problem.
now, i'll finish my project soon
I want learn a lot from u... 🙂