# Algorithm for division

Discussion in 'Homework Help' started by nonaaa, May 23, 2012.

May 23, 2012
8
0
2. ### Papabravo Expert

Feb 24, 2006
10,338
1,850
So is there a question about the algorithm?

3. ### nonaaa Thread Starter New Member

May 23, 2012
8
0
i want ASM and control implementation

4. ### nonaaa Thread Starter New Member

May 23, 2012
8
0
can i check my answer ?and if there is a mistake correct it to me ?

5. ### Papabravo Expert

Feb 24, 2006
10,338
1,850
Show us what you have so far. BTW, ASM = Algorithmic State Machine. Is that correct?

6. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
In other words, you want someone to do your homework for you?

Yes, but for us to check your answer, you have to provide your answer (and preferably describe the steps you took to get there). If there are mistakes, we will point them out and try to help you learn the concepts that will permit you to correct them.

7. ### atferrari AAC Fanatic!

Jan 6, 2004
2,663
783
What does it actually means?

ASM. Do you mean assembler perhaps?

Feb 24, 2006
10,338
1,850
9. ### nonaaa Thread Starter New Member

May 23, 2012
8
0
yes i mean "Algorithmic State Machine"

is that correct??

May 23, 2012
8
0
11. ### nonaaa Thread Starter New Member

May 23, 2012
8
0
and i want to know how to start to make the control circuit which make this Algorithm

12. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
It would help if you described, in words, your basic approach in coming up with your ASM diagram. For instance, something along the lines of:

The square root of X will be found by performing trials with Y. If X/Y > Y, then we know the true square root is greater than Y, while if it is less than Y we know that the true square root is less than Y. We will progressively narrow the range of possible values of Y by starting with Y=0 and then setting the most significant bit and performing our trial division. If Y needs to be increased, we will leave the bit set while, if Y needs to be decreased, we will clear the bit. In either case, we can then proceed to the next most significant bit. We are finished once we have performed a trial with the lsb and either set or cleared it accordingly.

If you can provide a coherent description of your basic approach in words, then it makes both generating the ASM and, for us, determining whether the ASM is doing what your description says, a lot easier.

A couple of questions based on your current ASM:

1) What are A, M, and Q? Describe, in words, what each of these variables means.

2) Where to M and Q come from? Keep in mind, if someone wants me to calculate the square root of 39753, they are only going to supply me with one number, namely 39753.

nonaaa likes this.
13. ### nonaaa Thread Starter New Member

May 23, 2012
8
0
thanks alot
but i don't know how to express this statement in my ASM " setting the most significant bit and performing our trial division. If Y needs to be increased, we will leave the bit set while, if Y needs to be decreased, we will clear the bit"
and if there is number like 17 it's square root isn't integer so i can't express it in binary numbers
there is example for using ASM to do the control circuit

i need ASM to make the control circuit so i can do this in logic works programe to test this circuit

14. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
First off, my description was merely an example of a high-level description of an algorithm. I'm making no claim that it is, or even should be, the algorithm you are trying to construct. But, whatever algorithm you are trying to build, if you can't describe what it is you are trying to do and how you are trying to go about doing it, then you have problems that need to be dealt with before you even start drawing an ASM. Think of the ASM as a road map for how to do something. Now think of planning a trip. Would you pull out an actual road map and start highlighting your route before you even decided whether you wanted to end up in Miami or Los Angeles? Of course not.

Your comment about the sqrt of 17 reveals that you do not understand what it is you are being asked to do. It's like your boss telling you to attend a conference in Phoenix and you start off by checking out the hotel prices in Chicago.

The problem statement very explicitly stated how to handle something like finding the square root of 17. It states, "The output is the smallest integer that is greater than or equals the square root."

Hence, the output for sqrt(17) should be 5.

A good start would be for you to try to describe, in words, how the division algorithm that was given as the starting point for your sqrt algorithm works. Unless you comprehend how and why it works as is, you stand almost no change of being able to modify it properly to do something else.

nonaaa likes this.
15. ### atferrari AAC Fanatic!

Jan 6, 2004
2,663
783
The title mentions division and the thread is about square root. Tell me about clear ideas of the problem.

nonaaa likes this.
16. ### nonaaa Thread Starter New Member

May 23, 2012
8
0

i want to have the squre root by using division
example M/Q=a if a= Q a it's squre root
16 /1 =16 so i will increase Q
16/2 =8
16 /4=4 Q=a so i have the squre root

17. ### WBahn Moderator

Mar 31, 2012
18,079
4,917
Good. You are on the right track.

Now expand your idea to the set of steps you would use for the following:

Find the square root of 36.

Find the square root of 48.

If you think you have an efficient algorithm at this point, try this one:

Find the square root of 39753.

If this turns out to be daunting, then you are still missing a key concept. But with what you already have, we should be able to lead you to that concept pretty quickly.

nonaaa likes this.
18. ### THE_RB AAC Fanatic!

Feb 11, 2008
5,435
1,305
In binary the square root always has roughly half the number of bits of the initial number.