Anonymous user
Fractran: Difference between revisions
→{{header|Nim}}
Line 2,553:
# Run the program to compute primes displaying values at each step and stopping after 10 steps.
echo "
PrimeProg.run(2, 10)
# Find the first 20 primes.
echo "\
for val in primes(20):
echo val
Line 2,564:
{{out}}
<pre>
1: 15
2: 825
Line 2,576:
10: 770
2
3
Line 2,597:
67
71
</pre>
===Using decomposition in prime factors===
With this algorithm, we no longer need big numbers. To avoid overflow, value at each step is displayed using
its decomposition in prime factors.
<lang Nim>
import algorithm
import sequtils
import strutils
import tables
const PrimeProg = "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"
type
Fraction = tuple[num, denom: int]
Factors = Table[int, int]
FractranProg = object
primes: seq[int]
nums, denoms: seq[Factors]
exponents: seq[int] # Could also use a CountTable.
iterator fractions(fractString: string): Fraction =
## Extract fractions from a string and yield them.
for f in fractString.split():
let fields = f.strip().split('/')
assert fields.len == 2
yield (fields[0].parseInt(), fields[1].parseInt())
iterator factors(val: int): tuple[val, exp: int] =
## Extract factors from a positive integer.
# Extract factor 2.
var val = val
var exp = 0
while (val and 1) == 0:
inc exp
val = val shr 1
if exp != 0:
yield (2, exp)
# Extract odd factors.
var d = 3
while d <= val:
exp = 0
while val mod d == 0:
inc exp
val = val div d
if exp != 0:
yield (d, exp)
inc d, 2
func newProg(fractString: string; init: int): FractranProg =
## Initialize a Fractran program.
for f in fractString.fractions():
# Extract numerators factors.
var facts: Factors
for (val, exp) in f.num.factors():
result.primes.add(val)
facts[val] = exp
result.nums.add(facts)
# Extract denominator factors.
facts.clear()
for (val, exp) in f.denom.factors():
result.primes.add(val)
facts[val] = exp
result.denoms.add(facts)
# Finalize list of primes.
result.primes.sort()
result.primes = result.primes.deduplicate(true)
# Allocate and initialize exponent sequence.
result.exponents.setLen(result.primes[^1] + 1)
for (val, exp) in init.factors():
result.exponents[val] = exp
func doOneStep(prog: var FractranProg): bool =
## Execute one step of the program.
for idx, factor in prog.denoms:
block tryFraction:
for val, exp in factor.pairs():
if prog.exponents[val] < exp:
# Not a multiple of the denominator.
break tryFraction
# Divide by the denominator.
for val, exp in factor.pairs():
dec prog.exponents[val], exp
# Multiply by the numerator.
for val, exp in prog.nums[idx]:
inc prog.exponents[val], exp
return true
func `$`(prog: FractranProg): string =
## Display a value as a product of prime factors.
for val, exp in prog.exponents:
if exp != 0:
if result.len > 0:
result.add('.')
result.add($val)
if exp > 1:
result.add('^')
result.add($exp)
proc run(fractString: string; init: int; maxSteps = 0) =
## Run a Fractran program.
var prog = newProg(fractString, init)
var stepCount = 0
while stepCount < maxSteps:
if not prog.doOneStep():
echo "*** No more possible fraction. Program stopped."
return
inc stepCount
echo stepCount, ": ", prog
proc findPrimes(maxCount: int) =
## Search and print primes.
var prog = newProg(PrimeProg, 2)
let oddPrimes = prog.primes[1..^1]
var primeCount = 0
while primeCount < maxCount:
discard prog.doOneStep()
block powerOf2:
if prog.exponents[2] > 0:
for p in oddPrimes:
if prog.exponents[p] != 0:
# Not a power of 2.
break powerOf2
inc primeCount
echo primeCount, ": ", prog.exponents[2]
#------------------------------------------------------------------------------
echo "First ten steps for program to find primes:"
run(PrimeProg, 2, 10)
echo "\nFirst twenty prime numbers:"
findPrimes(20)
</lang>
{{out}}
<pre>
First ten steps for program to find primes:
1: 3.5
2: 3.5^2.11
3: 5^2.29
4: 5^2.7.11
5: 5^2.7.13
6: 5^2.17
7: 2.3.5.13
8: 2.3.5.11
9: 2.5.29
10: 2.5.7.11
First twenty prime numbers:
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>
| |||