Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Perl > Perl Misc > Extracting bits out of huge numbers

Reply
Thread Tools

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

 
Reply With Quote
 
 
 
 
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
 
Reply With Quote
 
 
 
 
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)
> > $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

>
> 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
 
Reply With Quote
 
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


 
Reply With Quote
 
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


 
Reply With Quote
 
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 = ...;

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


 
Reply With Quote
 
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;
# 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
 
Reply With Quote
 
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:

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

or just

my $mask = 0x0001_F000;

--
Affijn, Ruud

"Gewoon is een tijger."
 
Reply With Quote
 
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:
>
> 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

--
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)
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Memory error due to the huge/huge input file size tejsupra@gmail.com Python 3 11-20-2008 07:21 PM
Hell of a time extracting bits from a vector Idgarad Perl Misc 5 03-19-2008 01:10 PM
extracting front bits from an unsigned long long? Digital Puer C Programming 36 11-13-2005 12:05 PM
8-Bits vs 12 or 16 bits/pixel; When does more than 8 bits count ? Al Dykes Digital Photography 3 12-29-2003 07:08 PM
win XP 32 bits on a 64 bits processor.. Abbyss Computer Support 3 11-13-2003 12:39 AM



Advertisments