Uploaded image for project: 'Qt'
  1. Qt
  2. QTBUG-36866

qhash internal prime number list contains composite numbers (non prime)

    XMLWordPrintable

Details

    • 121e71293500e08148d3c2ce31a8e9b618943cba

    Description

      In order to generate the bucket array size, internally, QHashData::rehash uses function primeForNumBits function, which, according to the documentation in the file, should generate prime numbers. Still, for some parameter values, it generates composite numbers:

      primeForNumBits(13) = 8201 = 59 * 139
      primeForNumBits(14) = 16409 = 61 * 269
      primeForNumBits(17) = 131093 = 337 * 389
      primeForNumBits(21) = 2097167 = 67 * 31301
      primeForNumBits(22) = 4194313 = 181 * 23173
      primeForNumBits(23) = 8388613 = 1277 * 6569
      primeForNumBits(24) = 16777219 = 1549 * 10831
      primeForNumBits(25) = 33554461 = 139 * 241399
      primeForNumBits(27) = 134217728 = 2 * 67108864
      primeForNumBits(28) = 268435456 = 2 * 134217728
      primeForNumBits(29) = 536870912 = 2 * 268435456
      primeForNumBits(30) = 1073741824 = 2 * 536870912

      The correct prime_deltas array should be:

      0, 0, 1, 3, 1, 5, 3, 3, 1, 9, 7, 5, 3, 1, 27, 3,
      1, 1, 3, 21, 7, 7, 15, 1, 5, 35, 15, 29, 3, 11, 3, 0

      Attached you can find the program that generates the above output.

      I did not make analysis of what impact the non prime numbers will have, but I would suggest either to fix the values, or fix the comment and function name as it can cause confusions when people read the code/reuse it.

      Attachments

        No reviews matched the request. Check your Options in the drop-down menu of this sections header.

        Activity

          People

            peppe Giuseppe D'Angelo
            vladmihaisima Vlad-Mihai Sima
            Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

              Created:
              Updated:
              Resolved:

              Gerrit Reviews

                There are no open Gerrit changes