Addition chains: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 26:
{{trans|Python}}
<syntaxhighlight lang="11l">F bauer(n)
V chain = [0] * n
V in_chain = [0B] * (n + 1)
Line 105:
=={{header|C}}==
{{trans|Kotlin}}
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 386:
=={{header|C sharp|C#}}==
{{trans|Java}}
<syntaxhighlight lang="csharp">using System;
namespace AdditionChains {
Line 486:
While this worked, something made it run extremely slow.
{{trans|D}}
<syntaxhighlight lang="cpp">#include <iostream>
#include <tuple>
#include <vector>
Line 584:
=={{header|D}}==
{{trans|Scala}}
<syntaxhighlight lang=
import std.typecons;
Line 673:
=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
;; 2^n
(define exp2 (build-vector 32 (lambda(i)(expt 2 i))))
Line 743:
===Version 1===
{{trans|Kotlin}}
<syntaxhighlight lang="go">package main
import "fmt"
Line 983:
{{trans|Phix}}
Much faster than Version 1 and can now complete the non-Brauer analysis for N > 79 in a reasonable time.
<syntaxhighlight lang="go">package main
import (
Line 1,191:
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang=
private static class Pair {
int f, s
Line 1,298:
Implementation using backtracking.
<syntaxhighlight lang="haskell">import Data.List (union)
-- search strategies
Line 1,340:
Tasks implementation
<syntaxhighlight lang="haskell">task :: Int -> IO()
task n =
let ch = chains total n
Line 1,385:
For the extra task used compiled code, not GHCi.
<syntaxhighlight lang="haskell">extraTask :: Int -> IO()
extraTask n =
let ch = chains brauer n
Line 1,422:
Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 21-38,'' [http://www.numdam.org/item?id=JTNB_1994__6_1_21_0].
<syntaxhighlight lang="haskell">binaryChain 1 = [1]
binaryChain n | even n = n : binaryChain (n `div` 2)
| odd n = n : binaryChain (n - 1)
Line 1,457:
=={{header|Java}}==
{{trans|D}}
<syntaxhighlight lang=
private static class Pair {
int f, s;
Line 1,562:
=={{header|Julia}}==
{{trans|Python}}
<syntaxhighlight lang="julia">checksequence(pos, seq, n, minlen) =
pos > minlen || seq[1] > n ? (minlen, 0) :
seq[1] == n ? (pos, 1) :
Line 1,631:
I've then extended the code to count the number of non-Brauer chains of the same minimum length - basically 'brute' force to generate all addition chains and then subtracted the number of Brauer ones - plus examples for both. For N <= 64 this adds little to the execution time but adds about 1 minute for N = 79 and I gave up waiting for N = 191! To deal with these glacial execution times, I've added code which enables you to suppress the non-Brauer generation for N above a specified figure.
<syntaxhighlight lang="scala">// version 1.1.51
var example: List<Int>? = null
Line 1,807:
=={{header|Lua}}==
{{trans|D}}
<syntaxhighlight lang="lua">function index(a,i)
return a[i + 1]
end
Line 1,927:
{{trans|Go}}
This is a translation of the second Go version.
<syntaxhighlight lang=
const
Line 2,093:
=={{header|Perl}}==
{{trans|Raku}}
<syntaxhighlight lang="perl">use strict;
use feature 'say';
Line 2,252:
Note the internal values of l(n) are [consistently] +1 compared to what the rest of the world says.
<!--<syntaxhighlight lang=
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 2,391:
=={{header|Python}}==
{{trans|Java}}
<syntaxhighlight lang="python">def prepend(n, seq):
return [n] + seq
Line 2,481:
====Faster method====
<syntaxhighlight lang="python">def bauer(n):
chain = [0]*n
in_chain = [False]*(n + 1)
Line 2,539:
This implementation uses the [https://docs.racket-lang.org/rosette-guide/index.html Rosette] language in Racket. It is inefficient as it asks an SMT solver to enumerate every possible solutions. However, it is very straightforward to write, and in fact is quite efficient for computing <code>l(n)</code> and finding one example (solve n = 379 in ~3 seconds).
<syntaxhighlight lang="racket">#lang rosette
(define (basic-constraints xs n)
Line 2,685:
(formerly Perl 6)
{{trans|Kotlin}}
<syntaxhighlight lang=
sub check-Sequence($pos, @seq, $n, $minLen --> List) {
Line 2,832:
=={{header|Ruby}}==
{{trans|D}}
<syntaxhighlight lang="ruby">def check_seq(pos, seq, n, min_len)
if pos > min_len or seq[0] > n then
return min_len, 0
Line 2,933:
=={{header|Scala}}==
Following Scala implementation finds number of minimum length Brauer chains and corresponding length.
<syntaxhighlight lang=
object chains{
Line 3,023:
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Module Module1
Function Prepend(n As Integer, seq As List(Of Integer)) As List(Of Integer)
Line 3,136:
Non-Brauer analysis limited to N = 191 in order to finish in a reasonable time - about 10.75 minutes on my machine.
<syntaxhighlight lang="ecmascript">var maxLen = 13
var maxNonBrauer = 191
Line 3,312:
=={{header|zkl}}==
{{trans|EchoLisp}}
<syntaxhighlight lang="zkl">var exp2=(32).pump(List,(2).pow), // 2^n, n=0..31
_minlg, _counts, _chains; // counters and results
Line 3,347:
}
}</syntaxhighlight>
<syntaxhighlight lang="zkl">fcn task(n){
_minlg=(0).MAX;
chains(n,List(1),0);
| |||