Re: [FWP] Counting bits from the other end

[Bennett Todd <bet@rahul.net>]

2000-05-01-16:17:07 Bernie Cosell:
> The solution I came up with used division remainders.  At the time I was 
> programming the PDP-1, which had 18-bit words and I noticed that if you 
> take the 18 powers-of-two and divide them by _nineteen_ you get all-
> distinct remainders [plus, as a nice benefit, zero gets you a remainder 
> of zero so you don't even need to test for zero!]

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.

Thanks for this seriously cool trick!

P.S. I tried Math::BigInt :constant, but it blew Out Of Memory
instantly, boo.

-Bennett
#!/usr/bin/perl -w
use strict;

# Bernie Cosell points out in ``[FWP] Counting bits from the other
# end'' that N % 19 has no collisions for powers of two in 0..2^17,
# which means you can do a little thinking ahead and pluck off the
# dispatch on table[x^(x&x-1)%19] as long as you're using 18-bit
# words. So this finds the smallest such modulus for other word
# sizes.

$| = 1;

print &find_smallest($_), "\n" for @ARGV;
exit 0;

sub find_smallest {
	my ($wordsize) = @_;
	my $try = $wordsize;
	try: while ($try++) {
		my %dup;
		print "$try\r";
		for (0 .. $wordsize-1) {
			my $remainder = (1<<$_)%$try;
			next try if exists $dup{$remainder};
			$dup{$remainder} = 1;
		}
		return $try;
	}
}

PGP signature