Talk:Integer square root

From Wikipedia, the free encyclopedia

Contents 1 Request for a picture 2 Remarks about the writing 3 Division-free square root 4 Algorithm in terms of integers 5 Integer square root code in C 6 Extend definition to include zero

[edit] Request for a picture

If someone with Maple, Mathematica, etc. and would graph a function of isqrt, that would be very appreciated. I have use of Maple over Putty, but it displays graphs with ASCII characters, and it's hideous to look at. Iamunknown 09:26, Sep 13, 2004 (UTC)-

On second thought, is a graph necessary? Opinions, please. Iamunknown 18:53, 28 July 2006 (UTC)

[edit] Remarks about the writing

Hi Olegalexandrov. I was planning on editing the page again, but wanted to consult you beforehand. I think that the apostrophe in the bottom link needs to be escaped; otherwise Wikipedia fails to recognize the enclosed text as a link. On the flip-side, thanks for cleaning up after me! I messed up on standardization of 'x' and 'n', 'x_n', and 'valid' is much better than 'correct'. I am wondering, however, about your excess of links. For the words (take 'number theory' for example) that are throughout the document, I personally think that only one reference should be linked, presumably at the top. Since that was a bulk of your edit, though, I decided to ask you beforehand; I didn't want to completely reverse your edit! ('Recursive function' is also linked more than once.) Also, I completely realize my ambiguity in the statement, "The beauty of Newton's Iteration for finding the integer square root of a number n is that it can use solely integers," and was wondering what you thought about this statement: "The beauty of Newton's Iteration as used to find the integer square root of a number n is its inherent ability to stay within the set of integers, requiring no use of floating-point arithmetic." That was definitely what I trying to get at. Thanks! --Iamunknown 08:45, 11 Dec 2004 (UTC)

Thanks for the info about the excess links; I will be reverting that soon. I do mean that every operation can be performed in integers. About the statement,

The beauty of Newton's Iteration as used to find the integer square root of a number n is its inherent ability to stay within the set of integers, requiring no use of floating-point arithmetic,

I mean the function itself is wholly algebraic. It uses fractions, yes, but fractions are merely two integers placed atop and beneath one another. Keeping that into perspective, you could retain their integer identites and continue on with your calculation (still remaining in the set of integers) and when you have reached the desired accuracy, then do your final division.

--Iamunknown 21:50, 11 Dec 2004 (UTC)

Got it now! You meant to say that you use rational numbers, not integers. Then it all makes sense! So maybe you should write on the integer square root page that finding the square root directly gives you irrational numbers, while doing Newton's method gives you rational numbers. What do you think? --Olegalexandrov 22:15, 11 Dec 2004 (UTC)

Excellent! That is much easier to understand than what I previously had written. I'll definitely add that right now. Thanks, Olegalexandrov! --Iamunknown 22:29, 11 Dec 2004 (UTC)

[edit] Division-free square root

Is anyone interested in the divison-free algorithm for the square root? Obviously it only converges linearly rather than quadratically, but, especially in binary, it might be faster anyway. —The preceding unsigned comment was added by 80.175.250.218 (talk • contribs) 10:46, 31 October 2005 (UTC).

Actually, now that I think about it, it's only purely division-free in binary, not in other bases. —The preceding unsigned comment was added by 80.175.250.218 (talk • contribs) 10:48, 31 October 2005 (UTC).

[edit] Algorithm in terms of integers

The algorithm given in the article

with x₀ = n works if you do integer calculations, too (truncate when dividing). Then the algorithm terminates when x_{k + 1} = x_k. And as far as I can see, it actually converges a little faster. Wouldn't it make more sense for the article to do everything in terms of integers, instead of rationals? dbenbenn | talk 09:45, 18 March 2006 (UTC)

[edit] Integer square root code in C

Would it be appropriate to post the following C code in the article? It is fast and tested:

#include <stdio.h>

/*
 * Return the truncated integer square root of "y" using longs.
 * Return -1 on error.
 */
long
lsqrt(long y)
{
        long    x_old, x_new;
        long    testy;
        int     nbits;
        int     i;

        if (y <= 0) {
                if (y != 0) {
                        fprintf(stderr, "Domain error in lsqrt().\n");
                        return -1L;
                }
                return 0L;
        }
/* select a good starting value using binary logarithms: */
        nbits = (sizeof(y) * 8) - 1;    /* subtract 1 for sign bit */
        for (i = 4, testy = 16L;; i += 2, testy <<= 2L) {
                if (i >= nbits || y <= testy) {
                        x_old = (1L << (i / 2L));       /* x_old = sqrt(testy) */
                        break;
                }
        }
/* x_old >= sqrt(y) */
/* use the Babylonian method to arrive at the integer square root: */
        for (;;) {
                x_new = (y / x_old + x_old) / 2L;
                if (x_old <= x_new)
                        break;
                x_old = x_new;
        }
        return x_old;
}

I have thoroughly tested this code and guarantee it is correct. --Gesslein 16:20, 2 July 2006 (UTC)

I do not know. I started a Integer square root codebase on Wikisource which was eventually deleted, because (although the programs in each language worked) the programs were original contributions. I think that applies to this article and would thus forbid you to place that code in the article, but I will forward the query to Charles Matthews, a prominent mathematics administrator. This article itself, however, may be an original contribution. He will be more likely to know than I. Iamunknown 20:03, 18 July 2006 (UTC)

I thought the terms of Wikipedia edits were "No original research". Contributions should always be welcome :-) --Gesslein 18:53, 28 July 2006 (UTC)

I agree that contributions should always be welcome. The proposed mathematics convention for algorithms, however, suggests that "Algorithms, like all other content in Wikipedia, should be traceable to reliable, published sources. Every presentation of an algorithm (both pseudocode and sample code) should include a citation." I agree with this, even though abiding by it currently prevents your code from inclusion. Iamunknown 19:34, 28 July 2006 (UTC)

Thanks for your thoughts on this. The algorithm used is Newton's method (also called the Babylonian method) described in the article. It gets a speed increase from using binary logarithms to select the starting value. --Gesslein 19:40, 28 July 2006 (UTC)

[edit] Extend definition to include zero

I would like to suggest that the definition is extended from 'a positive integer n' to 'a non-negative integer n', which would be in line with the definition of the (real-number domain) square root.

If that is accepted, it should be stated that the algorithm is only suitable for finding isqrt(n), n > 0.

Lklundin 09:53, 8 March 2007 (UTC).