Inverse symbolic calculator

Question

This challenge is based on the idea of Plouffle's Inverter.

Write a program in any language that does the following:

• Takes as input a non-negative rational number X written in decimal, for example 34.147425.

• Returns a mathematical expression using only non-negative integers, whitespace, parentheses, and the following binary operators:

  • Addition +
  • Subtraction -
  • Multiplication *
  • Division /
  • Exponentiation ^

  The expression should evaluate to X, or at least agree with all the digits of X. To continue the example, a correct output could be 13 + 20^(5/4) / 2, since 13 + 20^(5/4) / 2 = 34.1474252688...

• Output may optionally be written in Polish notation (prefix) or reverse Polish notation (postfix), i.e. + 13 / ^ 20 / 5 4 2 is fine.

The program is subject to the following retrictions:

• Standard loopholes are forbidden! In particular, the program cannot read any external lookup table.

• The source code of the program must be shorten than 1024 characters.

The program with the lowest average compression ratio will win.

To determine your average compression ratio, you can to use the following Python script, or write your own equivalent program. Here is the list of 1000 random numbers.

import random

def f(x):
    # edit this function so that it will return 
    # the output of your program given x as input
    return "1 + 1"

random.seed(666)

S = 1000 # number of samples

t = 0.0

for n in xrange(0, S):
    # pick a random decimal number
    x = random.uniform(0, 1000)

    # compute the compression ratio
    # length of output / length of input
    r = len(f(x).translate(None, " +-*/^()")) / float(len(str(x).translate(None, ".")))
    t += r

print "Your average compression ratio is:", t / S

Good luck!

NOTES:

• Whitespaces in the output are not mandatory. Strings like 1+1, 1 +2, or 1 + 2, are all okay. Indeed, the script to compute the score does not count whitespaces and parenthesis in the length of the output. However, note that the use of whitespaces is necessary if you choose Polish or reverse Polish notation.

• Regarding the usual infix notation, the precedence rules are the following: first all exponentiation (^), then all divisions (/), then all multiplications (*), then all additions (+) and all subtractions (-). But I do not know how much this could matter, since you can use parentheses.

• A way to edit the function f in the script above can be the following, however I think that it depends on your operating system; on GNU/Linux it works. Name your program "inverter" (or "inverter.exe") and place it in the same directory as the Python script. Your program should get X as the first argument of command line and return the expression in STDOUT. Then edit f as follows:

  import os
  def f(x):
      return os.popen("./inverter " + str(x)).read()
  

EDIT: As a consequence of the comment of Thomas Kwa, now the operators do not contribute to the length of the expression. The challenge should be more "challenging".

Answer 1

Haskell, 1.08404005439

import System.Environment
import Data.Ratio
import Data.Lists

main = do
   arg <- fmap head getArgs
   let number = read (arg ++ "5")
   let (_,_:decs) = span (/= '.') arg
   let acc = (read $ "0." ++ (decs >> "0") ++ "4999") :: Double
   putStr $ replace " % " "/" $ show $ approxRational number acc

This uses the approxRational function which converts a floating point number to a fraction with a accuracy of a given epsilon. It simply returns this fraction. As Haskell prints rationals with a % in-between, we have to replace it with the division sign /.

The accuracy parameter is calculated from the input number. We have to take into account that all the digits have to match, so 4.39 is fine for 4.3 but 4.29 isn't. I append a 5 to the number and the accuracy is a 4999 at the same decimal place as the appended 5, e.g.

12.347       -- input number
12.3475      -- append 5
 0.0004999   -- accuracy epsilon for the "approxRational" function.

E.g. 34.147425 -> 43777/1282.

Edit: the rules for accuracy have changed. The test case includes numbers with up to 11 decimal places and all have to match.

Edit II: it seems that the provides Python script doesn't strip off trailing newlines, so I've changed from putStrLn to putStr.

Edit III: again, new scoring rules

Answer 2

Mathematica, 1.1012 1.10976107226107

