Division Algorithm

Hi all! I'm new to the board, but I browsed it some today and this place looks great! On of the reasons I hit on it was because I was looking for help on a homework problem I have for my Algorithms class and figured this would be the place to find it!

Basically, I have to design a Division Algorithm DIVIDE(n, m) (n and m being positive integers) using only addition, multiplication, and subtraction and the running time for the algorithm must be better than Big Theta(n/m). If the numerator won't divide evenly, the algorithm rounds down.

I've already had this problem once in class on my last test, but it was a bonus problem, and although my algorithm was correct, it ran in Big Theta(n/m) time, so I only received 1 out of the 3 bonus points on the test. Now it's on my homework assignment and I'd like to finally beat this thing!

Thanks in advance for your help!

posted twice for some reason...

ou tof curiosity, what was your answer on the bonus?

How can you use "some" digits of number n to make the division?

1236 | 6
.........|__
.........|
.........|
12/6 =2
0
36/6 =6

thats the easy part;
but how the heck can someone "find" the 12 w/o dividing it first with 10 (123) then with 100 (12) or backwards firts with 1000 (1) then with 100 (12) ?

i have i clue in using data-structs like queues but this will make the running time toooooooooo big.

out.............................. in
..|..................................|
.V.................................V
|1| --> |2| --> |3| --> |6| --> NULL

=1236

btw : had to edit cause the blank spaces were deleted so i changed them with dots

Hey! I appreciate all the help so far! You guys are great. I should have posted the code I wrote so far to begin with. The idea I came up with was that you can keep a count of how many times you add a number to itself until you get to the numerator. For example, 9/2: 2+2+2+2, so the count would equal 4 which is the floor division of 9/2. Unfortunately, this runs in Theta(n/m) time, so it won't get me full credit on the assignment.

My code:

DIVIDE(n,m)
if m>n
..return 0
else if m<=n
..while m<=n
......count++
......m=m+m
......if m<=n
.........n=n-m
.........count++

return count


This was my pseudocode on the test which the professor replied: "Correct, but slow"

Thanks again!

I would start your code at the 'while' command, and skip the first 'if' command entirely. It's not necessary.

This should do the trick...

public loops as integer

divide(m,n)
loops = 0
return iterator(0, m, n)
end

iterator(startval, m, n)
val = n
times = 1
target = m - startval

While val < target
loops = loops + 1
times = times * 2
val = val * 2
Wend

If times = 1 Then
return 0
Else
return (times / 2) + iterator(startval + val / 2, m, n)
End If
End

it doubles the value of n for each loop until it hits m
then it restarts at the previous value by adding doubles of
n to that value.

I tested it and it works fine and fast.

Hope you like it...
/Mats

Sorry...

Realised that I used a couple of divisions (/2)
but store the previous values in temporary variables and you'll get rid of them...

/Mats

Hey Thanks for the help Mats! Your algorithm looks good!!!!!