bugGNU Octave - Bugs: bug #63089, dec2bin gives wrong answer for...

 
 

bug #63089: dec2bin gives wrong answer for negative int16

Submitter:  Mayeul C. <mayeulc>
Submitted:  Wed 21 Sep 2022 02:51:57 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * 7.2.0 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Thu 27 Oct 2022 07:22:25 PM UTC, comment #24: 

After examining it further, I'd like to close this report as fixed for stable, leaving the input duplication unchanged, at least for Octave 8.

The ideal call sequence would be:

  • Both dec2bin and dec2hex would pass their arguments to dec2base, without any significant input validation of their own (no code duplication).
  • dec2base would do all input validation and call a private conversion function.
  • dec2base would need to at least accept negative inputs to accommodate dec2bin and dec2hex, so that dec2bin doesn't have to duplicate that check and validation -- this is a major change to dec2base internals.
  • The above rules would implicitly make everything consistent.
  • Whether dec2base grows in future to accept fractional inputs (or not), that change would be local to dec2base's conversion routine, and the effect would transparently show up for dec2bin and dec2hex.


I have a feature-complete WIP patch of dec2base that covers the points above but the price is some ad hoc code duplication between dec2bin and dec2base, since dec2bin accommodates negative inputs of certain fixed sizes and dec2base does not.

I have a WIP to make everything fully consistent with no duplication, but there is not enough time before default is merged to stable for testing everything for Octave 8. I'd prefer leaving the current input validation code duplication stand the way it is for now, and fix it without the time pressure. I'll submit the WIP as a separate patch as a feature request ("accommodate negative inputs for dec2base so that code duplication can be removed"). The fractional inputs feature is optional and can be decided at that point.

Arun Giridhar <arungiridhar>
Group Member
Wed 26 Oct 2022 11:21:36 AM UTC, comment #23: 

Wrt the other patch: It might be best to open a report on Savannah with a feature request and attach your patch to that report.

Markus Mützel <mmuetzel>
Group administrator
Tue 25 Oct 2022 05:49:37 PM UTC, comment #22: 

Thanks. Pushed the stable version here: https://hg.savannah.gnu.org/hgweb/octave/rev/7880af7a3b3f

Marking as Ready For Test.

The input duplication is because dec2bin and dec2hex allow negative numbers but dec2base doesn't. I'll see how to merge that...

For the default branch, I am considering a feature addition to allow dec2base to handle both negative inputs and non-integer inputs, aiming to be fully backwards-compatible with existing use. The trial patch is here: https://octave.discourse.group/t/negative-and-fractional-inputs-for-dec2base/3326 but it didn't get any feedback earlier.

Arun Giridhar <arungiridhar>
Group Member
Tue 25 Oct 2022 04:10:20 PM UTC, comment #21: 

Looks mostly good to me.
Just some minor remarks:
- The error message should probably use plural "integers" (like in dec2base).
- Lines with function calls should end with a semicolon. It doesn't matter if those functions return arguments or not (like "error" in line 29 of your patch).

