Talk:Square root algorithms: Difference between revisions

Revision as of 02:58, 13 March 2020

Latest revision as of 00:02, 22 May 2025

(44 intermediate revisions by 24 users not shown)

Line 1:

{{User:MiszaBot/config

| algo = old(90d360d)

| archive = Talk:MethodsSquare ofroot computing square rootsalgorithms/Archive %(counter)d

| counter = 1

| maxarchivesize = 150K

| archiveheader = {{Automatic archive navigator}}

| minthreadstoarchive = 12

| minthreadsleft = 45

}}

{{WikiProject banner shell|class=C|

{{WikiProject Mathematics|importance= low}}

}}

{{Maths rating|class= Start|importance= low|field= analysis}}

{{archive box|auto=long}}

Line 27 ⟶ 29:

That cryptic constant is actually a composite of three bitfields, and twiddling it requires some understanding of what those fields are. It would be clearer, but a few more operations, to do that line as a pair of bitfield extract/inserts. But we're saving divides in the subsequent iterations, so the extra 1-cycle operations are a wash.

== Pell'sUndefined equation?behaviour ==

The examples using unions are invalid C, as they invoke undefined behaviour. An easy solution that is probably even clearer for the purpose of example code would be to use memcpy, e.g.

float f;

uint32_t u;

memcpy (&u, &f, sizeof (u));

[[Special:Contributions/37.49.68.13|37.49.68.13]] ([[User talk:37.49.68.13|talk]]) 13:08, 1 April 2022 (UTC)

:Type punning with unions is undefined in C++, but not in C. This is a topic of much confusion.

:The following is pulled from a footnote around section 6.5.2.3 of the C17 standard:

:"If the member used to read the contents of a union object is not the same as the member last used to store a value in the object, the appropriate part of the object representation of the value is reinterpreted as an object representation in the new type as described in 6.2.6 (a process sometimes called “type punning”). This might be a trap representation."

:This basically says, 'you may use a union to reinterpret the bits of one type into another but we're not going to promise that the new interpretation will be valid'

:I will say that the C code in this article is rather clunky and may benefit from a bitfield to separate the different sections of the float representation so it is easier to read and understand, but I will have to flatly disagree with you that <code>memcpy() </code>is more appropriate than a union in this code snippet. [[User:WillisHershey|WillisHershey]] ([[User talk:WillisHershey|talk]]) 17:24, 25 September 2023 (UTC)

== Lucas sequence method - original research? ==

I could not find any relevant research papers on the use of Lucas sequences for computing real square roots.

The closest I found is

G. Adj and F. Rodríguez-Henríquez, "Square Root Computation over Even Extension Fields," in IEEE Transactions on Computers, vol. 63, no. 11, pp. 2829-2841, Nov. 2014, doi: 10.1109/TC.2013.145.

which is concerned with square roots in finite fields and uses a different algorithm.

Should this paragraph be removed as original research?

Or it could also simply be made much shorter, by avoiding to repeat the properties of Lucas sequences. [[User:BlueRavel|BlueRavel]] ([[User talk:BlueRavel|talk]]) 23:27, 3 December 2023 (UTC)

: {{ping|BlueRavel}} I have searched, and I too failed to find any relevant source for this. It was posted into the article in 2009 without any explanation, by an editor who has never made any other substantial contribution, just one other very small edit. It looks as though it may well be original research, but whether it is or not, it is unsourced, so I have removed it. [[User:JBW|JBW]] ([[User talk:JBW|talk]]) 21:54, 5 December 2023 (UTC)

Pell's equation is a Diophantine equation, meaning it has integer coefficients, and requires an integer solution. So <math>S</math> in this case must be an integer (not zero and not a perfect square). Most of the time, we're not computing square roots of integers, because we can look them up. But let's just suppose we want the square root of 1361, First we come up against: ''Find positive integers p1 and q1... This is the hard part; It can be done either by guessing, or by using fairly sophisticated techniques.'' Guess?? This isn't the same kind of guessing we do in the Initial estimate section, because a bad guess there just means more work. No, a bad guess here is utterly worthless. There's no guessable solution to p² - 1361{{dot}}q²=1. (Yes, 1361 is prime, and has a few other properties that make it a particularly irascible number, but in the end, it's just an arbitrary number). The standard method of solving Diophantine equations is by continued fractions (one must find the period of the repetend); the problem is that the repetend may be long, extremely long, and it can be that long for seemingly innocuous choices of <math>S</math>. We don't elaborate that in the section.

== Merge "Approximations that depend on the floating point representation" into "Initial estimate" ==

Pell's equation is a recursive relationship that allows one to generate infinitely many solutions after finding one. It's finding one that's the hump, as it is with any Diophantine equation. And in the usual case, while there may be infinitely many solutions, none of them are small, small enough to make trial and error a useable approach. I don't think this section ought to be in the article, unless we greatly expand it to demonstrate how actually to solve the equation. Solving a Diophantine equation is a LOT more work than an arithmetic computation of square root. [[User:Sbalfour|Sbalfour]] ([[User talk:Sbalfour|talk]]) 22:09, 14 December 2019 (UTC)

