Algorithm writing tips? - Printable Version

Algorithm writing tips? - Printable Version

+- Southperry.net (https://www.southperry.net)
+-- Forum: Social (https://www.southperry.net/forumdisplay.php?fid=14)
+--- Forum: Rubik's Cube (https://www.southperry.net/forumdisplay.php?fid=58)
+--- Thread: Algorithm writing tips? (/showthread.php?tid=7282)

Pages: 1 2

Algorithm writing tips? - Nikkey - 2009-01-18

Stereo Wrote:Something I thought about later... sqrt is not cheap (iirc it uses Newton's method to approximate?).

primesList.get(i) <= Math.sqrt(n)
Use
primeslist.get(i)**2 <= n

Depends on what language you use. Shouldn't it equal to Math.pow(n, 0.5), which uses logaritms?

edit: Implementation-dependent:
[Image: sqrtms2.png]

Anyway, I save the value instead of recalculating it. e.g:

sqrt = (int) Math.sqrt(n)
for (i = 5; i < sqrt; i += 6)

instead of:

for (i = 5; i < Math.sqrt(n); i += 6)

Algorithm writing tips? - Stereo - 2009-01-18

Logarithms in turn would use iteration most likely though, they're another non basic operation.

Prestoring the value would work except I think its being called a lot of times and would still have to calculate the more complicated sqrt instead of just ^2 every time.

Algorithm writing tips? - KajitiSouls - 2009-01-18

Stereo Wrote:Logarithms in turn would use iteration most likely though, they're another non basic operation.

Prestoring the value would work except I think its being called a lot of times and would still have to calculate the more complicated sqrt instead of just ^2 every time.

For the purposes of the isPrime() function, calculating a pre-stored square of the number being indexed doesn't work. Pre-stored variables are a good choice only on the static limits of a loop, and assuming said loops aren't extremely short in duration.

For the function isPrime(int n):

Code:
if(preliminary tests failed) return false;

int upperLimit = sqrt(n);

for(int factor = x; factor <= upperLimit; increment factor by f(y)){

  if(n % factor == 0) return false;

}

return true;

Code:
if(preliminary tests failed) return false;

for(int factor = x; factor*factor <= n; increment factor by f(y)){

  if(n % factor == 0) return false;

}

return true;

Pre-storing the sqrt of n is noticeably faster than calculating the square of a number when used in the final algorithm I posted.

EDIT: What's the difference in Run Time and Real Time? (referring to DS's picture)

EDIT2: Thoughts confirmed xD

Algorithm writing tips? - Stereo - 2009-01-18

Algorithm writing tips? - Nikkey - 2009-01-19

KajitiSouls Wrote:EDIT: What's the difference in Run Time and Real Time? (referring to DS's picture)

Real time = lag, if any.

Spoiler

No lag on faster computers! Redface