Re: Power of two round up.
by I0 (Priest) on Dec 15, 2000 at 23:41 UTC
|
local $_ = (shift)-1;
$_ |= $_>>1; $_ |= $_>>2; $_ |= $_>>4; $_ |= $_>>8; $_ |= $_>>16;
return ++$_
| [reply] [d/l] |
|
I'm amazed at how clever this is, and I'm going to use it
in my program.
Thanks a lot.
| [reply] |
|
Although it's a technique more appropriate in a C program.
In Perl, log($_)/log(2) benchmarks faster.
(assuming it rounds properly at the boundaries)
Update: My earlier timethese qq{} may have been misleading.
With timethese sub{} the | >> method comes out faster
| [reply] |
|
|
|
Just to give Dominus more heebie jeebies :)
sub round_up {
local $_ = (shift)-1;
my $num = (2**int(log($_)/log(2)))-1;
return ++($_ |= $num);
}
| [reply] [d/l] |
|
sub shifty {
my $v = (shift)-1;
map { return ++$v } map { $v |= $v >> $_ } (1,2,4,8,16);
}
or alternately (the readable version):
sub shifty2 {
my $v = (shift)-1;
$v |= $v >> $_ foreach (1,2,4,8,16);
return ++$v;
}
i don't know why i was compelled to post that, but i knew one could reduce the repition and possibly obfuscate the code a little with some obviously useless uses of map doing things it wasn't meant to do...
my $0.02;
jynx | [reply] [d/l] [select] |
|
#or perhaps
$w=32; $v |= $v>>($w>>=1) while $w;
| [reply] [d/l] |
Re (tilly) 1: Power of two round up.
by tilly (Archbishop) on Dec 15, 2000 at 23:15 UTC
|
sub binround {
my $out = 1;
my $in = shift;
while ($in) {
$in >>= 1;
$out += $out;
}
$out;
}
| [reply] [d/l] |
|
sub next_pwr {
my ($x,$p) = (@_,2); # default to next_pwr(X,2)
my $log = log($x)/log($p);
$log = int($log+1) if $log != int($log);
return $p**$log;
}
You can even add a log() memoization in there:
{
my %LOG = (2 => log(2)); # most common
sub next_pwr {
my ($x,$p) = (@_,2); # default to next_pwr(X,2)
# assertions, etc.
die "illegal base: $p" if $p < 2;
return 1 if $x == 1;
$p = int $p;
my $log =
($LOG{$x} ||= log($x)) / ($LOG{$p} ||= log($p));
$log = int($log+1) if $log != int($log);
return $p ** $log;
}
}
japhy --
Perl and Regex Hacker | [reply] [d/l] [select] |
Re: Power of two round up.
by runrig (Abbot) on Dec 15, 2000 at 23:41 UTC
|
my $num = 17;
my $nlog = 2**(int(log($num)/log(2))+1);
print $nlog;
| [reply] [d/l] |
Re: Power of two round up.
by c-alpha (Novice) on Aug 26, 2023 at 13:59 UTC
|
With a little help from POSIX, and remembering some basics about polyadic number systems, i.e. with the help of the natural logarithm, an IMHO straightforward implementation can be made:
use POSIX qw(ceil);
sub powround {
my ( $x, $base ) = @_;
return ( $base ** ceil(log($x)/log($base)));
}
That is, ln(a) / ln(b) gives you the number of digits needed to represent the number a relative to the base b (and ln() is the natural logarithm, i.e. to the base e (Euler's number)).
Then round that up to the next greater or equal integer (POSIX::ceil), and exponentiate the base with it. Voilą, you have the next greater or equal power of the base.
p.s.: using `POSIX::ceil` covers all corner cases, whereas using `int(...) + 1` as suggested in previous responses, does not. | [reply] [d/l] |
|
...and ln() is the natural logarithm
Note that it doesn't have to be the natural logarithm. You can use a log to any base.
D:\>perl -MPOSIX="log10,log2" -le "$r1=log(1234)/log(2);$r2=log10(1234
+)/log10(2);$r3=log2(1234)/log2(2);print $r1; print $r2; print $r3;"
10.269126679149417887862906163471
10.269126679149417887862906163471
10.269126679149417887862906163471
Cheers, Rob
| [reply] [d/l] |
|
You can use a log to any base, indeed, for as long as you use the same base for both dividend and divisor.
And, coincidentally, the log to the base Euler's number is the only one one available as part of core Perl. So as to minimize the readers' confusion, I opted to using that.
| [reply] |
Re: Power of two round up.
by myocom (Deacon) on Dec 15, 2000 at 23:54 UTC
|
for my $foo (1..210) {
print "$foo ",dec2bin($foo)," binrounded is ",binround($foo),"\n";
}
sub binround {
my $bin = dec2bin(shift);
my $mod = 0;
$mod = 1 if (split('1','0'.$bin.'0') == 2);
return '1' . ('0' x (length($bin)-$mod));
}
sub dec2bin {
my $str = unpack("B32", pack("N", shift));
$str =~ s/^0+(?=\d)//;
return $str;
}
| [reply] [d/l] |
Re: Power of two round up.
by jimav (Sexton) on Aug 25, 2023 at 17:55 UTC
|
1 << length(sprintf("%b", $input))
Not fast, of course, but perfectly fine when called only once such as for a new constant (or other inlineable subs)
use Some::Other::Module 'SOM_FLAGS_MAX';
use constant MY_FLAGS_MIN => (1<<length(sprintf("%b", SOM_FLAGS_MAX));
| [reply] [d/l] |