Implementation of sqrt for the signed accum type. More...

#include "stdfix-full-iso.h"
#include "polynomial.h"
#include "pair.h"
#include "arm_acle.h"
#include "arm.h"

Macros
#define	__SQRT_HALF UINT32_C(3037000500)
	Square root of half, in integral form of unsigned long fract.

Functions
static int	even (int x)
	Test: is `x` even?

static int	odd (int x)
	Test: is `x` odd?

uint64_t	__x_u64_ulr (uint64_t x, uint32_t y)
	This function multiplies a 64 bit unsigned quantity, by a u0.32.

static uint64_t	r_squared (uint32_t r)
	This function calculates the square of `r`.

static uint64_t	newton_xr (uint32_t x, uint32_t r)
	This function calculates an improved value of `r`, the reciprocal square-root.

static uint64_t	newton_xlr (uint32_t x, uint64_t r)
	This function calculates an improved value of `r`, the reciprocal square-root.

static uint64_t	newton_lxr (uint64_t x, uint32_t r)
	This function calculates an improved value of `r`, the reciprocal square-root.

uint64_t	newton_lxlr (uint64_t x, uint64_t r)
	This function calculates an improved value of `r`, the reciprocal square-root.

uint64_t	newton_xr2 (uint32_t x, uint32_t r)
	This function calculates an improved value of r, the reciprocal square-root.

uint64_t	newton_xlr2 (uint32_t x, uint64_t r)
	This function calculates an improved value of `r`, the reciprocal square-root.

uint64_t	square_root_improve (uint32_t x, uint32_t r)
	A single stage of recip_normalized_root(); handles coarse approximation.

uint64_t	square_root_ximprove (uint32_t x, uint64_t r)
	A single stage of recip_normalized_root(); refines approximation.

uint64_t	recip_normalized_root (uint32_t x)
	Calculates the reciprocal square-root of the argument.

static int32_t	sqrtk_bits (int32_t x)
	Calculates the square-root of the argument.

accum	sqrtk (accum x)
	Square root.

unsigned accum	sqrtuk (unsigned accum x)
	Square root.

Detailed Description

Implementation of sqrt for the signed accum type.

The details of the algorithm are from "Elementary Functions: Algorithms and Implementation", 2nd edn, Jean-Michel Muller, Birkhauser, 2006.

Author: Dave Lester (david.nosp@m..r.l.nosp@m.ester.nosp@m.@man.nosp@m.chest.nosp@m.er.a.nosp@m.c.uk)

Copyright: Copyright (c) Dave Lester, Jamie Knight and The University of Manchester, 2014. All rights reserved. SpiNNaker Project Advanced Processor Technologies Group School of Computer Science The University of Manchester Manchester M13 9PL, UK

Date: 23 October, 2014

Function Documentation

◆ even()

static int even ( int x )

inlinestatic

Test: is x even?

Parameters

[in] x the value to test

Returns: True if the test passes

◆ odd()

static int odd ( int x )

inlinestatic

Test: is x odd?

Parameters

[in] x the value to test

Returns: True if the test passes

◆ __x_u64_ulr()

uint64_t __x_u64_ulr	(	uint64_t	x,
		uint32_t	y
	)

This function multiplies a 64 bit unsigned quantity, by a u0.32.

Parameters

[in]	x	A 64-bit unsigned quantity.
[in]	y	A 32-bit int representing an unsigned long fract (u0.32)

Returns: (x × y) >> 32

◆ r_squared()

static uint64_t r_squared ( uint32_t r )

inlinestatic

This function calculates the square of r.

Parameters

