Livt packages
Livt.Math
Version 1.7.2
Reusable integer and fixed-point arithmetic, complex numbers, trigonometry, and statistics for FPGA applications written in Livt.
Published files (90)
src/sqrt/SqrtNewtonRaphson.lvt
namespace Livt.Math.Sqrt
using Livt.Math.Arithmetic
/**
* Computes floor square roots for integer inputs up to MAX_INPUT.
*/
component SqrtNewtonRaphson
{
// Largest input accepted before clamping.
public const MAX_INPUT: int = 32767
// Fixed Newton-Raphson iteration count.
public const ITERATIONS: int = 16
// Serialized exact division for bounded Newton steps.
divider: UnsignedDivision<15>
/**
* Owns one divider for inputs clamped to MAX_INPUT.
*/
new()
{
divider = new UnsignedDivision<15>()
}
/**
* Returns floor(sqrt(n)) after clamping n into the supported range.
*/
public fn Compute(n: int) int
{
if (n <= 0) {
return 0
}
var bounded: int = n
if (bounded > MAX_INPUT) {
bounded = MAX_INPUT
}
if (bounded == 1) {
return 1
}
var x: int = bounded / 2 + 1
for (var i = 0; i < ITERATIONS; i++) {
var quotient = divider.Divide(bounded as uint, x as uint) as int
x = (x + quotient) / 2
}
if (x * x > bounded) {
x = x - 1
}
return x
}
}