Multiplicative Reverse Fibonacci Sequence Algorithm Approach

Supermarcel10 commented 1 month ago

Description

Algorithm

The previous algorithm was hugely inefficient at high output counts AND/OR at huge variety inputs. This algorithm uses a different approach, using a batch strategy.

The batch strategy uses a reverse fibonacci sequence under a maximum defined ingot count.

Why use a reverse fibonacci sequence?

From mathematical proofs, the numbers in primes and fibonacci are easily combinable in multiples to make up a bigger number.

The maximum of 8 was chosen, since from my testing any desired output of under about ~10 ingots on my machine provided a very fast output with the current algorithm implementation.

A reverse strategy was used to provide a more aggressive and greedy algorithm, which attempts to saturate the full amount as fast as possible.

Complexity Measurements

Checking if a batch can be created multiple times only takes a complexity of O(nm) where n is the length of used minerals, and m is the length of available minerals. n is rarely > 5, making the average decent. Despite being poor in complexity, a scaling approach usually yields faster results, since they are multiplicative.

Scaling a batch takes a time complexity of O(n) where n is the length of used minerals, but in the event of an unscalable batch, it is not called, saving processing time.

Other parts of the algorithm remain mostly unchanged in terms of complexity, so if needed, further complexity cuts can be explored there.

Example

Desired Output: 14 ingots
Possible batches: {
  {8x1, 5x1, 1x1},
  {5x2, 2x2},
  ...
}

Tests

Tests have been added to accomodate stress testing this change.

The testing strategy has also been updated to use a custom runner and clean up a lot of repetition and complexity around testing the algorithm.

Type of change

[x] Bug fix
[x] New feature
[x] Enhancement
[x] Documentation update

How Has This Been Tested?

Stress tests have been made to test 100, 500 and 1000 ingot counts.

Checklist:

[x] My code follows the style guidelines of this project
[x] I have performed a self-review of my own code
[x] I have commented my code, particularly in hard-to-understand areas
[x] I have made corresponding changes to the documentation
[x] My changes generate no new warnings
[x] I have added tests that prove my fix is effective or that my feature works
[x] New and existing unit tests pass locally with my changes

Additional Notes

vercel[bot] commented 1 month ago

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated (UTC)
tfg-calculator	✅ Ready (Inspect)	Visit Preview	💬 Add feedback	Nov 2, 2024 4:56pm

sonarcloud[bot] commented 1 month ago

Quality Gate passed

Issues
0 New issues
2 Accepted issues

Measures
0 Security Hotspots
0.0% Coverage on New Code
0.0% Duplication on New Code

See analysis details on SonarCloud

Supermarcel10 / TFCCalculator