When is 3 not really 3?

Dec 27 20:18 UTC 2006

Background: I want to store a collection of weekdays into a database
field as a single number. So, following chmod's example I have assigned
each day of the week a power of 2 and then add them together to get the
composite.

IE:   Monday, Wednesday, Friday = 2^0 + 2^2 + 2^3 = 21

So, now how do you go backwards? Here is what I hammered out:

while ( $number > 0 ) {
        $theday = 1 + floor(log($number,2));
        $day[$theday] = "X";
        $number = $number - pow(2,floor(log($number,2)));
}

So after this, $day should be an array containing an "X" for each day of
the week. And it seems to work just fine, except in some cases. I have
traced the problem to the following:

floor(log(64,2)) = 5???

So, why is 5 the floor of 6? This also happens with 3 (floor of 3
becomes 2 for some reason), but not to 1, 2, 4, or 5. Am I missing
something?

response 2 of 10:

Dec 27 20:51 UTC 2006

That is exactly how I intended to use it. But for some reason the floor
of log(64,2) is coming out as 5.

response 4 of 10:

Dec 27 21:59 UTC 2006

ew ew ew.

Regarding #1; Surely you meant `&'.

Regarding #0, #2, #3; Don't use exponential functions.  Ew ew ew.  Use shift
and bit test operators: then you won't end up with wierd things as you
convert to floating point representation and back to integers.  Here's my
routine:

use strict;
use warnings;

my ( $m, $t, $w, $r, $f, $s, $u );
$m = 1 << 0;
$t = 1 << 1;
$w = 1 << 2;
$r = 1 << 3;
$f = 1 << 4;
$s = 1 << 5;
$u = 1 << 6;

my $d1 = $m | $w | $f;
my $d2 = $s | $u;

# Here is the magic.
sub printdays
{
        my $d = shift;
        my @days = ('Nul', 'Mon', 'Tue', 'Wed', 'Thu', 'Fri', 'Sat', 'Sun');

        $d &= ($m | $t | $w | $r | $f | $s | $u);
        foreach my $bit (1..7) {
                my $day = 0;
                if ($d & (1 << $bit - 1)) {
                        $day = $bit;
                }

                print $days[$day], "\n" if ($day)
        }
}

printdays $d1;
printdays $d2;

For things like this, always prefer integer arithmetic over floating point.

response 6 of 10:

Dec 28 14:41 UTC 2006

Wow, thanks Dan. I see how treating the days as binary place values
makes things a lot easier. I do have one question though. What does  &=
  do? It isn't in my list of operators. :)

response 8 of 10:

Dec 28 20:01 UTC 2006

I'm pretty sure the problem you were seeing was due to round-off error.  
Because of the conversion to floating point, you probably weren't 
actually getting 6, but rather 5.99999...

As cross points out, using bitwise operations eliminates that problem.  
It's also faster.

response 10 of 10:

Dec 28 21:45 UTC 2006

Unfortunately, computers force you to face the hegemony of the real number
field as the basis of elementary mathematics for most people; your method
makes a lot of sense, from a mathematical perspective, but breaks down on a
computer because computers can't really represent real numbers, but rather
rational approximations.  This is usually okay, since the rationals are
dense in the reals and with sufficient percision, the error is neglibible
for most applications.

But every now and then, you run into a problem (like this one) where the
error between the rational approximation and the real value cannot be
ignored, and then your mathematical intuition fails you and you're left
realizing that you need a representational intuition as well; specifically,
you need to understand the p-adic (where, in this case, p = 2)
representation of integers (and their ratios).

It's a bummer!