Rosetta Code

Fractran: Difference between revisions

Page Discussion

Fractran (view source)

Revision as of 21:45, 14 January 2024

6,698 bytes added ,  4 months ago
Adding C#.
imported>JacobNoel
(Adding C#.)
 
(7 intermediate revisions by 5 users not shown)
Line 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 2,089 ⟶ 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,722 ⟶ 2,969:
 
using .Iterators: filter, map, take
import Base: iterate, show
 
struct Fractran
rs::Vector{Rational{BigInt}}
i₀::BigInt
limit::Int
end
 
Base.iterate(f::Fractran, i = f.i₀) =
for r in f.rs
if iszero(i % r.den) # faster than isinteger(i*r)
i = i ÷ r.den * r.num
return (i, i)
end
end
 
runinterpret(f::Fractran) = map(trailing_zeros, filter(ispow2, f))
take(
map(trailing_zeros,
filter(ispow2, f))
f.limit)
 
Base.show(io::IO, f::Fractran) = join(io, take(run(f), 30), ' ')
join(io, interpret(f), ' ')
 
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)
 
# Output
Line 2,921 ⟶ 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,940 ⟶ 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 4,028 ⟶ 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,548 ⟶ 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/343728...352282"