Results 1 to 2 of 2

Math Help - Help with question on computation time?

  1. #1
    Junior Member
    Joined
    Aug 2007
    Posts
    28

    Help with question on computation time?

    Can someone help with this question?

    Rank the following in order of computation time from quickest to slowest, with m and n being 100 diget random numbers.

    1. factor m
    2. find gcd(m,n)
    3. find two "probable primes" larger than m with a probabilty error of less than 10^-8

    The answer lists them as 2,3,1

    why is this? i would of thought 3 would be slowest and 1 quickest
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by BruceBronson View Post
    Can someone help with this question?

    Rank the following in order of computation time from quickest to slowest, with m and n being 100 diget random numbers.

    1. factor m
    2. find gcd(m,n)
    3. find two "probable primes" larger than m with a probabilty error of less than 10^-8

    The answer lists them as 2,3,1

    why is this? i would of thought 3 would be slowest and 1 quickest
    Look at your notes for the algorithms to do these things and compare
    operations counts.

    You could also look at the computational complexity of the problems, but that
    would not answer the question as it refers to a particular size of problem
    (though I expect that is what your instructor expects you to do).

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 23rd 2011, 05:21 PM
  2. Replies: 1
    Last Post: May 25th 2010, 01:32 AM
  3. help with computation
    Posted in the Calculus Forum
    Replies: 2
    Last Post: November 2nd 2009, 07:21 PM
  4. Simple computation?
    Posted in the Algebra Forum
    Replies: 4
    Last Post: April 14th 2009, 07:47 AM
  5. computation
    Posted in the Algebra Forum
    Replies: 2
    Last Post: April 8th 2009, 03:36 AM

Search Tags


/mathhelpforum @mathhelpforum