# Thread: When does this algorithm fail ?

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

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

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

5. 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. Sounds to me like the Extended Euclidean algorithm - Wikipedia, the free encyclopedia might apply here.

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

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

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

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