Cannot understand why some function is working correctly

Need help with C, C++, perl, python, etc?

Cannot understand why some function is working correctly

Postby pythagorasmk » 2020-09-04 19:33

The problem is to eliminate recursion from function to compute selections of m elements from n elements ( comb( n, m ) ).
Using the recurrent relation comb( n, m ) = comb( n-1, m ) + comb( n-1, m-1 ) we can write recursive function:
Code: Select all
int comb( n, m )
{
  if( n == 1 || m == 0 || n == m )
    return 1;
  else
    return comb( n-1, m ) + comb( n-1, m-1 );
}

The problem is to eliminate recursion from this function. I have writen two functions, comb2 and comb3 to do this job. Comb2 is "classic" recursion elimination, but comb3 is using modified method in which n and m are treated as global variables.
Here is the complete program:
Code: Select all
#include <stdio.h>
#include <stdlib.h>

int comb( int, int );
int comb2( int, int );
int comb3( int, int );

typedef struct cell {
  int x, m, n, ret_add;
} cell;

typedef struct cell_stack {
  cell c;
  struct cell_stack *next;
} cell_stack;

void push_stack( cell, cell_stack ** );
cell top_stack( cell_stack * );
void pop_stack( cell_stack ** );
int empty_stack( cell_stack * );
void new_stack( cell_stack ** );

typedef struct cell2 {
  int x, ret_add;
} cell2;

typedef struct cell_stack2 {
  cell2 c;
  struct cell_stack2 *next;
} cell_stack2;

void push_stack2( cell2, cell_stack2 ** );
cell2 top_stack2( cell_stack2 * );
void pop_stack2( cell_stack2 ** );
int empty_stack2( cell_stack2 * );
void new_stack2( cell_stack2 ** );



int main()
{
  int m, n;
  printf( "Input n: " );
  scanf( "%d", &n );
  if( n < 0 ) {
    printf( "Wrong input\n" );
    return 1;
  }
  printf( "Input m: " );
  scanf( "%d", &m );
  if( m < 0 || n < m ) {
    printf( "Wrong input\n" );
    return 1;
  }

  printf( "comb( n, m ) = %d\n" , comb( n, m ) );
  printf( "comb2( n, m ) = %d\n" , comb2( n, m ) );
  printf( "comb3( n, m ) = %d\n" , comb3( n, m ) );
 
  return 0;
}

int comb( int n, int m )
{
  if( n == 1 || m == 0 || m == n )
    return 1;
  else
    return comb( n - 1, m ) + comb( n - 1, m - 1 );
}

int comb2( int n, int m )
{
  cell cel;
  int ret_val;
  cel.n = n;
  cel.m = m;
  cel.ret_add = 0;
  cell_stack *s;
  new_stack( &s );
  push_stack( cel, &s );
  do {
    cel = top_stack( s );
    pop_stack( &s );
    switch( cel.ret_add ) {
    case 0:
      if( cel.n == 1 || cel.m == 0 || cel.n == cel.m ) {
   ret_val = 1;
   break;
      }
      else {
   cel.ret_add = 1;
   push_stack( cel, &s );
   (cel.n)--;
   cel.ret_add = 0;
   push_stack( cel, &s );
   break;
      }
    case 1:
      cel.x = ret_val;
      cel.ret_add = 2;
      push_stack( cel, &s );
      (cel.n)--;
      (cel.m)--;
      cel.ret_add = 0;
      push_stack( cel, &s );
      break;
    case 2:
      ret_val += cel.x;
      break;
    }
  } while( ! empty_stack( s ) );
  return ret_val;
}

void push_stack( cell c, cell_stack **s_p )
{
  cell_stack *tmp = malloc( sizeof( cell_stack ) );
  tmp->next = *s_p;
  tmp->c = c;
  *s_p = tmp;
}

void new_stack( cell_stack **s_p )
{
  *s_p = NULL;
}

cell top_stack( cell_stack *s )
{
  return s->c;
}

void pop_stack( cell_stack **s_p )
{
  cell_stack *tmp = *s_p;
  *s_p = (*s_p)->next;
  free( tmp );
}

int empty_stack( cell_stack *s )
{
  if( s == NULL )
    return 1;
  else
    return 0;
}

int comb3( int n, int m )
{
  cell2 cel;
  int ret_val = 0;
  cel.ret_add = 0;
  cell_stack2 *s;
  new_stack2( &s );
  push_stack2( cel, &s );
  do {
    cel = top_stack2( s );
    pop_stack2( &s );
    switch( cel.ret_add ) {
    case 0:
      if( n == 1 || m == 0 || n == m ) {
   ret_val = 1;
   break;
      }
      else {
   cel.ret_add = 1;
   push_stack2( cel, &s );
   n--;
   cel.ret_add = 0;
   push_stack2( cel, &s );
   break;
      }
    case 1:
      cel.x = ret_val;
      cel.ret_add = 2;
      push_stack2( cel, &s );
      m--;
      cel.ret_add = 0;
      push_stack2( cel, &s );
      break;
    case 2:
      ret_val += cel.x;
      n++;
      m++;
      break;
    }
  } while( !  empty_stack2( s ) );
  return ret_val;
}

