Rosetta Code

Fractran: Difference between revisions

Page Discussion

Fractran (view source)

Revision as of 21:45, 14 January 2024

11,527 bytes added ,  4 months ago
Adding C#.
imported>JacobNoel
(Adding C#.)
 
(14 intermediate revisions by 6 users not shown)
Line 284:
507519 71 (2361183241434822606848)
</pre>
 
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">fractran←{
parts ← ' '∘≠⊆⊢
frac ← ⍎¨'/'∘≠⊆⊢
simp ← ⊢÷∨/
mul ← simp×
prog ← simp∘frac¨parts ⍺
step ← {⊃⊃(1=2⊃¨next)/next←⍺ mul¨⊂(⍵ 1)}
(start nstep)←⍵
rslt ← ⊃(⊢,⍨prog∘step∘⊃)⍣nstep¨start
⌽(⊢(/⍨)(∨\0∘≠))rslt
}</syntaxhighlight>
{{out}}
<syntaxhighlight lang="apl"> '17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1' fractran 2 20
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30</syntaxhighlight>
 
=={{header|AutoHotkey}}==
Line 674 ⟶ 691:
return 0;
}</syntaxhighlight>
 
=={{header|C sharp|C#}}==
The use of <code> using Fractype = (BigInteger numerator, BigInteger denominator);</code> requires C# 12.0.
 
 
<syntaxhighlight lang="csharp">
namespace System.Numerics
{
using Fractype = (BigInteger numerator, BigInteger denominator);
struct Quotient
{
private Fractype _frac;
public Fractype Fraction
{
get => _frac;
set => _frac = Reduce(value);
}
 
public bool IsIntegral => _frac.denominator == 1;
 
public Quotient(BigInteger num, BigInteger den)
{
Fraction = (num, den);
}
 
public static BigInteger GCD(BigInteger a, BigInteger b)
{
return (b == 0) ? a : GCD(b, a % b);
}
 
private static Fractype Reduce(Fractype f)
{
if (f.denominator == 0)
throw new DivideByZeroException();
 
BigInteger gcd = Quotient.GCD(f.numerator, f.denominator);
return (f.numerator / gcd, f.denominator / gcd);
}
 
public static Quotient operator *(Quotient a, Quotient b)
=> new Quotient(a._frac.numerator * b._frac.numerator, a._frac.denominator * b._frac.denominator);
 
public static Quotient operator *(Quotient a, BigInteger n)
=> new Quotient(a._frac.numerator * n, a._frac.denominator);
 
public static explicit operator Quotient(Fractype t) => new Quotient(t.numerator, t.denominator);
}
 
class FRACTRAN
{
private Quotient[] code;
public FRACTRAN(Fractype[] _code)
{
code = _code.Select(x => (Quotient) x).ToArray();
}
 
public (BigInteger value, bool success) Compute(BigInteger n)
{
for (int i = 0; i < code.Length; i++)
if ((code[i] * n).IsIntegral)
return ((code[i] * n).Fraction.numerator, true);
return (0, false);
}
}
 
class Program
{
public static void Main(string[] args)
{
Fractype[] frac_code = args[0].Split(" ")
.Select(x => ((BigInteger)Int32.Parse(x.Split("/")[0]), (BigInteger)Int32.Parse(x.Split("/")[1].Trim(',')))).ToArray();
BigInteger init = new BigInteger(Int32.Parse(args[1].Trim(',')));
int steps = Int32.Parse(args[2].Trim(','));
FRACTRAN FRACGAME = new FRACTRAN(frac_code);
 
List<BigInteger> sequence = new List<BigInteger>();
sequence.Add(init);
bool halt = false;
for (int i = 0; i < steps - 1; i++)
{
var k = FRACGAME.Compute(sequence[sequence.Count - 1]);
if (k.success)
sequence.Add(k.value);
else
{
halt = true;
break;
}
}
 
for (int i = 0; i < sequence.Count; i++)
Console.WriteLine((i + 1).ToString() + ": " + sequence[i]);
if (halt)
Console.WriteLine("HALT");
}
}
}
</syntaxhighlight>
 
Input:
 
<code> "17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1", 2, 15 </code>
 
Output:
 
<pre>
1: 2
2: 15
3: 825
4: 725
5: 1925
6: 2275
7: 425
8: 390
9: 330
10: 290
11: 770
12: 910
13: 170
14: 156
15: 132
</pre>
 
Moreover, modifying the class <code>Program</code> to,
 
<syntaxhighlight lang="csharp">
 
class Program
{
private static bool PowerOfTwo(BigInteger b)
{
while (b % 2 == 0)
b /= 2;
return b == 1;
}
 
private static BigInteger BigLog2(BigInteger b)
{
BigInteger r = 0;
while (b > 1)
{
r++;
b /= 2;
}
return r;
}
public static void Main(string[] args)
{
Fractype[] frac_code = args[0].Split(" ")
.Select(x => ((BigInteger)Int32.Parse(x.Split("/")[0]), (BigInteger)Int32.Parse(x.Split("/")[1].Trim(',')))).ToArray();
BigInteger init = new BigInteger(Int32.Parse(args[1].Trim(',')));
int steps = Int32.Parse(args[2].Trim(','));
FRACTRAN FRACGAME = new FRACTRAN(frac_code);
 
List<BigInteger> sequence = new List<BigInteger>();
List<BigInteger> primes = new List<BigInteger>();
sequence.Add(init);
bool halt = false;
while (primes.Count() < 20)
{
var k = FRACGAME.Compute(sequence[sequence.Count - 1]);
if (k.success)
sequence.Add(k.value);
else
{
halt = true;
break;
}
if (PowerOfTwo(k.value))
primes.Add(BigLog2(k.value));
}
 
for (int i = 0; i < primes.Count; i++)
Console.WriteLine((i + 1).ToString() + ": " + primes[i]);
if (halt)
Console.WriteLine("HALT");
}
}
 
</syntaxhighlight>
 
with the same input, will print the first 20 primes.
 
<pre>
1: 2
2: 3
3: 5
4: 7
5: 11
6: 13
7: 17
8: 19
9: 23
10: 29
11: 31
12: 37
13: 41
14: 43
15: 47
16: 53
17: 59
18: 61
19: 67
20: 71
</pre>
 
=={{header|C++}}==
Line 761 ⟶ 987:
14 : 132
</pre>
 
=={{header|CLU}}==
<syntaxhighlight lang="clu">ratio = cluster is new, parse, unparse, get_num, get_denom, mul
rep = struct[num, denom: int]
new = proc (num, denom: int) returns (cvt)
return(simplify(rep${num: num, denom: denom}))
end new
parse = proc (rat: string) returns (ratio) signals (bad_format)
rat := trim(rat)
sep: int := string$indexc('/', rat)
if sep = 0 then signal bad_format end
num: string := string$substr(rat, 1, sep-1)
denom: string := string$rest(rat, sep+1)
return(new(int$parse(num), int$parse(denom))) resignal bad_format
end parse
trim = proc (s: string) returns (string)
start: int := 1
while start <= string$size(s) cand s[start] = ' ' do start := start + 1 end
end_: int := string$size(s)
while end_ >= 1 cand s[end_] = ' ' do end_ := end_ - 1 end
return(string$substr(s, start, end_-start+1))
end trim
unparse = proc (rat: cvt) returns (string)
return(int$unparse(rat.num) || "/" || int$unparse(rat.denom))
end unparse
get_num = proc (rat: cvt) returns (int)
return(rat.num)
end get_num
get_denom = proc (rat: cvt) returns (int)
return(rat.denom)
end get_denom
mul = proc (a, b: cvt) returns (ratio)
return(new(a.num * b.num, a.denom * b.denom))
end mul
simplify = proc (rat: rep) returns (rep)
num: int := int$abs(rat.num)
denom: int := int$abs(rat.denom)
sign: int
if (rat.num < 0) = (rat.denom < 0)
then sign := 1
else sign := -1
end
factor: int := gcd(num, denom)
return(rep${num: sign*num/factor, denom: denom/factor})
end simplify
gcd = proc (a, b: int) returns (int)
while b ~= 0 do
a, b := b, a // b
end
return(a)
end gcd
end ratio
 
fractran = cluster is parse, run
rep = sequence[ratio]
parse = proc (program: string) returns (cvt)
parsed: array[ratio] := array[ratio]$[]
for rat: ratio in ratioes(program) do
array[ratio]$addh(parsed, rat)
end
return(rep$a2s(parsed))
end parse
 
ratioes = iter (program: string) yields (ratio)
while true do
sep: int := string$indexc(',', program)
if sep = 0 then
yield(ratio$parse(program))
break
else
yield(ratio$parse(string$substr(program, 1, sep-1)))
program := string$rest(program, sep+1)
end
end
end ratioes
run = iter (program: cvt, n, maxiter: int) yields (int)
nrat: ratio := ratio$new(n, 1)
while maxiter > 0 do
yield(nrat.num)
begin
for rat: ratio in rep$elements(program) do
mul: ratio := rat * nrat
if mul.denom = 1 then
exit found(mul)
end
end
break
end except when found(new: ratio):
nrat := new
end
maxiter := maxiter - 1
end
end run
end fractran
 
start_up = proc ()
po: stream := stream$primary_output()
program: string := "17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, "
|| "77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1"
parsed: fractran := fractran$parse(program)
index: int := 0
for result: int in fractran$run(parsed, 2, 20) do
stream$putright(po, int$unparse(index), 3)
stream$putc(po, ':')
stream$putright(po, int$unparse(result), 10)
stream$putl(po, "")
index := index + 1
end
end start_up</syntaxhighlight>
{{out}}
<pre> 0: 2
1: 15
2: 825
3: 725
4: 1925
5: 2275
6: 425
7: 390
8: 330
9: 290
10: 770
11: 910
12: 170
13: 156
14: 132
15: 116
16: 308
17: 364
18: 68
19: 4</pre>
 
=={{header|Common Lisp}}==
Line 1,925 ⟶ 2,298:
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/FRACTRAN}}
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
 
