Extracting bits out of huge numbers

[hofer]

Hi,

I'd like to work with huge integers (> 64 bit precision)

Thus I can't use ordinary perl integers.

I thought Math::BigInt wouldn't be a too bad choice.


It's easy enough go create BigInts.
my $a = Math::BigInt->new("0x7777666655544443333222211110000");
my $b = Math::BigInt->new("0x1111111111111111111111111111111");

Calculating with them is also fine:
$a->badd($b); # $a = $a + $b


Now I would like to extract certain bits out of this huge number:

Example Bits 16 bis 12 should result in 0b00001 == 0x1 == 1
Bits 17 bis 12 should result in 0b100001 == 0x21 == 33



So far I see two ways of doing this conversion.

However I'm not really appealed by either solution.

Do you know anything faster / better or even another CPAN module?

# extract bits out of binary string
sub extbits { #
my ($val,$msb,$lsb) = @_; # $val must be Math::BigInt;
my $asbinstr = $val->as_bin(); # nun als binaer string
my $withoutprefix = substr($asbinstr,2); # fuehrendes '0b'
entfernen
my $substr = substr($withoutprefix,-$msb-1,$msb-$lsb+1); # den
substring extrahieren
$substr = 0 if $substr eq ""; # sollte mindestens einen character
enthalten
my $result = Mat::BigInt->new("0b".$substr); # zurueck in
Math::BigInt verwandeln
return $result;
} #

# extract bits via shifts operations follwed by a bit wise and
sub extbits { #/*{{{*/
my ($val,$msb,$lsb) = @_; # $val must be Math::BigInt;
my $mask = Math::BigInt->new(1); # create a 1
$mask->blsft($msb-$lsb+1); # 2 ^ (number of bits to extract)
$mask->bsub(1); # now we have a mask
my $tmp = $val->copy->brsft($lsb); # shift input value to the
right
return $tmp->band($mask);
} #/*}}}*/



Thanks in advance for any other suggestions
like rewriting the function to accelerate it or using another module.


bye


H

 

[sisyphus]

Hi,

I'd like to work with huge integers (> 64 bit precision)

Thus I can't use ordinary perl integers.

I thought Math::BigInt wouldn't be a too bad choice.

It's easy enough go create BigInts.
my $a = Math::BigInt->new("0x7777666655544443333222211110000");
my $b = Math::BigInt->new("0x1111111111111111111111111111111");

Calculating with them is also fine:
$a->badd($b); # $a = $a + $b

Now I would like to extract certain bits out of this huge number:

Example Bits 16 bis 12 should result in  0b00001 == 0x1 == 1
            Bits 17 bis 12 should result in 0b100001 == 0x21 == 33

So far I see two ways of doing this conversion.

However I'm not really appealed by either solution.

Do you know anything faster / better or even another CPAN module?

Math::GMP will allow you to access individual bits. I would expect it
to be siginificantly faster than Math::BigInt, though I haven't done
any benchmarking.

use warnings;
use Math::GMP;

$x = Math::GMP->new('12344' x 7);

# print the 10 least siginificant bits:

print Math::GMP::gmp_tstbit($x, $_) for reverse(0..9);
print "\n";

Cheers,
Rob

 

[hofer]

How about using 'unpack'?

Hi, Thrill5,

Thanks for the answer.

If I don't miss something, then pack and unpack allow to (hmmm) pack
and
unpack binary strings into a byte structure.

My second requirement is to perform operations like + - * / and or xor
% on these numbers.
I think this wouldn't be possible.

bye

H

 

[hofer]

Hi sisiphus,

I'll look at Math::GMP

In the doc I saw an interesting suggestion, which is to use
Math::BigInt, but let it use the faster libraries of Math::GMP.

This means probably, that I would run faste, but would stay backwards
compatible for the ones not having Math::GMP.

The suggested use statement is:

use Math::BigInt lib => 'GMP';

The function Math::GMP::gmp_tstbit() sounds very appealing to test a
few
bits of a big number.

However if I want to extract for example bits [967:13] , then the
approach to shift to the right and logical and then with a mask might
be
faster.
I have to try.


