#### Do you have a question? Post it now! No Registration Necessary. Now with pictures!

**posted on**

July 29, 2008, 12:28 pm

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

## Re: Extracting bits out of huge numbers

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

## Re: Extracting bits out of huge numbers

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

## Re: Extracting bits out of huge numbers

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

## Re: Extracting bits out of huge numbers

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

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

wrote:

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___systemSecond:

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

wrote:

## Re: Extracting bits out of huge numbers

I am familiar with multi precision and multi base concepts.

>>Example Bits 16 bis 12 should result in 0b00001 == 0x1 == 1

>> Bits 17 bis 12 should result in 0b100001 == 0x21 == 33

what do you mean by

"Bits 16 bis 12"

and

"Bit 17s bis 12"

what is "bis" ?

BugBear

## Re: Extracting bits out of huge numbers

'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

--

And if you wanna make sense / Whatcha looking at me for? (Fiona Apple)

* ben@morrow.me.uk *

## Re: Extracting bits out of huge numbers

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::Pari 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

## Re: Extracting bits out of huge numbers

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.

Ben

--

Heracles: Vulture! Here's a titbit for you / A few dried molecules of the gall

From the liver of a friend of yours. / Excuse the arrow but I have no spoon.

(Ted Hughes, [ Heracles shoots Vulture with arrow. Vulture bursts into ]

'Alcestis') [ flame, and falls out of sight. ] ben@morrow.me.uk

## Re: Extracting bits out of huge numbers

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

## Re: Extracting bits out of huge numbers

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

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

#### Site Timeline

- » FAQ 1.3 Which version of Perl should I use?
- — Next thread in » PERL Discussions

- » How to find ioctl.ph - is my version of perl busted?
- — Previous thread in » PERL Discussions

- » s suffix question
- — Newest thread in » PERL Discussions

- » SSD partition alignment revisited
- — The site's Newest Thread. Posted in » Computer Hardware