[[File:Fōrmulæ - FRACTRAN 01.png]]
 
It is a function that accepts the program to run (as a list), the initial value of n and the number of values to generate.
 
It uses a local nested function next() that calculates the next value of . If it can be calculated, it is added to a result array and return true, elsewhere return false.
 
The main work is to iterate while the next() returns true and the number of values to generate is not reached.
 
The following is the call with the program for primes, initial n value of 2, and returning 20 values:
 
[[File:Fōrmulæ - FRACTRAN 02.png]]
 
[[File:Fōrmulæ - FRACTRAN 03.png]]
 
'''Bonus''' using the previous FRACTAN program to generate the first 20 primes.
 
It requires a modification to the previous program.
 
[[File:Fōrmulæ - FRACTRAN 04.png]]
 
[[File:Fōrmulæ - FRACTRAN 05.png]]
 
[[File:Fōrmulæ - FRACTRAN 06.png]]
 
'''FRACTRAN program for addition'''
 
[[File:Fōrmulæ - FRACTRAN 07.png]]
 
[[File:Fōrmulæ - FRACTRAN 08.png]]
 
[[File:Fōrmulæ - FRACTRAN 09.png]]
 
'''FRACTRAN program for multiplication'''
 
[[File:Fōrmulæ - FRACTRAN 10.png]]
 
