Re^13: Module for 128-bit integer math? (updated)

That's interesting, but there are reasons other than performance for wanting fix-width integer semantics.

Try coding this with GMP (or any arbitrary precision math):

#! perl -slw
use strict;
use Math::Int128 qw[int128 uint128];

my $ZERO = uint128( 0 );
my $ONE  = uint128( 1 );
my $ALLONES = ~ $ZERO;
my $MASK1 = $ALLONES / 3;
my $MASK2 = $ALLONES / 15 * 3;
my $MASK3 = $ALLONES / 255;
my $MASK4 = $MASK3 * 15;

sub bcount {
    my $v = shift;
    $v = $v - ( ( $v >> 1 ) & $MASK1 );
    $v = ( $v & $MASK2 ) + ( ( $v >> 2 ) & $MASK2 );
    $v = ( $v + ( $v >> 4 ) ) &  $MASK4;
    my $c = ( $v * ( $MASK3 ) ) >> 120;
    return $c;
}

my $bits = uint128( 0 );

## set every 3rd bit
$bits |= $ONE << $_ for map $_*3+1, 0 .. 42;
print $bits;

## count the bits (43)
print bcount( $bits );

## now invert them and count again. (85)
print bcount( ~$bits );

__END__
c:\test>m128.pl
194447066811964836264785489961010406546
43
85
[download]

Note: I would have supplied a GMPz version, ~~but I couldn't work out how to do it from the docs~~. There seem to be a million ways to initialise a number; a million ways to divide two numbers etc, But not so much when it comes to doing bitwise math.

Update: Here's my attempt at a GMP version of the above. Note that it doesn't just produce the wrong results, but it does so silently:

#! perl -slw
use strict;
use Math::GMPz;

my $ZERO = Math::GMPz->new( 0 );
my $ONE  = Math::GMPz->new( 1 );
my $ALLONES = ~ $ZERO;
my $MASK1 = $ALLONES / 3;
my $MASK2 = $ALLONES / 15 * 3;
my $MASK3 = $ALLONES / 255;
my $MASK4 = $MASK3 * 15;

sub bcount {
    my $v = shift;
    $v = $v - ( ( $v >> 1 ) & $MASK1 );
    $v = ( $v & $MASK2 ) + ( ( $v >> 2 ) & $MASK2 );
    $v = ( $v + ( $v >> 4 ) ) &  $MASK4;
    my $c = ( $v * ( $MASK3 ) ) >> 120;
    return $c;
}

my $bits = Math::GMPz->new( 0 );

## set every 3rd bit
$bits |= $ONE << $_ for map $_*3+1, 0 .. 42;
print $bits;

## count the bits (43)
print bcount( $bits );

## now invert them and count again. (85)
print bcount( ~$bits );

__END__
c:\test>gmpz-t.pl
194447066811964836264785489961010406546
0
0
[download]

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.

"Science is about questioning the status quo. Questioning authority".

In the absence of evidence, opinion is indistinguishable from prejudice.

Comment on Re^13: Module for 128-bit integer math? (updated) Select or Download Code

