view release on metacpan or  search on metacpan

lib/Algorithm/BitVector.pm  view on Meta::CPAN

    } else {
        $run = '1';
    }
    my @bitlist = split //, "$self";
    shift @bitlist;
    foreach my $bit (@bitlist) {
        if (($bit == 0) && ($previous_bit == 0)) {
            $run .= '0';
        } elsif (($bit == 1) && ($previous_bit == 0)) {
            push @allruns, $run;
            $run = '1';
        } elsif (($bit == 0) && ($previous_bit == 1)) {
            push @allruns, $run;
            $run = '0';
        } else {
            $run .= '1';
        }
        $previous_bit = $bit;
    }
    push @allruns, $run;
    return @allruns
}

##  This method returns the "canonical" form of a BitVector instance that is obtained by
##  circularly rotating the bit pattern through all possible shifts and returning the
##  pattern with the maximum number of leading zeros.  This is also the minimum int value
##  version of a bit pattern.  This method is useful in the "Local Binary Pattern"
##  algorithm for characterizing image textures.  If you are curious as to how, see my
##  tutorial on "Measuring Texture and Color in Images."
sub min_canonical {
    my $self = shift; 
    my @intvals_for_circular_shifts = map {int($self << 1)} 0 .. $self->length();
    my $min_int_val = min @intvals_for_circular_shifts;
    return Algorithm::BitVector->new( intVal => $min_int_val, size => $self->length() );
}

##  Check if the integer value of the bitvector is a prime through the Miller-Rabin
##  probabilistic test of primality.  If not found to be a composite, estimate the
##  probability of the bitvector being a prime using this test.
sub test_for_primality {
    my $p = int(shift);
    die "\nThe primality test method test_for_primality() is intended for only " .
        "small integers --- integers that are relatively small in relation to " .
        "the largest integer that can fit Perl's 4-byte int representation:$!"
        if $p > 0x7f_ff_ff_ff;
    return "is NOT a prime" if $p == 1;
    my @probes = (2,3,5,7,11,13,17);
    foreach my $a (@probes) {
        return "is a prime" if $a == $p;
    }
    return "is NOT a prime" if any {$p % $_ == 0} @probes;
    my ($k, $q) = (0, $p-1);
    while (! ($q & 1)) {
        $q >>= 1;
        $k++;
    }
    foreach my $a (@probes) {
        my $a_raised_to_q = _powmod_small_ints($a, int($q), $p);
        next if $a_raised_to_q == 1 or $a_raised_to_q == $p - 1;
        my $a_raised_to_jq = $a_raised_to_q;
        my $primeflag = 0;
        foreach my $j (0..$k-1) {
            $a_raised_to_jq = _powmod_small_ints($a_raised_to_jq, 2, $p);
            if ($a_raised_to_jq == $p-1) {
                $primeflag = 1;
                last;
            }
        }
        return "is NOT a prime" unless $primeflag;
    }
    my $probability_of_prime = 1 - 1.0/(4 ** @probes);
    return "is a prime with probability $probability_of_prime";
}

##  This routine is for modular exponentiation of small integers, meaning the
##  integers that can be accommodated (before and after exponentiation) in the native
##  4-byte int representation.  For larger integers, a call to this function should
##  be replaced by a call to modular exponentiation of the Math::BigInt module.
sub _powmod_small_ints {
    my $base = shift;
    my $exponent = shift;
    my $mod = int(shift);
    warn "This is just a warning: The modular exponentiation method is not meant for very large numbers (IMPORTANT: This is just a very rough check on the size of the numbers involved)"
        if any {$_ > 0x0f_ff_ff_ff} (int($base), int($exponent), int($mod));
    my $result = 1;
    my $a = int($base);
    my $b = $exponent;
    while (int($b) > 0) {
        $result = ($result * $a) % $mod if int($b) & 1;
        $b = $b >> 1;
        $a = ($a * $a) % $mod;        
    }
    return $result;
}

##  This method is for a generating a bit pattern of a given size with random bits.
sub gen_random_bits {
    my $self = shift;
    my $width = shift;
    my $candidate_bits = "0b" . join '', Math::Random::random_uniform_integer($width, 0, 1);
    my $candidate = oct $candidate_bits;
    $candidate |= 1;
    $candidate |= (1 << $width-1);
    $candidate |= (2 << $width-3);
    return Algorithm::BitVector->new( intVal => $candidate );
}

sub length {
    my $self = shift;
    return $self->{size};
}

sub _check_for_illegal_params {
    my @params = @_;
    my @legal_params = qw / filename
                            size
                            intVal
                            bitlist
                            bitstring
                            hexstring
                            textstring
                          /;
    my $found_match_flag;
    foreach my $param (@params) {
        foreach my $legal (@legal_params) {
            $found_match_flag = 0;
            if ($param eq $legal) {
                $found_match_flag = 1;
                last;
            }
        }
        last if $found_match_flag == 0;
    }
    return $found_match_flag;
}

1;


=pod

=head1 NAME

Algorithm::BitVector --- A memory efficient packed representation of arbitrary sized
bit arrays and for logical and arithmetic operations on such arrays.

=head1 SYNOPSIS

    use Algorithm::BitVector;

    # Constructing a given sized bitvector of all zeros:
    $bv = Algorithm::BitVector->new( size => 7 );
    print "$bv\n";                                   # 0000000

    # Constructing a bitvector whose integer value is specified:
    $bv = Algorithm::BitVector->new( intVal => 123456 );
    print "$bv\n";                                    # 11110001001000000                          
    print int($bv);                                   # 123456

    # Constructing a bitvector from a very large integer:
    use Math::BigInt;
    $x = Math::BigInt->new('12345678901234567890123456789012345678901234567890');
    $bv = Algorithm::BitVector->new( intVal => $x );
         
    # Constructing a bitvector from a given bit string:
    $bv = Algorithm::BitVector->new( bitstring => '00110011' );
       
    # Constructing a bitvector from an ASCII text string:
    $bv = Algorithm::BitVector->new( textstring => "hello\njello" );

    # Constructing a bitvector from a hex string:
    $bv = Algorithm::BitVector->new( hexstring => "68656c6c6f" );

    # Constructing a bitvector from a bit list passed as an anonymous array:
    $bv = Algorithm::BitVector->new( bitlist => [1, 1, 0, 1] );

    # Constructing a bitvector from the contents of a disk file:
    $bv = Algorithm::BitVector->new( filename => 'testinput.txt' );
    $bv1 = $bv->read_bits_from_file(64);         # bitvector from the first 64 bits
                                                 # and so on


=head1 CHANGES

Version 1.26 incorporates the following changes: (1) It allows you to carry out
slice-based set and get operations on a BitVector object. The two new methods for
these operations are named C<get_slice()> and C<set_slice()>. (2) It includes a new
method named C<min_canonical()> that returns a circularly rotated version of a
BitVector with the least integer value.  For obvious reasons, this version would also
have the largest number of leading zeros. And (3) It fixes a bug in the
implementation of the method C<gf_divide_by_modulus()>.

Version 1.25 incorporates bugfix for the case when you try to construct a bitvector
of a specified length from a large integer that is supplied to the module constructor