[[File:Fōrmulæ - FRACTRAN 11.png]]
 
[[File:Fōrmulæ - FRACTRAN 12.png]]
In '''[https://formulae.org/?example=FRACTRAN this]''' page you can see the program(s) related to this task and their results.
 
=={{header|Go}}==
Line 2,555 ⟶ 2,966:
=={{header|Julia}}==
{{works with|Julia|1.9}}<syntaxhighlight lang="julia">
# FRACTRAN interpreter implemented as an Iteratoriterable struct
 
using .Iterators: filter, map, take
 
struct Fractran
fracsrs::Vector{Rational{BigInt}}
inputi₀::BigInt
maxoutlimit::Int
end
 
function Base.iterate(ftf::Fractran, i = ftf.inputi₀) =
for fracr ∈in ftf.fracsrs
r =if iszero(i *% fracr.den)
isone(r.den) && return ( i = i ÷ r.num,den * r.num)
return i, i
end
end
end
 
function evalinterpret(ftf::Fractran) =
take(
(Int(log2(i)) for i ∈ ft if ispow2(i))
map(trailing_zeros,
end
filter(ispow2, f))
f.limit)
 
function Base.show(io::IO, ftf::Fractran) =
join(io, Iterators.takeinterpret(eval(ft), ft.maxoutf), ' ')
end
 
