Grex Systems Conference

View Responses

Grex Systems Item 66: When is 3 not really 3?
Entered by nharmon on Wed Dec 27 20:18:53 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?

10 responses total.

#1 of 10 by easlern on Wed Dec 27 20:36:03 2006:

I'm not sure about the math stuff, but I think the usual way to find the
values is to use something like:
MONDAY = 1
TUESDAY = 2
WEDNESDAY = 4
THURSDAY = 8
...

if (day | MONDAY) print "there's a monday in this value thing.";

Is that how you intended to use it?

#2 of 10 by nharmon on Wed Dec 27 20:51:14 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.

#3 of 10 by nharmon on Wed Dec 27 20:55:30 2006:

Ok, so I changed the while loop to this:

while ( $number > 0 ) {
        echo "Number: $number <br>\n";
        $theday = 1 + floor(log($number,2)+0.0002);
        echo "Day: $theday <br>\n";
        echo "<br>\n";
        $day[$theday] = "X";
        $number = $number - pow(2,floor(log($number,2)+0.0002));
}

And now everything works ok. Weird!

#4 of 10 by cross on Wed Dec 27 21:59:10 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.

#5 of 10 by easlern on Thu Dec 28 14:18:57 2006:

Oops- yeah, use bitwise and to test.

#6 of 10 by nharmon on Thu Dec 28 14:41:01 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. :)

#7 of 10 by pfv on Thu Dec 28 16:55:18 2006:

a&=b; //and 'a' & 'b' - stored back to 'a'

#8 of 10 by gull on Thu Dec 28 20:01:03 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.

#9 of 10 by nharmon on Thu Dec 28 21:22:39 2006:

One good thing about working on computers is that there is always
something to learn and be amazed about.

#10 of 10 by cross on Thu Dec 28 21:45:54 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!

Response not possible - You must register and login before posting.