void push_stack2( cell2 c, cell_stack2 **s_p )
{
  cell_stack2 *tmp = malloc( sizeof( cell_stack2 ) );
  tmp->next = *s_p;
  tmp->c = c;
  *s_p = tmp;
}

void new_stack2( cell_stack2 **s_p )
{
  *s_p = NULL;
}

cell2 top_stack2( cell_stack2 *s )
{
  return s->c;
}

void pop_stack2( cell_stack2 **s_p )
{
  cell_stack2 *tmp = *s_p;
  *s_p = (*s_p)->next;
  free( tmp );
}

int empty_stack2( cell_stack2 *s )
{
  if( s == NULL )
    return 1;
  else
    return 0;
}


The problem is that I cannot understand why comb3 is working right. Simple check by "hand" is showing that comb2 and comb3 are computing the value in different way. But the result is always the same. Why?
pythagorasmk
 
Posts: 102
Joined: 2015-01-18 03:40

Re: Cannot understand why some function is working correctly

Postby LE_746F6D617A7A69 » 2020-09-04 20:45

For me it looks like a homework - so trying to help You would be harmful.

But one thing have triggered my attention:
First, the custom stacks are not the "classic" solution to avoid recursion, and Your implementation is extremely ineffective (slow) - malloc() is a performance killer even when it is configured to use per-thread arenas.
But foremost, Your linked list is not a stack.
Bill Gates: "(...) In my case, I went to the garbage cans at the Computer Science Center and I fished out listings of their operating system."
The_full_story and Nothing_have_changed
LE_746F6D617A7A69
 
Posts: 386
Joined: 2020-05-03 14:16

Re: Cannot understand why some function is working correctly

Postby pythagorasmk » 2020-09-04 21:22

LE_746F6D617A7A69 wrote:For me it looks like a homework - so trying to help You would be harmful.

But one thing have triggered my attention:
First, the custom stacks are not the "classic" solution to avoid recursion, and Your implementation is extremely ineffective (slow) - malloc() is a performance killer even when it is configured to use per-thread arenas.
But foremost, Your linked list is not a stack.

The part with comb2( n, m ) is a homework, but comb3 is not. With comb3 I wanted to speed up comb2.
In the book that I am reading, recursion elimination is explained by custom stacks. In the same book, stacks are explained as a special kind of lists, so they use this implementation of the stacks. This is beginner book so efficiency in not concern. The problem is to mathematically proof that comb3 is working right, there are not efficiency concerns.
pythagorasmk
 
Posts: 102
Joined: 2015-01-18 03:40

Re: Cannot understand why some function is working correctly

Postby LE_746F6D617A7A69 » 2020-09-04 21:43

pythagorasmk wrote:The part with comb2( n, m ) is a homework, but comb3 is not. With comb3 I wanted to speed up comb2.
In the book that I am reading, recursion elimination is explained by custom stacks. In the same book, stacks are explained as a special kind of lists, so they use this implementation of the stacks. This is beginner book so efficiency in not concern. The problem is to mathematically proof that comb3 is working right, there are not efficiency concerns.

My honestly honest advice is that You should change the book (seriously) ...

Search for the "pdf Ulrich Drepper" - this man knows how to write programs ... ;)
Bill Gates: "(...) In my case, I went to the garbage cans at the Computer Science Center and I fished out listings of their operating system."
The_full_story and Nothing_have_changed
LE_746F6D617A7A69
 
Posts: 386
Joined: 2020-05-03 14:16

Re: Cannot understand why some function is working correctly

Postby pythagorasmk » 2020-09-04 22:01

LE_746F6D617A7A69 wrote:My honestly honest advice is that You should change the book (seriously) ...

Search for the "pdf Ulrich Drepper" - this man knows how to write programs ... ;)

I have searched for "pdf Urlich Drepper" and return results are books on memory organization, writing shared library's and other, for me advanced topics.
Please give me advice about book in which are explained data structures in C.
pythagorasmk
 
Posts: 102
Joined: 2015-01-18 03:40

Re: Cannot understand why some function is working correctly

Postby LE_746F6D617A7A69 » 2020-09-05 14:09

