Project Euler #66, extended precision integer square roots, no spoilers Continuing the discussion, for which again thank you all: I found that what I really wanted was large *integer* square roots. Since this seems to come up frequently in Project Euler problems and since I believe there are Euler participants on the mailing list, here’s an integer square root verb that uses the extended precision facilities and works on roots up to 1e11. (Note that %: does not participate in extended precision.)
N.B.: I have not cracked #66 and nothing in this post should be construed as endorsing an approach to solving it. This is just a J implementation of a utility verb. intsqrt =: 3 : 0 NB. y Possible squares of integers. Return either integer NB. square roots or 0s. +Multiply to produce either integer square roots or 0s | +1s where the calculated square = the original square | | +Force extended precision on *: | | | +Square the square roots | | | | +Round the square roots to an integer | | | | | +Force extended precision on ^ | | | | | | +Calculate the square roots | | | | | | | +0.5(log(n)) = log(sqrt(n)) | | | | | | | | +Force extended precision on ^. | | | | | | | | | +Log base 10 | | | | | | | | | | y * y = x: *: <. 0.5 + x: 10 ^ -: x: 10 ^. Y ) (If J were written vertically, it might be easier to comment.) NB. Testing the verb… squares =: x: *: >: ? 1e5 $ 1e11 NB. 100000 integer squares <= 1e11 ^ 2 (+/ 0 < intsqrt squares) NB. All of the numbers are integer squares 100000 +/ 0 = intsqrt >: squares NB. None of the numbers are integer squares 100000 squares =: x: *: >: ? 1e5 $ 1e12 NB. Increase the roots to 1e12 +/ 0 < intsqrt squares NB. Above 1e11, extended precision starts to fail 77537 (6!:2) 'intsqrt squares' NB. Fast, it is not. (J901 on iPadOS) 1.59675 (6!:2) '%: squares' NB. Fast but inaccurate for large squares 0.013432 Ed P.S. Devon, I’ll be there. Thanks. Sent from my iPad > On Apr 22, 2022, at 6:11 AM, Devon McCormick <devon...@gmail.com> wrote: > > Hi Ed, > I was thinking of explaining Roger's sqrt code as part of next month's > NYCJUG. > You should take a look: > https://www.meetup.com/J-Dynamic-Functional-Programming/ . > Cheers, > Devon > >> On Fri, Apr 22, 2022 at 12:49 AM Ed Gottsman <edward.j.gotts...@gmail.com> >> wrote: >> >> Thanks to everyone who responded and in particular for the link to Roger >> Hui’s essay. The wiki discussion was also very good. >> >> (In an earlier life I disparaged “cargo cult” programming, in which you >> take a few lines of source you don’t understand and integrate them into >> your program. [That you effectively do the same thing when you adopt >> someone else’s compiled library cut no ice with me.] J has forced me to >> relax a bit in that regard and I will probably adopt some of Roger’s code >> without entirely understanding it. :-) ) >> >> Thanks again. >> >> Ed >> >> Sent from my iPad >> >>>> On Apr 21, 2022, at 8:18 PM, Gilles Kirouac <g1...@myriade.ca> wrote: >>> >>> Ed If you expand the Extended Integers section (below by bob), you will >> see a link to an essay by Roger on 'Extended Precision Functions'. There is >> a Square Root verb. >>> >>> NB. long rational result may exceed line length >>> sqrt 1x + *: 999999999x >>> >> 1249999998750000000625000000625000000468750000156249999765624999453r1250000000000000000000000000000000000000000000000000000000 >>> sqrt *: 999999999x >>> 999999999 >>> >>> >>> ~ Gilles >>> >>>> Le 2022-04-21 à 14:50, 'robert therriault' via Programming a écrit : >>>> Gilles, >>>> In Nuvoc the extended constant notation can be found here >> https://code.jsoftware.com/wiki/Vocabulary/Constants#Extended_Integers >>>> Having said that, it is hidden pretty well and most of its references >> are previous documentation on the jsoftware site. There is certainly work >> to be done on the wiki! >>>> Cheers, bob >>>>>> On Apr 21, 2022, at 11:44, Gilles Kirouac <g1...@myriade.ca> wrote: >>>>> >>>>> Ed >>>>> >>>>> You seem unaware of the extended precision constant notation: >>>>> >>>>> "digits with a trailing x denote an extended precision integer" >>>>> >>>>> https://www.jsoftware.com/help/dictionary/dcons.htm >>>>> [Where is the equivalent in NuVoc?] >>>>> >>>>> I would rather write >>>>> >>>>> 1x + *: 999999999x >>>>> 999999998000000002 >>>>> >>>>> ~ Gilles >>>>> >>>>> Le 2022-04-21 à 12:51, Henry Rich a écrit : >>>>>> 3!:0 %: x: 1 + x: *: x: 999999999 >>>>>> 8 >>>>>> The square root cannot be represented exactly. >>>>>> Henry Rich >>>>>> On 4/21/2022 12:43 PM, Ed Gottsman wrote: >>>>>>> Hello. >>>>>>> I’m working on the Project Euler “Diophantine equation” problem >> (#66) and using J’s extended precision facilities. I’ve run into behavior >> that confuses me. Boiled down (and overusing x: just to be sure): >>>>>>> x: %: x: 1 + x: *: x: 999999999 >>>>>>> 999999999 >>>>>>> That is (if my syntax is right), the square root of (one plus the >> square of a really large n) is n. I’m apparently misunderstanding >> something about extended precision. I’ve tried it with a variety of uses >> of x: but to no avail, and as I read the x: documentation…this is an odd >> result. >>>>>>> >>>>>>> Any help would be much appreciated. >>>>>>> (J901 on iPadOS, for which sincere kudos to Ian Clark.) >>>>>>> Many thanks. >>>>>>> Ed >>>>>>> >> ---------------------------------------------------------------------- >>>>>>> For information about J forums see >> http://www.jsoftware.com/forums.htm >>>>> ---------------------------------------------------------------------- >>>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>> ---------------------------------------------------------------------- >>>> For information about J forums see http://www.jsoftware.com/forums.htm >>> ---------------------------------------------------------------------- >>> For information about J forums see http://www.jsoftware.com/forums.htm >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm >> > > > -- > > Devon McCormick, CFA > > Quantitative Consultant > ---------------------------------------------------------------------- > For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
