February 20th, 2003, 04:36 PM
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, 05:11 PM
posted twice for some reason...
Last edited by andy3109; February 20th, 2003 at 05:42 PM.
February 20th, 2003, 05:12 PM
ou tof curiosity, what was your answer on the bonus?
February 21st, 2003, 04:47 AM
How can you use "some" digits of number n to make the division?
1236 | 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.
|1| --> |2| --> |3| --> |6| --> NULL
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.
February 21st, 2003, 07: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.
else if m<=n
This was my pseudocode on the test which the professor replied: "Correct, but slow"
Last edited by DansZs; February 21st, 2003 at 07:34 AM.
February 22nd, 2003, 06: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, 07:05 PM
This should do the trick...
public loops as integer
loops = 0
return iterator(0, m, n)
iterator(startval, m, n)
val = n
times = 1
target = m - startval
While val < target
loops = loops + 1
times = times * 2
val = val * 2
If times = 1 Then
return (times / 2) + iterator(startval + val / 2, m, n)
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...
February 22nd, 2003, 07:12 PM
Realised that I used a couple of divisions (/2)
but store the previous values in temporary variables and you'll get rid of them...
February 23rd, 2003, 08:05 PM
Hey Thanks for the help Mats! Your algorithm looks good!!!!!