Subversion Repositories integer_square_root

# Integer Square Root

# Integer Square Root

## Algorithm

## Algorithm

```

```

procedure ISR(value)

procedure ISR(value)

        for i<-31 to 0 do

        for i<-31 to 0 do

                proposed_solution[i]<-1

                proposed_solution[i]<-1

                if proposed_solution^2 > value then

                if proposed_solution^2 > value then

                        proposed_solution[i]<-0

                        proposed_solution[i]<-0

                end if

                end if

        end for

        end for

end procedure

end procedure

```

```

## Specification

## Specification

- If reset is asserted during a rising clock edge (synchronous reset), the value signal is to be stored.

- If reset is asserted during a rising clock edge (synchronous reset), the value signal is to be stored.

- If reset is asserted part way through a computation, the result of that computation is discarded and a new value is latched into the module.

- If reset is asserted part way through a computation, the result of that computation is discarded and a new value is latched into the module.

- When the module has finished computing the answer, the output is placed on the result line and done line is raised on the same cycle.

- When the module has finished computing the answer, the output is placed on the result line and done line is raised on the same cycle.

- It must not take more than 600 clock cycles to compute a result (from the last

- It must not take more than 600 clock cycles to compute a result (from the last

  clock that reset is asserted to the first clock that done is asserted.)

  clock that reset is asserted to the first clock that done is asserted.)

## ISR State Machine

## ISR State Machine

Computing: $\sqrt{\mathtt{value}}$

Computing: $\sqrt{\mathtt{value}}$

- On a reset

- On a reset

  - guess initialized to `32'h8000_0000`

  - guess initialized to `32'h8000_0000`

  - `value` is clocked into a register

  - `value` is clocked into a register

- guess gets the next bit set each time we cycle through the FSM again

- guess gets the next bit set each time we cycle through the FSM again

- Square `guess` (multiply it with itself)

- Square `guess` (multiply it with itself)

  - Wait until the multiplier raises its done

  - Wait until the multiplier raises its done

- if `guess` <= `value`

- if `guess` <= `value`

  - Keep the current bit

  - Keep the current bit

- else

- else

  - Clear the current bit

  - Clear the current bit

- Move to the next bit

- Move to the next bit