Simplify a continued fraction

Question

Continued fractions are expressions that describe fractions iteratively. They can be represented graphically:

Or they can be represented as a list of values: [a₀; a₁, a₂, a₃, ... a_n]

The challenge:

take a base number: a₀ and a list of denominator values: [a₁, a₂, a₃, ... a_n] and simplify the continued fraction to a simplified rational fraction: return or print numerator and denominator separately.

Examples:

√19 : [4;2,1,3,1,2]: 170/39
ℯ: [1;0,1,1,2,1,1]: 19/7
π: [3;7,15,1,292,1]: 104348/33215
ϕ: [1;1,1,1,1,1]: 13/8

Example implementation: (python)

def foo(base, sequence):
    numerator = 1
    denominator = sequence[-1]
    for d in sequence[-2::-1]:
        temp = denominator
        denominator = d * denominator + numerator
        numerator = temp
    return numerator + base * denominator, denominator

Winning:

shortest code in bytes: --no builtins that do the entire problem allowed--

You should make this sentence more clear, "and simplify the continued fraction to a single fraction"; unless you intended the wording to mean a result of 2.002 can be expressed as 2002/1000. That's technically a "single fraction", you probably want to say, "a single fraction, in its most simple form." — Magic Octopus Urn, Sep 14 '16 at 20:29
@carusocomputing point taken.. although I wouldn't feel too bad about 2/4 (or similar) as it has still simplified the multiple fraction structure to a single fraction — Aaron, Sep 14 '16 at 20:47
Hmm... I think there's a way to exploit that, but with the 13 byte golfscript answer, I'd have to probably use MATL to win. — Magic Octopus Urn, Sep 14 '16 at 21:00
@carusocomputing I'd say go for it... If you can beat the 13 byte answer, that'd be awesome — Aaron, Sep 14 '16 at 21:29

Community · Accepted Answer · 2020-06-17 09:04:33Z

15

J, 8 5 bytes

Same as this, but uses a build-in for rationals.

Argument is {a0,a1,a2,a3,...} as a list of J extended precision rational numbers. Result is the fraction as a J extended precision rational number.

(+%)/

(+%) the plus-the-reciprocal-of

/ reduction over

Try it online!

-3 thanks to miles.

edited Jun 17 at 9:04

Community♦

1

answered Sep 14 '16 at 23:07

Adám

30.5k2 gold badges92 silver badges247 bronze badges

\$\begingroup\$ If you take the input as a list of extended integers, you could save 3 bytes. Also you used APL division in the explanation. \$\endgroup\$ – miles Sep 14 '16 at 23:32
\$\begingroup\$ @miles Thanks. Can't get closer to the built-in prohibition than that. Too bad J doesn't have a hook composition character like Dyalog APL's ∘. \$\endgroup\$ – Adám Sep 14 '16 at 23:43
\$\begingroup\$ The try J online link is broken \$\endgroup\$ – Chiel ten Brinke Feb 27 '18 at 13:56
\$\begingroup\$ @ChieltenBrinke Thanks. Fixed. \$\endgroup\$ – Adám Feb 27 '18 at 14:03

add a comment |

nimi · Accepted Answer · 2016-09-15 14:35:19Z

12

Haskell, 37 36 18 bytes

foldr1$(.(1/)).(+)

This function expects Haskell's Ratio type as input. Usage example:

Prelude Data.Ratio> ( foldr1$(.(1/)).(+) )  [4%1,2,1,3,1,2] 
170 % 39

Note: one explicit Ratio in the input list (4%1) is enough, the type systems figures out that the others have to be Ratios, too.

Edit: @Lynn saved a byte. Thanks!

Edit II: removed the import (see this discussion on meta).

edited Sep 15 '16 at 14:35

answered Sep 14 '16 at 20:41

nimi

34.7k3 gold badges29 silver badges92 bronze badges

1

\$\begingroup\$ Oooh, nice edge case. The function itself is polymorphic, so it doesn't need the import. However to call it, you have to feed Ratios to it which does need the import. Should I add the import to the byte count or not? \$\endgroup\$ – nimi Sep 14 '16 at 20:47
1

