Loading ...
Sorry, an error occurred while loading the content.

programming

Expand Messages
  • Devaraj Kandadai
    A QUESTION ABOUT PROGRAMMING This pertains to my post: “An indirect primality test of......” For the sake of this example let x = 1000 i.e. The prime
    Message 1 of 2 , Jun 3, 2009
    • 0 Attachment
      A QUESTION ABOUT PROGRAMMING


      This pertains to my post: �An indirect primality test of......�


      For the sake of this example let x = 1000 i.e. The prime suspect is 1000^2
      + 1.


      My operation in pari would be


      if(Mod(1000^2+1,2)= =1, print(�It is an integer�)


      if(Mod(1000^2+1,5)= =2,print(�It is an integer�)


      if(Mod(1000^2+1,10)= =3,print(�It is an integer�)


      .if(Mod(1000^2+1,17))= = 4,, print(�It is an integer�) and so on.


      I can program the above as follows:


      {p(k)=if (Mod(1000^2+1,k^2+1)= =k, print(�It is an integer�))}


      for(k=1,500,print(p(k)))


      Q: Is there a better program?


      My knowledge of programming is elementary.

      Devaraj


      [Non-text portions of this message have been removed]
    • Maximilian Hasler
      ... The idea is to avoid large numbers. If you write Mod( big^something ...) you did not avoid anything. If you write Mod( big, m )^something then you create
      Message 2 of 2 , Jun 3, 2009
      • 0 Attachment
        --- In primenumbers@yahoogroups.com, Devaraj Kandadai <dkandadai@...> wrote:

        > My operation in pari would be
        > if(Mod(1000^2+1,2)= =1, print("It is an integer")

        The idea is to avoid large numbers.
        If you write Mod( big^something ...)
        you did not avoid anything.
        If you write Mod( big, m )^something
        then you create "big" as "an element of Z/mZ"
        (and thus "smaller than" m)

        The exponentiation is not a problem even for large exponents, since it can be done in O(log(exponent)) steps.

        When you do the calculation "in Z/mZ", then the number becomes never larger than m, and so the calculation is very fast.


        > .if(Mod(1000^2+1,17))= = 4,, print("It is an integer") and so on.

        should be

        if( Mod(1000,17)^2+1==4, print(integer))

        well, actually this works since (I think) a==4 is transformed into
        a-4 = 0,
        and Mod(x,y)+z is transformed into Mod(x+z,y)


        > {p(k)=if (Mod(1000^2+1,k^2+1)= =k, print("It is an integer"))}
        > for(k=1,500,print(p(k)))
        >
        > Q: Is there a better program?

        yes:
        {p(k)=if (Mod(1000,k^2+1)^2 + 1 == k, print("It is an integer"))}

        > My knowledge of programming is elementary.

        This is more "conceptual" than "programming", the idea being to work in Z/nZ right from the start, and not to do the reduction mod n
        only at the very end, when numbers may have grown huge.

        Maximilian
      Your message has been successfully submitted and would be delivered to recipients shortly.