COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Approximate integer square roots

• Email
• Follow

```Hi everyone!

If I write in pseudocode
include math.h
/*... */
approx. sqrt = sqrt((double) x) + 1

for any unsigned int x, will the approx sqrt of 4 be 3, the approx
sqrt of 5 be 3, the approx sqrt of 48 be 8, and the approx sqrt of 49
be 8?

Thanks
```
 0
Reply albert.xtheunknown0 (183) 1/30/2009 10:58:44 PM

See related articles to this posting

```On Jan 30, 2:58=A0pm, Albert <albert.xtheunkno...@gmail.com> wrote:
> Hi everyone!
>
> If I write in pseudocode
> include math.h
> /*... */
> approx. sqrt =3D sqrt((double) x) + 1
>
> for any unsigned int x, will the approx sqrt of 4 be 3, the approx
> sqrt of 5 be 3, the approx sqrt of 48 be 8, and the approx sqrt of 49
> be 8?
>
No

--
Fred K
```
 0
Reply fred.l.kleinschmidt (245) 1/30/2009 11:04:43 PM

```On Fri, 30 Jan 2009 14:58:44 -0800, Albert wrote:

> Hi everyone!
>
> If I write in pseudocode
> include math.h
> /*... */
> approx. sqrt = sqrt((double) x) + 1
>
> for any unsigned int x, will the approx sqrt of 4 be 3, the approx sqrt
> of 5 be 3, the approx sqrt of 48 be 8, and the approx sqrt of 49 be 8?

You could write the C code and find out for yourself.

What do you mean by approx? From your expression you can have many
approximations: 8, 7.9, 7.93 etc.

--
Ioan - Ciprian Tandau
tandau _at_ freeshell _dot_ org

```
 0

```Albert <albert.xtheunknown0@gmail.com> writes:
> Hi everyone!
>
> If I write in pseudocode
> include math.h
> /*... */
> approx. sqrt = sqrt((double) x) + 1

It would be helpful if you showed us some real code.  I guess
"approx. sqrt" is supposed to be an approximate square root, but what
is its type?

> for any unsigned int x, will the approx sqrt of 4 be 3, the approx
> sqrt of 5 be 3, the approx sqrt of 48 be 8, and the approx sqrt of 49
> be 8?

What are you trying to do, and why are you adding 1 to the result?

--
Keith Thompson (The_Other_Keith) kst-u@mib.org  <http://www.ghoti.net/~kst>
Nokia
"We must do something.  This is something.  Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
```
 0
Reply kst-u (21963) 1/30/2009 11:15:57 PM

```Albert wrote:
> Hi everyone!
>
> If I write in pseudocode
> include math.h
> /*... */
> approx. sqrt = sqrt((double) x) + 1
>
> for any unsigned int x, will the approx sqrt of 4 be 3, the approx
> sqrt of 5 be 3, the approx sqrt of 48 be 8, and the approx sqrt of 49
> be 8?

Do you intend to convert the root-plus-one to integer?
If so, three-quarters of your predictions are correct[*] but
the "approx sqrt" of 48 will be 7, not 8.

[*] Probably.  There are few guarantees on the accuracy
of the sqrt() function, and it is conceivable -- unlikely, but
conceivable -- that sqrt(49.0) might yield a number close to
but not exactly equal to 7.0.  If it's a tiny bit small, like
6.999999999999998446, you'll get 7, not 8, as the "approx sqrt"
of 49.

What problem are you trying to solve?

--
Eric Sosman
esosman@ieee-dot-org.invalid
```
 0
Reply esosman2 (3096) 1/30/2009 11:20:22 PM

```"Albert" <albert.xtheunknown0@gmail.com> wrote in message news:
> Hi everyone!
>
> If I write in pseudocode
> include math.h
> /*... */
> approx. sqrt = sqrt((double) x) + 1
>
> for any unsigned int x, will the approx sqrt of 4 be 3, the approx
> sqrt of 5 be 3, the approx sqrt of 48 be 8, and the approx sqrt of 49
> be 8?
>
sqrt(x), no need for a cast, will give to the square root of x as a
double, within the limits of the sqrt() fucntion accuracy.
To reduce to an integer, the best way is

(int) floor( sqrt(x) + 0.5 );

if you want to always round up for some reason, use

(int) ceil( sqrt(x) );

You can bypass the floor() and ceil() routines with careful casting, but it
is better to get into the habit of doing it properly.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

```
 0
