Re: [Fun With Perl] Another oddity from the days of assembler

[Roland Giersig <Roland.Giersig@bigfoot.com>]

>From vlb@cfcl.com  Tue Jun 15 01:20:10 1999 - apologies for the delay - vlb]
Message-ID: <37660AD5.8FE5AA93@bigfoot.com>
Date: Tue, 15 Jun 1999 10:12:05 +0200
References: <19990614160354.24613.qmail@plover.com>

I'm a nitpicker:

Mark-Jason Dominus wrote:
> When people talk about this stuff in the C newsgroups, someone always
> comes along and spoils the fun by saying `The fastest *and* simplest
> way it to just use a lookup table.'

Yes, of course, but does it work for arbitrary large integers
(for small numbers of `arbitrary large' ;-), like the `pack/unpack'
version automatically does?

This version assumes 32-bit integers:
[yes, I know this is just for the demonstration, you would
  have written it portably otherwise...]

>     lt2 => sub {
>         for $n (0..$m) {
>            my $b = $bs[$n & 0xff];
>            $b += $bs[$n & 0xff00 >> 8] ;
>            $b += $bs[$n & 0xff0000 >> 16];
>            $b += $bs[$n & 0xff000000 >> 24];
> #           print "$n\t$b\n";
>         }
>     },

At least it has to be rewritten without hardcoded integer size:

  while($n) {
    $b += $bs[$n & 0xff];
    $n >>= 8;
  }

Still faster, easy and elegant, darn...

> Here `@bt' has been initialized with 256 values as follows:
>
>         for ($i=0; $i < 256; $i++) {
>           my $b = 0;
>           my $n = $i;
>           while ($n) { $n &= $n-1, $b++ ; }
>           $bs[$i] = $b;
>         }

A! Ha!

This of course can be rewritten as:

  @bs = map {my $b = unpack("B*", pack("L*", $_)); $b =~ tr/1//} (0..255);


But why not using the power of Memoize?

use Memoize;
memoize '_bytewise';

sub _bytewise ($) {
   my $b = unpack("B*", pack("L*", $_));
   $b =~ tr/1//;
}

sub memo ($) {
   my $n = shift;
   my $sum = 0;
   while($n) {
     $sum += _bytewise($n & 0xff);
     $n >>= 8;
   }
}

Viola!(tm) Lookup-table gets built on-the-fly...

Roland
--
perl -e '@_=@ARGV;$_="@_[-3,-2,-1]";s{([@{[$_[-1]]}])}#($0=$1.
${[qw[>$%, ()%{&", &"=, |}+&" *]]}[$@++])=~y/*=->$%&"(-){-}+,/
lusternohack /,$0#eg; print; '        -- Roland Giersig, JAPH.

==== Want to unsubscribe from this list? (Don't you love us anymore?)
==== Well, if you insist... Send mail with body "unsubscribe" to
==== fwp-request@technofile.org

</x-flowed>