bugGNU Octave - Bugs: bug #55238, Modulo [mod(X,Y)] of larger...

 
 

bug #55238: Modulo [mod(X,Y)] of larger values seems to fail silently to output 0

Submitter:  None
Submitted:  Tue 18 Dec 2018 01:40:16 AM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Invalid / Not an Octave Bug Assigned to:  None
Originator Name:  C. Drew Originator Email:  -email is unavailable-
Open/Closed:  * Closed Release:  * 4.4.1
Operating System:  * GNU/Linux Fixed Release:  None
Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sun 23 Dec 2018 05:40:20 PM UTC, comment #9: 

Note added to the documentation in this cset: https://hg.savannah.gnu.org/hgweb/octave/rev/d00577d95369.

Rik <rik5>
Group administrator
Sun 23 Dec 2018 05:21:42 PM UTC, comment #8: 

I wouldn't say flintmax is not the point.  While mod does work for non-integers, the overwhelming use case is for integers.  Given that mod satisfies user's expectations as long as a reduced input range is used, I think it is worth noting that in the documentation.

For reference, Octave maps integer variable classes to the integer mod operator '%' in C++.  So for integer values greater than 2^53 it is possible to convert from double to uint64 and still get expected results.  For inputs of class double, we don't use fmod directly because Octave needs to match rounding rules for near-integers for Matlab compatibility.  In effect, Octave does calculate what is described in the documentation


retval = x - floor (x/y) * y


In the case from this code, x/y is still so large (10^26) that there is no fractional decimal portion that floor can truncate and it is a nop.  Hence,


retval = x - floor (x/y) * y
===
retval = x - (x/y) * y
===
retval = x - x
===
retval = 0


which is Octave is returning.


Rik <rik5>
Group administrator
Sat 22 Dec 2018 10:54:01 AM UTC, comment #7: 

mod is not constrained to integer input, so flintmax is not the point. I would expect also mod(100,pi) to be inaccurate in the last two digits, because most probably mod in this case is equivalent to fmod, thus giving the result of 100-31*pi (which obviously suffers from extinction in the last places).

Or is the documentation to be understood literally and mod is special-cased only for integer types and not doubles that are integers, so that also in the most common use-case mod falls back to fmod? Then the problem would be even more severe.

Michael Leitner <mleitner>
Fri 21 Dec 2018 07:41:01 PM UTC, comment #6: 

Should we change the documentation to note that values above flintmax are unreliable?

Is it worth changing the mod function in data.cc to validate that all inputs are less than flintmax()?

For what it's worth, Matlab also gets this completely wrong:


mod(17^23,55)
ans = 53



Rik <rik5>
Group administrator
Tue 18 Dec 2018 07:03:23 PM UTC, comment #5: 

The latest comments are correct, this is not a bug, but a limitation that requires understanding of the numerical operation of Octave.

See also bug #35680 and bug #50808, other results that people searching may find helpful.

As a workaround, if you want arbitrary precision integer arithmetic, you can look at Octave's symbolic package:


>> mod (17 ^ 23, 55)
ans = 0
>> double (mod (vpa(17) ^ vpa(23), 55))
ans =  18


Mike Miller <mtmiller>
Group Member
Tue 18 Dec 2018 10:22:31 AM UTC, comment #4: 

I think this is not a bug.

This is because 17^23 is larger than flintmax
while 17^12 and 17^11 are smaller than flintmax.

Therefore, 17^23 cannot be represented accurately by "double" type,
so the result of mod(17^23,55) has error.

Anonymous
Tue 18 Dec 2018 09:39:35 AM UTC, comment #3: 

I have attached a function that should do what I proposed. Of course the number of iterations is log2(a/b), which is bounded by 616 in the worst case.

(file #45687)

Michael Leitner <mleitner>
Tue 18 Dec 2018 08:19:32 AM UTC, comment #2: 

To the reporter: it is easily possible to answer what seems to be your issue by providing a link to a document that is aptly named "What Every Computer Scientist Should Know About Floating-Point Arithmetic":

https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf

Octave (and Matlab, and numpy, and Julia...) is an environment for numerics, not for arbitrary-precision arithmetics, so if you plan to use such software in the future, you would do well to familiarize yourself with it. Specifically, the argument to your modulo function is not 17^23 as an entity in the ring of integer numbers (which you seem to suppose, as you use number-theoretic tools to transform it), but rather is the closest-possible approximation to it that can be represented as an IEEE-754 double. So for your case of applied number theory, better use an environment with arbitrary-precision arithmetics.

To the developers: Is there something to be done? The main issue of the reporter is probably really that 17^23 is not what he expects it to be. However, mod is also not exact in calculating the result of the actual argument, because mod(2^100,3), which should be 1 ((-1)^100, as 2==-1(3)), gives also zero. Most probably mod(a,b) just gives a-b*floor(a/b), and if a/b is larger than bitmax, floor(x)==x. So this is an obvious condition which could trigger a warning of lost precision in mod. Yes, sin and friends also do not warn, but matrix inversion and friends do. Is this inconsistency a deliberate choice (other than that Matlab does it also)?

By the way, there would be a way to do it exactly: repeatedly find the largest n so that b*2^n<=a, and subtract this term from a, until n<=0. One could special-case this in mod, any iteration should just take a few CPU cycles as it involves only bit operations, and it should at worst only take 53 iterations.

Michael Leitner <mleitner>
Tue 18 Dec 2018 02:10:04 AM UTC, comment #1: 

Just a followup to the workaround, even larger numbers for the modulo command can be used by breaking it up into even more terms. For example, mod(24^23,55) can be solved with three iterations inside a wrap:   mod((mod(24^10,55)*mod(24^10,55))*mod(24^3,55),55)
[ = 19 ]

So, it looks like this is just a really-large-number issue after all. Not sure if this constitutes a bug, but in the meantime, hopefully people searching around will find this helpful. It appears that the exponent should be kept to 10 or less for each term, given a base of two digits at least.

Anonymous
Tue 18 Dec 2018 01:40:16 AM UTC, original submission:  

Hello!  While attempting a homework assignment, I seem to have stumbled onto a (potential?) bug with the mod(X,Y) command.

Specifically, mod(17^23,55) is giving an output of 0, when the result should be 18.

I have tried assigning the 17^23 value to a variable first, converting/casting it as a float, double, then applying as mod(x,55), yet... Octave still keeps returning 0 as the result.

Is there something I need to do to enable large number support, or is this a true bug?

WORKAROUND:  In the meanwhile, using the property of (a*b)mod n = ((a(mod(n) (b(mod(n)) mod n, I have been able to get the result using:  *mod((mod(17^12,55)*mod(17^11,55)),55)  = 18 
(but, to stress, even slightly larger numbers fail and give wild answers)

See screenshot for details. I hope this helps. :)

Anonymous

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #45687:  mod_mod.m added by mleitner (97B - text/x-matlab)
file #45686:  Screenshot_2018-12-17_20-26-14.png added by None (12KiB - image/png - Attached is a screenshot showing the command window, as an example)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by mleitner (Posted a comment)
  • -email is unavailable- added by None (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 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-12-18 mtmiller StatusNone Invalid / Not an Octave Bug
        Open/ClosedOpen Closed
    2018-12-18 mleitner Attached File- Added mod_mod.m, #45687
    2018-12-18 None Attached File- Added Screenshot_2018-12-17_20-26-14.png, #45686

    Back to the top

    Powered by Savane 3.13-d3ae.
    Corresponding source code