Reply regniztar (3128) 1/31/2009 5:54:37 PM

```Albert wrote:
> Hi everyone!
>
> If I write in pseudocode
> include math.h
> /*... */
> approx. sqrt = sqrt((double) x) + 1
>
> for any unsigned int x, will the approx sqrt of 4 be 3, the approx
> sqrt of 5 be 3, the approx sqrt of 48 be 8, and the approx sqrt of 49
> be 8?

When (a) is the largest integer that is
less than or equal to the square root of (n), then:

(n > a * a + a)

is the expression to use to determine whether to round
(a) up or down to get an approximation of the square root.

/* BEGIN new.c output */

n  sqrt(n)   ap_sq

0  0.000000  0
1  1.000000  1
2  1.414214  1
3  1.732051  2
4  2.000000  2
5  2.236068  2
6  2.449490  2
7  2.645751  3
8  2.828427  3
9  3.000000  3
10  3.162278  3
11  3.316625  3
12  3.464102  3
13  3.605551  4
14  3.741657  4
15  3.872983  4
16  4.000000  4
17  4.123106  4
18  4.242641  4
19  4.358899  4
20  4.472136  4
21  4.582576  5
22  4.690416  5
23  4.795832  5
24  4.898979  5
25  5.000000  5

/* END new.c output */

/* BEGIN new.c */

#include <stdio.h>
#include <math.h>

#define LIMIT       26

unsigned ap_sq(unsigned n);

int main(void)
{
unsigned n;

puts("/* BEGIN new.c output */\n");
puts(" n  sqrt(n)   ap_sq\n");
for (n = 0; n != LIMIT; ++n) {
printf("%2u  %f %2u\n", n, sqrt(n), ap_sq(n));
}
puts("\n/* END new.c output */");
return 0;
}

unsigned ap_sq(unsigned n)
{
unsigned a, b;

a = n;
for (b = ((1 == a) + a) / 2; a > b; b = (n / a + a) / 2) {
a = b;
}
return (n > a * a + a) + a;
}

/* END new.c */

--
pete
```
 0
Reply pfiland (6614) 1/31/2009 8:12:40 PM

6 Replies
53 Views

Similar Articles

12/11/2013 4:45:39 PM
[PageSpeed]

Similar Artilces:

Rounding of real square root of large integers
On the 49G+ is there a simple way to get the correctly rounded 12-digit mantissa in real square roots of large integers (13 to 500 digit integers?) Converting to real first and then doing a square root involves double rounding, which in some cases produces a real result off by 1 in the last place from ANSI/IEEE 854 required result. Doing SQRT() directly on the large integer doesn't terminate in any reasonable time even if the integer is a perfect square more than about 19 digits, and obviously has problems if the large integer isn't a perfect square. I know how to do it with my own sub...

Fixed Point Square Root Improvements?
I will be working with an embedded system with no FPU and need to be able to find the square root of a 16.16 fixed point integer. My current design is using a lookup table where the index is the root (with two decimal bits) of the value pointed to (with four decimal bits.) This doesn't cover every possible value, so I do a search for the nearest value that is contained in the array. Building the table: sqrtTable[0x400]; for (L = 0; L < 0x400; L++) { sqrtTable[L] = (L * L); } (Actually I write the results out to a file for direct compilation in) And my current function is as such: ...

Square-root Kalman Information filter
Has anyone written Mathematica code for the square-root Kalman information filter or references to its implementation? --V. Stokes The Kalman filter is mentioned in the Time Series package. Regards.. Ref: http://www.wolfram.com/products/applications/timeseries/features.html ...

Floating-Point Divide and Square Root Performance
Does anyone know offhand the kind of performance possible in FLOPS or FP ops per cycle for divide and square root operations in current microprocessors used for scientific calculations? I'm thinking for example of architectures like the Itanium 2, the pentium 4 Xeon, the AMD Opteron. It's trivial enough to get the peak FLOPS for multiply and addition given that there are, generally speaking, pipelined floating-point units that can give results every cycle. Things get complicated however when you start to look into things like the square root and divide on an architecture like the It...

Re: using rules for square roots #2
What about nested square roots, such as returning ab for Sqrt[aSqrt[a^2 b^4]] etc.? ...

