Boustrophedon transform: Difference between revisions

Content added Content deleted

Inline

@@ Line 480: / Line 480: @@
 =={{header|jq}}==
-{{Works with|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
@@ Line 500: / Line 502: @@
 # 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
@@ Line 506: / Line 513: @@
   | ($k | array(0)) as $list
   | {b: $list,
-     cache: [range(0;$k) | $list] }
+     cache: [] }
-  | .b[0] = $a[0]
-  # input {b, cache}
+  # input: {cache}, output: {result, cache}
   | def T($k; $n):
       if $n == 0 then .result = $a[k]
-      elif .cache[$k][$n] > 0 then .result = .cache[$k][$n]
+      else .cache[$k][$n] as $kn
-      else T($k; $n-1)
+      | if $kn > 0 then .result = $kn
-      | .result as $r1
+        else T($k; $n-1)
-      | T($k-1; $k-$n)
+        | .result as $r
-      | ($r1 + .result) as $r
+        | T($k-1; $k-$n)
-      | .cache[$k][$n] = $r
+        | .result = $r + .result
-      | .result = $r
+        | .cache[$k][$n] = .result
+        end
       end;
+  .b[0] = $a[0]
-  reduce range(1; $k) as $n (.; .b[$n] = (T($n; $n) | .result))
+  | reduce range(1; $k) as $n (.; T($n; $n) | .b[$n] = .result )
-  | .b ;
+  | .b;
 ### Exercises
@@ Line 541: / Line 549: @@
 "\nFactorials:",
-  boustrophedon([limit(15; factorials)])
+  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}}
@@ Line 562: / Line 577: @@
 Factorials:
 [1,2,5,17,73,381,2347,16701,134993,1222873,12279251,135425553,1627809401,21183890469,296773827547]
-</pre>
+Glimpse of the 1000th element for the Fibonaccis:
+56757474139659741321 ... 66135597559209657242 2370 digits
+Glimpse of 1000th element for the factorials:
+13714256926920345740 ... 19230014799151339821 2566 digits
+</pre>
 =={{header|Julia}}==