[in] r The value to be squared (where r represents the number R = 1-r/2³³, i.e. 2³¹ represents 0.75.

Returns: A 64-bit representation of 1 - R²

◆ newton_xr()

static uint64_t newton_xr	(	uint32_t	x,
		uint32_t	r
	)

inlinestatic

This function calculates an improved value of r, the reciprocal square-root.

Parameters

[in]	x	The number to be square-rooted, in u1.31 format
[in]	r	The current approximation R = 1 - r/2 (r is in u0.32)

Returns: x * r in u1.63 format

◆ newton_xlr()

static uint64_t newton_xlr	(	uint32_t	x,
		uint64_t	r
	)

inlinestatic

This function calculates an improved value of r, the reciprocal square-root.

Parameters

[in]	x	The number to be square-rooted, in u1.31 format
[in]	r	The current approximation R = 1 - r/2 (r is in u0.32)

Returns: x * r in u1.63 format

◆ newton_lxr()

static uint64_t newton_lxr	(	uint64_t	x,
		uint32_t	r
	)

static

This function calculates an improved value of r, the reciprocal square-root.

Parameters

[in]	x	The number to be square-rooted, in u1.63 format
[in]	r	The current approximation R = 1 - r/2 (r is in u0.32)

Returns: x * R in u1.63 format

◆ newton_lxlr()

uint64_t newton_lxlr	(	uint64_t	x,
		uint64_t	r
	)

This function calculates an improved value of r, the reciprocal square-root.

Parameters

[in]	x	The number to be square-rooted
[in]	r	The current approximation R

Returns: The new approximation

◆ newton_xr2()

uint64_t newton_xr2	(	uint32_t	x,
		uint32_t	r
	)

This function calculates an improved value of r, the reciprocal square-root.

Parameters

[in]	x	The number to be square-rooted, in u1.31 format
[in]	r	The current approximation R = 1 - r/2 (r is in u0.32)

Returns: (x * R² - 1) in u1.63 format

◆ newton_xlr2()

uint64_t newton_xlr2	(	uint32_t	x,
		uint64_t	r
	)

This function calculates an improved value of r, the reciprocal square-root.

Parameters

[in]	x	The number to be square-rooted
[in]	r	The current approximation R

Returns: The new approximation

◆ square_root_improve()

uint64_t square_root_improve	(	uint32_t	x,
		uint32_t	r
	)

A single stage of recip_normalized_root(); handles coarse approximation.

Parameters

[in]	x	The value to have its square root calculated
[in]	r	The current approximation

Returns: The improved approximation

◆ square_root_ximprove()

uint64_t square_root_ximprove	(	uint32_t	x,
		uint64_t	r
	)

A single stage of recip_normalized_root(); refines approximation.

Parameters

[in]	x	The value to have its square root calculated
[in]	r	The current approximation

Returns: The improved approximation

◆ recip_normalized_root()

uint64_t recip_normalized_root ( uint32_t x )

Calculates the reciprocal square-root of the argument.

Parameters

[in] x An unsigned integer, representing a u1.31. Leading bit is 1.

Returns: An unsigned 64-bit integer representing the reciprocal square-root of x, as a u0.64.

Todo:: INCORRECT FORMAT DOCUMENTATION. FIX THIS!

◆ sqrtk_bits()

static int32_t sqrtk_bits ( int32_t x )

inlinestatic

Calculates the square-root of the argument.

Parameters

[in] x A signed integer, representing an s16.15 accum.

Returns: A signed integer representing the square-root of x, as an s16.15.

◆ sqrtk()

accum sqrtk ( s1615 x )

Square root.

Parameters

[in] x Non-negative value to get the square root of

Returns: the square root of x

◆ sqrtuk()

unsigned accum sqrtuk ( u1616 x )

Square root.

Parameters

[in] x Non-negative value to get the square root of

Returns: the square root of x

Macros

Functions

Detailed Description

Function Documentation

◆ even()

◆ odd()

◆ __x_u64_ulr()

◆ r_squared()

◆ newton_xr()

◆ newton_xlr()

◆ newton_lxr()

◆ newton_lxlr()

◆ newton_xr2()

◆ newton_xlr2()

◆ square_root_improve()

◆ square_root_ximprove()

◆ recip_normalized_root()

◆ sqrtk_bits()

◆ sqrtk()

◆ sqrtuk()