[Jprogramming] Numerator and Denominator
Linda A Alvord
lindaalvord at verizon.net
Fri Mar 11 13:12:46 UTC 2016
Would this be helpful?
,v,.($v)#1
0 1 1 1 2 1 3 1
Linda
-----Original Message-----
From: Programming [mailto:programming-bounces at forums.jsoftware.com] On Behalf Of Martin Kreuzer
Sent: Friday, March 11, 2016 7:30 AM
To: programming at jsoftware.com
Subject: Re: [Jprogramming] Numerator and Denominator
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
><mike_liz.day at tiscali.co.uk> 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 <mike_liz.day at 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.day at 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" <rauldmiller at 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
><donguinn at 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" <thekipmurray at 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.canada at 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.day at 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 < >>>>>>>>>>>>
>thekipmurray at 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 <rauldmiller at gmail.com >>>>>>>>>>>>>
><javascript:;>> wrote: >>>>>>>>>>> 2 x:
>6r4 >>>>>>>>>>> >>>>>>>>>>>> 3 2 >>>>>>>>>>>>>>
>-- >>>>>>>>>>>>>>
>Raul >>>>>>>>>>>>>> >>>>>>>>>>>>>> >>>>>>>>>>>>>>
> On Tue, Mar 8, 2016 at 10:04 PM, Kip Murray < >>>>>>>>>>>>>>
>>>>>>>>>>>>>>> thekipmurray at 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 >>>> >>> >>>
> >> --- >> 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
More information about the Programming
mailing list