Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

64-bit division anomolies (Solved.)

by BrowserUk (Patriarch)
on Feb 16, 2015 at 19:45 UTC ( [id://1116920]=perlquestion: print w/replies, xml ) Need Help??

BrowserUk has asked for the wisdom of the Perl Monks concerning the following question:

Update: salva's Math::Int64 solved the problem with none of the pain I was expecting.


When working with large (>2**63) integers on a 64-bit build of perl, division/modulus operations get screwy.

The cause is that the results are automatically morphed into floating point numbers. The problem is, they don't have the precision to hold the results:

C:\test>\perl5.18\perl\bin\perl.exe -le"printf qq[%f : %f\n], $_ % 10, + ( $_ / 10 ) for 9_000_000_000_000_000_011, 10_000_000_000_000_000_01 +1" 1.000000 : 900000000000000000.000000 1.000000 : 1000000000000000000.000000

Note the loss of precision in the division result.

In an attempt to prevent the morphing to fp, I tried integer, but that creates a different problem:

C:\test>\perl5.18\perl\bin\perl.exe -Minteger -le"printf qq[%u : %u\n] +, $_ % 10, ( $_ / 10 ) for 9_000_000_000_000_000_011, 10_000_000_000_ +000_000_011" 1 : 900000000000000001 18446744073709551611 : 17602069666338596456 C:\test>\perl5.18\perl\bin\perl.exe -Minteger -le"printf qq[%d : %d\n] +, $_ % 10, ( $_ / 10 ) for 9_000_000_000_000_000_011, 10_000_000_000_ +000_000_011" 1 : 900000000000000001 -5 : -844674407370955160

How does the division of one positive number by another positive number render a negative result? (When what should be unsigned division is done as signed?)

The latest I've tried this on is 5.18, so it might have been fixed in later builds, but that's not a solution for me at the moment.

Can anyone think of a simple work around that doesn't involve Math::BigInt or Math::Int128?


With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
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". I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Replies are listed 'Best First'.
Re: 64-bit division anomolies (Solved.)
by salva (Canon) on Feb 17, 2015 at 09:05 UTC
    A Pure Perl work-around:
    #!/use/bin/perl use strict; use warnings; sub udiv64 { my ($a, $b) = @_; return 0 if $b > $a; my $c = $a >> 1; my $d = do { use integer; $c / $b }; my $e = $a - (do { use integer; $d * $b } << 1); ($d << 1) + do { use integer; $e / $b } } use Devel::Peek; Dump udiv64(10_000_000_000_000_000_011, 10); Dump udiv64(10_000_000_000_000_000_011, 1)

      Neat. Thankyou.

      However, despite my initial misgivings of using a Math::* module with an overload interface -- mostly based on my bad experiences with using Math::BigInt way back when -- I was pleasantly surprised to discover that modifying the routine where the problem occurred from:

      sub Q2b36 { my $n = shift; ...

      to:

      sub Q2b36 { my $n = uint64( shift ); ...

      Fixed all the problems with no other changes required. About as simple as a work around for Perl's deficiencies could get.

      Once again. Thank you for Math::Int64 & Math::Int128.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      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". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
      oh.. well.. If you have time, can i ask you to comment a bit more your code?
      just to make it more appreciable by people with low mathfu as me.. ;=)?

      L*
      There are no rules, there are no thumbs..
      Reinvent the wheel, then learn The Wheel; may be one day you reinvent one of THE WHEELS.
        My method, first builds an approximation of the solution of a/b as...
        s1 = ((a / 2) / b) * 2;
        a / 2 is done using the bug-free shift-right operator (>>) and results always in a number with bit 64 unset, so we can divide it by b without incurring in the convert-to-NV bug. Again multiplying by 2 is done with the shift-left operator (<<).

        Then, we use the approximation to build the exact solution as:

        s = s1 + (a - s1 * b) / b

        Well, actually, in order to do everything using bug-free operations, the code uses the following equivalence:

        s2 = (a / 2) / b s1 = s2 * 2 s = s1 + (a - s1 * b) / b s = s2 * 2 + (a - (s2 * b) * 2) / b
        where $d is s2, and $e is (a - (s2 * b) * 2).
Re: 64-bit division anomolies (Solved.)
by syphilis (Archbishop) on Feb 17, 2015 at 03:29 UTC
    The latest I've tried this on is 5.18, so it might have been fixed in later builds

    It hasn't been - and it goes back to at least 5.16, and it affects 32-bit perls in the same way for unsigned values greater than 2 ** 31.

    I couldn't find a way to successfully perform integer division/modulation with these large unsigned values without resorting to XS (as you've done).
    (Update: Obviously, I've ignored Math::BigInt.)
    However, I'm sure the integer pragma is supposed to cater for this and I couldn't find anything in the docs to suggest otherwise.

    So I've submitted a bug report against integer for this - in case there's someone who cares enough to fix it.
    (I hit "Send" before thinking to reference the original PM post in that report ... sorry 'bout that.)

    Cheers,
    Rob
      So I've submitted a bug report against integer for this - in case there's someone who cares enough to fix it.

      Turns out that the integer pragma only works with integer values in the range -(2**63) .. (2**63-1).
      On 32-bit perls that range becomes -(2**31) .. (2**31-1).
      Yes - it's that crappy, and I doubt that anyone cares.

      It's all there in the integer docs if one reads that documentation properly - which I didn't do.

      Wiping egg off face (... yet again),
      Rob
        But still the unnecessary conversion to float when dividing two unsigned integers looks like a bug to me.

        BTW, the multiplication is also affected.

      So I've submitted a bug report against integer for this - in case there's someone who cares enough to fix it. (I hit "Send" before thinking to reference the original PM post in that report ... sorry 'bout that.)

      NP. It's more likely to get taken seriously with (only) your name attached.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      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". I'm with torvalds on this
      In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1116920]
Approved by atcroft
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others romping around the Monastery: (7)
As of 2024-03-28 12:47 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found