dk96-os / mathtools Goto Github PK

Upgrade the BytePrimeCache using properties of small prime numbers to reduce the space requirement, and extend the coverage (ie. increase maxIndex).

A succinct or compact data structure uses space on the order of the minimum number of bits required to represent each element.

A basic fact to get started with:

• All prime numbers (except 2) are odd, and so the smallest bit of all numbers is always 1, never 0.

This could increase the maxIndex (up to double the highest prime) by adding a bit shift operation when the index is between the current maxIndex, and the new maxIndex.

It would be very helpful to have the JavaDocs available.

The recommended naming convention is kebab case for Gradle project. According to documentation at Gradle Docs there is name abbreviation support when calling gradle tasks from the command line.

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

The recordData function in MeasurementQueue would be more helpful to the caller if it returned the number of remaining measurements instead of a boolean.
The same boolean value, representing whether the data was successfully recorded can be obtained by checking this returned value. Negative value can be reserved for error codes.

Update the documentation for the project. Enable another developer to quickly understand what is provided, and how to use it.

The goal of a library is to use it, and so it is the time to make this available for use.

A simple and convenient method of obtaining a released version needs to be chosen and provided. The first version will be called v0.1

Using object methods from Java code requires an extra INSTANCE keyword. This shows that these generated methods are not actually static.

The original intent behind using object keyword in this library was to contain static methods.

One known challenge with converting certain Lists objects to Java is the default arguments of some methods. Defaults are not supported in Java 11.

These will have to be replaced with overloaded methods.

The list searching functions can have an endpoint argument with default value equal to the list size - 1.

A choice exists between whether to use inclusive or exclusive endpoint index.

Originally posted by @DK96-OS in #32 (comment)

Important Note: The term "Package" here is used to refer to the Java package name, not to be confused with the GitHub Package that is deployed by each Module.

Why Promote Array Package to Module

The Array Package is dedicated to performing operations on java primitive data arrays. This Package is currently a Sub-Package of the List Package inside List Module.

This package structure is not aligned with the Java Language itself, because Lists and Arrays are two different data structures.

Another reason, is that a library user may only work with numerical data in Arrays to maximize performance. This means that the List tools are included unnecessarily.

Challenges With Promoting Array Package

• Renaming all import usages of Array components.
• Any Code Shared between Arrays and Lists Modules will be duplicated

Exploring the decompiled Numbers artifact shows some potential for nanoscale improvement.

• Type casting an int to a long is done repeatedly inside some for loops in PrimeCacheBase
• Some decompiled boolean expressions can be simplified
• The ArrayList of UByte requires boxing and unboxing when an item is added, or when an item is read or removed.
• Creating a new UByte number uses a constructor. A newly discovered prime is cast from int to byte to UByte.

The Lists module contains multiple largeSum methods and LongArrayExt contains a sum method.

These methods return either BigInteger or BigDecimal depending on the input type.

They have been created and tested with positive numbers only, until now.

A list containing only negative numbers, has produced an output of 0, and it is suspected that any negative numbers in a list would be ignored by the sum method.

Data Processing and Formatting

To reach a greater level of testing automation in this area, additional methods involved in data assessment are suggested:

• Outlier detection and removal
• Distribution characteristics
• Uncertainty quantification

Originally posted by @DK96-OS in #23 (comment)

There could be an option that throws an exception if a conversion completely ruins a number, such as a large float or double being converted to Byte - the number ends up being completely different. When the output of the conversion is nothing like the input.

Originally posted by @DK96-OS in #55 (comment)

Add some interaction to the MeasurementQueue such as a callback listener.

• Callback implemented as optional
• Emit a Container Full Event
• Emit Container Almost Full Event(s) optionally

Another piece of the strategy is to look for changes in work required on large inputs. The CompareFactors.lcm method is the most impacted by changes in inputs. It appears that this method has no tests on inputs larger than 256.

Originally posted by @DK96-OS in #86 (comment)

It is important that valid inputs to public methods be determined and demonstrated by test cases. This example of a chaotic method shows how Testing Strategy needs improvements.

Define a system that iteratively:

• Determines testing requirements
• Creates and organizes test cases
• Inspects and improves existing test cases

Is this an important feature: for ensuring accuracy, improving efficiency, ease-of-use?

