263:
number around 1, i.e. 1+k, is (as a linear approximation) 1+k/2. Shifting the fp number represented as an integer down by 1 effectively divides k by 2, since the '1' is not represented. Subtracting that from a constant fixes up the 'smeared' mantissa and exponent, and leaves the sign bit flipped, so the result is an estimate of the reciprocal square root, which requires a multiply to re-vert back to the square root. It's just a quick way of guessing that gives you 1+ digits of precision, not an algorithm.
86:
76:
55:
165:
24:
301:"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."
253:
since I can readily find, by testing incremental offsets from the original, a constant which reduces the maximum error, the original constant isn't optimal, probably resulting from trial and error. How does one verify something that's basically a plausible random number? That it works for a range of
407:
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
361:
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
233:
already - the estimation code should go there. Also, I first saw this trick in
Burroughs B6700 system intrinsics about 1979, and it predated my tenure there, so it's been around a long time. That's well before the drafting of IEEE 754 in 1985. Since the trick is based on linear approximation of an
266:
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
262:
I think we should include at least an outline of the derivation of the estimate expression, thus: a normalized floating point number is basically some power of the base multiplied by 1+k, where 0 <= k < 1. The '1' is not represented in the mantissa, but is implicit. The square root of a
382:
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
408:
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.
611:
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.
386:
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.
257:
because it requires a multiply to get back a square root, on architectures without fast multiply, it won't be such a quick estimate relative to others (if multiply and divide are roughly comparable, it'll be no faster than a random seed plus a Newton
338:
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.
307:
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
681:
603:
481:
547:
390:
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.
335:
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.
142:
275:
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.
250:
It definitely won't work on architectures like Unisys mainframes which are 48/96 bit, or 64-bit IEEE floats. Restructuring the expression to make it work in those cases is non-trivial.
254:
typical values is cold comfort. (Because its only use is as an estimate, maybe we don't actually care that enumerable cases aren't handled(?)... they'll just converge slowly.)
699:
I don't think they are useful. In the first, you have replaced a square root and an addition with a square root, an addition, and a division to get an approximate answer.
229:
This piece of code is a composite of a quirky square root starting estimate and Newton's method iterations. Newton's method is covered elsewhere; there's a section on
181:
304:
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'
683:
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".
723:
132:
108:
247:
we don't know whether values like zero, infinity and unnormalized floating point numbers, and big/little endian formats are correctly handled.
718:
234:
arc seqment of x which in the end, is how all estimates must be made, I'm certain that the method has been reinvented a number of times.
332:
I could not find any relevant research papers on the use of Lucas sequences for computing real square roots. The closest I found is
281:
99:
60:
630:
555:
433:
496:
617:
413:
35:
214:
193:
613:
409:
317:
285:
395:
344:
608:
I sometimes use this for quick pencil and paper calculations, if Im close enough to a convenient value.
41:
85:
391:
356:
340:
23:
107:
on
Knowledge. If you would like to participate, please visit the project page, where you can join
313:
199:
91:
703:
692:
621:
417:
399:
371:
348:
321:
289:
75:
54:
378:
Merge "Approximations that depend on the floating point representation" into "Initial estimate"
295:
Type punning with unions is undefined in C++, but not in C. This is a topic of much confusion.
197:
195:
164:
712:
688:
367:
700:
298:
The following is pulled from a footnote around section 6.5.2.3 of the C17 standard:
244:
the result of bit-twiddling floating point numbers, bypassing the API, is undefined
104:
81:
241:
the result of type punning via pointer dereferencing in C/C++ is undefined
684:
363:
676:{\displaystyle {\sqrt {x+2c}}\approx {\frac {x+c}{\sqrt {x}}}}
278:
float f; uint32_t u; memcpy (&u, &f, sizeof (u));
200:
158:
17:
598:{\displaystyle {\sqrt {x+4}}\approx {\frac {x+2}{\sqrt {x}}}}
476:{\displaystyle {\sqrt {x+2}}\approx {\frac {x+1}{\sqrt {x}}}}
430:
Not sure if its useful, but I have found that, in general,
542:{\displaystyle {\sqrt {n^{2}+2}}\approx n+{\frac {1}{n}}}
312:
is more appropriate than a union in this code snippet.
633:
558:
499:
436:
362:
it is or not, it is unsourced, so I have removed it.
103:, a collaborative effort to improve the coverage of
675:
597:
541:
475:
208:This page has archives. Sections older than
8:
328:Lucas sequence method - original research?
49:
653:
634:
632:
575:
559:
557:
529:
506:
500:
498:
453:
437:
435:
267:the extra 1-cycle operations are a wash.
237:There're numerous issues with this code:
627:There is nothing special about 2 and 4:
51:
21:
218:when more than 5 sections are present.
7:
97:This article is within the scope of
40:It is of interest to the following
14:
724:Low-priority mathematics articles
212:may be automatically archived by
117:Knowledge:WikiProject Mathematics
383:typically iteratively improved.
163:
120:Template:WikiProject Mathematics
84:
74:
53:
22:
137:This article has been rated as
322:17:24, 25 September 2023 (UTC)
1:
704:08:02, 13 February 2024 (UTC)
693:01:45, 13 February 2024 (UTC)
622:21:05, 11 February 2024 (UTC)
418:21:09, 11 February 2024 (UTC)
225:Reciprocal of the square root
111:and see a list of open tasks.
719:C-Class mathematics articles
400:14:54, 4 December 2023 (UTC)
372:21:54, 5 December 2023 (UTC)
349:23:27, 3 December 2023 (UTC)
740:
290:13:08, 1 April 2022 (UTC)
136:
69:
48:
143:project's priority scale
100:WikiProject Mathematics
677:
599:
543:
477:
215:Lowercase sigmabot III
30:This article is rated
678:
600:
544:
478:
631:
556:
497:
434:
123:mathematics articles
614:CogitoErgoCogitoSum
410:CogitoErgoCogitoSum
271:Undefined behaviour
673:
595:
539:
473:
92:Mathematics portal
36:content assessment
671:
670:
648:
593:
592:
570:
537:
518:
471:
470:
448:
426:Useful addition??
222:
221:
187:
186:
157:
156:
153:
152:
149:
148:
731:
682:
680:
679:
674:
672:
666:
665:
654:
649:
635:
604:
602:
601:
596:
594:
588:
587:
576:
571:
560:
548:
546:
545:
540:
538:
530:
519:
511:
510:
501:
492:
482:
480:
479:
474:
472:
466:
465:
454:
449:
438:
360:
311:
217:
201:
178:
177:
167:
159:
125:
124:
121:
118:
115:
94:
89:
88:
78:
71:
70:
65:
57:
50:
33:
27:
26:
18:
739:
738:
734:
733:
732:
730:
729:
728:
709:
708:
655:
629:
628:
577:
554:
553:
502:
495:
494:
484:
455:
432:
431:
428:
380:
354:
330:
309:
279:
273:
227:
213:
202:
196:
172:
122:
119:
116:
113:
112:
90:
83:
63:
34:on Knowledge's
31:
12:
11:
5:
737:
735:
727:
726:
721:
711:
710:
707:
706:
696:
695:
669:
664:
661:
658:
652:
647:
644:
641:
638:
591:
586:
583:
580:
574:
569:
566:
563:
536:
533:
528:
525:
522:
517:
514:
509:
505:
469:
464:
461:
458:
452:
447:
444:
441:
427:
424:
423:
422:
421:
420:
379:
376:
375:
374:
329:
326:
325:
324:
305:
302:
299:
296:
277:
272:
269:
260:
259:
255:
251:
248:
245:
242:
231:Rough estimate
226:
223:
220:
219:
207:
204:
203:
198:
194:
192:
189:
188:
185:
184:
174:
173:
168:
162:
155:
154:
151:
150:
147:
146:
135:
129:
128:
126:
109:the discussion
96:
95:
79:
67:
66:
58:
46:
45:
39:
28:
13:
10:
9:
6:
4:
3:
2:
736:
725:
722:
720:
717:
716:
714:
705:
702:
698:
697:
694:
690:
686:
667:
662:
659:
656:
650:
645:
642:
639:
636:
626:
625:
624:
623:
619:
615:
609:
606:
589:
584:
581:
578:
572:
567:
564:
561:
550:
534:
531:
526:
523:
520:
515:
512:
507:
503:
491:
487:
467:
462:
459:
456:
450:
445:
442:
439:
425:
419:
415:
411:
406:
405:
404:
403:
402:
401:
397:
393:
388:
384:
377:
373:
369:
365:
358:
353:
352:
351:
350:
346:
342:
336:
333:
327:
323:
319:
315:
314:WillisHershey
306:
303:
300:
297:
294:
293:
292:
291:
287:
283:
276:
270:
268:
264:
256:
252:
249:
246:
243:
240:
239:
238:
235:
232:
224:
216:
211:
206:
205:
191:
190:
183:
180:
179:
176:
175:
171:
166:
161:
160:
144:
140:
134:
131:
130:
127:
110:
106:
102:
101:
93:
87:
82:
80:
77:
73:
72:
68:
62:
59:
56:
52:
47:
43:
37:
29:
25:
20:
19:
16:
610:
607:
551:
489:
485:
429:
389:
385:
381:
337:
334:
331:
280:
274:
265:
261:
236:
230:
228:
209:
169:
139:Low-priority
138:
98:
64:Low‑priority
42:WikiProjects
15:
282:37.49.68.13
258:iteration).
114:Mathematics
105:mathematics
61:Mathematics
713:Categories
552:Similarly
483:, and if
392:BlueRavel
357:BlueRavel
341:BlueRavel
310:memcpy()
182:Archive 1
210:360 days
170:Archives
701:Bubba73
493:we get
141:on the
32:C-class
38:scale.
689:talk
618:talk
414:talk
396:talk
368:talk
345:talk
318:talk
286:talk
685:JBW
364:JBW
133:Low
715::
691:)
651:≈
620:)
605:.
573:≈
549:.
521:≈
451:≈
416:)
398:)
370:)
347:)
320:)
288:)
687:(
668:x
663:c
660:+
657:x
646:c
643:2
640:+
637:x
616:(
590:x
585:2
582:+
579:x
568:4
565:+
562:x
535:n
532:1
527:+
524:n
516:2
513:+
508:2
504:n
490:n
488:=
486:x
468:x
463:1
460:+
457:x
446:2
443:+
440:x
412:(
394:(
366:(
359::
355:@
343:(
316:(
284:(
145:.
44::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