I believe the section "Approximations that depend on the floating point representation" should be merged into "Initial estimate", since it is a special case of "Binary estimates". Merging would clear up the fact that the floating point trick gives an initial rough approximation, which is then typically iteratively improved.

:I agree. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 09:29, 15 December 2019 (UTC)

I also believe the "Initial estimate" section should appear after the section on Heron's method, as the reader is likely more interested in the general idea of iterative refinement than in the details of how to obtain a good initial estimate in all possible ways.

== What's the programming language used here? ==

Additionally, in my opinion the entirety of the article could benefit from some trimming/rewriting, as many sections contain redundant information, unnecessary details, and awkward formulations. [[User:BlueRavel|BlueRavel]] ([[User talk:BlueRavel|talk]]) 14:54, 4 December 2023 (UTC)

Which languages have been used to desribe the algorothms?

:: Your proposition makes sense to me, and I dont necessarily disagree. That said though, as a pure mathematician, I am uninclined to blur the lines between programmatical issues and mathematical problems. I think maintaining a distinction is appropriate. An analysis of the pure mathematical problem of initial estimation in these abstract reiterative processes is a decidedly distinct discussion from considerations in this programming language, or that programming language, or this architecture, or that architecture. The former is future-proofed, the latter is not. [[User:CogitoErgoCogitoSum|CogitoErgoCogitoSum]] ([[User talk:CogitoErgoCogitoSum|talk]]) 21:09, 11 February 2024 (UTC)

[[Special:Contributions/2003:E0:5F1B:749A:DC42:9B8D:E639:24FC|2003:E0:5F1B:749A:DC42:9B8D:E639:24FC]] ([[User talk:2003:E0:5F1B:749A:DC42:9B8D:E639:24FC|talk]]) 22:09, 7 January 2020 (UTC)

== Useful addition?? ==

:In general, at Wikipedia we try to avoid using any specific programming language in the articles. If an example is necessary, it is generally done in [[pseudocode]].

Not sure if its useful, but I have found that, in general, <math>\sqrt{x+2} \approx \frac{x+1}{\sqrt{x}}</math>, and if {{math|''x''{{=}}''n''{{sup|''2''}}}} we get <math>\sqrt{n^2+2} \approx n + \frac{1}{n}</math>.

:Obviously, articles about a particular language are an exception.

:In this article, it appears that the three examples are in [[C (programming language)]]. But we do ''not'' guarantee that they will work as written. [[User:JRSpriggs|JRSpriggs]] ([[User talk:JRSpriggs|talk]]) 00:38, 8 January 2020 (UTC)

Similarly <math>\sqrt{x+4} \approx \frac{x+2}{\sqrt{x}}</math>.

== "nearest perfect square" in Bakhshali method? ==

I sometimes use this for quick pencil and paper calculations, if Im close enough to a convenient value.

The example in the Bakhshali method has me published. The initial guess is said to be "''x''₀² be the initial approximation to ''S''." The example uses <math>S = 125348</math>, and chooses <math> x_0 = 600 </math>. How can that be? <math>600^2 = 360000</math> and there are many perfect squares closer to ''S'', like 400 or 350.

Not sure if this is a known or established property, proven, bounded, or if its already in the article in some alternative capacity, or if its even appropriate for this article. I do know the taylor series approximation with two terms connects these expressions.

How is the initial guess ''really'' meant to be chosen? Unfortunately, the material here (in particular, this example) isn't well-referenced enough to explain how 600 meets the criteria given in the article. -- [[User:Mikeblas|Mikeblas]] ([[User talk:Mikeblas|talk]]) 21:06, 26 February 2020 (UTC)

[[User:CogitoErgoCogitoSum|CogitoErgoCogitoSum]] ([[User talk:CogitoErgoCogitoSum|talk]]) 21:05, 11 February 2024 (UTC)

: There is nothing special about 2 and 4: <math>\sqrt{x+2c} \approx \frac{x+c}{\sqrt{x}}</math> provided that c is small compared to x. This is, in fact, just the first two terms of the series given in the article under the section heading "Taylor series". [[User:JBW|JBW]] ([[User talk:JBW|talk]]) 01:45, 13 February 2024 (UTC)

:The methodI doesdon't notthink requirethey theare initialuseful. guess to beIn the closestfirst, perfectyou square.have This was only used to obtainreplaced a boundsquare onroot theand error.an Theaddition 600with valuea issquare obtainedroot, inan the above section on scalar estimatesaddition, and wasa useddivision asto theget initialan guessapproximate in the previous exampleanswer. --[[User:WcherowiBubba73|Bill Cherowitzo Bubba73]] (^{[[User talk:WcherowiBubba73|talkYou talkin' to me?]])} 2308:2702, 2613 February 20202024 (UTC)