Thread: 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.

> 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.

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.

Sounds to me like the Extended Euclidean algorithm - Wikipedia, the free encyclopedia might apply here.

Originally Posted by phantomotap

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.

Originally Posted by phantomotap

*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.

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.