Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??
you would have to remove it yourself by doing a mod(2 ** 128):

That's exactly what I wish to avoid. It's not even so much to do with having to perform the modulo, (pain in the ass though that it is). It's more knowing when it needs to be done.

For some calculations, doing them at arbitrary precision and doing a single modulo operation at the end will produce the right result, but at the cost of all the intermediate calculations being done at far higher precision, and therefore much more slowly, than is wanted for the final result.

As (just) an example of this, the following compares performing 128-bit FNV1 and FNV1a hashing, both fixed precision; and infinite precision with the mod'ing done per step, and once at the end:

#! perl -slw use strict; use Benchmark qw[ cmpthese ]; use Math::Int128 qw[ uint128 uint128_to_hex ]; use Math::GMPz; sub FNV_1_128 { my $s = shift; my $h = uint128( '144066263297769815596495629667062367629' ); my $p = uint128( '309485009821345068724781371' ); $h *= $p, $h ^= $_ for unpack 'C*', $s; return $h; } sub FNV_1a_128 { my $s = shift; my $h = uint128( '144066263297769815596495629667062367629' ); my $p = uint128( '309485009821345068724781371' ); $h ^= $_, $h *= $p for unpack 'C*', $s; return $h; } sub FNV_1_128_gmpz { my $s = shift; my $h = Math::GMPz->new( '144066263297769815596495629667062367629' + ); my $p = Math::GMPz->new( '309485009821345068724781371' ); my $m = Math::GMPz->new( 1 ) << 128; $h *= $p, $h ^= $_ for unpack 'C*', $s; return $h % $m; } sub FNV_1a_128_gmpz { my $s = shift; my $h = Math::GMPz->new( '144066263297769815596495629667062367629' + ); my $p = Math::GMPz->new( '309485009821345068724781371' ); my $m = Math::GMPz->new( 1 ) << 128; $h ^= $_, $h *= $p for unpack 'C*', $s; return $h % $m; } sub FNV_1_128_gmpz2 { my $s = shift; my $h = Math::GMPz->new( '144066263297769815596495629667062367629' + ); my $p = Math::GMPz->new( '309485009821345068724781371' ); my $m = Math::GMPz->new( 1 ) << 128; $h *= $p, $h ^= $_, $h %= $m for unpack 'C*', $s; return $h; } sub FNV_1a_128_gmpz2 { my $s = shift; my $h = Math::GMPz->new( '144066263297769815596495629667062367629' + ); my $p = Math::GMPz->new( '309485009821345068724781371' ); my $m = Math::GMPz->new( 1 ) << 128; $h ^= $_, $h *= $p, $h %= $m for unpack 'C*', $s; return $h; } our $text = do{ local( @ARGV, $/ ) = $0; <> }; print length $text; cmpthese -1, { int128 => q[ my $fnv1 = uint128_to_hex( FNV_1_128( $text ) ); my $fnv1a = uint128_to_hex( FNV_1a_128( $text ) ); ], GMPz => q[ my $fnv1 = Math::GMPz::Rmpz_get_str( FNV_1_128_gmpz( $text ), + 16 ); my $fnv1a = Math::GMPz::Rmpz_get_str( FNV_1a_128_gmpz( $text ) +, 16 ); ], GMPz2 => q[ my $fnv1 = Math::GMPz::Rmpz_get_str( FNV_1_128_gmpz2( $text ) +, 16 ); my $fnv1a = Math::GMPz::Rmpz_get_str( FNV_1a_128_gmpz2( $text +), 16 ); ], }; __END__ C:\test>FNV128.pl 2455 Rate GMPz GMPz2 int128 GMPz 14.1/s -- -77% -95% GMPz2 61.4/s 334% -- -78% int128 274/s 1840% 347% --

Notice how the _gmpz2() functions are 3 1/2 times faster than the _gmpz() functions, despite that they perform 2,455 modulo 128 operations on intermediate values, versus the latter's single modulo 128 at the end. The cost of carrying that extra precision adds up fast.

But far more pernicious are calculations where not performing the modulo operation at the appropriate times actually changes the outcome of the calculation. I went through the same thing trying to use Math::BigInt to perform 64-bit math before I had a 64-integer capable Perl. You start sticking in modulo ops all over the place with the inevitable disastrous affects on both the readability of the calculation and performance. And then you start trying to back them out again one at a time and verifying the results to ensure you haven't screwed the calculation up in the process.

The performance affects are bad enough. But the affect on readability and maintainability of complex calculations is simply too high to pay. Same thing goes for using the function call interface rather than the overloaded interface. It renders simple calculations all but unreadable; and complex ones nigh impossible to construct.

That's why I asked up front about a 128-bit math package, not an infinite precision math package. And why I tried really hard to avoid this debate. (Note. Not with you, given that you've provided me with the to both packages :)


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.

In reply to Re^17: Module for 128-bit integer math? (updated) by BrowserUk
in thread Module for 128-bit integer math? by BrowserUk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (2)
As of 2024-04-26 02:52 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found