Integer Basic integers
Is there a hack, tip, or trick to get Integer Basic to use 0 - 65535 for the integer range instead of -32768 - 32767. I would expect 255 * 256 to produce a negative number instead of an error. Thanks. On Apr 27, 10:55=A0pm, datajerk <dataj...@gmail.com> wrote: > Is there a hack, tip, or trick to get Integer Basic to use 0 - 65535 > for the integer range instead of -32768 - 32767. =A0I would expect 255 * > 256 to produce a negative number instead of an error. > > Thanks. Wouldn't that involve modifying ROMs? On Apr 27, 8:55=A0pm, datajerk <dataj...@gmail.com>...

Re: DATE-OF-INTEGER and DAY-OF-INTEGER
>>> On 11/24/2007 at 12:16 PM, in message <13kgu5plo64ki32@corp.supernews.com>, Rick Smith<ricksmith@mfi.net> wrote: > "Rick Smith" <ricksmith@mfi.net> wrote in message > news:13kgjju5gi3orcb@corp.supernews.com... >> >> <john@wexfordpress.com> wrote in message >> news:6cf06ba0-f376-4801-8d1a-5e0838a1ee05@y43g2000hsy.googlegroups.com... > [snip] >> > Thanks much. It almost works. I use Tiny COBOL and Open COBOL. >> > Both blow up on the colon in >> > move function current-date (1:8) to today >&g...

How do I add an Integer to another Integer? #2
Hi! I have a question. How can I add an Integer to another Integer? I ask, because the Java compiler printed an error message to the screen, while I was compiling my source file: <output> calcit2004.java:77: operator + cannot be applied to java.lang.Integer,java.lang.Integer iTmp3 = String.valueOf(iTmp1 + iTmp2); ^ </output> Here is the line 77: <code> String iTmp3 = new String(); Integer iTmp1 = new Integer(zahl1); Integer iTmp2 = new Integer(zahl2); iTmp3 = String.valueOf(iTmp1 + iTmp2); </code> ...

Squares ?!?!
Hi, I prepared a new database for my job at home. I made an export of the old program, imported it in FM6 and all looks fine. Now, at the office this very same file has ALL empty fields filled with squares (some ASCII-character). The same version of FM (v6), the same database. The only difference is the OS. At home XP Pro, at the office 2000. Went back home, still looks good, without the squares. What could be going on? (BTW: A simple find/replace action can not be executed with this character) TIA Bert Wild guess here...fonts. Are the fields formatted in a certain font that is not avai...

Other with integer
hi, how to do an other condition with no change like this : N : integer with sig select N<= 11 when "00", 13 when "01", N when other; ?????? Quartus inffer a latch !!! with vector as std_logic_vector I do this : with sig select vector <= "00" when "00", "11" when "01", "--" when other; patrick.melet@dmradiocom.fr wrote: > hi, > > how to do an other condition with no change like this : > > N : integer > with sig select > N<= > 11 when "00", > 13 when "01", > N...

approximation?
Hello, I got a approximation problem I want to solve with matlab. What I have got: I plot of one graph found in a lecture. What I already did: I made a table with x and y values out of hte graph. Now there is a grid of 2x20 values on my paper. What I want: I would like to approximate the problem, so that I got one function which represents all values. The function is like x=f(y) I am a new matlab user and I have no clue what to do? May someone give me some hints, so that I can solve this problem? Thanks a lot yours, Jan Kubiczek Choose Basic Fitting tool by selecting Basic Fitting fro...

Square
Hi guys, This is probably very easy, is there a function in SAS that computes the square of a function or a cube. example 4^3 Thanks. fxsquared=f(x)**2; fxcubed=f(x)**3; hth Paul Vdesilva wrote: > This is probably very easy, is there a function in SAS that computes > the square of a function or a cube. > > example 4^3 ^ as the exponentiation operator is found in other languages, in SAS its **. Take a moment to read some of the extensive SAS help file (F1). In table of contents Drill down SAS Products / Base SAS / SAS Language Concepts / SAS System Concepts ...

char->integer, integer->char commands
Hi, I created two subroutines, I want to know if there is a better, faster way to do this. I just use ord() and chr(): 1) Take a upper case string like "GRABER" and covert it to its ASCII equivalent (a string of 2 digit numbers, concatenated) - 718265666982 # Convert a string of A-Z Characters to 2 digit ASCII numbers, one after another sub ToNumbers { my \$character_string = shift; # remove whitespace at beginning and end of name? # what about spaces or dashe's IN the name? my \$numbers_string; for (\$i=0; \$i < length(\$character_string); \$i++) { \$number...

