Algorithm improvments research

TNTU-RS-internship / PrimeNumbersTask

Inteview challenge

0 stars 0 forks source link

Algorithm improvments research #2

Open vitalyte opened 6 months ago

vitalyte commented 6 months ago

Add new method isPrimeNumber_improved with improved algorithm. Research what should be improved. Make tests for input 67280421310721L

isPrimeNumber_improved calculate value 10 times output min, max and median time
isPrimeNumber calculate value 10 times output min, max and median time

Verify your improvements for isPrimeNumber_improved
Explain min and max for the same input values and the same algorithm.

VitaliiBalaiev commented 6 months ago

New method isPrimeNumber_improved() is implemented in algorithm-research branch. It's using the Miller–Rabin primality test, which determines whether number is likely to be prime. It is much more efficient for large numbers.

vitalyte commented 5 months ago

@VitaliiBalaiev Add table with values for Explain min and max for the same input values and the same algorithm. in the comments for this issue.

VitaliiBalaiev commented 5 months ago

What the table should look like? What tools should I use?

VitaliiBalaiev commented 5 months ago

These are timed tests results for both methods, it is included in PrimeCheckerTest in algorithm-research branch.

isPrimeNumber() Execution Times (nanoseconds):
Min: 18667100 (18ms)
Max: 21795500 (21ms)
Median: 20061200 (20ms)

isPrimeNumber_improved() Execution Times (nanoseconds):
Min: 122100 (0ms)
Max: 235800 (0ms)
Median: 182700 (0ms)

It is normal for run time to be different min and max for same inputs and algorithm as computer is running many things, including OS, not only that piece of code and this will affect CPU clock speeds. It is considered normal to have variations around at least 20-30% in runtime.