Runtime of Seemingly Unpredictable Division Algorithm

[matineesuxxx]

Last week on my computer science assignment I had to write a division algorithm using only addition and subtraction to tackle a problem. My first attempt was the simple and naive repeated subtraction, although I quickly discovered it was not nearly efficient enough for how I needed to use it, So I developed a quicker one. (I have attached a PDF of the algorithm, and the C code for any who are interested in helping)

The problem is that I want to find the runtime, however I cannot predict when the division will reset with a new numerator, thus I have not even the slightest clue as to the worst case scenario.

Can anybody give me some advice on how to estimate the runtime of such algorithms?

Code:

int div_help(int a, int b, int bconst, int quotient, int acc){
  if(a-b<0){return 0;}
  if(b==a){return quotient+acc;}
  return b+b > a ? div_help(a-b,bconst, bconst,1,acc+quotient):div_help(a,b+b, bconst,quotient+quotient,acc);
}

int div(int a, int b){
  div_help(a,b,b,1,0);
}

[edit] I don't know if there is a way to properly post code here, so the whitespace at the beginning of each line of code doesn't show up.

 

[jtbell]

[edit] I don't know if there is a way to properly post code here, so the whitespace at the beginning of each line of code doesn't show up.

Enclose the code between [code] and [/code] tags. I did it for you for this thread.

 

[matineesuxxx]

Enclose the code between [code] and [/code] tags. I did it for you for this thread.

Thank you very much.

 

[FactChecker]

For given inputs a and b you can write an equation for how many calls to div_help it will need to do. Each call requires about the same amount of time, time_one_call, so multiply the number of calls by that time. My guess is that it will take about time_one_call * a / b

A few comments:
1) I don't see any correspondence between the algorithm in the PDF and your code. The PDF is based on powers of 2, and that doesn't appear in your code at all. You are using repeated addition / subtraction by means of recursive calls.
2) Don't hesitate to add comments to your code. You can even put a single statement on several lines and put a comment on each line. When you are using recursion, you should explain what you are doing with comments.
3) Function calls can take a long time compared to simple arithmetic and loops. Your use of recursive function calls just to repeatedly add / subtract will run a lot slower.
4) Recursive calls often requires special care to make sure that a lower level call is not corrupting a variable whose value needs to be retained in a higher level call. That is language dependent.

 

[matineesuxxx]

2) Don't hesitate to add comments to your code. You can even put a single statement on several lines and put a comment on each line. When you are using recursion, you should explain what you are doing with comments...

Yes, I should have commented the code.

// To caclulate a/b.
// PRE: a > 0, b > 0.
// This implementation simlpy returns 0 if b does not divide a.

int div_help(int a, int b, int bconst, int quotient, int acc){

  // a: numerator
  // b: denominator
  // bconst: original denominator (constant)
  // quotient: numerator that is doubled
  // acc: accumulator

  printf("(%d, %d, %d)\n",a,b,acc);
  if(a-b<0){return 0;}
  if(b==a){return quotient+acc;}

  /*b+b is doubling the denominator then checking if its bigger than a, (largest denominator less than or equal to a)*/
  /*a-b is replacing the old numerator with a-b, and keeping constant denominator, or bconst */

  // if b+b > a, then the new numerator becomes a-b, and reset the denominator, increase acc
  // by the correct power of 2 (which is quotient)

  return b+b > a ? div_help(a-b,bconst, bconst,1,acc+quotient):div_help(a,b+b, bconst,quotient+quotient,acc);
  // else keep doubling the denominator and quotient.

1) I don't see any correspondence between the algorithm in the PDF and your code. The PDF is based on powers of 2, and that doesn't appear in your code at all. You are using repeated addition / subtraction by means of recursive calls...

This is probably because I had not commented my code, however I assure you they are one in the same. Since I was not allowed to multiply i had to repeatedly add the denominator, b, to itself and same with quotient.

here is the same example from the pdf as presented by the code code:

(a, b, quotient)

(50, 7, 1)
(50, 14, 2)
(50, 28, 4)
(22, 7, 1)
(22, 14, 2)
(8, 7, 1)
(1, 7, 1)

7 + 1/7

 

[FactChecker]

Yes, I should have commented the code.

Wow! That is a lot better. If everyone commented like that, programming would be a lot more fun.

 

[matineesuxxx]

Wow! That is a lot better. If everyone commented like that, programming would be a lot more fun.

Thanks.

About the recursion, the way I derived the algorithm, it just seemed natural to use recursion, and so far in my course we are not permitted to use any imperative programming techniques as of yet.

 

[willem2]

The runtime would be easier to compute with an inner loop where you would double b until you got the largest number of the form b * 2^n that was <=a, and an outer loop where you would subtract the result from the inner loop and then execute the inner loop again with a - b * 2^n instead of a until you got 0. The recursive function rather obscures this.
In a functional programming style you could use 2 functions, 1 function that computes both the largest b * 2^n <= a and 2^n as well, since we have to add it to the result, and an outer function div(a,b) which returns 2^n + div (a - 2^n b, b).
In a C program, the inner function would have to return a struct.

It's simple to see that b=1 will produce the largest number of iterations in the inner loop: 2log(a) = (the number of binary digits of a).

Every step of the outer loop will make a smaller. Since there is a power of two with a/2 <= 2^n <=a, a will get at least twice as small after each step of the outer loop, so a will lose 1 binary digit at least. If a is of a special form, it's possible to show that a will lose exactly 1 binary digit at each step, so the outer loop will take 2log(a_0) iterations as well. Of course the number of iterations of the inner loop depends on the running value of a as well, so you still have a sum to calculate.