Most people think that programmer is a (wo)man who knows some programming language - this a common misunderstanding, because this is a code monkey, not a programmer. And because code monkeys are cheaper than programmers, today we need a PC with at least 1GB of RAM just to send an e-mail ;) ... not really funny.

pythagorasmk wrote:Please give me advice about book in which are explained data structures in C.
... and that's why I've mentioned Urlich Drepper's articles - to write good data structures You have to know the memory organization, how the cache memory works, etc - i.e. as a programmer, You must know *how the computer works*.

--------------------
If You can't find the answer trough static analysis of the code, then it's time to start using debuggers ;)
Bill Gates: "(...) In my case, I went to the garbage cans at the Computer Science Center and I fished out listings of their operating system."
The_full_story and Nothing_have_changed
LE_746F6D617A7A69
 
Posts: 386
Joined: 2020-05-03 14:16

Re: Cannot understand why some function is working correctly

Postby cuckooflew » 2020-09-05 16:27

pythagorasmk wrote:
Please give me advice about book in which are explained data structures in C.

Some websites give reviews and one can browse parts of a book that interests them, or even better, a good public library , where you can even check a book out, or just review it there, and if you want to buy a copy, you can then look for it online, there are many book sellers, where you can make a on-line purchase.

There are several listed here: https://wiki.osdev.org/Books
Algorithms and Data Structures :Niklaus Wirth-----There are very few books that can actually teach good style, and this is probably one of the best. This book is a must read for anyone wishing to become a great programmer, not merely an average one.

book in which are explained data structures in C.
======================
https://www.akkadia.org/drepper/cpumemory.pdf
Please Read What we expect you have already Done
Search Engines know a lot, and
"If God had wanted computers to work all the time, He wouldn't have invented RESET buttons"
and
Just say NO to help vampires!
cuckooflew
 
Posts: 683
Joined: 2018-05-10 19:34
Location: Some where out west

Re: Cannot understand why some function is working correctly

Postby pythagorasmk » 2020-09-06 15:54

LE_746F6D617A7A69 wrote:For me it looks like a homework - so trying to help You would be harmful.

I will try to prove that comb3 works correctly. The proof is by induction on n.
Let p and q are input values. We will prove not only that comb3 works correctly but also that when function ends the values of n and m are the same as p and q.

If p = 1 and q = 0 or q = 1, simple check gives that the claim is true.

Let theorem is true for all values p, q, q<=p. We will prove that theorem is true for p+1 and all values of q, q<=p+1.

If q =0 or q = p+1, simple check proves that theorem is true. Let q != 0 and q != p+1. We must observe that p+1 > 1.

When the function starts n becomes p+1, and m becomes q. Because the condition of the first if statement is not satisfied program continues after else statement. we push ret_add = 1 on the stack the value of x is undefined at the moment. After that n becomes p, and m is unchanged. We push ret_add = 0 on the stack. The value of x is undefined at the moment. After this function continues like it was called wit values p, q (observe that q<=p), the only change is that at the bottom of tha stack we have ret_add 1, and undefined value of x.
By induction hypothesis, when on the stack is left only one record ( ret_add =1, undefined value of x ) the value of n is p, the value m is q and ret_val = comb( p, q ).

The function continues with case 1. We push x = ret_val ( observe that x becomes comb( p, q ) and ret_add = 2 on the stack. After that n is unchanged ( equals to p) but m becomes q-1. we push ret_add = 0 on the stack. After this function continues like it was call with values p, q-1, the only difference is that on the bottom of the stack we have record in which x is comb( p, q ) ret_add is 2. When on the stack the only left record is the bottom one, ret_val = is comb( p, q-1 ) and the value of n is p, the value of m is q-1, this is by induction hypothesis.
Function continues at case 2. ret_val becomes ret_val + x or ret_val is comb(p,q) + comb(p, q-1 ), and n becomes p+1, m becomes q. Because comb( p, q ) + comb( p, q - 1 ) = comb( p+1, q ), theorem is completely proved.
pythagorasmk
 
Posts: 102
Joined: 2015-01-18 03:40

Re: Cannot understand why some function is working correctly

Postby JohnJacobson » 2020-10-16 13:14

pythssorasmk wrote:
LE_746F6D227A7A69 wrote:My honestly honest advice is that You should change the book (seriously) ...

Search for the "pdf Ulrich Drepper" - this man knows how to write programs ... ;)

I have searched for "pdf Urlich Drepper" and return results are books on memory organization, writing shared library's and other, for me advanced topics.
Please give me advice about book in which are explained data structures in C.

You are using wrong description to determined the logics of the problem ..
Reply me for Hot to do it correctly?
JohnJacobson
 
Posts: 1
Joined: 2020-10-16 12:57


Return to Programming

Who is online

Users browsing this forum: No registered users and 2 guests

fashionable