BytePrimeCache Does Not Utilize 8th Bit In Byte

[DK96-OS]

Introduction

The purpose of BytePrimeCache is to store prime numbers. Prime numbers are unlimited, but numerical representation on finite machines is severely limited.

A byte is a sequence of 8 bits, and is the smallest unit of numerical representation using machine memory. After the byte data type has been exhausted, the next type that must be used is the 16-bit short. As such, any prime numbers that rely on short rather than byte are using 2x the amount of memory.

In Kotlin JVM ecosystem, the Byte data type is a signed integer, meaning that it uses one of it's 8 bits as a sign flag. This reduces the maximum permutations of bits from 256 to 128. One of those permutations must always correspond to zero, so the maximum number that can be represented on Kotlin JVM is 255, or 127.

Currently, the BytePrimeCache supports prime numbers from 2 to 127, as it does not use unsigned bytes or work with the sign flag in any way.

Issue Statement

The BytePrimeCache fails to make complete use of the byte data type. The memory required to represent prime numbers in the range 128 to 255, is 2x the theoretical limit. There are over 20 prime numbers in this range, almost as many prime numbers in the range 2 to 127.

Additional Affected Areas

ShortPrimeCache relies on BytePrimeCache for as many numbers as it can, as bytes are more efficient than shorts.

Guidance

• Investigate at least two potential solutions that will support this
• Provide complete explanation or evidence for why the chosen solution is better

Resolution Requirements

• Utilize the 8th bit in a byte to expand the range of prime numbers supported by BytePrimeCache
• Update the initial prime numbers hard-coded into ShortPrimeCache
• Upgrade Tests for both BytePrimeCache and ShortPrimeCache

[DK96-OS]

• The new maxIndex for BytePrimeCache will be 53, corresponding to the prime number 251.
• The new initial prime numbers for ShortPrimeCache array:
  • 257, 263, 269, 271, 277, 281, 283, 293.