[Octave-bug-tracker] [bug #65441] nextpow2 incorrect for some inputs slightly larger than powers of two

[anonymous]

URL:
  <https://savannah.gnu.org/bugs/?65441>

                 Summary: nextpow2 incorrect for some inputs slightly larger
than powers of two
                   Group: GNU Octave
               Submitter: None
               Submitted: Sun 10 Mar 2024 08:23:57 AM UTC
                Category: Octave Function
                Severity: 3 - Normal
                Priority: 5 - Normal
              Item Group: Incorrect Result
                  Status: None
             Assigned to: None
         Originator Name: 
        Originator Email: 
             Open/Closed: Open
                 Release: dev
         Discussion Lock: Any
        Operating System: Any
           Fixed Release: None
         Planned Release: None


    _______________________________________________________

Follow-up Comments:


-------------------------------------------------------
Date: Sun 10 Mar 2024 08:23:57 AM UTC By: Anonymous
The help text for nextpow2 is:
> Compute the exponent for the smallest power of two larger than the input.
> For each element in the input array x, return the first integer n such that
2^n ≥ abs (x).

First, I should point out that these two sentences seem to specify two
different behaviors ("larger than" vs. "≥").  I assume that the second one
is correct.

Second, the documentation does not indicate what nextpow2(0) returns.  It
returns 0, which seems rather strange, but is presumably for MATLAB
compatibility.  This certainly seems worth documenting.

Third, and finally getting to the original reason I am filing this report,
nextpow2 returns incorrect results for some inputs slightly larger than exact
integer powers of two.  For instance, nextpow2(1024 + eps(1024)) returns 10
instead of 11.

The current implementation (excluding input validation) is:

function n = nextpow2 (x)
  n = ceil (log2 (abs (x)));
  n(x == 0) = 0;  # special case
endfunction


The base-2 logarithm of 1024 + eps(1024) is closer to 10 than it is to the
next larger double.  Accuracy of Octave's log2(x) function is unspecified, but
it does return 10 here on my system.

Attached is a version of nextpow2.m with the following changes:
* Clarify help text.
* Reject non-real input.
* Hopefully calculate the correct output for all inputs, including integer
types.
* Return output of same class as input to match documented MATLAB behavior.
* Add tests.
        * Note that some of the tests rely on 2 .^ x being exact for 
integer-valued
x, which I don't believe is documented.

This function has an interesting history; see bug #44291, bug #53463, and bug
#62947.  I think this will be at least the fifth attempt.  I'm reasonably
confident it's correct, but careful review is probably warranted.







    _______________________________________________________
File Attachments:


-------------------------------------------------------
Name: nextpow2.m  Size: 4KiB
<http://savannah.gnu.org/bugs/download.php?file_id=55818>

    AGPL NOTICE

These attachments are served by Savane. You can download the corresponding
source code of Savane at
https://git.savannah.nongnu.org/cgit/administration/savane.git/snapshot/savane-04b18e1179b14c0ef710c8e9c8e59d1e4bcd7bd0.tar.gz

    _______________________________________________________

Reply to this item at:

  <https://savannah.gnu.org/bugs/?65441>

_______________________________________________
Message sent via Savannah
https://savannah.gnu.org/