Integer Square Root

Algorithm

procedure ISR(value)
	for i<-31 to 0 do
		proposed_solution[i]<-1
		if proposed_solution^2 > value then
			proposed_solution[i]<-0
		end if
	end for
end procedure

Specification

• 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.
• 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 clock that reset is asserted to the first clock that done is asserted.)

ISR State Machine

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

• On a reset

  • guess initialized to 32'h8000_0000
  • value is clocked into a register

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

• Square guess (multiply it with itself)

  • Wait until the multiplier raises its done

• if guess <= value

  • Keep the current bit

• else

  • Clear the current bit

• Move to the next bit

• After the last bit, raise done