Re: [FWP] Counting bits from the other end

["Bernie Cosell" <bernie@fantasyfarm.com>]

On 2 May 2000, at 20:10, Adam Rice wrote:

> Quoting Bennett Todd (bet@rahul.net):
> > That's stone cool! A quick search suggests that 37 is the smallest n
> > for which that trick works for 32-bit words; however, either the
> > smallest such divisor for a 64-bit wordsize is _gigantic_, or else
> > perl on a 32-bit platform can't compute it with the attached search
> > script.
> 
> primes 64 | head -1
> 67
> 
> Sometimes Perl is no substitute for a Maths degree :-)

Indeed, as as another side effect of some math background, note that to 
verify that you don't need to do 64-bit-arithmetic.

    if a mod b = c, then 2a mod b = 2c mod b

That is, instead of dealing with huge integers, you can just deal with 
the -remainders-, nice, small integers.  The loop to set up the 
remainders would look something like this:

    my $pow = 0 ;
    my $rem = 1 ;
    use constant divisor => 67 ;
    my @remainders ;
    for ( ; $pow < 64 ; $pow += 1, $rem *= 2)
    {
        $rem %= divisor ;
        die "Got a collision at $pow\n" if defined $remainders[$rem] ;
        $remainders[$rem] = $pow ;
    }
    for ($rem = 0 ; $rem < divisor; $rem += 1)
    {
        next if not defined $remainders[$rem] ;
        print "2^$remainders[$rem] has a remainder of $rem\n" ;
    }

And indeed, 67 works just fine..:o)

  /Bernie\
-- 
Bernie Cosell                     Fantasy Farm Fibers
mailto:bernie@fantasyfarm.com     Pearisburg, VA
    -->  Too many people, too few sheep  <--          

==== Want to unsubscribe from Fun With Perl?  Well, if you insist...
==== Send email to <fwp-request@technofile.org> with message _body_
====   unsubscribe