Algorithm-BitVector
view release on metacpan or search on metacpan
Examples/BitVectorDemo.pl view on Meta::CPAN
print "\nTesting reverse():\n";
$bv = Algorithm::BitVector->new( bitstring => '0001100000000000001' );
print "original bv: $bv\n"; # 0001100000000000001
print "reversed bv: " . $bv->reverse() . "\n"; # 1000000000000011000
# Calculate the GCD of two bitvectors using Euclid's algorithm on the integers values:
print "\nTesting Greatest Common Divisor (gcd):\n";
$bv1 = Algorithm::BitVector->new( bitstring => '01100110' );
print "first arg bv: $bv1 of int value: " . int($bv1) . "\n"; #102
$bv2 = Algorithm::BitVector->new( bitstring => '011010' );
print "second arg bv: $bv2 of int value: " . int($bv2) . "\n"; # 26
$bv = $bv1->gcd( $bv2 );
print "gcd bitvec is: $bv of int value: " . int($bv) . "\n"; # 2
# Calculate the multiplicative inverse of a bitvector with respect to a modulus vector:
print "\nTesting multiplicative_inverse:\n";
my $bv_modulus = Algorithm::BitVector->new( intVal => 32 );
print "modulus is bitvec: $bv_modulus of int value: " . int($bv_modulus) . "\n";
$bv = Algorithm::BitVector->new( intVal => 17 );
print "bv: $bv of int value: " . int($bv) . "\n";
$result = $bv->multiplicative_inverse( $bv_modulus );
Examples/BitVectorDemo.pl view on Meta::CPAN
print "Find multiplicative inverse of a single bit array\n";
$modulus = Algorithm::BitVector->new( bitstring => '100011011' ); # AES modulus
$n = 8;
$a = Algorithm::BitVector->new( bitstring => '00110011' );
my $mi = $a->gf_MI($modulus, $n);
print "Multiplicative inverse of $a in GF(2^8) is $mi\n";
# Experiments with finding ALL multiplicative inverses in a small Galois Field:
print "\nIn the display produced by following statements, you will see " .
"\nthree rows. The first row shows the binary code words, the " .
"\nsecond the multiplicative inverses, and the third the product " .
"\nof a binary word with its multiplicative inverse modulo the " .
"\nprime polynomial:\n";
$mod = Algorithm::BitVector->new( bitstring => '1011' );
$n = 3;
my @bitarrays = map Algorithm::BitVector->new(intVal=>$_, size=>$n), 1 .. 2**3 -1;
my @mi_list = map $_->gf_MI($mod,$n), @bitarrays;
print "bit arrays in GF(2^3) : @bitarrays\n";
print "multiplicative inverses: @mi_list\n";
my @products;
foreach my $i (0..@bitarrays-1) {
push @products, $bitarrays[$i]->gf_multiply_modular($mi_list[$i], $mod, $n);
}
print "bit_array * multi_inv: @products\n";
# Experiments with finding ALL multiplicative inverses in a rather large Galois Field:
#UNCOMMENT THE FOLLOWING LINES FOR
#DISPLAYING ALL OF THE MULTIPLICATIVE
#INVERSES IN GF(2^8) WITH THE AES MODULUS:
print "\nMultiplicative inverses in GF(2^8) with modulus polynomial x^8 + x^4 + x^3 + x + 1:\n";
print "\n(This may take a few seconds)\n";
$mod = Algorithm::BitVector->new( bitstring => '100011011' );
$n = 8;
@bitarrays = map Algorithm::BitVector->new(intVal=>$_, size=>$n), 1 .. 2**8 -1;
@mi_list = map $_->gf_MI($mod,$n), @bitarrays;
print "multiplicative inverses: @mi_list\n";
@products = ();
foreach my $i (0..@bitarrays-1) {
push @products, $bitarrays[$i]->gf_multiply_modular($mi_list[$i], $mod, $n);
}
print "\nShown below is the product of each binary code word in GF(2^3) and its multiplicative inverse:\n\n";
lib/Algorithm/BitVector.pm view on Meta::CPAN
push @outlist1, $self->get_bit($i);
}
my @outlist2 = ();
foreach my $i ( ($self->{size} / 2) .. ($self->{size} - 1) ) {
push @outlist2, $self->get_bit($i);
}
return Algorithm::BitVector->new( bitlist => \@outlist1 ),
Algorithm::BitVector->new( bitlist => \@outlist2 );
}
## Permute a bitvector according to the indices shown in the second argument list.
## Return the permuted bitvector as a new bitvector.
sub permute {
my $self = shift;
die "Abort: The permute() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $permute_list = shift;
die "Bad permutation index in your permutation list"
if max(@$permute_list) > $self->{size} - 1;
my @outlist = ();
foreach my $index (@$permute_list) {
push @outlist, $self->get_bit($index);
}
return Algorithm::BitVector->new( bitlist => \@outlist );
}
## Unpermute the bitvector according to the permutation list supplied as the
## second argument. If you first permute a bitvector by using permute() and
## then unpermute() it using the same permutation list, you will get back the
## original bitvector.
sub unpermute {
my $self = shift;
die "Abort: The unpermute() method invoked on an object that is " .
"not of type Algorithm::BitVector"
unless UNIVERSAL::isa( $self, 'Algorithm::BitVector');
my $permute_list = shift;
die "Bad permutation index in your permutation list: $!"
if max(@$permute_list) > $self->{size} - 1;
lib/Algorithm/BitVector.pm view on Meta::CPAN
}
## Computes the Jaccard similarity coefficient between two bitvectors
sub jaccard_similarity {
my $self = shift;
my $other = shift;
die "Jaccard called on two zero vectors --- NOT ALLOWED: $!"
if (int($self) == 0) && (int($other) == 0);
die "Jaccard called on vectors of unequal size --- NOT ALLOWED: $!"
if $self->{size} != $other->{size};
my $intersection = $self & $other;
my $union = $self | $other;
return $intersection->count_bits_sparse() / $union->count_bits_sparse();
}
## Computes the Jaccard distance between two bitvectors
sub jaccard_distance {
my $self = shift;
my $other = shift;
die "Jaccard called on vectors of unequal size --- NOT ALLOWED: $!"
if $self->{size} != $other->{size};
return 1 - $self->jaccard_similarity( $other );
}
lib/Algorithm/BitVector.pm view on Meta::CPAN
}
if (int($num) != 1) {
return "NO MI. However, the GCD of $NUM and $MOD is $num\n";
} else {
my $z = $x_old ^ $MOD;
($quotient, $remainder) = $z->gf_divide_by_modulus($MOD, $n);
return $remainder;
}
}
## Returns a list of the consecutive runs of 1's and 0's in the bitvector.
## Each run is either a string of all 1's or a string of all 0's.
sub runs {
my $self = shift;
die "An empty vector has no runs" if $self->{size} == 0;
my @allruns = ();
my $run = '';
my $previous_bit = $self->get_bit(0);
if ($previous_bit == 0) {
$run = '0';
} else {
lib/Algorithm/BitVector.pm view on Meta::CPAN
of bit fields than non-circular shifts. You can still carry out non-circular shifts
by calling the methods C<shift_left()> and C<shift_right()> as illustrated elsewhere
in this documentation.
Another B<important> thing to bear in mind is the overloading of the `C<+>' operator.
It is B<NOT> addition. On the other hand, it is a concatenation of the two operand
bitvectors. This was done to keep the usage of this operator the same as in the
Python version of this module.
By virtue of how the operators are overloaded, you can make the calls listed in the
rest of this section. To illustrate these calls, I will use the following two bit
vectors:
$bv1 = Algorithm::BitVector->new( bitstring => "111000" );
$bv2 = Algorithm::BitVector->new( bitstring => "000101000" );
These two bitvectors are intentionally of different lengths to illustrate what role
the size differences play in how the various operators work.
=over 4
lib/Algorithm/BitVector.pm view on Meta::CPAN
$bv = Algorithm::BitVector->new( filename => 'testinput1.txt' );
print "$bv\n"; # Nothing to show yet
$bv1 = $bv->read_bits_from_file(64); # Now you have a bitvector from the
# first 64 bits
Note that it takes two calls to create bitvectors from the contents of a file. The
first merely creates an empty bitvector just to set the necessary file handle for
reading the file. It is the second call in which you invoke the method
C<read_bits_from_file()> that actually returns a bitvector from the bits read from
the file. Each call to C<read_bits_from_file()> in this manner spits out a new bit
vector.
=back
=head1 METHODS
=head3 close_file_handle()
lib/Algorithm/BitVector.pm view on Meta::CPAN
print $bv->get_bit(4); # 1 (the last bit)
Negative values for the index scan a bitvector from right to left, with the C<-1>
index standing for the last (meaning the right-most) bit in the vector:
print $bv->get_bit(-1); # 1 (the last bit)
print $bv->get_bit(-2); # 1
print $bv->get_bit(-5); # 1 (the first bit)
The C<get_bit()> can also return a slice of a bitvector if the argument to the
method is an anonymous array of the index range you desire, as in the second
statement below:
$bv = Algorithm::BitVector->new( bitstring => "10111011");
my $arr = $bv->get_bit( [3..7] );
print "@$arr\n"; # 1 1 0 1 1
In this example, we want C<get_bit()> to return all bits at positions indexed 3
through 7, both ends inclusive. Note that the slice is returned as an array of bits.
lib/Algorithm/BitVector.pm view on Meta::CPAN
=back
=head3 set_bit()
=over 4
With array-like indexing, you can use this method to set the individual bits of a
previously constructed bitvector. Both positive and negative values are allowed for
the bit position index. The method takes two explicit arguments, the first for the
position of the bit you want to set and the second for the value of the bit.
$bv = Algorithm::BitVector->new( bitstring => '1111' );
$bv->set_bit(0,0); # set the first bit to 0
$bv->set_bit(1,0); # set the next bit to 0
print $bv; # 0011
$bv->set_bit(-1,0); # set the last bit to 0
$bv->set_bit(-2,0); # set the bit before the last bit to 0
print $bv; # 0000
=back
=head3 set_slice()
=over 4
You can set a slice in a given BitVector by calling this method. It takes two
arguments, with the first argument as the range of the position index values at which
you want to set the bits and the second argument the bit values at those positions.
$bv = Algorithm::BitVector->new( intVal => 63437, size => 16 );
$values_bv = Algorithm::BitVector->new( bitlist => [1,1,1,1] );
$bv->set_slice( [4..8], $values_bv );
print "BitVector after set_slice(): $bv\n"; # 1111111111001101
When specifying the index values with the range operator in the form C<i..j>, you
would be setting the bits at the positions C<i> through C<j-1>.
=back
( run in 1.050 second using v1.01-cache-2.11-cpan-39bf76dae61 )