Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

?gcd(x c y , z)

  • 12-03-2011 1:21pm
    #1
    smslca
    Registered Users, Registered Users 2 Posts: 28 ✭


    can we find the value of gcd(x c y , z) easily and very fast using a computer.

    where
    1. "c" represents "combinations" used in 'permutations and combinations'.
    2. x is very very large number (ex: may be of 100 or 1000 numerical digits)
    3. y is also large having 2 to 5 digits less than x.
    4. z is also large having the same number of digits as x.


Comments

  • #2
    RoundTower
    Registered Users, Registered Users 2 Posts: 5,083 ✭✭✭RoundTower


    interesting question, I can't think of any obvious way to do it.

    do you have an application in mind?


  • #3
    ZorbaTehZ
    Registered Users, Registered Users 2 Posts: 2,149 ✭✭✭ZorbaTehZ


    http://en.wikipedia.org/wiki/Euclidean_algorithm


  • #4
    Professor_Fink
    Registered Users, Registered Users 2 Posts: 861 ✭✭✭Professor_Fink


    smslca wrote: »
    can we find the value of gcd(x c y , z) easily and very fast using a computer.

    No, there is no known efficient algorithm. Such an algorithm would provide an efficient means to factor large integers for which there is no known polynomial time algorithm. The best algorithm runs in O(exp(n^1/3 (log n)^2/3), which then gives a lower bound for the runtime of the best known algorithm for your problem.


Advertisement