\$\begingroup\$ That sounds like a good question for meta. \$\endgroup\$ – Martin Ender Sep 14 '16 at 20:48
\$\begingroup\$ I've never used Haskell, so correct me if I'm wrong, but if the python equivelent would be: from fractions import Fraction to do operations with Fraction objects, the import statement is counted as well. \$\endgroup\$ – Aaron Sep 14 '16 at 20:54
\$\begingroup\$ .. we had that before. \$\endgroup\$ – nimi Sep 14 '16 at 20:54
\$\begingroup\$ @Aaron: the problem is: the definition of the function doesn't need the import, because it's polymorphic. When you want to call it, you need to provide numbers of type Ratio which can only be constructed via %, which requires the import. Usually we don't count bytes for calling overhead, just for the function itself. \$\endgroup\$ – nimi Sep 14 '16 at 20:59

| show 6 more comments

Community · Accepted Answer · 2017-04-13 12:39:03Z

GolfScript, 13 bytes

~]-1%{\-1?+}*

Try it online!

Yay for GolfScript's hidden rationals. :)

Explanation

GolfScript's only "official" number type is integers. But the exponentiation operator doesn't cast its result to integer and conveniently the native result of an integer exponentiation in Ruby (the language of GolfScript's interpreter) is a rational number. So we can easily get fractions by raising something to the power of -1. Conveniently, we want reciprocals anyway...

~]     # Evaluate input and wrap all a_i in a list.
-1%    # Reverse the list so that a_n is at the start and a_0 at the end.
{      # Fold... (apply this block to each element from a_n-1 down to a_0, with
       # the previous result on the stack)
  \    #   Swap previous result with current a_i.
  -1?  #   Raise previous result to the power of -1, computing its reciprocal
       #   as a rational number.
  +    #   Add a_i.
}*

ijustlovemath · Accepted Answer · 2016-09-14 22:43:18Z

10

LabVIEW, 36 equivalent bytes

Fairly straight forward naive implementation using OP's algorithm. Is there a nicer way to do this?

answered Sep 14 '16 at 22:43

ijustlovemath

3311 silver badge6 bronze badges

5

\$\begingroup\$ Your electrical engineering degree is showing. \$\endgroup\$ – Magic Octopus Urn Sep 15 '16 at 11:52
1

\$\begingroup\$ @ijustlovemath Props, but..... relevant \$\endgroup\$ – Aaron Sep 15 '16 at 13:30
\$\begingroup\$ Yeah it's a contentious language to be sure. I see LabVIEW as the "I hate math" of the programmers world. The problem is not math itself, but how it's taught (or often the lack of teaching at all). \$\endgroup\$ – ijustlovemath Sep 15 '16 at 14:02

add a comment |

Community · Accepted Answer · 2017-04-13 12:39:07Z

Mathematica, 23 22 bytes

Fold[#2+1/#&]@*Reverse

Essentially a port of my GolfScript answer. Here are some alternatives:

For 24 bytes, we can write a recursive variadic function:

f@n_=n
n_~f~m__:=n+1/f@m

For 21 bytes, we can even define a "variadic operator", but its calling convention would be so weird, that I'm reluctant to count this one:

±n_=n
n_ ±m__:=n+1/±m

You would have to call this with a sequence of the input values, e.g. ±Sequence[3, 7, 15, 1, 292, 1] or ±##&[3, 7, 15, 1, 292, 1].

And also for 21 bytes, there would be the (forbidden) built-in:

FromContinuedFraction

Community · Accepted Answer · 2020-06-17 09:04:33Z

6

Dyalog APL, 10 bytes

Does not even use a build-in for rationals.

Takes {a₀,a₁,a₂,a₃,...} as argument, returns {denominator,numerator}.

1(,÷∨)+∘÷/

1(,÷∨) 1-prepended-to divided by the GCD of 1 and

+∘÷ plus-the-reciprocal-of

/ reduction over

TryAPL online!

edited Jun 17 at 9:04

Community♦

1

answered Sep 14 '16 at 21:43

Adám

30.5k2 gold badges92 silver badges247 bronze badges

add a comment |

Community · Accepted Answer · 2017-04-13 12:39:03Z

Python 2, 62 bytes

a=d=0
b=c=1
for n in input():a,b=b,n*b+a;c,d=d,n*d+c
print b,d

It's unfortunately not as golfy (see @xnor's answer for shorter), but it calculates the fraction without needing to reverse the input. This uses the "magic table" approach for convergents – given the last two fractions a/c and b/d, the next fraction is (n*b+a)/(n*c+d).