thanks and bye


H

 

[hofer]

Hi Bugbear,

I'm not that gifted in explaining, but I t'll try.

First if your question concerns the representation of binary numbers:
Then look at http://en.wikipedia.org/wiki/Binary_numeral_system

Second:
ust a small example however just with 8 bit numbers.
Please keep in mind, that I really want to work with really big
numbers.

well an unsigned 8 bit number can have values from
0 to 255

The number 26 for example would be represented as
00011010 in binary format
For small numbers I could just use
printf("%08b",26) to get the binary string
# result should be 00011010

going from binary string representation to decimal could be done with
the oct() function
I just have to prefix the bit string with "0b" and pass it to the
oct() function.
print oct("0b"."00011010");
# result shoud be 26

the bits of this number are number from right to left so the bt on the
right is bit 0 and the bit on the left is bit7
the number 26

would have
bit 0 = 0
bit 1 = 1
bit 2 = 0
bit 3 = 1
bit 4 = 1
bit 5 = 0
bit 6 = 0
bit 7 = 0

if I want to extract bits 4 to bits 2 from my number 26 it would mean
taking
bit 2 = 0
bit 3 = 1
bit 4 = 1
which is 110 or 0b110 (0b marks a binary number in perl)
and would be equivalent to number 6 in decimal.

so I could do for example

$num = 26; #
$size=8; # tha value has a max size of 8 bits
$bitfrom=4;
$bitto=2;
$bitstring = sprintf("%0%sizeb",$num); # -> "00011010"
# the first character in this string is bit 7, tha last one is bit 0
so to get bits 4 to 2 I could now do
$bits4to2 = substr($bitstring,-$from,$from-$to+1); # -> "110"
$num4to2 = oct("0b".$bits4to2); # -> 6

I hope that clarified a little.

bye H

 

[Ben Morrow]

what do you mean by
"Bits 16 bis 12"

and

"Bit 17s bis 12"

what is "bis" ?

'To' in English, 'through' or 'thru' in American. So, the OP wishes to
look at only the bits from bit 16 to bit 12; something like

my $num = ...;

my $mask = 0;
$mask |= 1<<$_ for 12..16;
$num &= $mask;
$num >>= 12;

would do what he wants, but slowly, and with small(ish) integers only.

Ben

 

[hofer]

Apologies,


I posted the same message to a German and en ENglish news group.
'bis' is the word I forgot to translate to Englisch :-( shame on me.



I wanted to extrect the bits 12 to 16, assuming, that the lsb is
numbereed 0


bye

H

 

[sisyphus]

I wanted to extrect the bits 12 to 16, assuming, that the lsb is
numbereed 0

If it's the same bits each and every time, then a combination of
bitwise & and right-shifting (as already suggested) would be best:

$and = (2 ** 16) + (2 ** 15) + (2 ** 14) + (2 ** 13) + (2 ** 12);
for(@nums) {
$wanted = ($_ & $and) >> 12;
# do additional stuff
}

where both $wanted and the elements of @nums could be Math::BigInt or
Math::GMP or Math:ari or Bit::Vector objects (to name a few
options). Each of those modules overloads both '&' and '>>', so the
above (untested) code should work as is - irrespective of which module
you use.

Cheers,
Rob

 

[Dr.Ruud]

sisyphus schreef:

$and = (2 ** 16) + (2 ** 15) + (2 ** 14) + (2 ** 13) + (2 ** 12);

Or as Ben Morrow suggested:

my $mask = 0;
$mask |= 1 << $_ for 12 .. 16;

or just

my $mask = 0x0001_F000;

 

[Ben Morrow]

sisyphus schreef:


Or as Ben Morrow suggested:

my $mask = 0;
$mask |= 1 << $_ for 12 .. 16;

I particularly don't like using 2**$N for bit operations, as it returns
a floating-point result.

or just

my $mask = 0x0001_F000;

Well, yes , but I was assuming the bits to mask in were not known
until runtime.

Ben

 

[Dr.Ruud]

Ben Morrow schreef:

Ruud:

I particularly don't like using 2**$N for bit operations, as it
returns a floating-point result.


Well, yes , but I was assuming the bits to mask in were not known
until runtime.

Yeah, my "Or" was to be read as "Rather" and my "or just" was to be read
as "or if feasible".

 

[Peter J. Holzer]

sisyphus schreef:


Or as Ben Morrow suggested:

my $mask = 0;
$mask |= 1 << $_ for 12 .. 16;

Or use the formula used by hofer in his original posting which doesn't
need a loop ;-)