Should DeviationPolicy maintain an instance of DistributionCharacteristics?
Originally posted by @DK96-OS in #32 (comment)

Reorganize the classes in Statistics to optimize efficiency for different use cases.

For example, there are use cases for DistributionStatistics that do not require computation of the standard deviation. Some library users only care about the mean value.

Design and build an interface that provides more control over the computations that are run.

• Consider that the mean value is a prerequisite computation for standard deviation.
• Consider new computations such as the number of unique values, most frequent value (on integer types)

The PrimeNumberTools object has a private ShortPrimeCache member that it uses to serve it's functions.

This cache is inaccessible to users, and so if a user needs a PrimeNumber cache they will have to create one. If PrimeNumberTools is being used, then the cache will be duplicated.

Potential solutions:

• Make the cache public
• Refactor PrimeNumberTools members to use functional dependency injection, design for any size cache, and remove private cache
• Make ShortPrimeCache static

Some list functions can be broken using large and specifically constructed data sets, but test cases do not show it.

Originally posted by @DK96-OS in #49 (comment)

It is important to know whether the test cases cover all code branches. A tool should be added to measure code coverage, and provide reports that can improve coverage and provide further insight.

To improve usability of Number Structs classes, add Object method implementations for equals, hashCode, and toString.

Array Statistics contains functions that calculate the mean and standard deviation of Number Array types.

The Calculate Mean function of ByteArray uses a sum method with an Int return type, which will overflow with enough elements.

Originally posted by @DK96-OS in #32 (comment)

How to isolate these tests that occasionally fail due to statistical fluctuations, and use retry mechanics.

There is likely a better way to validate floating point numbers. This allocates a String.

• There may be some static method in Float class.
• Converting to int, and converting back, and comparing would be more efficient than a String.

Originally posted by @DK96-OS in #81 (comment)

Performance testing using Kotlin's built in measureNanoTime function provides highly accurate and reliable time measurements for blocks of code.
This has been demonstrated offline using OpenJDK 11, however it appears that on GitHub, the measureNanoTime function returns values that are multiples of 100, or 0.

Table 1: TargetedAccess Test Measurements The most recent GitHub Actions Test report for PrimeCachePerformanceTest, showing the TargetedAccess Test output.
This occurs in both Java 8 and Java 11 Test Reports.

Implications

Without a common reliable computing resource, reproducibility is a challenge. Comparing results between changes over time will require consideration of the system running the tests, which unfortunately will not be GitHub.

Potential Resolutions

One way that this could be resolved, is to investigate alternative OpenJDK distributions available in GitHub Actions. Another is to try to use a newer version of OpenJDK.

Originally posted by @DK96-OS in #21 (comment)

The verification step in the Code Coverage workflow did not catch the Statistics module, which has coverage below 80%.

A Java 17 Variant may be useful for those using newer Java versions, based on the assumption that newer bytecode will perform better.

Note to Java 17 Users

It is important that the variants use the same source code to keep development friction low. What this means:

• Switch blocks will not be replaced with switch expressions.
• Newer Standard Library APIs (newer than 11) will not be used

How this may be Accomplished

1. Add a "-java17" extension to an id in the maven coordinates.
2. Modify Gradle script to build Java 17 bytecode.

There are Strict Number List operations provided for Byte and Short types. They are important because these are the most limited Number types.

The remaining Number types are more common, and it would be great to have the same operations for them.

• int
• long
• float
• double

Originally posted by @DK96-OS in #62 (comment)

There is an Integer Range Java interface that can be enhanced by providing two simple implementations.

Fixed Integer Range

This implementation is constructed with the start and end of range values. The values will be declared as final.

Mutable Integer Range

The key difference with this implementation is that the start and end of range values can be modified.

Constructors

The range constructors will ensure that regardless of input values, the start of range value will not be greater than the end of range. No exceptions will be thrown, the values will be swapped.

These implementations can provide optional constructors with one parameter that uses zero as the other range endpoint.

Gradle 7.4 introduces a new plugin, test-report-aggregation.

This can simplify the build and test workflow, reducing the number of artifacts that are uploaded, and enabling all tests to be verified in one place.

Hopefully, each of the independent test classes will still be able to be read separately.