Jump to content

Talk:Continued fraction/Arithmetic/G(matrix ng, continued fraction n1, continued fraction n2)

From Rosetta Code

Idiomaticity?

Is putting that many operations on a single line really idiomatic? Yes it makes the code short, but it also makes it very hard to read. Let's face it, newlines just aren't that expensive! (If I was doing a formal code review of this, I'd be complaining about it a lot…) The watchword of Rosetta Code is “idiomatic”; the code is meant to be read by other people in order to learn how to do a task with a particular language or to compare how different languages do the same thing. (I don't just write my Tcl solutions to be short, but rather to demonstrate how to write good Tcl code that can be read long after it was written and that takes advantage of the features of the language. YMMV, but I'd expect something similar; it's not just “look we can solve this” but “we can solve this and you can understand how we did it”.)

You might also like to refactor a bit so that the code to print out a sequence is a shared method. That's the sort of thing that makes an excellent candidate for not being written out every time. –Donal Fellows 12:10, 10 March 2013 (UTC)

Non-unique solutions

The solutions in C++ and Tcl have different answers to the computation of , but if you work the sequences out they are the same actual fraction; both are correct. I suspect this is due to differences of rounding semantics with mixed-sign integer division. –Donal Fellows 10:22, 11 March 2013 (UTC)