hp

 

[sln]

Hi,

I'd like to work with huge integers (> 64 bit precision)

Thus I can't use ordinary perl integers.

I thought Math::BigInt wouldn't be a too bad choice.


It's easy enough go create BigInts.
my $a = Math::BigInt->new("0x7777666655544443333222211110000");
my $b = Math::BigInt->new("0x1111111111111111111111111111111");

Calculating with them is also fine:
$a->badd($b); # $a = $a + $b


Now I would like to extract certain bits out of this huge number:

Example Bits 16 bis 12 should result in 0b00001 == 0x1 == 1
Bits 17 bis 12 should result in 0b100001 == 0x21 == 33



So far I see two ways of doing this conversion.

However I'm not really appealed by either solution.

Do you know anything faster / better or even another CPAN module?

# extract bits out of binary string
sub extbits { #
my ($val,$msb,$lsb) = @_; # $val must be Math::BigInt;
my $asbinstr = $val->as_bin(); # nun als binaer string
my $withoutprefix = substr($asbinstr,2); # fuehrendes '0b'
entfernen
my $substr = substr($withoutprefix,-$msb-1,$msb-$lsb+1); # den
substring extrahieren
$substr = 0 if $substr eq ""; # sollte mindestens einen character
enthalten
my $result = Mat::BigInt->new("0b".$substr); # zurueck in
Math::BigInt verwandeln
return $result;
} #

# extract bits via shifts operations follwed by a bit wise and
sub extbits { #/*{{{*/
my ($val,$msb,$lsb) = @_; # $val must be Math::BigInt;
my $mask = Math::BigInt->new(1); # create a 1
$mask->blsft($msb-$lsb+1); # 2 ^ (number of bits to extract)
$mask->bsub(1); # now we have a mask
my $tmp = $val->copy->brsft($lsb); # shift input value to the
right
return $tmp->band($mask);
} #/*}}}*/



Thanks in advance for any other suggestions
like rewriting the function to accelerate it or using another module.


bye


H

0x7777666655544443333222211110000

Hex Bits Bytes
------------------------------------
7777666 64 8 (really: 63 7)
65554444 64 8
33332222 64 8
11110000 64 8
------------------------------------
Total 256 32


0x1111111111111111111111111111111

Hex Bits Bytes
------------------------------------
1111111 64 8 (really: 63 7)
11111111 64 8
11111111 64 8
11111111 64 8
------------------------------------
Total 256 32


I count 256 bits here. This is strange.
In reality, there is no use in having integers that
specific unless you need unique identifiers.

In the case of that many individuals, and I can only
think on a macro level here, it would be the amount
of stars in the universe. In that case, I believe it
still falls short, not sure.

On the atomic level, and you mention "precision", probably
this is a misnomer as a macro, there is no measurement below
sub-micron (1/10), a simple 6 decimal places.

I don't know but there are other possiblilites here though.
Like, in a weird way, you are somehow running a piramyd simulation,
statistics, where every digit counts, jacking up all intermediate
calculations to whole numbers until the final result.

Regardless, you need to do work on and have a big matissa, so to speak.
The Calculator program under windows is very interresting, you may
want to take a look at it.

There is a function (enable advanced scientific) x^y.
If you put in 2^100 you get 1267650600228229401496703205376.
That would be 100 bits on my 32 bit integer machine.

Apparently "BigInt" means it, but is it so hard to do?
Why don't you do your own?

Binary math is simple, you don't need 100 bit registers to do it.
That module simply uses the available machine register width, the
wider the better, to simulate extended integer arithmatic.

