home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!zaphod.mps.ohio-state.edu!cs.utexas.edu!gateway
- From: FELSON_ADJ@CCSUA.CTSTATEU.EDU
- Newsgroups: comp.sys.hp48
- Subject: Re: Power of 2
- Date: 19 Dec 1992 19:22:42 -0600
- Organization: UTexas Mail-to-News Gateway
- Lines: 49
- Sender: daemon@cs.utexas.edu
- Message-ID: <921219202242.26018622@CCSUA.CTSTATEU.EDU>
- NNTP-Posting-Host: cs.utexas.edu
-
- ! From: kcooke@stein.u.washington.edu (Kenneth E. Cooke)
- ! akcs.joehorn@hpcvbbs.cv.hp.com (Joseph K. Horn) writes:
- !
- ! >flynn@sabrina.dei.unipd.it [Salvatore A. Colomba] writes:
- !
- ! >> I have a better one [to test for a power of 2]; I've not tested it,
- ! >> but it should work in principle...
- ! >> << DUP LN 2 LN / IP 2 ^ - >>
- ! >> It should give zero only if the number is EXACTLY a power of
- ! >> two...:)
- !
- ! >Doesn't work at all. I assume you meant
- !
- ! > << DUP LN 2 LN / IP 2 SWAP ^ - >>
- !
- ! >which usually works, but fails for 2^19, 2^24, 2^29, 2^34, and 2^39.
- ! >Replacing the LN's with LOG's fixes all these cases but then fails for
- ! >2^6, 2^8, 2^35 and 2^38.
- !
- ! >Algorithms which work in principle often fail in practice due to
- ! >round-off errors. Good hypotheses deserve the honor of being tested.
- !
- ! >-jkh-
- !
- ! Here is a cleaner way to check for a power of 2. As Joe points out, you
- ! should not depend on "ideal" mathematics when working with a limited-
- ! precision machine. You can sometimes get away with this kind of thing on
- ! the HP48, because it has an EXCELLENT implementation of floating-point
- ! arithmetic (thanks in part to Prof. Kahan). My only regret is that they
- ! threw out the full IEEE version in the HP71.
- !
- ! This is a user-code translation of the power-of-2 check in FFT. If your
- ! binary word-size is N, it will work for 0 to 2^N - 1 (for binary integers).
- ! It considers #0 and #1 to be powers of 2.
- !
- ! << NOT DUP 1 + OR 1 + #0 == >>
- !
- ! The first "1 +" will fill the first 0. If there was only one 0, the second
- ! "1 +" will cause it to roll-over to #0. Sorry if this makes no sense :)
- !
-
-
- Actually the problem was in using IP to get the integer... numbers like
- 1.9999999999999 will return 1 where 2 is the desired result. I think
- using something like 5 RND instead of IP should do the trick. Or 2 -
- ABS 0.0001 <
-
-
- __a__d__a__m__
-