This depends on the definition of the canonical form for negative numbers. 151/77 is [1;1,24,1,2] so the negative form [-1;-1,-24,-1,-2] seems clearer to me. Continued_fraction/Arithmetic/Construct_from_rational_number defines how to construct continued fractions thus determine: the integer part; and remainder part, of N1 divided by N2. It then sets N1 to N2 and N2 to the determined remainder part. It then outputs the determined integer part. It does this until abs(N2) is zero. Here N1 is -151 and N2 is 77. -151/77 is -1 remainder -74. Wikis seem to define the canaonical form as [a0;ai,...,aj] where a0 is an integer and ai,...,aj are positive integers. [1] gives [-2 ; 25,1,2,1705908949761,1,1,4,2,1,4,1,23…] so your version has some support, but if we adopt it then Mathmatica will have to be rewritten and I think the form which makes the negative form similar to the positive form is better.--Nigel Galloway 13:36, 11 March 2013 (UTC)
Right, but the problem is that there are (at least) two different definitions of division / remainder for negative numbers. For example, in C99/Java, (-151) / 77 is -1 and (-151) % 77 is -74, but in Python/Ruby, (-151) / 77 is -2 and (-151) % 77 is 3. --Spoon! 20:27, 11 March 2013 (UTC)
[[2]] says the Quotient is -2 and the Remainder is -74. So let's hope the students being tutored never have to divide negative rational numbers. I'd have to pay for tutoring to get an explanation, so I won't bother (though there is a money back guarantee if I'm not satisfied, and I can't see how I would be). what-s-the-difference-remainder-vs-modulus.aspx gives a good explanation of the difference between remainer and modulus functions, (% in ruby is a modulus function). Quoting from what-s-the-difference-remainder-vs-modulus.aspx "The net result here is that integer division rounds towards zero. That should make sense; we want 123/4 to be 30 with a remainder of 3, not 31 with a remainder of -1. Similarly, we want -123/4 to be -30, not -31! It would be bizarre to say that 4 goes into 123 30 times but goes into -123 -31 times! One expects that changing the sign of a term changes the sign of the result; it does not change the magnitude of the result." I think the other result comes from a linguistic extension of Euclid's algorithm with no consideration for the "bizarre" mathematical logic resulting. So my view remains:
151/77 is 1 remainder 74 and is [1;1,24,1,2]
-151/77 is -1 remainder -74 (not -2 remainder 3) and is [-1;-1,-24,-1,-2] or -[1;1,24,1,2] (not [-2;25,1,2])
the other definition works, but is it pretty or pretty bizzare?--Nigel Galloway 13:27, 12 March 2013 (UTC)
My point is that there is no guarantee that a sequence is actually unique. The fundamental issue is that there are two ways of solving the integer division problem when extending into producing negative results: one states that the sign is an indication of the sign of the inputs, and the other states that division is about partitioning the number line and indicating which partition. (Alternatively, one definition of integer division uses round-to-zero and the other uses round-down rules when converting from a non-integer intermediate result; I've never heard of a universally-accepted definition of which of those two is right.) As long as is true, mathematical sanity is maintained. Different languages have different rounding rules. (BTW, C prior to C99 has implementation-defined rounding rules[3]. With C++, I think C++11 is the first revision of the standard to define this clearly[4].) –Donal Fellows 15:24, 12 March 2013 (UTC)
Is your point that you want the task defining so that it has a unique solution? I have shown that both are used in other places so it is dificult to say one is right. Interestingly that which Spoon! says above is true for Python2 but Python3 returns a floating point. So if I define Q/R as A remainder B where A=trunc(Q/R) and B=Q-A*R Python2 will produce your answer and Python3 will produce the better answer. How cool is that? UberKool or what? A killer reason to upgrade to Python3!!!--Nigel Galloway 12:50, 13 March 2013 (UTC)

Marking as draft

I am marking this task as draft for reasons similar to Talk:Continued_fraction/Arithmetic/G(matrix_NG,_Contined_Fraction_N)#Marking_as_.22draft.22 --Rdm (talk) 10:31, 9 July 2015 (UTC)

Also note that the code here (for example in the C++ implementation) is incomplete, as is the task description. To solve this, you need to know which rosettacode tasks contain the missing task description and how to adapt the code there to work here. (That may be simple - I do not know yet.)

Specifically, the task lacks a specific terminating condition. And the C++ implementation uses a .moreTerms() method which is not included in the implementation here. Meanwhile Continued_fraction/Arithmetic/G(matrix_NG,_Contined_Fraction_N) has an "I am done when" clause in the task description and code which won't compile without the NG_8 implementation here (unless you remove that reference) and an implementation of the .moreTerms() method. Also the c++ implementation there (and here) has a further [currently undocumented] dependency on code in the task Continued_fraction_r2cf(Rational_N).

This is a somewhat depressing state of affairs - implementations should not be this incomplete -- users should not have to puzzle out which other rosetta code tasks they need to extract code from to debug an implementation. --Rdm (talk) 11:44, 11 July 2015 (UTC)

Have added some links to the C++ entry, since no-one else was ever going to. --Pete Lomax (talk) 19:37, 17 August 2020 (UTC)
The main thing is that G, NG, matrixNG, N1, N2, NG4, and NG8 are quite ridiculous names, it would actually be better or at least less misleading if they were changed to Galloway, NigelGalloway, matrixNigelGalloway, Nigel1, Nigel2, NigelGalloway4 and NigelGalloway8. (Ha-Bloody-Ha). And Yes, that would also include moving things to two new pages names of
Continued_fraction/Arithmetic/Galloway(matrix_NigelGalloway,_Contined_Fraction_Nigel), and
Continued_fraction/Arithmetic/Galloway(matrix_NigelGalloway,_Contined_Fraction_Nigel1,_Contined_Fraction_Nigel2)
Hopefully my latest Phix entry will help clarify/suggest better names for things.
As noted, the scatterbox over several (inadequately linked) pages issue also needs addressing. --Pete Lomax (talk) 14:18, 18 August 2020 (UTC)

Rename/rewrite Suggestion

The above two tasks should be renamed as simply "Continued_fraction/Arithmetic/Unary" and "Continued_fraction/Arithmetic/Binary", and read more like this (for "Binary"):

Perform arbitrary mathethatical operations on two continued fractions, such as +, -, *, and /.

The suggested approach is to write a function/class/method apply_full_matrix(ctrl,cf1,cf2) which takes a 2x4 control array and two continued fractions, and yields a continued fraction result. Assume ctrl is eight plain integers of the form

             {{ a12, a1, a2, a },
              { b12, b1, b2, b }}

Then the result of apply_full_matrix(ctrl,cf1,cf2) would be

       (a12*cf1*cf2 + a1*cf1 + a2*cf2 + a)
       -----------------------------------
       (b12*cf1*cf2 + b1*cf1 + b2*cf2 + b)

For instance:

             {{ 0, 1, 1, 0},       calculates cf1 + cf2
              { 0, 0, 0, 1}}         (divided by 1)
             {{ 0, 1,-1, 0},       calculates cf1 - cf2
              { 0, 0, 0, 1}}         (divided by 1)
             {{ 1, 0, 0, 0},       calculates cf1 * cf2
              { 0, 0, 0, 1}}         (divided by 1)
             {{ 0, 1, 0, 0},       calculates cf1
              { 0, 0, 1, 0}}          divided by cf2

If a12,a1,b12,b1 are all 0 then cf1 is not required/referenced and apply_fm() could accept some form of dummy/null value for it.
If a12,a2,b12,b2 are all 0 then cf2 is not required/referenced and apply_fm() could accept some form of dummy/null value for it.
Such cases are covered by a "baby" 2x2 control matrix in [["Continued_fraction/Arithmetic/Unary"]] (currently named/located as Continued_fraction/Arithmetic/G(matrix_NG,_Contined_Fraction_N)) and it should (in theory) be perfectly possible to use this full form to replicate those results.

If b12,b1,b2,b are all zero we are done (presumably if that was initial state we end up with no terms, corresponding to undefined/error/divide by zero).
If a12,a1,a2,a are initially all zero the result should be zero.
If a12,a1,a2,b12,b1,b2 are all zero then neither cf1 nor cf2 are required and the result is the constant fraction a/b (but in continued fraction format). In effect we define apply_fm() as operations on ctrl which (eventually) make a12..b2 zero so that we can then simply read the (rest of the) result from a and b.

At that point I ran out of steam... Maybe this can be finished(/tweaked here) in small steps? --Pete Lomax (talk) 14:18, 18 August 2020 (UTC)

Cookies help us deliver our services. By using our services, you agree to our use of cookies.