Warn of overflow of loops

[jeanluct]

Matlab is not great for manipulating types. Margaux was confused by something she rightfully expected to work. Load the attached MAT file, then do

#!matlab

b = compact(braid(XY));
entropy(b)
   ans = 5.1058
entropy(b,'trains')
   ans = 5.1058    % answers agree
l = loopcoords(b);
log(minlength(b^100*l)/minlength(l)) / 100   % find entropy by iteration
   ans = 0.3556

These are radically different, and they shouldn't be. The problem is that since loopcoords tries to use int, it can overflow.

Compare this to using way fewer iterations:

#!matlab

log(minlength(b^6*l)/minlength(l)) / 6
  ans = 5.0872

or using a loop object directly:

#!matlab

l = loop(b.n);
log(minlength(b^100*l)/minlength(l)) / 100
  ans = 5.1082

which are both close to the real answer.

When I wrote this I looked for a way to check for overflow: it's not trivial. It's also possible to force use of exact types, but there are no built-in ones. I tried the package VariablePrecisionIntegers.

But in any case, there is a flag 'checkoverflow' that is set to true, so something should have complained. The problem, I think, is that the check is done in loopcoords but not in the multiplication.

[jeanluct]

From Marko Budisic on 2013-10-21 16:42:00+00:00

Replicated in testsuite for the braid class.

Commit

[jeanluct]

From Marko Budisic on 2013-10-21 17:35:00+00:00

This .m file replicates the test case, after the .mat file has been loaded and prints out the difference between internal entropy computation and manual, a la Margaux. Using this file we can clearly see at which iterate the computation fails majorly.

[jeanluct]

From Marko Budisic on 2013-10-21 19:03:27+00:00

loopsigma now uses a guarded sum that throws an error if there is a pending overflow. Fixes Issue #11

→ <<cset 49f1a1ae330e>>

[jeanluct]

From Marko Budisic on 2013-10-21 19:11:39+00:00

Note that this fix slows down the code a bit. But I'd rather be correct first and quick second.

[jeanluct]

From Jean-Luc Thiffeault on 2013-10-21 21:54:08+00:00

I think that was one reason why I was dithering on that. I don't love the performance hit of doing all that checking. Then again the real work-intensive application is for doubles, which won't get checked (right?).

In loopcoords.m, it is possible to use vpi types (VariablePrecisionIntegers), which are included in extern. They are not yet used by default, but can be turned on. Have you checked whether your test is compatible? That is, it should skip the test if the integer type is vpi.

Also, the check for overflow/underflow in loopcoords could use your test. Maybe move the test to the private subfolder, so other methods can use it? In any case the comment text in loopcoords should be amended.

[jeanluct]

From Jean-Luc Thiffeault on 2013-10-21 22:13:06+00:00

4edae45 - Move sumg to separate file (use lowercase).

[jeanluct]

From Jean-Luc Thiffeault on 2013-10-21 22:34:23+00:00

Ok, I checked that isinteger returns 0 for a VPI type. (Which is what we want.)

[jeanluct]

From Jean-Luc Thiffeault on 2013-10-22 00:48:00+00:00

Ok, VPI functionality now integrated.

#!matlab

b=braid([1 -2])
ab(loopcoords(b^100,[],'vpi'))

ans =

vpi element: (1,1)
    453973694165307953197296969697410619233825

vpi element: (1,2)
   -1

[jeanluct]

From Jean-Luc Thiffeault on 2013-10-22 00:49:43+00:00

As of e708696 VPI gets included as part of the ditribution (bumped to 1.0.1 but not tagged yet... need to do a bit more checking.)