macro code_str(s)
[eval(Meta.parse("[" * replace(st, "/" => "//"))) *for "t ∈ split(s)]"))
end
 
primes = Fractran(code"17/91 78/85 19/51 23/38 29/33 77/29 95/23
# Example FRACTRAN program generating primes
primes = Fractran(code"17 77/91,19 781/85,17 1911/51,13 2313/38,11 2915/33,14 7715/29,2 9555/231", 2, 30)
77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1", 2, 40)
 
# Output
println("First 25 iterations of FRACTRAN program 'primes':\n2 ",
join(Iterators.take(primes, 25), ' '))
 
println("\nWatch the first $(primes.maxout)30 primes dropping out within seconds:")
 
primes</syntaxhighlight>
Line 2,596 ⟶ 3,011:
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30 225 12375 10875 28875 25375
 
Watch the first 4030 primes dropping out within seconds:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173
</pre>
 
Line 2,757 ⟶ 3,172:
result.add(newRat(f))
 
proc run(progStr: string; init,: Natural; maxSteps: Natural = 0) =
## Run the program described by string "progStr" with initial value "init",
## stopping after "maxSteps" (0 means for ever).
Line 2,776 ⟶ 3,191:
if isZero(val and (val - 1)):
# This is a power of two.
yield val.digits(2).int - 1 # Compute the exponent as number of binary digits minus one.
inc count
if count == n:
Line 3,864 ⟶ 4,279:
</pre>
Output note: &nbsp; There are intermediary numbers (that aren't powers of two) that are hundreds of digits long. <br><br>
 
=={{header|RPL}}==
≪ → text
≪ "{'" 1 text SIZE '''FOR''' j
text j DUP SUB
'''IF''' DUP " " == '''THEN''' DROP "' '" '''END''' +
'''NEXT'''
"'}" + STR→
≫ ≫ '<span style="color:blue">PRECOMPIL</span>' STO <span style="color:grey">@ ( "fractions" → { 'fractions' } )</span>
≪ SWAP 20 → prog steps
≪ {} SWAP
1 steps '''FOR''' n
1 CF
1 prog SIZE '''FOR''' j
prog j GET OVER * EVAL RND
'''IF''' DUP FP '''THEN''' DROP '''ELSE'''
SWAP DROP SWAP OVER + SWAP
prog SIZE 'j' STO 1 SF '''END'''
'''NEXT'''
'''IF''' 1 FC?C '''THEN''' steps 'n' STO '''END'''
'''NEXT''' DROP
≫ ≫ '<span style="color:blue">RUN20</span>' STO <span style="color:grey">@ ( { 'fractions' } n → { results } )</span>
 
"17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1" <span style="color:blue">PRECOMPIL</span>
2 <span style="color:blue">RUN20</span>
{{out}}
<pre>
1: { 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30 }
</pre>
 
=={{header|Ruby}}==
Line 4,384 ⟶ 4,829:
{{libheader|Wren-big}}
Extra credit is glacially slow. We just find the first 10 primes which takes about 85 seconds.
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt, BigRat
 
var isPowerOfTwo = Fn.new { |bi| bi & (bi - BigInt.one) == BigInt.zero }
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/343073...352282"