btw (and as expected) D.E. Knuth, The Art of Computer Programming, 2nd, vol 2, pages 339 ff uses this convention as a shorthand to describe a regular continued fraction: / x1, x2, ...,xn / like in these examples 8/29 = / 3, 1, 1, 1, 2 / e = 2 + / 1, 2, 1, 1, 4, 1, 1, 6, 1,... / -M
At 2016-03-10 22:01, you wrote:
[ a0 ; a1 a2 a3 ... ] ? Usage seems to vary - the ";" appears to be optional, but if used, it can be thought of as the integer part: a0 + 1 % (a1 + 1 % ( a2 + 1 % (a3 +... ) ) ) The notation may be extended to use a comma (",") to indicate repeated groups, so, dropping the ";" rt2 = [1 2 2 2 2... ] == [1 ,2] rt3 = [1 1 2 1 2 1 2 ... ] == [1,1 2] and here's an extension I hadn't seen before: e = [2 1 2 1 1 4 1 1 6 1 ...] == [2, 1 2n+2 1] I'll have a look at Abramowitz & Stegun; so far I've looked at http://perl.plover.com/classes/cftalk/ and https://hal.inria.fr/file/index/docid/75792/filename/RR-0760.pdf I expect Knuth has something on it too. Sorry for going a bit off topic, Cheers, Mike On 10/03/2016 19:35, Kip Murray wrote: > Your question is too hard for me. If I wanted to look into it, I would > start with paragraph 3.10 Theorems on Continued Fractions on page 10 of the > Handbook of Mathematical Functions edited by Abramowitz and Stegun. The > matrix theorem shown there may help. > > What does your notation [ a0 ; a1 a2 a3 ... ] mean? > > --Kip > > On Thursday, March 10, 2016, Mike Day <[email protected]> wrote: > >> So how do you add [a0; a1 a2 a3 ...] and [b0; b1 b2 b3 b4] >> to yield [c0;c1 c2 c3 c4...] using just their encodings as cfs? >> >> For example, 3r11 + 1r2 = 17r22 ; >> or, as c.f. [1;5 2] + [0;2] = [1;1 2 7] >> How would you do the latter directly? >> >> Mike >> >> On 10/03/2016 17:18, Kip Murray wrote: >> >>> J Continued Fractions >>> >>> Let us consider the continued fraction >>> >>> 1 + 2 % 3 + 4 % 5 + 6 % 7 + >>>> >>> This represents the infinite list >>> >>> 1 , (1+2%3), (1 + 2%3 + 4 % 5), >>> >>> I follow the conventionn that each term after the first ends with a >>> denominator. >>> >>> We can calculate 1 + 2 % 3 + 4 % 5 using. +`% / 1 2 3 4 5 >>> >>> Try it! >>> >>> The verb cf below calculates terms of our continued fraction >>> >>> cf =: [: +`%/ 1 + [: i. 1 + 2 * ] >>> cf 0 >>> 1 >>> cf 1 >>> 1.666666667 >>> cf 2 >>> 1.526315789 >>> cf 3 >>> 1.543046358 >>> cf"0 i. 4 >>> 1 1.666666667 1.526315789 1.543046358 >>> >>> --Kip Murray >>> >>> On Thursday, March 10, 2016, Mike Day <[email protected]> wrote: >>> >>> Thanks, Bo. >>>> I was going to reply saying "yes, but what about doing arithmetic with >>>> cf?" >>>> >>>> But I see there are methods for addition etc with such representations. >>>> They're >>>> fairly formidable, and I don't quite see yet how to control the >>>> precision >>>> of such >>>> operations. Unlike p-adics, they're not built in to Pari GP, but this >>>> is J of course, >>>> which has neither p-adics nor c.f. built-in.... >>>> >>>> Cheers, >>>> Mike >>>> >>>> On 10/03/2016 08:00, Bo Jacoby wrote: >>>> >>>> The standard approach to get rational approximations to irrational >>>>> numbers is that of continued fractions. >>>>> >>>>> Den 0:23 torsdag den 10. marts 2016 skrev Mike Day < >>>>> [email protected]>: >>>>> >>>>> I'm not at all sure that you'll find this relevant, but here goes, >>>>> anyway: >>>>> I recently solved Euler problem 541 which concerns harmonic numbers: >>>>> https://projecteuler.net/problem=541 >>>>> >>>>> I started out, in J of course, with rationals, but the size of the >>>>> problem is >>>>> against at least my naive application of them. I _did_ manage to solve >>>>> it >>>>> using Pari GP, and it helped a lot that Pari GP has a "p-adic" type, >>>>> >>>>> For example, a p-adic representation of 22r7 in base 7 is 3*7^-1 + 1 + >>>>> O(7) >>>>> So I toyed around with p-adic arithmetic in J, but maintaining a >>>>> consistent >>>>> level of precision has somewhat escaped me. Nevertheless, I've managed >>>>> to set up verbs to add, subtract, multiply, divide p-adics, and even >>>>> raise them >>>>> to integer powers. >>>>> >>>>> So, for example, to express 3r5 1r15 22r7 in base 7 to within O(7^6) >>>>> (7 6&rat2padic)"0] 3r5 1r15 22r7 >>>>> >>>>> 7 6 0 2 4 5 2 1 4 >>>>> >>>>> 7 6 0 1 5 3 6 0 5 >>>>> >>>>> 7 6 _1 1 3 0 0 0 0 >>>>> >>>>> >>>>> The leading digit is the base, the next one is the precision, and the >>>>> next is a scaling power, 0 by default. The remaining values are >>>>> coefficients >>>>> of powers of the base. >>>>> >>>>> >>>>> So 3r5 is approx >>>>> (7 #.|.2 4 5 2 1 4)%7^6 >>>>> >>>>> 0.600005 >>>>> >>>>> >>>>> And it can do: >>>>> >>>>> padicadd/7 6 0 2 4 5 2 1 4,:7 6 _1 1 3 NB. "add" 3r5 and 22r7 >>>>> >>>>> 7 6 _1 1 5 4 5 2 1 >>>>> >>>>> which agrees with >>>>> (7 6&rat2padic)3r5+22r7 NB. represent 3r5 + 22r7 >>>>> >>>>> 7 6 _1 1 5 4 5 2 1 >>>>> NB. Loses the coefficient for 7^5 (!) >>>>> >>>>> >>>>> In Pari GP: >>>>> >>>>> (22:49) gp > 3/5+O(7^6) \\ express 3r5 as p-adic base 7 >>>>> %1 = 2 + 4*7 + 5*7^2 + 2*7^3 + 7^4 + 4*7^5 + O(7^6) >>>>> (22:49) gp > 22/7+O(7^6) \\ express 22r7 as p-adic base 7 >>>>> %2 = 7^-1 + 3 + O(7^6) >>>>> (22:50) gp > 3/5+22/7+O(7^6) \\ add them... >>>>> %3 = 7^-1 + 5 + 4*7 + 5*7^2 + 2*7^3 + 7^4 + 4*7^5 + O(7^6) >>>>> (22:52) gp > \\ coefficients of 1 5 4 5 2 1 (4) match my J ones >>>>> >>>>> >>>>> I don't remember studying p-adics at ("high") school or university... >>>>> >>>>> >>>>> They seem pretty powerful in some circumstances. >>>>> >>>>> >>>>> I tried using my J version of p-adics to solve the Euler problem, but >>>>> (a) my implementation is far too slow, and >>>>> (b) precision remains a problem way before reaching the target base, >>>>> namely 137. >>>>> >>>>> >>>>> I suspect the precision difficulty is to do with the way I chose to >>>>> handle multiplication and division rather than inability of a 64-bit >>>>> machine to handle rationals! (Also addition (subtraction) of p-adics >>>>> with different scaling powers, as for 3r5 + 22r7 above.) >>>>> Currently >>>>> padicdivide/7 6 0 2 4 5 2 1 4,:7 6 _1 1 3 NB. "divide" 3r5 by >>>>> 22r7 >>>>> >>>>> 7 6 0 0 2 5 3 5 5 >>>>> Pari GP has:(23:12) gp > (3/5+O(7^6)) / (22/7+O(7^6)) >>>>> %8 = 2*7 + 5*7^2 + 3*7^3 + 5*7^4 + 5*7^5 + O(7^7) >>>>> >>>>> >>>>> The coefficients are the same, but Pari GP has shifted the precision to >>>>> O(7^7) .... >>>>> >>>>> >>>>> So it's unfinished business. >>>>> >>>>> >>>>> Any interest? >>>>> >>>>> >>>>> Mike >>>>> >>>>> >>>>> >>>>> On 09/03/2016 21:44, Don Guinn wrote: >>>>> >>>>> Rational numbers have always fascinated me. I wanted to build a gear >>>>>> train >>>>>> for a science fair where the gears form a loop where the gear train >>>>>> does >>>>>> not mesh. But only after many thousands of revolutions. Then a sign on >>>>>> the >>>>>> front asking people to break the gears by turning the crank. >>>>>> >>>>>> Long ago the Hammond organ used a gear train to approximate the twelfth >>>>>> root of two and powers of it to build the notes in the octave. Now >>>>>> electronics do that more effectively. >>>>>> >>>>>> The ratio Roger showed in a previous post are too large to be pleasing. >>>>>> Smaller numbers in the ratio could still be useful and still be >>>>>> accurate >>>>>> enough for some purposes. >>>>>> >>>>>> I realize that this request is a little vague, but this is just an >>>>>> extention to the original challenge. >>>>>> On Mar 9, 2016 9:38 AM, "Raul Miller" <[email protected]> wrote: >>>>>> >>>>>> That seems a bit underspecified, or open-ended, at the moment. >>>>>> >>>>>>> For example, pi could be 1p1 (or o.1) or pi could be any of a number >>>>>>> of algorithms: https://en.wikipedia.org/wiki/Category:Pi_algorithms >>>>>>> >>>>>>> Meanwhile, there's also the precision aspect - that could also be >>>>>>> specified in a variety of ways. >>>>>>> >>>>>>> In other words, you might be asking for something like this: >>>>>>> 7%~x:<.0.5+7*1p1 >>>>>>> 22r7 >>>>>>> >>>>>>> Or you might have something different in mind, like perhaps this: >>>>>>> ~.@(#~ (= <./)@:|@:-&1p1),%/~i.100x >>>>>>> 22r7 >>>>>>> >>>>>>> Or, significantly slower, but almost tolerable: >>>>>>> ~.@(#~ (= <./)@:|@:-&1p1),%/~i.1000x >>>>>>> 355r113 >>>>>>> >>>>>>> Or, ... any of a variety of other mechanisms... (and even brute force >>>>>>> search techniques could be made to be significantly more efficient - a >>>>>>> moment's thought would show that incorporating the rounding technique, >>>>>>> for example, could have increased the speed of that last search by >>>>>>> something near a factor of 1000). >>>>>>> >>>>>>> Anyways, if you can say a bit more about what you were aiming for, >>>>>>> maybe we could do a better job of getting there? >>>>>>> >>>>>>> Thanks, >>>>>>> >>>>>>> -- >>>>>>> Raul >>>>>>> >>>>>>> On Wed, Mar 9, 2016 at 11:18 AM, Don Guinn <[email protected]> >>>>>>> wrote: >>>>>>> >>>>>>> How about rounding to a rational of some precision like pi rounded to >>>>>>>> 22r7 ? >>>>>>> On Mar 9, 2016 8:52 AM, "Kip Murray" <[email protected]> wrote: >>>>>>>> Thanks, Roger and Raul. Not understanding GCD +. I had a Rube >>>>>>>> Goldberg >>>>>>>> solution involving Format ": and Do ". --Kip >>>>>>>> >>>>>>>>> On Wednesday, March 9, 2016, Roger Hui <[email protected]> >>>>>>>>> >>>>>>>>> wrote: >>>>>>>> den and num illustrate different ways of computing the same thing, >>>>>>>> >>>>>>>>> hopefully in so doing improves understanding. If you want speed >>>>>>>>>> 2&x: >>>>>>>>>> >>>>>>>>>> is >>>>>>>> going to be faster. >>>>>>>> >>>>>>>>> Also, watch this: >>>>>>>>>> 2 x: o. 1 >>>>>>>>>> 1285290289249 409120605684 >>>>>>>>>> x: o. 1 >>>>>>>>>> 1285290289249r409120605684 >>>>>>>>>> >>>>>>>>>> 2 x:!.0 o. 1 >>>>>>>>>> 884279719003555 281474976710656 >>>>>>>>>> x:!.0 o. 1 >>>>>>>>>> 884279719003555r281474976710656 >>>>>>>>>> >>>>>> >>>> >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Wed, Mar 9, 2016 at 7:20 AM, Mike Day < >>>>>>>>>> [email protected] >>>>>>>>>> <javascript:;>> wrote: >>>>>>>>>> >>>>>>>>>> Roger, are these (among) recommended and preferred methods for >>>>>>>>>> >>>>>>>>>>> recovering num & den, or do they just show an elegant way of >>>>>>>>>>> avoiding 2 x: ? >>>>>>>>>>> >>>>>>>>>>> Thanks, >>>>>>>>>>> >>>>>>>>>>> Mike >>>>>>>>>>> >>>>>>>>>>> >>>>>>>>>>> On 09/03/2016 04:32, Roger Hui wrote: >>>>>>>>>>> >>>>>>>>>>> x=: %/?2$10^8x >>>>>>>>>>> >>>>>>>>>>>> x >>>>>>>>>>>> 69904549r40669028 >>>>>>>>>>>> >>>>>>>>>>>> den=: [: % 1 +. ] >>>>>>>>>>>> num=: * den >>>>>>>>>>>> >>>>>>>>>>>> den x >>>>>>>>>>>> 40669028 >>>>>>>>>>>> num x >>>>>>>>>>>> 69904549 >>>>>>>>>>>> >>>>>>>>>>>> >>>>>>>>>>>> > >>>>>>>>>>> >>>>>>>>>>>> On Tue, Mar 8, 2016 at 7:28 PM, Kip Murray < >>>>>>>>>>>> [email protected] >>>>>>>>>>>> >>>>>>>>>>>> <javascript:;>> >>>>>>>>>>> wrote: >>>>>>>>>>> >>>>>>>>>>>> That's great! It's still a nice puzzle to write your own. --Kip >>>>>>>>>>>> >>>>>>>>>>>> On Tuesday, March 8, 2016, Raul Miller <[email protected] >>>>>>>>>>>>> <javascript:;>> wrote: >>>>>>>>>>> 2 x: 6r4 >>>>>>>>>>> >>>>>>>>>>>> 3 2 >>>>>>>>>>>>>> -- >>>>>>>>>>>>>> Raul >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>> On Tue, Mar 8, 2016 at 10:04 PM, Kip Murray < >>>>>>>>>>>>>> >>>>>>>>>>>>>> [email protected] >>>>>>>>>>>> <javascript:;> >>>>>>>>> <javascript:;>> wrote: >>>>>>>>>>>> How do you find the numerator and denominator in lowest terms >>>>>>>>>>>>>> of a >>>>>>>>>>>>>> >>>>>>>>>>>>> rational >>>>>>>>> fraction? For example, >>>>>>>>>>>>>>> nd 6r4 >>>>>>>>>>>>>>> 3 2 >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> --Kip Murray >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>> >>>>> >>>>>>>>>>>>>>> -- >>>>>>>>>>>>>>> Sent from Gmail Mobile >>>>>>>>>>>>>>> >>>>>>>>>>>>>>> >>>>>>>>>> >>>>> >>>>>>>>>> ---------------------------------------------------------------------- >>>>>>>>>> >>>>>>>>>> For information about J forums see >>>>>>>>>>>> http://www.jsoftware.com/forums.htm >>>>>>>>> ---------------------------------------------------------------------- >>>>>>>>> >>>>>>>>> For information about J forums see >>>>>>>>>>> http://www.jsoftware.com/forums.htm >>>>>>>>>>>> -- >>>>>>>>>>>> Sent from Gmail Mobile >>>>>>>>>>>>> >>>>>>>>>>>>> >>>>>>>>> ---------------------------------------------------------------------- >>>>>>>>> >>>>>>>>> For information about J forums see >>>>>>>>>>> http://www.jsoftware.com/forums.htm >>>>>>>>> ---------------------------------------------------------------------- >>>>>>>>> >>>>>>>>> For information about J forums see >>>>>>>>>>> http://www.jsoftware.com/forums.htm >>>>>>>>>>> > >>>>>>>>> --- >>>>>>>>>> >>>>>>>>>>> This email has been checked for viruses by Avast antivirus >>>>>>>>>>> software. >>>>>>>>>>> https://www.avast.com/antivirus >>>>>>>>>>> >>>>> >>>>>> >>>>>>>>>>> >>>>>>>>>>> >>>>>>> ---------------------------------------------------------------------- >>>>>>> >>>>>>> For information about J forums see >>>>>>>>> http://www.jsoftware.com/forums.htm >>>>>>>> ---------------------------------------------------------------------- >>>>>>>> >>>>>>>>> For information about J forums see >>>>>>>>>> http://www.jsoftware.com/forums.htm >>>>>>>>> -- >>>>>>>>> Sent from Gmail Mobile >>>>>>>>> >>>>>>>>> ---------------------------------------------------------------------- >>>>>>>>> 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 >>>>>> >>>>>> --- >>>>> This email has been checked for viruses by Avast antivirus software. >>>>> https://www.avast.com/antivirus >>>>> >>>>> ---------------------------------------------------------------------- >>>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>>> >>>>> > >>>> ---------------------------------------------------------------------- >>>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>>> >>>>> > >>> --- >>>> This email has been checked for viruses by Avast antivirus software. >>>> https://www.avast.com/antivirus >>>> >>>> ---------------------------------------------------------------------- >>>> For information about J forums see http://www.jsoftware.com/forums.htm >>>> >>> >>> >> --- >> This email has been checked for viruses by Avast antivirus software. >> https://www.avast.com/antivirus >> >> ---------------------------------------------------------------------- >> For information about J forums see http://www.jsoftware.com/forums.htm > > --- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
