Boustrophedon transform: Difference between revisions
Added FreeBASIC
(→{{header|Perl}}: use vecsum from ntheory (~4x faster) (Math::AnyNum::sum() would be even faster)) |
(Added FreeBASIC) |
||
| (5 intermediate revisions by 3 users not shown) | |||
Line 245:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
</pre>
=={{header|EasyLang}}==
<syntaxhighlight>
cache[][] = [ ]
a[] = [ ]
#
func T k n .
if n = 1
return a[k]
.
if cache[k][n] = 0
cache[k][n] = T k (n - 1) + T (k - 1) (k - n + 1)
.
return cache[k][n]
.
#
proc boustrophedon . .
k = len a[]
cache[][] = [ ]
len cache[][] k
for i to k
len cache[i][] k
.
b[] &= a[1]
for n = 2 to k
b[] &= T n n
.
print b[]
.
len a[] 15
print "1 followed by 0's:"
a[1] = 1
boustrophedon
#
print "\nAll 1's:"
proc mkall1 n . a[] .
a[] = [ ]
while len a[] <> n
a[] &= 1
.
.
mkall1 15 a[]
boustrophedon
#
print "\nAlternating 1, -1"
proc mkalt n . a[] .
a[] = [ ]
h = 1
while len a[] <> n
a[] &= h
h *= -1
.
.
mkalt 15 a[]
boustrophedon
#
print "\nPrimes:"
func isprim num .
i = 2
while i <= sqrt num
if num mod i = 0
return 0
.
i += 1
.
return 1
.
proc mkprimes n . a[] .
a[] = [ ]
i = 2
while len a[] <> n
if isprim i = 1
a[] &= i
.
i += 1
.
.
mkprimes 15 a[]
boustrophedon
#
print "\nFibonacci numbers:"
proc mkfibon n . a[] .
a[] = [ 1 ]
val = 1
while len a[] <> n
h = prev + val
prev = val
val = h
a[] &= val
.
.
mkfibon 15 a[]
boustrophedon
print "\nFactorials:"
proc mkfact n . a[] .
a[] = [ ]
f = 1
while len a[] <> n
a[] &= f
f *= len a[]
.
.
mkfact 15 a[]
boustrophedon
</syntaxhighlight>
{{out}}
<pre>
1 followed by 0's:
[ 1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981 ]
All 1's:
[ 1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574 ]
Alternating 1, -1
[ 1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530 ]
Primes:
[ 2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691 ]
Fibonacci numbers:
[ 1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189 ]
Factorials:
[ 1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547 ]
</pre>
=={{header|FreeBASIC}}==
===Basic===
{{trans|Wren}}
<syntaxhighlight lang="vbnet">Function T(Byval k As Integer, Byval n As Integer, a() As Integer, cache() As Integer) As Integer
If n = 0 Then
Return a(k)
Elseif cache(k * Ubound(a) + n) <> 0 Then
Return cache(k * Ubound(a) + n)
Else
cache(k * Ubound(a) + n) = T(k, n - 1, a(), cache()) + T(k - 1, k - n, a(), cache())
Return cache(k * Ubound(a) + n)
End If
End Function
Sub Boustrophedon(a() As Integer)
Dim As Integer k = Ubound(a)
Dim As Integer cache(k * k + k)
Dim As Integer b(k)
b(0) = a(0)
For n As Integer = 1 To k
b(n) = T(n, n, a(), cache())
Next
Print "[";
For n As Integer = 0 To k
Print b(n); ",";
Next
Print Chr(8); !" ]\n"
End Sub
Dim As Integer i
Print "1 followed by 0's:"
Dim As Integer a0(14) = {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Boustrophedon(a0())
Print "All 1's:"
Dim As Integer a1(14) = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Boustrophedon(a1())
Print "Alternating 1, -1:"
Dim As Integer a2(14)
For i = 0 To 14
a2(i) = Iif((i\2 = i/2), 1, -1)
Next i
Boustrophedon(a2())
Print "Primes:"
Sub primeSieve(n As Integer, primes() As Integer)
Redim primes(n - 1)
Dim As Integer j, i = 2, count = 0
While count < n
j = 2
While j <= i \ 2
If i Mod j = 0 Then Exit While
j += 1
Wend
If j > i \ 2 Then
primes(count) = i
count += 1
End If
i += 1
Wend
End Sub
Dim As Integer a3(14)
primeSieve(15, a3())
Boustrophedon(a3())
Print "Fibonacci numbers:"
Dim As Integer a4(14)
a4(0) = 1 ' start from fib(1)
a4(1) = 1
For i = 2 To 14
a4(i) = a4(i-1) + a4(i-2)
Next i
Boustrophedon(a4())
Print "Factorials:"
Dim As Integer a5(14)
a5(0) = 1
For i = 1 To 14
a5(i) = a5(i-1) * i
Next i
Boustrophedon(a5())
Sleep</syntaxhighlight>
{{out}}
<pre>1 followed by 0's:
[ 1, 1, 1, 2, 5, 16, 61, 272, 1385, 7936, 50521, 353792, 2702765, 22368256, 199360981 ]
All 1's:
[ 1, 2, 4, 9, 24, 77, 294, 1309, 6664, 38177, 243034, 1701909, 13001604, 107601977, 959021574 ]
Alternating 1, -1:
[ 1, 0, 0, 1, 0, 5, 10, 61, 280, 1665, 10470, 73621, 561660, 4650425, 41441530 ]
Primes:
[ 2, 5, 13, 35, 103, 345, 1325, 5911, 30067, 172237, 1096319, 7677155, 58648421, 485377457, 4326008691 ]
Fibonacci numbers:
[ 1, 2, 5, 14, 42, 144, 563, 2526, 12877, 73778, 469616, 3288428, 25121097, 207902202, 1852961189 ]
Factorials:
[ 1, 2, 5, 17, 73, 381, 2347, 16701, 134993, 1222873, 12279251, 135425553, 1627809401, 21183890469, 296773827547 ]</pre>
=={{header|F_Sharp|F#}}==
Line 288 ⟶ 519:
13250869953362054385 ... 82450325540640498987 (2371 digits)
</pre>
=={{header|J}}==
Implementation:<syntaxhighlight lang=J>b=: {{
Line 477 ⟶ 709:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
1,000th element: 13714256926920345740 ... 19230014799151339821 (2566 digits)
</pre>
=={{header|jq}}==
'''Works with gojq, the Go implementation of jq'''
'''Works with jq, the C implementation of jq, within the limits of IEEE 764 arithmetic'''
'''Adapted from [[#Wren|Wren]]'''
The results for the "stretch" tasks are based on the use of gojq.
<syntaxhighlight lang="jq">
### Generic functions
# The stream of Fibonacci numbers beginning with 1, 1, 2, ...
def fibs:
def f: [0,1] | recurse( [.[1], add] );
f | .[1];
# The stream of factorials beginning with 1, 1, 2, 6, 24, ...
def factorials:
def f: recurse( [.[0] + 1, .[0] * .[1]] );
[1, 1] | f | .[1];
# An array of length specified by .
def array($value): [range(0; .) | $value];
# Give a glimpse of the (very large) input number
def glimpse:
tostring
| "\(.[:20]) ... \(.[-20:]) \(length) digits";
### The Boustrophedon transform
def boustrophedon($a):
($a|length) as $k
| ($k | array(0)) as $list
| {b: $list,
cache: [] }
# input: {cache}, output: {result, cache}
| def T($k; $n):
if $n == 0 then .result = $a[$k]
else .cache[$k][$n] as $kn
| if $kn > 0 then .result = $kn
else T($k; $n-1)
| .result as $r
| T($k-1; $k-$n)
| .result = $r + .result
| .cache[$k][$n] = .result
end
end;
.b[0] = $a[0]
| reduce range(1; $k) as $n (.; T($n; $n) | .b[$n] = .result )
| .b;
### Exercises
"1 followed by 0's:",
boustrophedon( [1] + (14 | array(0)) ),
"\nAll 1's:",
boustrophedon(15|array(1)),
"\nAlternating 1, -1",
boustrophedon( [range(0;7) | 1, -1] + [1] ),
"\nPrimes:",
boustrophedon([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]),
"\nFibonacci numbers:",
boustrophedon([limit(15; fibs)]),
"\nFactorials:",
boustrophedon([limit(15; factorials)]),
## Stretch tasks require gojq
"\nGlimpse of 1000th element for the Fibonaccis",
(boustrophedon([limit(1000; fibs)]) | .[999] | glimpse),
"\nGlimpse of 1000th element for the factorials:",
(boustrophedon([limit(1000; factorials)]) | .[999] | glimpse)
</syntaxhighlight>
{{output}}
<pre>
1 followed by 0's:
[1,1,1,2,5,16,61,272,1385,7936,50521,353792,2702765,22368256,199360981]
All 1's:
[1,2,4,9,24,77,294,1309,6664,38177,243034,1701909,13001604,107601977,959021574]
Alternating 1, -1
[1,0,0,1,0,5,10,61,280,1665,10470,73621,561660,4650425,41441530]
Primes:
[2,5,13,35,103,345,1325,5911,30067,172237,1096319,7677155,58648421,485377457,4326008691]
Fibonacci numbers:
[1,2,5,14,42,144,563,2526,12877,73778,469616,3288428,25121097,207902202,1852961189]
Factorials:
[1,2,5,17,73,381,2347,16701,134993,1222873,12279251,135425553,1627809401,21183890469,296773827547]
Glimpse of the 1000th element for the Fibonaccis:
56757474139659741321 ... 66135597559209657242 2370 digits
Glimpse of 1000th element for the factorials:
13714256926920345740 ... 19230014799151339821 2566 digits
</pre>
Line 976 ⟶ 1,314:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
1000th term: 13714256926920345740…19230014799151339821 (2566 digits)</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">func boustrophedon_transform(seq) {
func T(k,n) is cached {
return seq[k] if (n == 0)
T(k, n-1) + T(k-1, k-n)
}
var bt = seq.range.map {|n| T(n,n) }
T.uncache
return bt
}
const N = 100 # n terms
[
'1 followed by 0\'s A000111', Math.seq(1,{0}),
'All-1\'s A000667', Math.seq({1}),
'(-1)^n A062162', Math.seq({|_,k| (-1)**(k+1) }),
'Primes A000747', Math.seq(2,{ .tail.next_prime }),
'Fibbonaccis A000744', Math.seq(1,1,{ .last(2).sum }),
'Factorials A230960', Math.seq(1,{|a,k| a.last * (k-1) }),
].each_slice(2, {|name, seq|
var bt = boustrophedon_transform(seq.first(N))
say "\n#{name}:\n#{bt.first(15).join(' ')}"
var v = bt[N-1]
say ("#{N}th term: ", Str(v).first(20), '..', Str(v).last(20), " (%s digits)" % v.len)
})</syntaxhighlight>
{{out}}
<pre>
1 followed by 0's A000111:
1 1 1 2 5 16 61 272 1385 7936 50521 353792 2702765 22368256 199360981
100th term: 45608516616801111821..68991870306963423232 (137 digits)
All-1's A000667:
1 2 4 9 24 77 294 1309 6664 38177 243034 1701909 13001604 107601977 959021574
100th term: 21939873756450413339..30507739683220525509 (138 digits)
(-1)^n A062162:
1 0 0 1 0 5 10 61 280 1665 10470 73621 561660 4650425 41441530
100th term: 94810791122872999361..65519440121851711941 (136 digits)
Primes A000747:
2 5 13 35 103 345 1325 5911 30067 172237 1096319 7677155 58648421 485377457 4326008691
100th term: 98967625721691921699..78027927576425134967 (138 digits)
Fibbonaccis A000744:
1 2 5 14 42 144 563 2526 12877 73778 469616 3288428 25121097 207902202 1852961189
100th term: 42390820205259437020..42168748587048986542 (138 digits)
Factorials A230960:
1 2 5 17 73 381 2347 16701 134993 1222873 12279251 135425553 1627809401 21183890469 296773827547
100th term: 31807659526053444023..65546706672657314921 (157 digits)
</pre>
=={{header|Wren}}==
| |||