SPUG: Cool power-of-2 trick
Aaron W. West
tallpeak at hotmail.com
Thu Jan 20 14:42:38 PST 2005
I wonder if there's a quick way to find the smallest power of two equal to
or greater than a given number.
Here's some of "e" for you.
QPI-Quick Pi v2.70, (c) 2000-2003 S. Pagliarulo
Freely distributable, email: s_pagliarulo at hotmail.com
mobile AMD Athlon(tm) XP2400+ detected
System speed measured at 1.8 GHz
Using default training data
Computation of e to 4,194,304 digits
Method used : Series SUM 1/n!
Started : Mon Aug 23 17:38:02 2004
Series size : 769340 (4,194,309 digits)
Initialization time : 0.01
Series processing time : 6.18
Final value time : 3.06
Total time : 9.24 seconds
Total memory used : 46,910,676 (44.74 MB)
CPU utilization : 88.51%
e = 2.
7182818284 5904523536 0287471352 6624977572 4709369995 : 50
9574966967 6277240766 3035354759 4571382178 5251664274 : 100
2746639193 2003059921 8174135966 2904357290 0334295260 : 150
5956307381 3232862794 3490763233 8298807531 9525101901 : 200
1573834187 9307021540 8914993488 4167509244 7614606680 : 250
8226480016 8477411853 7423454424 3710753907 7744992069 : 300
(300 digits is enough for this email...)
----- Original Message -----
From: "Michael R. Wolf" <MichaelRWolf at att.net>
To: "Brian Hatch" <bri at ifokr.org>
Cc: <spug-list at mail.pm.org>
Sent: Thursday, January 20, 2005 1:30 PM
Subject: Re: SPUG: Cool power-of-2 trick
At 12:29 PM 1/20/2005, Brian Hatch wrote:
> > While reading through the perl-quiz-of-the-week, I noticed this neat
> > test
> > to find if a number is a power of 2. Originally, I didn't even believe
> > it
> > worked so I wrote a little program to test it. The program helped me
> > figure out that it does, in deed, work, and *how* it works. If a
> number is
> > a pure powere of 2, it only has one bit set.
>This only works on systems where data is stored in binary. If you're on
>a machine that uses ternary storage units (-1 0 +1) then it does not
>work for powers of two, but it does work for powers of three.
>Of course I'm still waiting for the completely optimal system which uses
>storage units of 'e' instead of rounding to 3 for simplicity.
In a grad school EE/CS class, the professor did a proof on the board that
the best computer would, in fact, have each storage unit contain e (approx
2.718281828....?) states. Since that's closer to 3 than 2, it would be
better to have a trinary system instead of a binary system. And yes, it
was hard for him to continually say trits (instead of bits) without
scrambling it up!
To muck with an old punch line -- You silly Rabbi, trits are for kids!!!!
Michael R. Wolf
All mammals learn by playing!
MichaelRWolf at att.net
More information about the spug-list