isqrt.c
3.43 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//*****************************************************************************
//
// isqrt.c - Integer square root.
//
// Copyright (c) 2005-2014 Texas Instruments Incorporated. All rights reserved.
// Software License Agreement
//
// Texas Instruments (TI) is supplying this software for use solely and
// exclusively on TI's microcontroller products. The software is owned by
// TI and/or its suppliers, and is protected under applicable copyright
// laws. You may not combine this software with "viral" open-source
// software in order to form a larger program.
//
// THIS SOFTWARE IS PROVIDED "AS IS" AND WITH ALL FAULTS.
// NO WARRANTIES, WHETHER EXPRESS, IMPLIED OR STATUTORY, INCLUDING, BUT
// NOT LIMITED TO, IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE APPLY TO THIS SOFTWARE. TI SHALL NOT, UNDER ANY
// CIRCUMSTANCES, BE LIABLE FOR SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES, FOR ANY REASON WHATSOEVER.
//
// This is part of revision 2.1.0.12573 of the Tiva Utility Library.
//
//*****************************************************************************
#include <stdint.h>
#include "utils/isqrt.h"
//*****************************************************************************
//
//! \addtogroup isqrt_api
//! @{
//
//*****************************************************************************
//*****************************************************************************
//
//! Compute the integer square root of an integer.
//!
//! \param ui32Value is the value whose square root is desired.
//!
//! This function will compute the integer square root of the given input
//! value. Since the value returned is also an integer, it is actually better
//! defined as the largest integer whose square is less than or equal to the
//! input value.
//!
//! \return Returns the square root of the input value.
//
//*****************************************************************************
uint32_t
isqrt(uint32_t ui32Value)
{
uint32_t ui32Rem, ui32Root, ui32Idx;
//
// Initialize the remainder and root to zero.
//
ui32Rem = 0;
ui32Root = 0;
//
// Loop over the sixteen bits in the root.
//
for(ui32Idx = 0; ui32Idx < 16; ui32Idx++)
{
//
// Shift the root up by a bit to make room for the new bit that is
// about to be computed.
//
ui32Root <<= 1;
//
// Get two more bits from the input into the remainder.
//
ui32Rem = ((ui32Rem << 2) + (ui32Value >> 30));
ui32Value <<= 2;
//
// Make the test root be 2n + 1.
//
ui32Root++;
//
// See if the root is greater than the remainder.
//
if(ui32Root <= ui32Rem)
{
//
// Subtract the test root from the remainder.
//
ui32Rem -= ui32Root;
//
// Increment the root, setting the second LSB.
//
ui32Root++;
}
else
{
//
// The root is greater than the remainder, so the new bit of the
// root is actually zero.
//
ui32Root--;
}
}
//
// Return the computed root.
//
return(ui32Root >> 1);
}
//*****************************************************************************
//
// Close the Doxygen group.
//! @}
//
//*****************************************************************************