ensj / fibpseudoprime Goto Github PK

Problem:

The current factorization algorithms we are using doesn't give us an output until everything is factored out into primes. This becomes a bigger problem as our numbers get too large to factor at a reasonable time.

Solution:

Thus, the solution is to implement a version of Lenstra's ECM that quits after it deems a number "unfactorable". We will likely use the factor package to do this.

Strategy:

1. Implement a custom version of ECM (that factors everything.)
2. Benchmark it against the package's ECM and a previous factoring algorithm we were using to optimize.
3. Integrate it into our full test and check how much further we can go, and how many unique fibpsps we generate.

Problem:

Is this really a problem? Perhaps we need faster methods to generate large fibonacci pseudoprimes.

Solution:

Implement the methods described in the following file.
Homework 2.pdf

Strategy:

We will likely need a prime number search function and a twin prime search function for this to be viable.

Problem:

Currently, we have no way to verify whether or not our output is completely accurate, save for professor Schaefer. We need to automate our test suite so we can check that we are getting correct results with each new change introduced to carlTest.

Solution:

We use hspec and QuickCheck to generate random tests for our various functions.

Strategy:

1. Create useful test functions for Spec.hs. (Do not test functions that can easily get out of hand though, like subsets)
2. Create tests to verify the following:
   • Verify that the factoring algorithm creates actual factors of the numbers we input.
   • Verify fibpsp spits out actual fibonacci pseudoprimes.
   • The other functions are rather trivial in function, so it's probably better to make an independent decision on whether or not making a test for it is useful.

Problem:

Right now, we are manually setting up test ranges for carlTest to work on, and carlTest doesn't give us an output until it finishes everything. This is problematic, especially if we jump into using a school computer for the project.

Solution:

We create a full test that automatically tests bigger ranges of numbers, and gives an aptly-named output after each iteration. (i.e. output_1-100.txt, output_101-200.txt, ...)

Strategy:

1. We start off by creating an infinite list in haskell from[1, 2, ...].
2. We partition each list by 100 (we can partition into smaller lists depending on the size of the smallest number in the partition as well)
3. We create a new output file named output_<start_ind>-<end_ind>.txt
4. We run carlTest on our first list and output the results to our newly created file. We repeat until... the program is forcefully stopped by the user?