On the hardware side, if my data register were 16 bit, I would use 8x8 bit
chunks for calculations, 32 bit, 16x16, 64 bit, 32x32, etc..

Doesen't matter how big the width is of the input. I'm sure this is
nothing new, this is a simulation, intermediate results, the way it
was before 80 bit data registers in floating point chips doing similar
things by example.

For example, if my machine were 32 bit integer data width registers,
I would create an array of 16 bit integers large enough to represent
the largest number of bits needed in the calculation.
Doesen't matter how big the array is.

The logical binary math progresses upward, from one 16 bit frame to the next,
until the resultant array is populated.

So it is possible to do binary calculations for as much as you have memory
to create an array of integers. I haven't calculate 2^4,000,000 but I assume
its very large array.

Concerning retreiveing bits of that very large number, how hard would it
be to shift the frame, knowing its size, to the index of the array, of the
bits in question? Not hard at all, its simple, and that bit number will fit
into a 32 bit register. Its quick. If bits are on adjacent frames, algorithmacally
its easy.

Remember, this does not use strings at all. Integer arithmatic is the easiest
thing in the world. But your not doing trig are you...

This would be trivial... So I suggest you roll your own. I won't do it, although
I could.

--

256 bit example (from above) ADDITION, 16 bit Frame pseudocode:

@a = (0x0000,0x0777,0x7666,0x6555,0x4444,0x3333,0x2222,0x1111,0x0000);
@b = (0x0000,0x1111,0x1111,0x1111,0x1111,0x1111,0x1111,0x1111,0x1111);
@c = ();

In this case you would work the array frame (index) from the largest to smallest.
In reality, the array's should be reversed, but thats details when thier populated.
Do the frame calculation, carry over remainder to next frame, continue, populate
array @c.

Given the frame size, its trivial to find a sequential series of bits, even if overlapping
frames.


Let me know if this sounds about right.

sln

 

[sln]

On the atomic level, and you mention "precision", probably
this is a misnomer as a macro, there is no measurement below
sub-micron (1/10), a simple 6 decimal places.

To clarify... that can be manufactured.

sln

 

[hofer]

Hi,

Just some update:

The solution, that works without any additional perl modules and that
will benefit from Math::BigInt::GMP if it is installed is:

use Math::BigInt lib => 'GMP';

# extract bits via a shift operations follwed by a bit wise and
sub extbits { #/*{{{*/
my ($val,$msb,$lsb) = @_; # $val must be Math::BigInt;
my $mask = Math::BigInt->bone()->blsft($msb-$lsb+1)->bsub(1);
return $val->copy->brsft($lsb)->band($mask);

} #/*}}}*/

following example runs now for me in 15 seconds if Math::BigInt::GMP
doesn't exist and in 10 secodns if it does.

my $v1 = Math::BigInt->new("0x".( "76543210"x6));
print $v1->as_hex(),"\n";
my $v2;
for(my $i=0;$i<300;$i++){
for(my $j = 0; $j < 64;$j++){
$v2 = extbits($v1,$j+66,$j+50);
print($v2->as_hex(),"\n") if($i==0);
}
}


The other option I found is the CPAN module

Bit::Vector

I didn't try how fast it is for arithmetics, but for bit field
extraction /
copying / concatenation it's rather quick (run time 1 s)

Disadvantage / advantage:
The max size (in bits) for a bit vector has to be set during the
vector creation.

use Bit::Vector;

ub extbitsbv { #
my($v,$from,$to) = @_;
my $len = $from-$to+1;
my $v2 = Bit::Vector->new($len);
$v2->Interval_Copy($v,0,$to,$len);
return $v2;
} #

my $v1 = Bit::Vector->new_Hex(32*6,"76543210"x6);
my $v2;
print $v1->to_Hex(),"\n";
for(my $i=0;$i<300;$i++){
for(my $j = 0; $j < 64;$j++){
$v2 = extbitsbv($v1,$j+66,$j+50);
print($v2->to_Hex(),"\n") if($i==0);
}
}


bye


H