Rationalize[# + 5 (a = 10^(Floor@Log10@# - Length[First@RealDigits@# //. {a___, 0} :> {a}])), 5 a - 1*^-4 a]~ToString~InputForm &

So far, this has the lowest score! Gives the rational with the smallest denominator given the digits. (Sorry for the unreadability, forgot that this wasn't a golf contest for a minute.) Some testing:

In[1]:= f=Rationalize[#+5(a=10^(Floor@Log10@#-Length[First@RealDigits@#//.{a___,0}:>{a}])),5a-1*^-4a]~ToString~InputForm&;

In[2]:= f[811.359484104]

Out[2]= 9876679/12173

In[3]:= f[0.000000001]

Out[3]= 1/666666666

In[4]:= f[999.999999999]

Out[4]= 2000021150999/2000021151

Answer 3

Python, 1.25927791772

I'm surprised no one else has tried the obvious approach, which incurs about 26% overhead:

from decimal import *
def simplify(numstr):
    numdec = Decimal(numstr)
    digits = -(numdec.as_tuple().exponent)
    num = float(numstr)
    return '{0:.0f}'.format(num * 10**digits) + '/10^' + str(digits)

This just converts XX.XXXX into XXXXXX/10^4 and so on. For the majority of test numbers, this means converting 12 digits (and an uncounted decimal point) to the same 12 digits plus three more (plus two uncounted symbols).

Answer 4

JavaScript 1.7056771894771656

Very simple, very bad score

F=x=>([x,d]=x.split`.`,n=+(x+d),d=+d.replace(/./g,9)+1,G=(a,b)=>b?G(b,a%b):a,g=G(n,d),(n/g)+'/'+(d/g))

test=[456.119648977, 903.32315398, 434.375496831, 500.626690792, 811.359484104, 
553.673742554, 712.174768248, 123.142093787, 814.759762152, 385.493673216, 
629.109959804, 891.825687728, 988.817827772, 16.7651557543, 967.455933006, 
99.3802569984, 681.552992408, 169.770898456, 921.658967707, 610.512640655, 
420.065644152, 702.514151372, 517.04720252, 86.3589856368, 960.117250449, 
311.152728003, 620.240077706, 130.232920047, 901.22564153, 528.511688187, 
50.841278105, 737.146071519, 836.88270257, 13.9544843156, 45.8723706867, 
760.14443626, 256.035110545, 460.972156302, 217.514875811, 34.4165446011, 
426.209854826, 500.979753237, 930.071200996, 751.301967463, 817.525354878, 
918.861794618, 794.520266221, 531.896652685, 419.295924811, 927.526963939, 
989.027382734, 82.1589263516, 965.904769963, 708.295178015, 778.541588483, 
410.404428666, 894.612613172, 470.045387404, 460.773246884, 505.524899467, 
451.852274382, 417.910824093, 883.45180574, 319.767238241, 544.794416784, 
346.361844704, 122.300743514, 517.293385872, 748.134450425, 589.547392631, 
870.937945528, 465.607198253, 379.697188157, 215.095671553, 471.696590273, 
544.827425571, 883.01895272, 514.893297677, 703.800591, 788.816870867, 
777.433484884, 990.615076538, 925.473132794, 494.964321255, 911.643885633, 
103.244050895, 425.938382631, 421.075783639, 363.155392963, 301.617712632, 
268.237096551, 42.0971441114, 252.071029659, 260.398845137, 433.781658026, 
278.550969539, 446.456847155, 466.145132666, 23.1267325005, 92.2303701531, 
792.994090972, 100.482658881, 796.600758817, 786.019664003, 328.859998399, 
390.221668208, 750.32581915, 332.277362524, 983.205082197, 862.001172096, 
823.825060923, 662.455639665, 926.337262367, 618.446017944, 696.465793349, 
408.095136772, 519.31659792, 928.091368548, 177.367743543, 980.822594006, 
401.832552937, 66.1163636071, 127.511709579, 291.85194129, 11.338995907, 
880.568902788, 982.945394792, 491.753920356, 222.011915866, 317.023389252, 
601.694693495, 871.340895438, 427.621115915, 886.273120812, 345.688431619, 
248.992214068, 738.874584632, 109.03516681, 146.362341902, 447.713463802, 
600.947018155, 415.419601291, 369.549014288, 141.697677152, 895.502232931, 
528.201404793, 673.817459041, 215.852364841, 164.552047867, 764.085838441, 
323.70504093, 197.868519457, 759.91813327, 369.341528152, 768.793424447, 
111.674153727, 495.99248701, 363.669738825, 596.082713332, 747.205484326, 
666.879146337, 102.908405893, 424.113319661, 476.379228696, 971.353959219, 
162.634464034, 761.838583493, 767.799964665, 347.294217881, 353.760366385, 
230.905221575, 125.898250349, 565.850510939, 667.61204275, 196.449923318, 
279.792505368, 279.034332146, 533.902967966, 57.688797172, 153.08128158, 
821.993175733, 982.886617074, 433.447389936, 29.0911289168, 442.422057169, 
804.518563086, 500.73307383, 948.932673563, 723.030013363, 572.092408062, 
853.660849797, 481.331513905, 942.064561235, 42.4709711072, 982.87325027, 
352.171583912, 238.247057259, 823.238147233, 526.013997729, 644.51102393, 
366.71793217, 933.49508788, 903.534625763, 857.169528071, 735.780465845, 
378.732263357, 12.1875971069, 964.370964223, 419.654315024, 705.414457347, 
353.953487281, 501.657967991, 849.706011343, 713.414932699, 827.420809946, 
596.719004174, 609.780183857, 826.546581587, 76.33513551, 0.500492073649, 
627.694684485, 186.236492637, 360.200893605, 478.625892592, 229.111877611, 
423.754891888, 657.973373515, 16.9761882463, 974.491769915, 945.864753785, 
237.454051339, 179.687469205, 418.658590265, 714.833543375, 318.816023475, 
650.727666516, 488.596054138, 987.542619517, 216.006047902, 80.7125255243, 
144.181653533, 266.522883823, 818.574355104, 600.21171237, 895.307289865, 
198.329664663, 124.824876993, 31.1227116403, 541.348603643, 542.257190363, 
304.231517157, 506.706000025, 84.9413478067, 170.491409724, 229.013799764, 
671.014301245, 87.1441069227, 763.676724963, 742.639944243, 435.559778934, 
383.882521911, 238.741657776, 647.17907848, 927.512981306, 549.612975568, 
791.443454295, 701.809936899, 987.551368536, 91.3122813408, 398.587619734, 
847.240295481, 470.53644512, 507.410113063, 540.35838629, 637.883207888, 
982.322584309, 975.975221911, 371.493982019, 172.638439006, 747.126873375, 
99.5418242164, 309.903703204, 640.628684948, 314.750618166, 146.000991772, 
384.388581648, 217.815818267, 733.571499911, 690.506791178, 945.671862182, 
344.854300466, 66.9720187046, 600.727439672, 98.4760964868, 295.60483304, 
478.855074245, 490.351187811, 479.533769337, 239.205093033, 58.7686847649, 
375.442162104, 615.561415277, 974.347539912, 743.935932659, 210.319831557, 
782.442881822, 556.123534411, 774.571029531, 821.094541585, 782.478179678, 
123.630035193, 652.088033798, 753.122074115, 303.840694329, 449.088557671, 
38.4843483532, 173.031570335, 728.973326841, 226.816627623, 119.472479023, 
705.899011665, 927.865200825, 157.998809157, 327.490515863, 225.137067487, 
501.556087254, 167.031923234, 396.975128016, 826.305341676, 396.340544863, 
569.58630546, 694.788762272, 10.1343501944, 369.36109683, 29.8034453658, 
916.970188353, 985.814850566, 888.359275561, 689.939392935, 409.116566134, 
144.938228502, 67.8210674843, 870.61549803, 563.639796984, 431.618386108, 
145.691380363, 350.505911146, 326.638836654, 708.160936271, 345.738257395, 
159.932627655, 311.885663889, 229.603462168, 110.746858295, 517.566252532, 
231.2683822, 908.329966697, 999.286952896, 700.486300449, 532.543272168, 
548.536320153, 248.586068291, 844.156717745, 477.281959996, 964.072712855, 
157.863146561, 919.917761996, 187.741733233, 358.474587832, 541.364663045, 
297.862474812, 673.876495999, 641.468684483, 934.366789232, 112.750864631, 
179.36727691, 744.421362119, 954.914513373, 356.362877284, 642.423557253, 
835.156704382, 145.847575914, 917.085464611, 633.00944503, 4.20412765537, 
577.177004175, 774.63403371, 846.937269117, 978.134451441, 927.806763324, 
3.39763102303, 650.528163199, 347.525631206, 378.956292306, 266.22945414, 
175.085055263, 571.539823838, 274.670508282, 835.348780918, 190.612093018, 
425.355323169, 283.050471535, 573.262462068, 236.809923974, 86.5812138421, 
442.645729259, 376.598156438, 412.17611326, 575.13654395, 76.4906160271, 
382.261334337, 419.108062252, 413.347694426, 726.1697083, 738.059837008, 
228.479265313, 982.210601477, 693.205052764, 788.820483643, 279.491316277, 
381.050856949, 914.836538216, 369.451591691, 828.975002455, 33.0866822761, 
552.943575842, 229.194581446, 900.603947989, 697.081349116, 38.8501269177, 
599.81038281, 199.242914298, 565.383604483, 241.671424615, 874.199638779, 
294.933677019, 238.713921761, 953.886254575, 126.3147347, 156.308580451, 
1.01666626965, 410.067483484, 969.052527031, 184.927913357, 282.530928636, 
204.745328524, 450.670433109, 129.119772077, 581.256246505, 6.84233762299, 
39.4666067908, 865.975624765, 868.401636982, 114.207339514, 921.542812579, 
435.593193085, 346.934279797, 830.059520451, 691.952980275, 694.258623119, 
548.775134898, 527.057955887, 267.64250387, 113.091700858, 210.713307935, 
253.707632265, 832.083850441, 455.161145588, 403.528402677, 237.983049672, 
903.782609365, 314.331975332, 209.862002009, 488.057537383, 905.587478495, 
929.797161232, 325.793664626, 734.098176437, 519.087164488, 555.076580313, 
97.8973027155, 260.92615898, 391.460005616, 187.462694014, 660.460370626, 
861.783280209, 751.657352012, 528.280341385, 943.741294674, 204.705877292, 
106.65265656, 17.8070044565, 233.101412197, 38.2613365534, 729.385921979, 
773.529715946, 429.882870272, 166.782428109, 738.061383178, 381.289974545, 
425.98872381, 405.120420988, 672.370449304, 276.696982879, 640.620718977, 
244.652935713, 43.3611372718, 611.721720179, 552.336391617, 939.435275549, 
337.333914132, 88.3768763311, 537.456873711, 98.6468535441, 601.024140128, 
526.374477437, 959.339713851, 794.438445711, 419.365144317, 128.425263651, 
894.306756225, 750.689349267, 849.804073407, 144.580034264, 5.21870382078, 
316.954557791, 258.037070914, 907.185890899, 821.078874769, 73.0065239329, 
902.397997543, 623.811378865, 278.742785334, 546.742289504, 306.338798014, 
624.510083572, 278.778694986, 992.433419109, 568.791129496, 800.987198104, 
817.781503455, 364.391142069, 229.768701593, 791.500313449, 523.97492671, 
711.79222697, 841.514367793, 811.043873744, 312.112640331, 344.686366808, 
362.852877349, 908.102021975, 77.1500991776, 383.192419609, 686.951731951, 
220.529025627, 867.530056756, 14.3366282672, 408.594160445, 123.165786631, 
998.59134116, 548.326927924, 94.1928597561, 324.065711084, 731.488189617, 
665.464202995, 306.278211631, 986.173950386, 627.219661146, 333.954277825, 
90.2956353646, 162.227112949, 272.511457828, 857.528739452, 503.843643462, 
576.629152535, 548.024554676, 363.491120268, 679.874538441, 583.700940158, 
106.952792329, 9.38392100562, 338.353858169, 293.571162077, 804.681145319, 
767.462050744, 313.643862301, 468.190192547, 572.949085984, 350.221796616, 
917.105455473, 303.54853149, 391.390619956, 504.247647998, 93.0135480388, 
246.512166315, 908.97228941, 943.218403856, 530.309445245, 309.754887232, 
959.789201543, 970.486542083, 797.580736004, 290.319550119, 846.108212188, 
532.653666441, 887.339176163, 679.691675058, 912.533817736, 920.067525894, 
222.511534133, 96.2743176283, 21.4898199044, 77.2132479765, 371.345880832, 
436.959444929, 215.804186286, 399.231434773, 621.793520068, 670.184752989, 
898.150427875, 223.481192922, 886.318270113, 516.799097006, 533.999918536, 
713.480918784, 917.832970718, 372.788549636, 628.966711322, 944.179767515, 
192.101163486, 343.997422161, 804.100009349, 931.645390583, 990.171180084, 
260.766724798, 785.681499223, 356.704428677, 700.517830816, 951.584623525, 
144.084686297, 259.528412476, 171.745260869, 139.015277926, 901.447521593, 
620.501210347, 151.032781338, 46.1159165911, 425.230998623, 894.613060967, 
625.179508617, 242.868974022, 106.982050541, 301.464135508, 573.158784529, 
688.278622585, 464.999428923, 322.662480912, 110.118666284, 731.557589997, 
946.121567036, 495.536592777, 721.786554826, 401.204812967, 523.199107158, 
941.414041302, 13.1534875549, 156.596310513, 983.985066957, 371.429892366, 
597.927750948, 983.992168593, 170.977999856, 83.6807794877, 817.971626168, 
516.088416242, 827.937736139, 859.209288785, 615.315584986, 609.792111637, 
554.693516004, 470.967675734, 223.237818744, 990.385531141, 530.824138102, 
909.365555497, 994.864631519, 997.447332309, 328.212731713, 307.035914722, 
409.123485776, 799.130975525, 967.234526581, 959.671441584, 353.229298604, 
420.982728285, 76.7863969552, 28.5449571984, 210.265549753, 913.543941547, 
315.091741118, 662.094750123, 852.203603892, 298.207293217, 509.30012338, 
65.7679645109, 621.200794815, 935.510670259, 779.330025526, 937.283929747, 
756.173490123, 733.792396159, 795.211149457, 302.088313881, 570.641269144, 
757.135463505, 242.60845981, 457.593727034, 225.360079221, 142.221548109, 
17.6336964488, 360.261380451, 623.475218825, 692.670820913, 584.185971173, 
662.861929515, 276.807298644, 480.122225367, 954.608081636, 627.928577217, 
459.835351987, 485.168643598, 793.612119132, 654.855590208, 271.958933288, 
969.652698005, 976.785064283, 505.116414306, 797.184208528, 628.943525947, 
959.160096155, 663.113680213, 768.371354051, 590.4585491, 773.296754989, 
407.351603593, 88.0630070991, 905.529072694, 340.59794601, 439.12099902, 
233.540790202, 364.088450076, 470.123174021, 102.448882161, 608.789225571, 
392.768415134, 713.100614552, 209.2003898, 62.2154487033, 372.921756097, 
492.623365519, 581.128110129, 820.570542768, 339.686321984, 713.824072462, 
999.045113081, 306.938298797, 184.480805204, 465.144186806, 753.870865996, 
78.4248974773, 914.793550949, 952.526126809, 745.524994917, 138.306312094, 
727.779875346, 561.393678162, 772.777064716, 72.7542234799, 504.766493657, 
753.225048814, 171.848362302, 941.292665664, 441.751526079, 63.0349316166, 
535.273783514, 629.040768898, 808.08324249, 457.787416804, 187.372504534, 
418.1266562, 433.695070727, 776.092568964, 211.004041498, 740.766035298, 
816.391594543, 458.991042003, 94.0308738235, 624.589391691, 118.430830788, 
178.888039553, 905.16710481, 148.542033271, 962.242139722, 35.5229349814, 
716.472840429, 587.99823034, 252.557765324, 37.8879245566, 399.689202524, 
383.425506008, 464.748020898, 308.786698798, 583.669994119, 231.746308268, 
524.76171028, 897.374397044, 577.218755662, 562.645278506, 434.940887118, 
254.327344231, 540.874257344, 123.680835723, 539.503191151, 816.484752836, 
961.415099734, 349.660216271, 596.159995894, 595.762432693, 955.539005194, 
687.809440375, 571.725613886, 308.13021345, 617.471476595, 701.003582396, 
3.96581420188, 185.987820184, 48.1246847598, 539.131050625, 989.571379915, 
249.821643429, 725.895300104, 711.034103146, 74.8291260662, 721.572101122, 
142.992636014, 419.591421178, 984.914852359, 36.7363617464, 133.19819475, 
380.054235605, 692.83285665, 827.597995374, 995.818667532, 126.589103128, 
682.800070236, 466.330036969, 302.143073837, 786.240218566, 299.551583986, 
430.07770804, 483.534119703, 473.617334239, 1.64416431436, 953.126991927, 
251.892147628, 366.320222366, 137.6878957, 287.000037146, 348.549654758, 
55.6668003422, 65.1444653143, 810.336733005, 247.448273359, 514.541152359, 
545.299341596, 740.254480746, 607.431747363, 176.075079982, 922.502042696, 
585.799132666, 5.53670276888, 304.467968825, 298.915106192, 561.78882135, 
42.5914472262, 486.800635021, 61.0833598622, 944.347739678, 668.746271709, 
756.586266764, 408.787974993, 161.622855, 76.9222121123, 273.398447299, 
224.158188706, 869.44674983, 58.3114312618, 490.559449132, 439.137943547, 
816.959032357, 73.0577752895, 613.711059891, 899.395509193, 230.235211112, 
651.089914878, 418.795635547, 873.424446884, 897.792771782, 704.102385815, 
518.126528796, 545.099037865, 104.410545145, 416.115870896, 617.579630637, 
333.700660761, 698.454752336, 323.794560581, 614.778464988, 978.982432433, 
656.459219246, 311.387615291, 262.993283002, 98.703803798, 316.038737757, 
511.251635007, 597.716611457, 837.873132231, 985.745340467, 653.714321915, 
759.002380543, 257.908251778, 764.546995782, 336.260865935, 746.604123567, 
640.209566004, 448.844970845, 925.255475065, 972.485574416, 47.0841050739, 
231.133339622, 994.520385942, 766.591528041, 355.476025092, 325.525579517, 
591.707824382, 302.51618806, 250.791496027, 325.751078168, 148.78604636, 
488.176440838, 760.361648381, 213.189413642, 509.565395067, 284.468094856, 
567.126065507, 828.024492382, 938.902419548, 141.420420877, 719.989392811, 
854.189823836, 545.746745299, 713.177111859, 800.749418944, 217.781813549, 
692.416094897, 703.129981045, 607.928079305, 876.072026145, 983.933471359, 
824.755945781, 472.143208136, 22.2541577801, 640.071388089, 52.8148724127, 
646.607940231, 228.870749952, 824.59255967, 20.4078078906, 211.860134988, 
176.392620646, 786.744977859, 983.183973543, 738.585099683, 75.976724176, 
49.4604753001, 628.2042889, 991.358549436, 526.125428702, 836.487360003, 
216.533860839, 654.106395874, 65.4049854833, 858.352891393, 777.146190395, 
630.588944701, 141.352770092, 501.454292251, 792.956685991, 709.053823609];

console.log=(...x)=>O.textContent+=x.join` `+`\n`

console.log(test.length)
var r=0
test.forEach(v=>{
  v=v+''; // to decimal string
  var x=F(v);
  check = v==eval(x)
  if (!check) console.log ("Error",v,x,eval(x));
  else 
    // console.log(v,x),
    r+=x.length/v.length
    
});
console.log(r/1000)

<pre id=O></pre>

Answer 5

Python, 1.9901028749

Continued fractions turn out to not be a serious contender, unfortunately.

from fractions import *
def simplify(numstr):
    frac = Fraction(numstr)
    terms = []
    while frac>0:
        terms.append(int(frac))
        frac -= int(frac)
        if frac > 0:
            frac = 1/frac
    for n in range(0,len(terms)):
        temp = 0
        for i in range(n,0,-1):
            temp = 1.0/(terms[i]+temp)
            # print i, terms[i], temp
        temp += terms[0]
        # print repr(temp)
        if repr(temp)[:len(numstr)] == numstr:
            break
    return '+1/('.join([str(x) for x in terms[:n+1]]) + ')' * n

examples:

141.352770092 141+1/(2+1/(1+1/(5+1/(20+1/(20+1/(1+1/(1)))))))
501.454292251 501+1/(2+1/(4+1/(1+1/(31+1/(1+1/(4+1/(1+1/(1+1/(2)))))))))
792.956685991 792+1/(1+1/(22+1/(11+1/(2+1/(6+1/(1+1/(2+1/(1+1/(2)))))))))
709.053823609 709+1/(18+1/(1+1/(1+1/(2+1/(1+1/(1+1/(1+1/(10+1/(58)))))))))

Answer 6

Python, 1.10900874126

Actually evaluating the continued fractions in my previous answer yields the equivalent of @LegionMammal978 s Mathematic answer, which I think is the naive optimum. Doing better than this will require getting creative with representing the integers, possibly including searching for sub-optimal fractions to get to easier-to-represent integers.

from fractions import *
def simplify(numstr):
    frac = Fraction(numstr)
    terms = []
    while frac>0:
        terms.append(int(frac))
        frac -= int(frac)
        if frac > 0:
            frac = 1/frac
    for n in range(0,len(terms)):
        temp = Fraction(0)
        for i in range(n,0,-1):
            temp = Fraction(1)/Fraction(terms[i]+temp)
            # print i, terms[i], temp
        temp += terms[0]
        if repr(float(temp))[:len(numstr)] == numstr:
            break
    return str(temp.numerator) + '/' + str(temp.denominator)

examples:

141.352770092 == 1992650/14097
501.454292251 == 5041120/10053
792.956685991 == 33373961/42088
709.053823609 == 154592878/218027