1 Reply Latest reply on Jan 31, 2012 5:23 AM by mbraendle

    Interesting bug in sort algorithm (not FMP)

    Vaughan

      I just read this article talking about a bug in sort algorithm that has been dormant for 50 years:

       

      http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html

       

      TL;DR -- the bug is in this line of code:

       

      int mid = (low + high) / 2;

       

      ...which "sets m to the average of l and u, truncated down to the nearest integer." The bug occurs when the sum of (low + high) is greater than the maximum positive int value (231 - 1).

       

      As data sets get bigger and bigger these kinds of errors are going to crop up more frequently.

        • 1. Re: Interesting bug in sort algorithm (not FMP)
          mbraendle

          Thanks Vaughan, interesting article.

           

          It depends on how record pointers are represented internally in FM (which is able to address 64 quadrillion records per table; I assume this is US short notation, so 64*10^15 records = ca. 2^55).

           

          If, however, the sort algorithm of FM uses 32bit pointers, then we may sooner or later run into a problem. E.g. I have

          one 40 GB database with about 306 million records (still far away from the 2^31 -1 = 2.15 billion record limit); for certain export operations, this DB needs to be sorted.