Solaris 9 - Root Password Expired
This drives me crazy... I can't believe a sun box ends up in this situation by default. This is the second time I encountered this problem, where the root password expires, and you can't SU to root to change it: > su - Password: Password for user 'root' has expired - use passwd(1) to update it > Both situations on Solaris 9. Anyone know how I can change it without rebooting the server? Thanks! On Jun 4, 2:07 pm, Michelle <newsgrps_rem0ve_t...@mst.ca> wrote: > This drives me crazy... I can't believe a sun box ends up in this > situation by defaul...

96-bit integer modulo, Athlon64 gcc 64-bit integers, libc codefor 64-bit division, etc.
Hi, To effectively solve a research problem, I need a very fast (sub-microsecond, if possible) method to determine whether one 96-bit integer is an exact multiple of another 96-bit integer. The high-level application is mostly written in Perl and is intended to be portable, but right now I am concentrating on the hardware that I have in-hand, which include 2.4 GHz Xeons, a 1.8 GHz Athlon64 ("3000+), a 1.8GHz Pentium M, and a Mac with a G5 CPU (sorry, I don't know the CPU speed). The x86s (except for the Pentium M) are running Linux, the Pentium M is running Windows XP and the Mac i...

while executing my client program i get the exception javax.naming.LinkException: [Root exception is javax.naming.LinkException: [Root exception is javax.naming.NameNotFoundException: remain
Following is the error occured while tetsing the EJB. If anybody knowthe solution plz tell us the how to face this error. thanks inadvancejavax.naming.LinkException: [Root exception isjavax.naming.LinkException: [Root exception isjavax.naming.NameNotFoundException: remaining name: /app/ejb/rcxEJB.jar#FoxServicePayRollBean/local-home]; Link Remaining Name:'null']; Link Remaining Name: 'java:app/ejb/rcxEJB.jar#FoxServicePayRollBean/local-home' atweblogic.rjvm.BasicOutboundRequest.sendReceive(BasicOutboundRequest.java:108) atweblogic.rmi.cluster.ReplicaAwareRemoteRef.invoke(Rep...

Packed Integers
What exactly are packed integers? How do they differ from normal integers? Does it just simply mean that several integers can be packed into one large register, or does it mean a different encoding? I've looked around the web and can't find an answer. luke@ukonline.co.uk wrote: >What exactly are packed integers? How do they differ from normal integers? >Does it just simply mean that several integers can be packed into one large >register, or does it mean a different encoding? I've looked around the web >and can't find an answer. In what context? The term "...

Random Integer
The rand function generates a random number between 0 and 1. Does someone have a subroutine I can use to generate a random integer between 0 and integer n, inclusive? Thank you. -- Mike Lepore - Email delete the 5 >>>>> "ML" == Mike Lepore <lepor5e@bestweb.net> writes: ML> The rand function generates a random number between 0 and 1. ML> Does someone have a subroutine I can use to generate a ML> random integer between 0 and integer n, inclusive? hmmm, how hard can this be? do you know basic math? have you read the docs on rand to see what it...

Integer optimization
Hi! Is there any function that solves integer optimization problems other than the 'bintprog', which only focuses on binary ones, but is the only one I've found? example the problem: f = [-8; -5] A = [1 1 ; 9 5] ; b = [6; 45] [x, fval, exitflag,output] = bintprog(f,A,b) gives x = [1; 1] although that's very well within the limits and the optimal would probably be x = [5; 0]. > Is there any function that solves integer optimization problems other than the 'bintprog', which only focuses on binary ones, but is the only one I've found? A Google...

Down-casting integer
I want to translate the following C code to Common Lisp: int main() { char a = 255; char b = 244; char c = (a << 8) | b; printf ("%d\n", c); // => -12 } I tried this: (logior (ash 255 8) 244) ;; => 65524 The values are treated as integers. How can I get `logior` and `ash` to treat their arguments as bytes and get the same result produced by the C code? Best regards, --Vijay Vijay Mathew <vijay.the.lisper@gmail.com> wrote: > I want to translate the following C code to Common Lisp: > > int main() > { > char a ...