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
	}
}