Algorithm-BitVector
view release on metacpan or search on metacpan
Examples/BitVectorDemo.pl view on Meta::CPAN
# Experiment with the fast algorithm for counts the set bits in large but sparse bitvectors:
print "\nTesting count_bits_sparse() on a vector of TWO MILLION bits (be patient):\n";
$bv = Algorithm::BitVector->new( size => 2000000 );
$bv->set_bit(345234, 1);
$bv->set_bit(233, 1);
$bv->set_bit(243, 1);
$bv->set_bit(18, 1);
$bv->set_bit(785, 1);
print "The number of bits set: " . $bv->count_bits_sparse() . "\n"; # 5
# Experiments with resetting the internals of a bitvector:
print "\nTest set_value() method:\n";
$bv = Algorithm::BitVector->new( intVal => 7, size => 16 );
print "$bv\n"; # 0000000000000111
$bv->set_value( intVal => 45 );
print "$bv\n"; # 101101
# Experiment with Jaccard similarity and distance and with Hamming distance:
print "\nTesting Jaccard similarity and distance and Hamming distance:\n";
$bv1 = Algorithm::BitVector->new( bitstring => '11111111' );
$bv2 = Algorithm::BitVector->new( bitstring => '00101011' );
print "Jaccard similarity: " . $bv1->jaccard_similarity( $bv2 ) . "\n"; # 0.5
print "Jaccard distance: " . $bv1->jaccard_distance( $bv2 ) . "\n"; # 0.5
print "Hamming distance: " . $bv1->hamming_distance( $bv2 ) . "\n"; # 4
# Experiments in finding the position of the next set bit after a given position:
print "\nTesting next_set_bit():\n";
$bv = Algorithm::BitVector->new( bitstring => '00000000000001' );
print $bv->next_set_bit(5) . "\n"; # 13
$bv = Algorithm::BitVector->new( bitstring => '000000000000001' );
print $bv->next_set_bit(5) . "\n"; # 14
$bv = Algorithm::BitVector->new( bitstring => '0000000000000001' );
print $bv->next_set_bit(5) . "\n"; # 15
$bv = Algorithm::BitVector->new( bitstring => '00000000000000001' );
print $bv->next_set_bit(5) . "\n"; # 16
# The rank of a bit is the number of bits set prior to that bit:
print "\nTesting rank_of_bit_set_at_index():\n";
$bv = Algorithm::BitVector->new( bitstring => '01010101011100' );
print $bv->rank_of_bit_set_at_index( 10 ) . "\n"; # 6
# Experiment with determining whether the int value of a bitvector is a power 2:
print "\nTesting is_power_of_2():\n";
$bv = Algorithm::BitVector->new( bitstring => '10000000001110' );
print "int value: " . int($bv) . "\n"; # 826
print $bv->is_power_of_2() . "\n"; # 0
print "\nTesting is_power_of_2_sparse():\n";
print $bv->is_power_of_2_sparse() . "\n"; # 0
# Experiment with reversing a bitvector:
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 );
if ($result) {
print "MI bitvec is: $result of int value: " . int($result) . "\n"; # 17
} else {
print "No multiplicative inverse in this case\n";
}
# Experiments with non-circular shifts to the left and to the right:
print "\nExperiments with regular and chained invocations of NON-circular shifts:\n";
$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
print "$bv\n"; # 111001
$bv->shift_right(1);
print "$bv\n"; # 011100
$bv->shift_right(1);
print "$bv\n"; # 001110
$bv->shift_right(1)->shift_right(1);
print "$bv\n"; # 000011
$bv->shift_right(1);
print "$bv\n"; # 000001
$bv = Algorithm::BitVector->new( bitlist => [1,1, 1, 0, 0, 1] );
print "$bv\n"; # 111001
$bv->shift_left(1);
print "$bv\n"; # 110010
$bv->shift_left(1);
print "$bv\n"; # 100100
$bv->shift_left(1)->shift_left(1);
print "$bv\n"; # 010000
$bv->shift_left(1);
print "$bv\n"; # 100000
# Experiment with the calculation of multiplication in a Galois Field GF(2);
print "\nTest multiplication in GF(2):\n";
$a = Algorithm::BitVector->new( bitstring => '0110001' );
$b = Algorithm::BitVector->new( bitstring => '0110' );
my $c = $a->gf_multiply($b);
print "Product of a = $a with b = $b is $c\n";
# Product of a = 0110001 with b = 0110 is 00010100110
# Experiment with dividing one vector by another in GF(2^n):
print "\nTest division in GF(2^n):\n";
my $mod = Algorithm::BitVector->new( bitstring => '100011011' ); # AES modulus
my $n = 8;
$a = Algorithm::BitVector->new( bitstring => '11100010110001' );
my ($quotient, $remainder) = $a->gf_divide_by_modulus($mod, $n);
print "Dividing a= $a by mod= $mod in GF(2^8) returns the quotient $quotient and the remainder $remainder\n";
#Dividing a=11100010110001 by mod=100011011 in GF(2^8) returns the quotient 00000000111010 and the remainder 10001111
# Experiment in modular multiplication of bit patterns in GF(2^n):
print "\nTest modular multiplication in GF(2^n):\n";
my $modulus = Algorithm::BitVector->new( bitstring => '100011011' ); # AES modulus
$n = 8;
$a = Algorithm::BitVector->new( bitstring => '0110001' );
$b = Algorithm::BitVector->new( bitstring => '0110' );
$c = $a->gf_multiply_modular($b, $modulus, $n);
print "Modular product of a = $a b = $b in GF(2^8) is $c\n";
# Modular product of a = 0110001 b = 0110 in GF(2^8) is 10100110
# Experiment with finding the multiplicative inverse in GF(2^8) for modulus polynomial = x^8 + x^4 + x^3 + x + 1:
print "\nTest multiplicative inverses in GF(2^3) with modulus polynomial = x^8 + x^4 + x^3 + x + 1:\n";
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";
print "@products\n";
# Experiments with finding runs of 1's and 0's in a bit pattern:
print "\nExperimenting with runs():\n";
$bv = Algorithm::BitVector->new( bitlist => [1, 0, 0, 1] );
my @bvruns = $bv->runs();
print "For bitvector: $bv";
print " the runs are: @bvruns\n";
$bv = Algorithm::BitVector->new( bitlist => [1, 0] );
@bvruns = $bv->runs();
print "For bitvector: $bv";
print " the runs are: @bvruns\n";
$bv = Algorithm::BitVector->new( bitlist => [0, 1] );
@bvruns = $bv->runs();
print "For bitvector: $bv";
print " the runs are: @bvruns\n";
$bv = Algorithm::BitVector->new( bitlist => [0, 0, 0, 1] );
@bvruns = $bv->runs();
print "For bitvector: $bv";
print " the runs are: @bvruns\n";
$bv = Algorithm::BitVector->new( bitlist => [0, 1, 1, 0] );
@bvruns = $bv->runs();
print "For bitvector: $bv";
print " the runs are: @bvruns\n";
# Experiments with primality testing of small integers:
print "\nRun the small-integer primality test on a a bunch of known primes:\n";
my @primes = (179, 233, 283, 353, 419, 467, 547, 607, 661, 739, 811, 877,
947, 1019, 1087, 1153, 1229, 1297, 1381, 1453, 1523, 1597,
1663, 1741, 1823, 1901, 7001, 7109, 7211, 7307, 7417, 7507,
7573, 7649, 7727, 7841);
foreach my $p (@primes) {
my $bv = Algorithm::BitVector->new( intVal => $p );
my $check = $bv->test_for_primality();
print "The primality test for $p: $check\n";
}
# Experiments with random bit generation for a bitvector:
print "\nGenerate 16-bit wide candidates for primality testing:\n";
foreach my $i (0..10) {
$bv = Algorithm::BitVector->new( intVal => 0 );
$bv = $bv->gen_random_bits(16);
print "\n$bv\n";
my $check = $bv->test_for_primality();
print "The primality test for " . int($bv) . ": $check\n";
}
# Experiments with constructing the min canonical form of a BitVector:
print "\nTest generating min-canonical form of a BitVector instance:\n";
foreach my $i (map {255 + 1555 * $_} 1 .. int(10000 / 1555)) {
( run in 0.775 second using v1.01-cache-2.11-cpan-39bf76dae61 )