Replies are listed 'Best First'.
Re^14: Module for 128-bit integer math? (updated) by syphilis (Archbishop) on Feb 12, 2011 at 14:30 UTC
there are reasons other than performance for wanting fix-width integer semantics Definitely correct ... though I must confess that the reasons you've implicitly put forward in your demos were not exactly what I was thinking of when I acknowledged this (or tried to) in my earlier post. For a Math::GMPz rendition of your demo I would put forward the following: #! perl -slw use strict; use Math::GMPz qw(:mpz); my $ZERO = Math::GMPz->new( 0 ); my $ONE = Math::GMPz->new( 1 ); #my $ALLONES = ~ $ZERO; my $ALLONES = (Math::GMPz->new(1) << 128) - 1; my $MASK1 = $ALLONES / 3; my $MASK2 = $ALLONES / 15 * 3; my $MASK3 = $ALLONES / 255; my $MASK4 = $MASK3 * 15; my $bits = Math::GMPz->new( 0 ); ## set every 3rd bit $bits \|= $ONE << $_ for map $_*3+1, 0 .. 42; print $bits; ## count the bits (43) #print bcount( $bits ); print Rmpz_popcount($bits); ## now invert them and count again. (85) #print bcount( ~$bits ); print Rmpz_popcount($ALLONES ^ $bits); [download] I hope it doesn't miss the point ... I think the only changes are that: 1) It changes the way that $ALLONES is created; 2) It removes the need for sub bcount() Update: And, there's also now a `qw(:mpz)` in the third line. Cheers, Rob	[reply] [d/l] [select]
Re^15: Module for 128-bit integer math? (updated) by BrowserUk (Patriarch) on Feb 12, 2011 at 14:41 UTC
2) It removes the need for sub bcount() That does miss the point, which was not what the bcount() sub did, but the way it did it. The result of using bitwise math using arbitrary precision doesn't follow the fix-width integer semantics. Ie. the math isn't automatically module 2^128. That means you get quite different results: #! perl -slw use strict; use Math::GMPz; my $ZERO = Math::GMPz->new( 0 ); my $ONE = Math::GMPz->new( 1 ); #my $ALLONES = ~ $ZERO; my $ALLONES = (Math::GMPz->new(1) << 128) - 1; my $MASK1 = $ALLONES / 3; my $MASK2 = $ALLONES / 15 * 3; my $MASK3 = $ALLONES / 255; my $MASK4 = $MASK3 * 15; sub bcount { my $v = shift; $v = $v - ( ( $v >> 1 ) & $MASK1 ); $v = ( $v & $MASK2 ) + ( ( $v >> 2 ) & $MASK2 ); $v = ( $v + ( $v >> 4 ) ) & $MASK4; my $c = ( $v * ( $MASK3 ) ) >> 120; return $c; } my $bits = Math::GMPz->new( 0 ); ## set every 3rd bit $bits \|= $ONE << $_ for map $_*3+1, 0 .. 42; print $bits; ## count the bits (43) print bcount( $bits ); ## now invert them and count again. (85) print bcount( ~$bits ); __END__ C:\test>gmpz-t.pl 194447066811964836264785489961010406546 4019000903644796537894933644280473643 6698389137940470254461716813547458644 [download] Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice.	[reply] [d/l]
Re^16: Module for 128-bit integer math? (updated) by syphilis (Archbishop) on Feb 13, 2011 at 00:14 UTC
the math isn't automatically module 2^128 Quite so ... I don't think the gmp library provides a way of enforcing fixed precision. Therefore "the overflow" doesn't get automatically discarded, and you would have to remove it yourself by doing a mod(2 ** 128): #! perl -slw use strict; use Math::GMPz qw(:mpz); my $ZERO = Math::GMPz->new( 0 ); my $ONE = Math::GMPz->new( 1 ); my $MOD128 = Math::GMPz->new(1) << 128; my $ALLONES = $MOD128 - 1; my $MASK1 = $ALLONES / 3; my $MASK2 = $ALLONES / 15 * 3; my $MASK3 = $ALLONES / 255; my $MASK4 = $MASK3 * 15; my $bits = Math::GMPz->new( 0 ); ## set every 3rd bit $bits \|= $ONE << $_ for map $_3+1, 0 .. 42; print $bits; ## count the bits (43) print bcount( $bits ); ## now invert them and count again. (85) #print bcount( ~$bits ); print bcount($ALLONES ^ $bits); sub bcount { my $v = shift; $v = $v - ( ( $v >> 1 ) & $MASK1 ); $v = ( $v & $MASK2 ) + ( ( $v >> 2 ) & $MASK2 ); $v = ( $v + ( $v >> 4 ) ) & $MASK4; my $c = ( ( $v ( $MASK3 ) ) % $MOD128) >> 120; return $c; } __END__ C:\_64\pscrpt>perl buk1.pl 194447066811964836264785489961010406546 43 85 [download] Not sure what to do with the `~` operator in Math::GMPz. Currently it just does a one's complement - which is not the right thing for your purposes. I notice that Math::GMP doesn't overload the `~` operator ... perhaps Math::GMPz should do the same ? Cheers, Rob	[reply] [d/l] [select]
Re^17: Module for 128-bit integer math? (updated) by BrowserUk (Patriarch) on Feb 13, 2011 at 14:28 UTC
Re^18: Module for 128-bit integer math? (updated) by syphilis (Archbishop) on Feb 14, 2011 at 11:55 UTC
Some notes below your chosen depth have not been shown here
Re^18: Module for 128-bit integer math? (updated) by salva (Canon) on Feb 23, 2011 at 17:08 UTC
Some notes below your chosen depth have not been shown here


laziness, impatience, and hubris
	PerlMonks