For instance, for pi:

          3    7    15     1      292        1

  0   1   3   22   333   355   103993   104348
  1   0   1    7   106   113    33102    33215

We can see that 15*22 + 3 = 333, 15*7 + 1 = 106, 1*333 + 22 = 355, 1*106 + 7 = 113, etc.

miles · Accepted Answer · 2016-09-14 23:49:04Z

4

M, 5 bytes

Ṛİ+¥/

The input is a list of the values [a0, a1, ..., aN] and it outputs a rational number.

Try it online! or Verify all test cases.

Explanation

Ṛİ+¥/  Input: list A
Ṛ      Reverse A
    /  Reduce A from left to right using
   ¥     A dyadic chain
 İ         Take the reciprocal of the left value
  +        Add the reciprocal to the right value
       Return and print implicitly

answered Sep 14 '16 at 23:49

miles

15.7k2 gold badges23 silver badges90 bronze badges

1

\$\begingroup\$ What is this? Some new Jelly dialect? \$\endgroup\$ – Adám Sep 15 '16 at 12:41
\$\begingroup\$ @miles actually 9 bytes sorry :( \$\endgroup\$ – Aaron Sep 15 '16 at 13:42
\$\begingroup\$ @Adám It's an old fork of Jelly meant for math and symbolics. Here's its Github repo. \$\endgroup\$ – miles Sep 15 '16 at 14:00
1

\$\begingroup\$ @Aaron M uses the same code page as Jelly, and it can be encoded using a byte for each character. \$\endgroup\$ – miles Sep 15 '16 at 14:01
\$\begingroup\$ @miles OK, added. \$\endgroup\$ – Adám Sep 15 '16 at 15:21

| show 1 more comment

xnor · Accepted Answer · 2016-09-15 00:49:14Z

4

Haskell, 30 bytes

foldr(\h(n,d)->(h*n+d,n))(1,0)

Recursively adds each layer going outward, updating n/d to h+(1/(n/d)), which equals h+d/n or (h*n+d)/n. The fraction is stored as a tuple of (num,denom). The initial fraction of (1,0) flips to 0/1 which is 0.

edited Sep 15 '16 at 0:49

answered Sep 15 '16 at 0:29

xnor

122k21 gold badges230 silver badges544 bronze badges

add a comment |

xnor · Accepted Answer · 2016-09-15 00:49:55Z

3

Python, 50 bytes

f=lambda l,n=1,d=0:l and f(l,l.pop()*n+d,n)or(n,d)

Builds the continued fraction from the end of the list going backwards, repeatedly updating the fraction n/d on the last element x as n/d -> 1+1/(n/d) == (x*n+d)/n.

answered Sep 15 '16 at 0:49

xnor

122k21 gold badges230 silver badges544 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

Common Lisp, 54

A somewhat verbose fold-right:

(lambda(s)(reduce(lambda(a r)(+(/ r)a))s :from-end t))

Tests

PASS  NAME  ACTUAL               EXPECTED
===============================================
T     √19   170/39               170/39              
T     ℯ     19/7                 19/7                
T     π     104348/33215         104348/33215        
T     ϕ     13/8                 13/8

Magic Octopus Urn · Accepted Answer · 2016-09-14 20:53:38Z

2

Julia (53 Bytes)

This is my first time ever using Julia, if I overlooked an iterator I could have used to lose some more bytes, let me know. Here's a hint to anyone who doesn't know what language to choose for this specific challenge: https://en.wikipedia.org/wiki/Rational_data_type

f(x,c)=(a=0;for b in x[end:-1:1];a=1//(b+a);end;a+c;)

Reverse the input array.
Iterate through it with rational division.
Add c to the decimal result.

answered Sep 14 '16 at 20:53

Magic Octopus Urn

19.6k4 gold badges50 silver badges129 bronze badges

\$\begingroup\$ you can save two bytes by defining an operator (e.g. ∘) instead of a function \$\endgroup\$ – Tasos Papastylianou Sep 15 '16 at 0:44
\$\begingroup\$ also, change the for loop for a while and pop: x∘c=(a=0;while x!=[];a=1//(pop!(x)+a);end;a+c;) \$\endgroup\$ – Tasos Papastylianou Sep 15 '16 at 0:55
1

\$\begingroup\$ 25: x->foldr((x,y)->x+1//y,x) (same as Haskell solution). usage: (x->foldr((x,y)->x+1//y,x))([4//1,2,1,3,1,2]) \$\endgroup\$ – Fengyang Wang Sep 15 '16 at 3:04
\$\begingroup\$ Ooo... A reverse folding function? That's beautiful! I don't deserve to take credit for that though haha. \$\endgroup\$ – Magic Octopus Urn Sep 15 '16 at 11:52

add a comment |

Arnauld · Accepted Answer · 2016-09-14 23:07:50Z

Javascript (ES6), 55 bytes

s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

Test cases

var f =
s=>eval('for(F=[1,0];s+"";)F=[s.pop()*F[0]+F[1],F[0]]')

console.log(f([4, 2, 1, 3, 1, 2]));
console.log(f([1, 0, 1, 1, 2, 1, 1]));
console.log(f([3, 7, 15, 1, 292, 1]));
console.log(f([1, 1, 1, 1, 1, 1]));

Sp3000 · Accepted Answer · 2016-09-15 00:33:15Z

CJam, 18 16 bytes

XUq~W%{2$*+\}/]p

Online interpreter.

XU                  Push 1 and 0 to the stack
  q~W%              Push input, eval and reverse it
      {     }/      For each n in the reversed input...
       2$             Copy numerator
         *+           Calculate n*denominator + numerator
           \          Swap numerator and denominator
              ]p   Wrap in array and output

Emigna · Accepted Answer · 2016-09-15 06:52:07Z

05AB1E, 19 17 bytes

R¬V¦vyY*X+YUV}YX)

