search

nick8325 / quickcheck

Automatic testing of Haskell programs.
Other
714 stars 119 forks source link

Shrink fractions in an asymptotic manner #212

Closed leftaroundabout closed 6 years ago

leftaroundabout commented 6 years ago

The current behaviour of shrink for fractional / floating numbers is not particularly useful: it only tries replacing the number with integers, but that often leads to quite different behaviour of numerical functions.

I've implemented an algorithm based on continued fractions, which generates an asymptotic sequence that actually approximates the original number, and also behaves more sensibly for infinities etc..

Examples:

*Test.QuickCheck.Arbitrary> shrink (32/7)
[0.0,2.0,3.0,4.0,5.0,4.5,4.6]
*Test.QuickCheck.Arbitrary> shrink (-5.23)
[0.0,3.0,4.0,5.0,5.5,5.333333333333333,5.25,5.2,5.222222222222222,5.230769230769231,5.229508196721311,5.2298850574712645,-3.0,-4.0,-5.0,-5.5,-5.333333333333333,-5.25,-5.2,-5.222222222222222,-5.230769230769231,-5.229508196721311,-5.2298850574712645]
*Test.QuickCheck.Arbitrary> shrink pi
[0.0,2.0,3.0,3.25,3.1666666666666665,3.142857142857143,3.1403508771929824,3.1411764705882352,3.1414141414141414,3.141509433962264,3.1415929203539825,3.141592387376536,3.1415925642779543,3.141592615554178,3.1415926355092054,3.141592644537946,3.141592649310873,3.1415926511741086,3.1415926520961532,3.1415926530119025,3.141592653921421,3.1415926534674368]
*Test.QuickCheck.Arbitrary> shrink (1/0::Double)
[0.0,1.0,2.0,16.0,512.0,65536.0,3.3554432e7,6.8719476736e10,5.62949953421312e14,1.8446744073709552e19,2.4178516392292583e24,1.2676506002282294e30,2.658455991569832e36,2.2300745198530623e43,7.482888383134223e50,1.004336277661869e59,5.391989333430128e67,1.157920892373162e77,9.946464728195733e86,3.417579257473456e97,4.6970851655476665e108,2.5822498780869086e120,5.678427533559429e132,4.994797680505588e145,1.757388200993436e159,2.4733040147310453e173,1.392346379889586e188,3.135285318820699e203,2.8240139587082175e219,1.0174582569701926e236,1.466311880625918e253,8.452712498170644e270,1.94906280228e289]

Compare this to the old behaviour:

*Test.QuickCheck.Arbitrary> shrink (32/7)
[0.0,2.0,3.0]
*Test.QuickCheck.Arbitrary> shrink (-5.23)
[5.23,5.0,0.0,-3.0,-4.0]
*Test.QuickCheck.Arbitrary> shrink pi
[0.0,2.0]
*Test.QuickCheck.Arbitrary> shrink (1/0::Double)
[0.0,8.98846567431158e307,1.348269851146737e308,1.5729814930045264e308,1.6853373139334212e308,1.7415152243978685e308,1.7696041796300922e308,1.783648657246204e308,1.79067089605426e308,1.794182015458288e308,1.795937575160302e308,1.796815355011309e308,1.7972542449368124e308,1.7974736898995642e308,1.79758341238094e308,1.797638273621628e308,1.797665704241972e308,1.797679419552144e308,1.79768627720723e308,1.797689706034773e308,1.7976914204485444e308,1.7976922776554302e308,1.797692706258873e308,1.7976929205605945e308,1.7976930277114552e308,1.7976930812868855e308,1.7976931080746007e308,1.7976931214684583e308,1.7976931281653871e308,1.7976931315138515e308,1.7976931331880837e308,1.7976931340251998e308,1.7976931344437579e308,1.7976931346530369e308,1.7976931347576764e308,1.7976931348099962e308,1.797693134836156e308,1.797693134849236e308,1.797693134855776e308,1.797693134859046e308,1.797693134860681e308,1.7976931348614984e308,1.7976931348619072e308,1.7976931348621115e308,1.7976931348622137e308,1.7976931348622648e308,1.7976931348622904e308,1.7976931348623031e308,1.7976931348623095e308,1.7976931348623127e308,1.7976931348623143e308,1.7976931348623151e308,1.7976931348623155e308,1.7976931348623157e308]
nick8325 commented 6 years ago

Cool, thanks!