Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

Re: How can I calculate the right combination of postage stamps?

by Taulmarill (Deacon)
on Nov 26, 2008 at 16:15 UTC ( [id://726147]=note: print w/replies, xml ) Need Help??


in reply to How can I calculate the right combination of postage stamps?

Was kind'a bored, so i worked on a perl solution. This should be much faster:

#!/usr/bin/perl use strict; use warnings; my $desired_postage = $ARGV[0] || 1.51; $desired_postage = int $desired_postage * 100; my @stamps = sort { $a <=> $b } grep { chomp; $_ < $desired_postage } map { int $_ * 100 } grep { ! /^#/ } <DATA>; my $exact = grep { $_ == $desired_postage } @stamps; print "Exact postage: " . $exact / 100 . "\n" if $exact; my $dim_max = 6; recurse( $desired_postage, [] ); sub recurse { my( $rest, $select ) = @_; if ( $rest == 0 ) { print $_ / 100 . " " for @$select; print "\n"; return; } return if @$select >= $dim_max; my @filtered = grep { $_ >= $rest / ($dim_max - @$select) and $_ <= $rest } @stamps; @filtered = grep{ $_ <= $select->[-1] } @filtered if $select->[-1] +; for my $stamp ( sort{ $b <=> $a } @filtered ) { recurse( $rest - $stamp, [ @$select, $stamp ] ); } return; }


Also i made integers of all values, because apearently on a Pentium IV 1.51 - 0.87 - 0.42 - 0.1 - 0.1 - 0.02 != 0

Replies are listed 'Best First'.
Re^2: How can I calculate the right combination of postage stamps?
by caddict (Initiate) on Nov 28, 2008 at 14:46 UTC
      Also i made integers of all values, because apearently on a Pentium IV 1.51 - 0.87 - 0.42 - 0.1 - 0.1 - 0.02 != 0
    

    It fails on AMD as well...

    bc gives the correct output. This is a sweet bug in Perl, i presume... 8-{

      That's not a bug in Perl. It's an artifact of using floating point numbers. There are many numbers that cannot be represented exactly in floating point.

      At a glance, it appears that none of those would be exactly represented in the IEEE floating point formats. (I could be wrong.) So there would be some error in the calculation in any language, on any processor.

      G. Wade

        Strictly, it's not because it's floating point, it's because it's binary floating point.

        When decimal 1.51 is converted to a binary fraction the result is:

          1.1000_0010_1000_1111_0101_1100_0010_1000_1111_0101_1100_0010_1000_1111_0101_1100_0010_1000_1111_0101...
        
        which you can see is a repeating binary fraction.

        As you say, most decimal fractions are like this... so before any errors can be introduced by rounding and what not, most decimal fractions have a built-in "representation" error.

        Most of the time you won't see the "representation" error, because conversion back to decimal rounds it off. This can lead to bafflement when two values look the same when printed out, but fail $x == $y. Addition and subtraction are the more difficult floating point operations, so you're more likely to see the problems there. Consider:

        print 1.09 - 1, "\n" ; print "0.84 - 0.34 == ", 0.84 - 0.34, ( 0.84 - 0.34 == 0.5 ? " ==" : " but !=" ), " 0.5\n" ;
        which gives:
          0.0900000000000001
          0.84 - 0.34 == 0.5 but != 0.5
        
        it really makes me wonder why we persist in using binary floating point for decimal arithmetic !

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others musing on the Monastery: (6)
As of 2024-03-29 09:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found