Explanation

Input taken as a list of numbers

                     # variable X is initialized as 1
R¬V¦                 # reverse the list, remove the first item and store it in variable Y
    v        }       # for each item N left in list
     yY*X+  V        # store N*Y+X in Y
          YU         # store Y in X
              YX)    # wrap X and Y in a list

Try it online!

Neil · Accepted Answer · 2016-09-15 09:03:31Z

2

JavaScript (ES6), 44 bytes

a=>a.reduceRight(([n,d],v)=>[v*n+d,n],[1,0])

answered Sep 15 '16 at 9:03

Neil

105k9 gold badges50 silver badges210 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Javascript (ES6), 50 bytes

f=(s,n=1,d=s.pop())=>s+""?f(s,d,s.pop()*d+n):[d,n]

It's thanks to Arnauld's answer, before seeing it I was stuck to 66 bytes:

f=(b,s,i=s.length-1,n=1,d=s[i])=>i?f(b,s,--i,d,s[i]*d+n):[n+b*d,d]

Example:
Call: f([1, 0, 1, 1, 2, 1, 1])
Output: Array [ 19, 7 ]

edited Jun 17 at 9:04

Community♦

1

answered Sep 14 '16 at 23:45

Hedi

1,8971 gold badge8 silver badges17 bronze badges

add a comment |

Brad Gilbert b2gills · Accepted Answer · 2016-09-15 20:06:36Z

Perl 6, 24 bytes

