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 convention 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 <mike_liz....@tiscali.co.uk> 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 <
>> mike_liz....@tiscali.co.uk>:
>>
>> 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" <rauldmil...@gmail.com> 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 <dongu...@gmail.com> wrote:
>>>>
>>>>> How about rounding to a rational of some precision like pi rounded to
>>>>>
>>>> 22r7 ?
>>>>
>>>>> On Mar 9, 2016 8:52 AM, "Kip Murray" <thekipmur...@gmail.com> 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 <rogerhui.can...@gmail.com>
>>>>>>
>>>>> 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 <mike_liz....@tiscali.co.uk
>>>>>>> <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 <thekipmur...@gmail.com
>>>>>>>>>
>>>>>>>> <javascript:;>>
>>>>>>>
>>>>>>>> wrote:
>>>>>>>>>
>>>>>>>>> That's great! It's still a nice puzzle to write your own. --Kip
>>>>>>>>>
>>>>>>>>>> On Tuesday, March 8, 2016, Raul Miller <rauldmil...@gmail.com
>>>>>>>>>>
>>>>>>>>> <javascript:;>> wrote:
>>>>>>>
>>>>>>>> 2 x: 6r4
>>>>>>>>>>
>>>>>>>>>>> 3 2
>>>>>>>>>>>
>>>>>>>>>>> --
>>>>>>>>>>> Raul
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> On Tue, Mar 8, 2016 at 10:04 PM, Kip Murray <
>>>>>>>>>>>
>>>>>>>>>> thekipmur...@gmail.com
>>>>
>>>>> <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
--
Sent from Gmail Mobile
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
