Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <h1>Fractran - 1779 fractions</h1> <p><strong>(Edit: fixed)</strong></p> <p>(I hope people are still following this thread, because this took a while!)</p> <p>It appears SO won't let me post something as long as this, so I posted the Fractran source <a href="http://www.math.uiuc.edu/~beder/interpreter.fr" rel="noreferrer">here</a>.</p> <p>Input is specified as follows:</p> <p>First, we encode a fraction <code>m/n = p_0^a0... p_k^ak</code> by:</p> <ul> <li>Start with 1. Then, for each <code>ai</code>:</li> <li>Multiply by <code>p_2i^ai</code> if <code>ai &gt; 0</code></li> <li>Multiply by <code>p_2i+1^{-ai}</code> if <code>a_i &lt; 0</code></li> </ul> <p>This way, we encode any fraction as a positive integer. Now, given a progoram (sequence of encoded fractions F0, F1, ...), we encode that by</p> <pre><code>p_0^F0 p1^F1 ... </code></pre> <p>Finally, input to the interpreter is given by:</p> <pre><code>2^(program) 3^(input) 5 </code></pre> <p>where <code>program</code> and <code>input</code> are encoded as above. For example, in the first test problem, <code>3/2</code> gets encoded to <code>15</code>, so the program gets encoded to <code>2^15</code>; and <code>108</code> gets encoded to <code>500</code>. So, we pass</p> <pre><code>2^{2^15} 3^500 5 </code></pre> <p>to the program. The output, then is of the form</p> <pre><code>2^(program) 3^(output) </code></pre> <p>so in the first example, it'll be</p> <pre><code>2^{2^15} 3^3125 </code></pre> <hr/> <h2>How does it work?</h2> <p>I wrote a meta-language that compiles down to Fractran. It allows for functions (simple Fractran and sequences of other functions), and a <code>while</code> loop and <code>if</code> statement (for convenience!). The code for that can be found <a href="http://www.math.uiuc.edu/~beder/interpreter.frp" rel="noreferrer">here</a>.</p> <p>If you want to compile that code down to Fractran yourself, my (C++) program can be found <a href="http://www.math.uiuc.edu/~beder/fracc.tar.gz" rel="noreferrer">here</a> [tar.gz]. In a stunning display of dogfooding (and showing off), I used my C++ YAML parser <a href="http://code.google.com/p/yaml-cpp/" rel="noreferrer">yaml-cpp</a>, so you'd have to download and link with that. For both yaml-cpp and the "compiler", you'll need <a href="http://www.cmake.org" rel="noreferrer">CMake</a> for cross-platform makefile generating.</p> <p>The usage of this program is:</p> <pre><code>./fracc interpreter.frp </code></pre> <p>The it reads the name of a function from standard input, and writes the corresponding "pseudo-Fraction" (I'll explain that in a second) to standard output. So to compile the interpreter (the Interpret function), you could run</p> <pre><code>echo "Interpret" | ./fracc interpreter.frp &gt; interpret </code></pre> <p>The output ("pseudo-Fractran") will be a sequence of lines, each with a string of space-separated digits. A line corresponds to a fraction: if the <code>n</code>th digit in the line is <code>an</code>, then the fraction is the product of <code>p_n^an</code>.</p> <p>It's very easy to convert this to Fractran, but if you're lazy, you can use <a href="http://www.math.uiuc.edu/~beder/to-fractions.py" rel="noreferrer">to-fractions.py</a>. [<strong>Note</strong>: earlier I had a C++ program, and I had carelessly ignored integer overflow. I translated it to Python to avoid this.]</p> <p><strong>Note about input</strong>: if you want to test out a different function this way, the convention is always the same. It has a number of parameters (usually the comment above the function explains this) in pseudo-Fractran, so give it what it wants, plus a <code>1</code> on the very next slot (so in ordinary Fractran, multiply once by the first prime that it won't use). This is a "signal" bit to the function to start going.</p> <hr/> <h2>However,</h2> <p>I don't recommend actually trying to run the Fractran interpreter (alas). I tested many of its components, and, for example, the function <code>IncrementPrimes</code>, which takes a pair of primes and returns the next two primes, takes about <strong>8 minutes</strong> to run, using my silly C++ interpreter (no need to post that :). Plus, it goes (at least) quadratically in the number of function calls - doubling the number of function calls makes it take at least four times as long (more if there are <code>while</code> loops or <code>if</code> statements). So I'm guessing that running the interpreter will take at least days, if not years :(</p> <p>So how do I know it works? Well, of course I'm not 100% certain, but I'm pretty close. First of all, I tested many, many of its components, and in particular, I tested all of the elements of the meta-language (sequences of functions and <code>if</code> and <code>while</code> statements) very thoroughly.</p> <p>Also, the meta-language is easy to translate into your favorite language, and even easier to translate to C++, since all parameters of functions are passed by reference. If you're feeling lazy again, you can download my translation <a href="http://www.math.uiuc.edu/~beder/interpreter-cpp.tar.gz" rel="noreferrer">here</a> [tar.gz] (there's no makefile; it's just two .cpp files, so directly calling gcc is fine).</p> <p>So you can compare the two interpreters, run the C++ version (it also takes input/output in pseudo-Fractran), check that that works, and then convince yourself that the meta-language works too.</p> <hr/> <h2>Or!</h2> <p>If you're feeling inspired, and <em>really</em> want to see this interpreter interpreted, you can write a "clever" Fractran interpreter based around the type of Fractran output that we get. The output is very structured - sequences of functions are implemented using signals, so if you somehow cache where the interpreter was, you could jump there immediately if nothing important changed. This, I think, would dramatically speed up the program (perhaps cutting down running time by one or more powers).</p> <p>But, I'm not really sure how to do this, and I'm happy with what's done, so I'll leave it as an exercise for the reader.</p>
    singulars
    1. This table or related slice is empty.
    1. POCode Golf: Fractran
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJesse Beder
    1. USJesse Beder
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POCode Golf: Fractran
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhoa. Really impressive. Still trying to get the test vector to run - if it does, you get 500 points. ;) What did you use to compile the meta-language down to fractran statements?
      singulars
      1. PO
      1. USNick Johnson
    2. COSo, using Useless's Python implementation, with the test vector you suggest, the output I get is not the expected output: data = (2**(2**15))*(3**500)*5; output = f(data, program); expected = (2**(2**15))*(3**3125) # output != expected and output % expected != 0. What's wrong?
      singulars
      1. PO
      1. USNick Johnson
    3. COHmmm... see my latest update - I didn't expect it to actually finish (it doesn't with my C++ interpreter). How long did it take? Also, what's the actual output it gives?
      singulars
      1. PO
      1. USJesse Beder
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload