February 20th, 2003, 05:36 PM

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!
February 20th, 2003, 06:11 PM

posted twice for some reason...
Last edited by andy3109; February 20th, 2003 at 06:42 PM.
hmmm...
February 20th, 2003, 06:12 PM

ou tof curiosity, what was your answer on the bonus?
hmmm...
February 21st, 2003, 05:47 AM

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 datastructs 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 05:52 AM.
No sign
February 21st, 2003, 08:30 AM

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=nm
.........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 08:34 AM.
February 22nd, 2003, 07:45 AM

I would start your code at the 'while' command, and skip the first 'if' command entirely. It's not necessary.
February 22nd, 2003, 08:05 PM

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
February 22nd, 2003, 08:12 PM

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
February 23rd, 2003, 09:05 PM

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