Re: little isprime challenge

Would it be faster to compute the square root of p, and use it as the loop
limit?
This would eliminate the need for the 'i*i' test.

If you want to keep the I*I test, there's a way to turn the multiplication
into
addition. Initial a new variable ISQUARE to 9 before the beginning of the
loop
and then update at the end with ISQUARE = ISQUARE + I + I + 1
or ISQUARE = ISQUARE + 2*I+1 (which is better depends on how
clever your compiler is, since multiplying by 2 can often be optimized into
a bit shift operation). Whether this will actually be faster is hard to
say, try it
and see.


"e p chandler" <epc8@xxxxxxxx> wrote in message
news:1124848022.896820.218980@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> Bart Vandewoestyne wrote:
>> I know there has been a kind of `string-challenge' in this group
>> which I have not been following... but it's been taking a while
>> and from what I've read I have the feeling that some people got
>> bored of it and now are definitely in need for something else...
>> so I have another little `isprime-challlenge' :-)
>>
>> It's just 100% pure for the fun of it, and maybe it will also
>> teach some more novices and `less experienced' young fortran
>> programmers as me good optimization skills. It might also be usefull for
>> some people in need for some prime routines.
>>
>> The `assignment' would be (I will try to formulate it as formal
>> as possible in order to avoid confusion...):
>>
>> "Write a standard Fortran 95 function isprime(p) that also adheres to
>> the F-language and that checks if the number p is a prime. The routine
>> should be as fast as possible (to be measured with the CPU_TIME
>> intrinsic.
>> 2 is considered to be a prime. The speed of your routine will be
>> measured
>> by checking the numbers 1,n where n is a very big number, whatever
>> `very big' may be ;-)"
>>
>> I've put up a skeleton file that is available online at
>>
>> http://www.cs.kuleuven.ac.be/~bartv/stuff/time_isprime.f95
>>
>> This is the file where you should add your version to.
>>
>> My first result on an Intel(R) Pentium(R) 4 CPU 2.40GHz running
>> a stable Debian GNU/Linux and compiled with the latest
>> F-compiler:
>>
>> bartv@vonneumann:~/fortran$ make time_isprime
>> F -o time_isprime -O4 time_isprime.f95
>> bartv@vonneumann:~/fortran$ ./time_isprime
>> Enter the number of points you want to time for: 10000000
>> Bart's method found 664579 primes in 27.120001 seconds.
>>
>> Good luck!
>> Bart
>> :-)
>>
>> --
>> "Share what you know. Learn what you don't."
>
> I'm going to go for the "fairly easy" and post the result of a simple
> modification to your function. Instead of testing the candidate against
> all numbers from 2 and up, why not test for 2, then test for
> divisibility by 2, then test against odd numbers from 3 and up?
>
> The core of my function is:
>
> res = .false.
>
> if (p < 2) then
> res = .false.
> return
> else if (p == 2) then
> res = .true.
> return
> else if (modulo(p,2) == 0) then
> res = .false.
> return
> else
> do i=3,p,2
> if (i*i > p) then
> res = .true.
> return
> else if (modulo(p,i) == 0) then
> res = .false.
> return
> end if
> end do
> end if
>
> Here's a run on a 2.8 GHz P4-HT under WinXP(SP2):
>
> C:\temp>F -O4 -o test.exe test.f95
>
> C:\temp>test
> Enter the number of points you want to time for: 10000000
> Bart's method found 664579 primes in 23.156250 seconds.
> Elliot's method found 664579 primes in 11.656250
> seconds.
>
> This took only a few minutes to write and test but it cut the run time
> nearly in half.
>
> If I was doing this program in ye olden days, I would have put in a
> COMMON block which contains an array holding the primes found so far.
> Then I would have divided by the list of primes already found. Of
> course F does not allow COMMON blocks. :-).
>


.

Relevant Pages

  • Re: little isprime challenge
    ... Bart Vandewoestyne wrote: ... The speed of your routine will be measured ... res = .false. ... COMMON block which contains an array holding the primes found so far. ...
    (comp.lang.fortran)
  • Re: Speed Speed Speed - Cutting down on wasted cycles
    ... result of my ignorance on how to best utilize VB6 coding techniques. ... So I had two sections within this one routine that were slowing ... I tacked first the Recordset issue first. ... Now I'm down to a loop that has to perform extensive date manipulation ...
    (microsoft.public.vb.general.discussion)
  • Re: massive data analysis with lisp
    ... while res do ... (loop for k being the hash-keys in movidx using (hash-value v) ... (if (not (gethash custid assoctab)) ...
    (comp.lang.lisp)
  • Re: Using ZLib
    ... >> If only it were so easy - I tried using a repeat..until loop, ... >when Count>bytes left, inflate() sets FZRec.avail_out to 0, otherwise ... the main exit condition, and suggest that you check your Delphi CD. ... routine to ensure that they are asking for /exactly/ the decompressed ...
    (comp.lang.pascal.delphi.misc)
  • Re: Math libarary
    ... thought would have been a bette routine than Math.Exp and I was wrong;/ ... Both of these depend on S only but have to take into account the boundaries. ... Right now I have two functions that essentially loop over S seperately. ... The following is the code I use to compute the laplacian of a scalar field. ...
    (microsoft.public.dotnet.languages.csharp)