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

    Join Date
    Feb 2003
    Posts
    3
    Rep Power
    0

    Smile 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!
  2. #2
  3. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2002
    Posts
    421
    Rep Power
    12
    posted twice for some reason...
    Last edited by andy3109; February 20th, 2003 at 05:42 PM.
    hmmm...
  4. #3
  5. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2002
    Posts
    421
    Rep Power
    12
    ou tof curiosity, what was your answer on the bonus?
    hmmm...
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2003
    Location
    Greece
    Posts
    63
    Rep Power
    12
    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.
    No sign
  8. #5
  9. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    Feb 2003
    Posts
    3
    Rep Power
    0

    Thumbs up


    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.
  10. #6
  11. 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.
  12. #7
  13. 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
  14. #8
  15. 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
  16. #9
  17. 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!!!!!

IMN logo majestic logo threadwatch logo seochat tools logo