1. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2003
Posts
3
Rep Power
0

#### 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!

2. posted twice for some reason...
Last edited by andy3109; February 20th, 2003 at 05:42 PM.
4. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Jan 2003
Location
Greece
Posts
63
Rep Power
16
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
Last edited by tony825; February 21st, 2003 at 04:52 AM.
5. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2003
Posts
3
Rep Power
0

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!
Last edited by DansZs; February 21st, 2003 at 07:34 AM.
6. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2003
Posts
10
Rep Power
0
I would start your code at the 'while' command, and skip the first 'if' command entirely. It's not necessary.
7. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2003
Location
Stockholm, Sweden
Posts
2
Rep Power
0
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
8. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2003
Location
Stockholm, Sweden
Posts
2
Rep Power
0
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
9. No Profile Picture
Junior Member
Devshed Newbie (0 - 499 posts)

Join Date
Feb 2003
Posts
3
Rep Power
0
Hey Thanks for the help Mats! Your algorithm looks good!!!!!