# Algorithm use

## Algorithm use

Hi there,

Just a thought regarding the "original creation" phrase in the rules:
how would it be viewed if I said, for example, "I implemented algorithm
ABC by John Smith to solve this problem"? Assuming that the algorithm
is in the public domain, of course, and available to be used by anyone (for non-commercial use at least),
is that all OK?

This wasn't really much of an issue for the Maze of Life, but there's
plenty of commentary out there about calculation of prime numbers. It's
hard to say whether implementing an advanced algorithm would be
practical in a limited time, but well, it'd be interesting to know :)

Thanks!

9 posts / 0 new
For more complete information about compiler optimizations, see our Optimization Notice.

Hi,
You can refer to an algorithm and use it to solve this problem.

Thanks
-Rama

Hi Rama

algorithm is fine but what about precomputed stuff like calculation of prime numbers before hand & using hardcoded stuff either in program or in some txt file.
is this allowed?

Thanks
Hitesg

My rhetoric question?

How is it possible to calculate 78^9 with 5 multiplications :)

(78*78)*(78*78)*(78*78)*(78*78)*78
=
(6084*6084)*(6084*6084)*78
=
37015056*37015056*78
=
1370114370683136*78
=
106868920913284608

:)

I have got another one:

A number needs only to be divisible by a prime not to be prime.

If you use the Nth root you can compute it using the formula Nth_root = exp[ 1/N * ln ( a ) ]
then you can move ln( a ) out of the loop over N :

tmp = ln ( a );
for(int N=2; N<=maxPow; N++)
root = exp( 1./N * tmp );

...

You can save many logarithmic calculations.

How are you calculating ln(a)? After implementing this method, I unfortunately found that the log function of the cmath library is not accurate enough for our purposes. To confirm my findings:"Function:doublelog(doublex)This function returns the natural logarithm ofx.exp (log (x))equalsx, exactly in mathematics and approximately in C."from the GNU C libraryhttp://www.gnu.org/s/hello/manual/libc/Exponents-and-Logarithms.html#Exponents-and-LogarithmsI don't wish to be convicted of treason, but I think AMD has a mathematics library as well. I don't know if their log function is more accurate, however.

This is true, many mathematical functions should be used with considerable caution...

Even though varslan's statement could be quite helpful, I implement the inaccurate log power only as a starting point for the root and then adjust the root before following up with an efficient (and accurate) power calculation.

Regards

I tried gmp.h and mkl_gmp.h libraries to perform calculation of prime numbers.
They give accurate results and they are better than my non-probabilistic code.