{[R[&(1/*+*)]](@_).nude}

Explanation:

1 / * + * is a lambda with two parameters (*) which takes the reciprocal of the first, and adds the second. ( returns a Rat )
R[&(…)] uses that as if it was an infix operator and reverses it.
( including making it right associative )
[…](@_) takes that and uses it to reduce the input.
… .nude returns the numerator and denominator of the Rat.
{ … } make it a bare block lambda with implicit parameter @_.

Usage:

say {[R[&(1/*+*)]](@_).nude}(3,7,15,1,292,1) #*/# (104348 33215)

my &code = {[R[&(1/*+*)]](@_).nude}; # stupid highlighter */

say code 4,2,1,3,1,2;    # (170 39)
say code 1,0,1,1,2,1,1;  # (19 7)
say code 1,1,1,1,1,1;    # (13 8)

DLosc · Accepted Answer · 2016-09-16 07:54:58Z

Zephyr, 145 bytes

input n as Integer
set a to Array(n)
for i from 1to n
input a[i]as Integer
next
set r to a[n]
for i from 1to n-1
set r to(/r)+a[n-i]
next
print r

Zephyr is the first programming language I ever created. It was designed to be intuitive and have clean syntax--rather at the expense of brevity. Why am I golfing with it, you ask? Because, unlike any language I've written since, it has a built-in Fraction type. You can even use the division operator / as a unary operator for "inverse" (a feature I borrowed for Pip).

Now, there are significant limitations. The biggest problem for this challenge is that arrays must be defined with fixed size, which means that the program starts by reading the size of the array from the user. (I hope this is ok; the alternative is hardcoding the size.) There's also the minor problem that operator precedence doesn't exist, meaning multi-operator expressions have to have parentheses.

Here's an example run:

C:\Zephyr> python zephyr.py contfrac.zeph
6
1
1
1
1
1
1
13/8

IMP1 · Accepted Answer · 2019-07-24 14:04:36Z

Ruby, 34 bytes

->a{a.reverse.inject{|b,i|i+1r/b}}

This performs a right fold (by reversing and then left folding), adding each element to 1 over the running total (the elements to the right). Ruby has the Rational type, which is really nice. And literal rationals are a number suffixed with r.

recursive · Accepted Answer · 2019-07-24 15:50:08Z

1

Stax, 4 bytes

╣╩┼►

Run and debug it

As small as it is, it's not a built-in. The built-in rationals help quite a bit though. Unpacked to ascii, the program is rksu+.

Reverse the array.
Fold the array using (a, b) => (a + 1/b).

answered Jul 24 '19 at 15:50

recursive

8,96116 silver badges32 bronze badges

add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

APL(NARS), 15+1 chars, 30+2 bytes

{1=≢⍵:↑⍵⋄+∘÷/⍵}

Translation in Apl(Nars) from Adam J solution... the input allowed for that function will be all list of integer numbers, where the first element will be of type rational. Test:

  f←{1=≢⍵:↑⍵⋄+∘÷/⍵}      
  f 4x 2 1 3 1 2
170r39 
  f 1x 0 1 1 2 1 1
19r7 
  f 3x 7 15 1 292 1
104348r33215 
  f 1x 1 1 1 1 1
13r8 
  f 3x 89 888 999 11 222 373 7282 9272 3839 2828 
158824716824887954093160207727r52744031585005490644982548907 
  f ,0x
0 
  f ,9x
9

so it would be 15 chars as length of function and 1 char for "x" for enter the type of input I want and exit the type I want...

Simplify a continued fraction

The challenge:

Examples:

Example implementation: (python)

Winning:

22 Answers 22

J, 8 5 bytes

Haskell, 37 36 18 bytes

GolfScript, 13 bytes

Explanation

LabVIEW, 36 equivalent bytes

Mathematica, 23 22 bytes

Dyalog APL, 10 bytes

Python 2, 62 bytes

M, 5 bytes

Explanation

Haskell, 30 bytes

Python, 50 bytes

Common Lisp, 54

Tests

Julia (53 Bytes)

Javascript (ES6), 55 bytes

Test cases

CJam, 18 16 bytes

05AB1E, 19 17 bytes

JavaScript (ES6), 44 bytes

Javascript (ES6), 50 bytes

Perl 6, 24 bytes

Explanation:

Usage:

Zephyr, 145 bytes

Ruby, 34 bytes

Stax, 4 bytes

APL(NARS), 15+1 chars, 30+2 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf math rational-numbers or ask your own question.

Linked

Related

Hot Network Questions