Oops. Foolish error as I prepared for presentation. My apologies. Here’s the accurate implementation of intsqrt.
intsqrt =: 3 : 0 NB. y An array of possible integer squares NB. Return 0 for non-squares or integer roots s * y = x: *: s =. <. 0.5 + x: 10 ^ -: x: 10 ^. y ) Note that it is explicit to the point of being obscene. I’ll leave the tacit implementation to someone more experienced than I. Thanks. Ed Sent from my iPad > On Apr 27, 2022, at 1:50 PM, Ed Gottsman <edward.j.gotts...@gmail.com> wrote: > > > 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