With these modifications, the patch is good to go on stable imho. For the default branch, we could try to avoid having double input validation for positive input (once in dec2bin and then again in dec2base). Maybe, we could split the actual work in dec2base from the input validation. That "core" function could be a private `__dec2base__` function (which wouldn't contain any input validation). Both, dec2bin and dec2base could call that private "core" function.

Markus Mützel <mmuetzel>
Group administrator
Tue 25 Oct 2022 03:05:10 PM UTC, comment #20: 

Oof! Matlab is being gratuitously inconsistent there. Thanks @nrjank for looking it up.

I've attached an updated patch that restores old behavior for non-integer  inputs.

(file #53906)

Arun Giridhar <arungiridhar>
Group Member
Tue 25 Oct 2022 01:02:41 PM UTC, comment #19: 

in matlab 2022b:


>> dec2bin(+2.7)

ans =

    '10'

>> dec2bin(-2.7)

ans =

    '11111101'

>> dec2bin(+3.1)

ans =

    '11'

>> dec2bin(-3.1)

ans =

    '11111101'

>> dec2hex(+2.7)
Error using dec2hex
First argument must contain finite integers.

>> dec2hex(-2.7)
Error using dec2hex
First argument must contain finite integers.

>> dec2hex(+3.1)
Error using dec2hex
First argument must contain finite integers.

>> dec2hex(-3.1)
Error using dec2hex
First argument must contain finite integers.


Nicholas Jankowski <nrjank>
Group Member
Mon 24 Oct 2022 10:33:00 PM UTC, comment #18: 

IIUC, we chose to differ from Matlab in this particular case. And we shouldn't change that behavior (at least for a .dot release. But I'd prefer if we wouldn't in general).

See e.g. the top of `dec2base` for a possible implementation of the check.

It would also make sense to think of a way that doesn't duplicate the checks for positive input. If that is too intrusive, we could do that part of the change on the default branch only.

Markus Mützel <mmuetzel>
Group administrator
Mon 24 Oct 2022 08:54:21 PM UTC, comment #17: 

The attached patch works for me for this input validation. I also edited the docstring to match current behavior. Could someone check what Matlab returns for these please?


dec2bin (+2.7)
dec2bin (-2.7)
dec2bin (+3.1)
dec2bin (-3.1)

dec2hex (+2.7)
dec2hex (-2.7)
dec2hex (+3.1)
dec2hex (-3.1)


(file #53905)

Arun Giridhar <arungiridhar>
Group Member
Mon 24 Oct 2022 05:43:37 PM UTC, comment #16: 

just checking compatibility:


>> a.b = 1

a =

  struct with fields:

    b: 1

>> dec2bin(a)
Error using dec2bin
D must be numeric.

>> dec2bin(-1.5)

ans =

    '11111110'

so it seems at least the last item is compatible.


Nicholas Jankowski <nrjank>
Group Member
Mon 24 Oct 2022 05:17:58 PM UTC, comment #15: 

Input validation is broken for `dec2bin` since this change.
E.g.:

>> a.b = 1;
>> dec2bin(a)
error: binary operator '<' not implemented for 'scalar struct' by 'scalar' operations
error: called from
    dec2bin at line 81 column 7


Also, negative floating-point values are silently truncated(?). According to the docstring, they should throw an error:

>> dec2bin(-1.5)
ans = 11111110


Re-opening report.

Markus Mützel <mmuetzel>
Group administrator
Thu 29 Sep 2022 11:29:52 AM UTC, comment #14: 

I tried locally, and there was a merge conflict. But after resolving it (with a graphical 3-way merge tool), I could continue grafting the change.
Fwiw, I used the following commands:

hg graft --log 31239
hg resolve
hg graft --continue


It's probably also ok to manually cherry-pick entire files or some lines of code from one branch to the other. But it might be better to not calling it "grafting" in that case.

Markus Mützel <mmuetzel>
Group administrator
Thu 29 Sep 2022 11:14:49 AM UTC, comment #13: 

I also tried "hg transplant" first before "hg graft" but that too had unexpected side effects. I'll probably have to try them first elsewhere before the Octave repository.

Arun Giridhar <arungiridhar>
Group Member
Thu 29 Sep 2022 11:06:11 AM UTC, comment #12: 

This case was a manual copy-paste of the two files from default to stable. I tried "hg graft" first but it didn't do what I expected.

Arun Giridhar <arungiridhar>
Group Member
Thu 29 Sep 2022 07:03:11 AM UTC, comment #11: 

Did you `hg graft` those changes to the stable branch? Or did you manually cherry-pick them?
Not a big deal. I was just a bit confused by the commit message...

Markus Mützel <mmuetzel>
Group administrator
Wed 28 Sep 2022 09:13:47 PM UTC, comment #10: 

I grafted the changes into the stable branch so that release 7.3 can return correct results for dec2bin and dec2hex for negative integer types. https://hg.savannah.gnu.org/hgweb/octave/rev/96ad887ae4f8

Closing as Fixed. If there are further changes it can be reopened.

Arun Giridhar <arungiridhar>
Group Member
Sun 25 Sep 2022 10:34:01 AM UTC, comment #9: 

Thanks for checking with Matlab. I've pushed changes to both dec2bin and dec2hex here: https://hg.savannah.gnu.org/hgweb/octave/rev/dd6b37f67db2

Marking as Ready For Test.

Arun Giridhar <arungiridhar>
Group Member
Sat 24 Sep 2022 09:02:11 PM UTC, comment #8: 

R2022b:


dec2bin(int16(-4200),5): 1110111110011000

dec2bin(-3): 11111101

dec2bin(-4200): 1110111110011000

dec2bin(intmin("int64")): 1000000000000000000000000000000000000000000000000000000000000000


A.R. Burgers <arb>
Sat 24 Sep 2022 08:51:02 PM UTC, comment #7: 

There's so much commonality between dec2bin and dec2hex that I rewrote dec2hex to make use of the patched dec2bin, instead of repeating all the preparation code. Now dec2hex also accepts 64-bit negative input.

Patch attached for dec2hex.

(file #53751)

Arun Giridhar <arungiridhar>
Group Member
Sat 24 Sep 2022 05:45:05 PM UTC, comment #6: 

Improved patch attached (v2).

I activated several BISTs that had been commented out. All BISTs now pass. I've fixed them to expect 64-bit strings instead of 53-bit ones, and to allow numbers down to -2^63 without expecting an error.

The practice of left-padding with ones for negative inputs is standard two's complement notation, but the practice of further left-padding that with zeroes is not mathematically sound at all. Is Matlab still doing that or have they fixed it to consistently left-pad with ones for all negative inputs? In any case, I've added a note to the docstring explaining what to expect.

Since the domain of valid inputs has changed, should we mention this in NEWS? If so, is it going into 7.3 or 8?

(file #53748)

Arun Giridhar <arungiridhar>
Group Member
Sat 24 Sep 2022 03:17:39 PM UTC, comment #5: 

I am attaching a WIP patch for testing. It is vectorized (no loops) and can accommodate negative numbers below flintmax to the full range of int64 for signed and uint64 for unsigned. It passes all BISTs except for these:


dec2bin (-2^31 -1)
dec2bin (-2^52)
error <negative inputs cannot be less than> dec2bin (- flintmax ())


In the first two cases, the expected result was a 53-bit string but the patched version returns a 64-bit string with more leading 1s, which on reflection I think is an improvement since the other conversions of negative numbers when length is not specified return 8, 16, or 32 bits, so returning a bit string with 64 bits is more consistent than 53 bits.

The last failing BIST is because the patched version can handle negative numbers below flintmax, so the expected error does not happen.

The trimming-to-length part is subjective for negative numbers, because one can either return the minimum number of bits plus a leading "1", or one can return a fixed power-of-2 number of bits with several leading "1"s. Both choices can be defended. The patch at present does the second case, which is similar what C++ does when casting signed to unsigned, returning e.g. 32 bits or 64 bits but not something in between:

  int32_t c = -123456789;
  int64_t d = -123456789;
  std::cout << uint32_t (c) << ' ' << uint64_t (d) << '\n';


Please test against Matlab for the following cases:

dec2bin (-3)     # should return 8 bits
dec2bin (-4200)  # should return 16 bits
dec2bin (int16(-4200), 5)  # should hopefully still return 16 bits, not just 13 bits
dec2bin (intmin ("int64")) # should return one 1 followed by 63 zeroes.



(file #53747)

Arun Giridhar <arungiridhar>
Group Member
Fri 23 Sep 2022 12:28:44 PM UTC, comment #4: 

Also, are there specific function calls we should check against Matlab? If you provide examples someone can test the and provide the output from a current version.

Nicholas Jankowski <nrjank>
Group Member
Fri 23 Sep 2022 08:15:37 AM UTC, comment #3: 

Could you please provide your proposed changes in form of a Mercurial (or Git) patch relative to the current head of the Octave repository?

Markus Mützel <mmuetzel>
Group administrator
Wed 21 Sep 2022 07:46:36 PM UTC, comment #2: 

Affected file is https://hg.savannah.gnu.org/hgweb/octave/file/b542b88ad3b6/scripts/strings/dec2bin.m

I was going to write a comment to the effect of "I won't have time to work on this before ~1 month", but I got nerd-sniped (I really should have worked on something else instead).

Anyway, I'm not too proud of how I implemented compatibility with arrays (and growing strings to the same lenghts), but I think the file I'm attaching is feature-complete.

If you want to refactor, the gist is:

% Perform the base conversion on:
i = uint64(-1*(int64(i)+1));
out = dec2base(i, 2, len)
% Then invert the output:
out = char((out=='0') + '0');


Things I'm not sure of:

  • How Matlab handles length extension. I implemented what made more sense to me. See comments in tests.
  • Apparently this was supposed not to work on floating point values? From my testing it does work on them, and I see no reason not to (I added a check to error after fmaxint(i)).
  • If there is a better way to concatenate values with the correct sign extension


Ideally, I'd have wanted (u)int<n> to default to <n> output digits, especially if <n> isn't default. But I can live with the attached implementation.

(file #53739)

Mayeul C. <mayeulc>
Wed 21 Sep 2022 03:28:02 PM UTC, comment #1: 

confirmed behavior on linux in 8.0.0 and windows, and that matlab behavior is comment #0 states is expected.

matlab 2022a:

>> dec2bin(int16(-4200))
ans =
    '1110111110011000'

>> dec2bin(int32(-4200))
ans =
    '1110111110011000'

>> dec2bin(int32(-4200),32)
ans =
    '11111111111111111110111110011000'

>> dec2bin(int32(-42000))
ans =
    '11111111111111110101101111110000'

>> dec2bin(-42000)
ans =
    '11111111111111110101101111110000'


Nicholas Jankowski <nrjank>
Group Member
Wed 21 Sep 2022 02:51:57 PM UTC, original submission:  

Consider:


> dec2bin(int16(-4200))
ans = 111111111111111
> dec2bin(int32(-4200))
ans = 1110111110011000


-4200 obviously fits in a 2-complemented signed 16 bit integer, this is a bug. The first line should return the same result as the second one.

While I am at it:


Octave:1> dec2bin(int32(-4200), 32)
ans = 00000000000000001110111110011000
Octave:2> dec2bin(int32(-42000))
ans = 1111111111111111111111111111111
Octave:3> dec2bin(-42000)
ans = 11111111111111110101101111110000


Octave:1 -- The leading zeroes should be leading ones for negative integers in 2-complement.

Octave:2 -- This is doubly wrong: wrong number of digits, and wrong result. The next line shows a seemingly-correct result

There seems to be some of the same behaviours with i64, but I'm soon hitting "dec2bin: negative inputs cannot be less than -flintmax () / 2".

Mayeul C. <mayeulc>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #53906:  dec2bin.patch added by arungiridhar (2KiB - text/x-patch)
file #53905:  dec2bin.patch added by arungiridhar (2KiB - text/x-patch)
file #53751:  dec2hex.patch added by arungiridhar (3KiB - text/x-patch)
file #53748:  dec2bin.patch_v2 added by arungiridhar (5KiB - application/octet-stream)
file #53747:  dec2bin.patch added by arungiridhar (2KiB - text/x-patch)
file #53739:  dec2bin.m added by mayeulc (8KiB - text/x-objcsrc)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by arb (Posted a comment)
  • -email is unavailable- added by arungiridhar (Updated the item)
  • -email is unavailable- added by mmuetzel (Posted a comment)
  • -email is unavailable- added by nrjank (Posted a comment)
  • -email is unavailable- added by mayeulc (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only group members can vote.

     

    Follow 18 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2022-10-27 arungiridhar StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2022-10-25 arungiridhar StatusIn Progress Ready For Test
    2022-10-25 arungiridhar Attached File- Added dec2bin.patch, #53906
    2022-10-24 arungiridhar Attached File- Added dec2bin.patch, #53905
    2022-10-24 mmuetzel StatusFixed In Progress
        Open/ClosedClosed Open
        Releasedev 7.2.0
    2022-09-28 arungiridhar StatusReady For Test Fixed
        Open/ClosedOpen Closed
    2022-09-25 arungiridhar StatusConfirmed Ready For Test
    2022-09-24 arungiridhar Attached File- Added dec2hex.patch, #53751
    2022-09-24 arungiridhar Attached File- Added dec2bin.patch_v2, #53748
    2022-09-24 arungiridhar Attached File- Added dec2bin.patch, #53747
    2022-09-21 mayeulc Attached File- Added dec2bin.m, #53739
    2022-09-21 nrjank StatusNone Confirmed
        Release7.2.0 dev
        Operating SystemGNU/Linux Any

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code