Like Tree2Likes
  • 1 Post By phantomotap
  • 1 Post By manasij7479

When does this algorithm fail ?

This is a discussion on When does this algorithm fail ? within the C Programming forums, part of the General Programming Boards category; I want to determine if there is some a,b,c for which ax+by+cz=n ; (n,x,y,z>0) This is my function: Code: int ...

  1. #1
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498

    When does this algorithm fail ?

    I want to determine if there is some a,b,c for which
    ax+by+cz=n ; (n,x,y,z>0)
    This is my function:
    Code:
    int min(int x,int y,int z)
    {
        x=(y<x)?y:x;
        x=(z<x)?z:x;
        return x;
    }
    int check(int n,int x,int y,int z) /*0 for no, 1 for yes*/
    {
        if(n<min(x,y,z))
            return 0;
        else if(n==x||n==y||n==z)
            return 1;
        else
            return check(n-x,x,y,z)||check(n-y,x,y,z)||check(n-z,x,y,z);
    }
    I am testing it against random inputs, and in some cases it just never returns !
    (But that is probably not an asymptotic problem, as most equally large inputs give insta-results. )
    Code:
    #include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    int main(void)
    {
        int n,x,y,z;
        clock_t tms,tme;
        srand(time(NULL));
        while(1)
        {
            int m;
            n= rand() % 1000 +1;
            x= rand() % 100+1;
            y= rand() % 100+1;
            z= rand() % 100+1;
            printf("%d %d %d %d\n",n,x,y,z);
            tms = clock();
            m = check(n,x,y,z);
            tme = clock();
            printf("MM:%d\t%lf\n",m,((double)(tme-tms))/CLOCKS_PER_SEC);
        }
        return 0;
    }
    Is there any obvious problem in the recursive logic?
    Perhaps a missing base case ?
    More likely, this makes a very bad use case for recursion, like generating fibonacci nums, I'd like someone to confirm that.
    Last edited by manasij7479; 03-24-2013 at 06:24 AM.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,484
    > More likely, this makes a very bad use case for recursion, like generating fibonacci nums, I'd like someone to confirm that.
    Or you just run it in the debugger yourself.
    When it appears to lock up, just press ctrl-C, ctrl-break (or whatever your debugger manual says) to break the program.
    Then look in the debugger to see how deep the stack is.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    Is there any obvious problem in the recursive logic?
    O_o

    It depends on your definition of "obvious".

    Serious Hint: The check devolves into a simpler series depending on inputs.

    Playful Hint: We go allllll the way down. And we come back up. And we go allllllll the way down. And we come back up.

    More likely, this makes a very bad use case for recursion, like generating fibonacci nums, I'd like someone to confirm that.
    Memoization or How I Learned to Stop Worrying and Learned to Stop Worrying and Learned to Stop Worrying and Learned to Stop Worrying and...

    This is a bad use of recursion because your implementation is flawed.

    I wouldn't recommend the use of recursion here, but you are clearly trying to blame the tool for your problem.

    If you didn't implement it properly, the iterative version would have the same problem.

    Soma

  4. #4
    Registered User
    Join Date
    May 2009
    Posts
    2,541
    I want to determine if there is some a,b,c for which
    ax+by+cz=n ; (n,x,y,z>0)
    This is my function:
    Without any limits on the allowed values of a,b,c; the answer is always true.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  5. #5
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    Without any limits on the allowed values of a,b,c; the answer is always true.
    O_o

    I imagine that we are to assume integers.

    Soma

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Sounds to me like the Extended Euclidean algorithm - Wikipedia, the free encyclopedia might apply here.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    May 2009
    Posts
    2,541
    Quote Originally Posted by phantomotap View Post
    O_o

    I imagine that we are to assume integers.

    Soma
    Better assume positive integers; because if negative or zero allowed the answer is still true.
    I am not even sure what happens if one is allowed for A,B,C.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  8. #8
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,213
    Sounds to me like the Extended Euclidean algorithm - Wikipedia, the free encyclopedia might apply here.
    *sigh*

    I wish I math'd better; it took me entirely too long to read that.

    Better assume positive integers; because if negative or zero allowed the answer is still true.
    If I understand your concern: 2 2 2 3

    Soma
    stahta01 likes this.

  9. #9
    Registered User
    Join Date
    May 2009
    Posts
    2,541
    Quote Originally Posted by phantomotap View Post
    *sigh*

    I wish I math'd better; it took me entirely too long to read that.



    If I understand your concern: 2 2 2 3

    Soma
    I now see, that I was mistaken, there are values that have no whole number solution.

    Tim S.
    "Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the universe trying to produce bigger and better idiots. So far, the Universe is winning." Rick Cook

  10. #10
    Registered User manasij7479's Avatar
    Join Date
    Feb 2011
    Location
    Kolkata@India
    Posts
    2,498
    I'd say, whole numbers.
    Memoization seems to have solved it, with a nice pair of mutually recursive functions.
    Code:
    #include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    int min(int x,int y,int z)
    {
        x=(y<x)?y:x;
        x=(z<x)?z:x;
        return x;
    }
    int check(int n,int x,int y,int z);
    int check_rec(int n,int x,int y,int z) /*-1 for no, 1 for yes*/
    {
        if(n<min(x,y,z))
            return -1;
        else if(n==x||n==y||n==z)
            return 1;
        else
            return (check(n-x,x,y,z)==1||check(n-y,x,y,z)==1||check(n-z,x,y,z)==1)?1:-1;
    }
    int check(int n,int x,int y,int z)
    {
        static int* table=NULL;
        if(!table)
            table=calloc(1000,sizeof(int));
        if(n<0)
            return -1;
        if(table[n]==0)
            table[n]=check_rec(n,x,y,z);
        return table[n];
    }
    int main(void)
    {
        int n,x,y,z;
        clock_t tms,tme;
        srand(time(NULL));
        while(1)
        {
            int m;
            n= rand() % 999 +1;
            x= rand() % 100+1;
            y= rand() % 100+1;
            z= rand() % 100+1;
            printf("%d %d %d %d\n",n,x,y,z);
            tms = clock();
            m = check(n,x,y,z);
            tme = clock();
            printf("MM:%d\t%lf\n",m,((double)(tme-tms))/CLOCKS_PER_SEC);
        }
        return 0;
    }
    Now, I'd look for a while trying to find a better solution.
    I'm not yet totally sure how Euclid's Algorithm can help, but the similarity is worth investigating more.
    Last edited by manasij7479; 03-25-2013 at 09:01 AM.
    stahta01 likes this.
    Manasij Mukherjee | gcc-4.8.2 @Arch Linux
    Slow and Steady wins the race... if and only if :
    1.None of the other participants are fast and steady.
    2.The fast and unsteady suddenly falls asleep while running !



Popular pages Recent additions subscribe to a feed

Similar Threads

  1. fail to count digit of an integer (fail at 9)
    By azsquall in forum C++ Programming
    Replies: 3
    Last Post: 05-02-2008, 09:42 AM
  2. I fail at learning...
    By indigo0086 in forum A Brief History of Cprogramming.com
    Replies: 20
    Last Post: 07-07-2006, 08:14 AM
  3. Why does this fail?
    By kryonik in forum C++ Programming
    Replies: 8
    Last Post: 04-08-2006, 03:09 PM
  4. cin.fail
    By bj31t in forum C++ Programming
    Replies: 3
    Last Post: 04-01-2004, 02:26 PM
  5. help with cin.fail()
    By volk in forum C++ Programming
    Replies: 6
    Last Post: 04-02-2003, 02:32 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21