Here is one of the problems we had for Theory of Comp. and my solution. It’s an interesting problem, but really just a an excuse to try out the CodeBeautifier plugin for MT.
4)Write a computer program that finds the smallest power of 2 that starts with a given number k. Run the program for k = 97. (For example, the smallest power of 2 that starts with 54 is 239 = 549755813888.)
#!/usr/bin/perl -w
use strict;
use bignum;
my $prefix = $ARGV[0];
my $test_num;
my $n = 0;
my $bool = 1;
while($bool)
{
$test_num = 2 ** $n;
if( $test_num =~ /^($prefix).*/ )
{ $bool = 0; }
else
{ $n = $n + 1; }
}
print "n is $n\n";
Spiffy looking. But it’s way inefficient. You’re doing the 2 ** n every time!
I agree it’s the brute force way of doing it, but what is a better way than doing successive powers of two?
Ah. You want to keep an $n counter and a running total. Each time through the loop, you += n, and *= 2 the total.
That way you only do one multiplication and one addition, rather than n multiplications.
Nice, that is much better.