Velocity Reviews > Perl > Extracting bits out of huge numbers

# Extracting bits out of huge numbers

hofer
Guest
Posts: n/a

 07-29-2008
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)
my \$tmp = \$val->copy->brsft(\$lsb); # shift input value to the
right
} #/*}}}*/

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

bye

H

sisyphus
Guest
Posts: n/a

 07-30-2008
On Jul 29, 10:28*pm, hofer <(E-Mail Removed)> wrote:
> 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
Guest
Posts: n/a

 07-31-2008
On Jul 30, 1:23 am, "Thrill5" <(E-Mail Removed)> wrote:
> "hofer" <(E-Mail Removed)> wrote in message
>
> news:(E-Mail Removed)...
>
>
>
> > 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)
> > my \$tmp = \$val->copy->brsft(\$lsb); # shift input value to the
> > right
> > } #/*}}}*/

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

>
> > bye

>
> > H

>

Hi, Thrill5,

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
Guest
Posts: n/a

 07-31-2008
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

On Jul 30, 4:12 am, sisyphus <(E-Mail Removed)> wrote:
> On Jul 29, 10:28 pm, hofer <(E-Mail Removed)> wrote:
>
>
>
> > 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
Guest
Posts: n/a

 07-31-2008
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

On Jul 30, 10:32 am, bugbear <bugbear@trim_papermule.co.uk_trim>
wrote:
> hofer wrote:
> > Hi,

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

>
> I don't understand your examples
>
> BugBear

Ben Morrow
Guest
Posts: n/a

 07-31-2008

Quoth bugbear <bugbear@trim_papermule.co.uk_trim>:
> hofer wrote:
> >>
> >>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" ?

'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 = ...;

\$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)
* http://www.velocityreviews.com/forums/(E-Mail Removed) *

hofer
Guest
Posts: n/a

 07-31-2008
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

On Jul 31, 6:55 am, bugbear <bugbear@trim_papermule.co.uk_trim> wrote:
> hofer wrote:
> > 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 athttp://en.wikipedia.org/wiki/Binary_numeral_system

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

sisyphus
Guest
Posts: n/a

 08-01-2008
On Aug 1, 7:18*am, hofer <(E-Mail Removed)> wrote:

>
> 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;
}

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
Guest
Posts: n/a

 08-01-2008
sisyphus schreef:

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

Or as Ben Morrow suggested:

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

or just

--
Affijn, Ruud

"Gewoon is een tijger."

Ben Morrow
Guest
Posts: n/a

 08-01-2008

Quoth "Dr.Ruud" <(E-Mail Removed)>:
> sisyphus schreef:
>
> > \$and = (2 ** 16) + (2 ** 15) + (2 ** 14) + (2 ** 13) + (2 ** 12);

>
> Or as Ben Morrow suggested:
>
> \$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
>

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. ] (E-Mail Removed)