Anonymous user
Addition chains: Difference between revisions
→{{header|Haskell}}: added practical solution
(→{{header|Haskell}}: added solution) |
(→{{header|Haskell}}: added practical solution) |
||
Line 1,295:
=={{header|Haskell}}==
Implementation using backtracking.
<lang haskell>import Data.List (union)
Line 1,413 ⟶ 1,415:
Non-Brauer analysis suppressed</pre>
Calculation took about 16 seconds (compiled with -O2 flag). If one doesn't need to count all chains, but just get an example it will be found much faster due to Haskell laziness.
=== Nearly optimal chains ===
In practical work use binary chains or the smart algorithm given in ''F. Bergeron, J. Berstel, and S. Brlek, published in
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].
<lang haskell>binaryChain 1 = [1]
binaryChain n | even n = n : binaryChain (n `div` 2)
| odd n = n : binaryChain (n - 1)
dichotomicChain n
| n == 3 = [3, 2, 1]
| n == 2 ^ log2 n = takeWhile (> 0) $ iterate (`div` 2) n
| otherwise = let k = n `div` (2 ^ ((log2 n + 1) `div` 2))
in chain n k
where
chain n1 n2
| n2 <= 1 = minChain n1
| otherwise = case n1 `divMod` n2 of
(q, 0) -> minChain q `mul` minChain n2
(q, r) -> [r] `add` (minChain q `mul` chain n2 r)
c1 `mul` c2 = map (head c2 *) c1 ++ tail c2
c1 `add` c2 = map (head c2 +) c1 ++ c2
log2 = floor . logBase 2 . fromIntegral</lang>
<pre>λ> binaryChain 191
[191,190,95,94,47,46,23,22,11,10,5,4,2,1]
λ> dichotomicChain 191
[191,187,176,88,44,22,11,8,4,3,2,1]
λ> binaryChain 1910
[1910,955,954,477,476,238,119,118,59,58,29,28,14,7,6,3,2,1]
λ> dichotomicChain 1910
[1910,1888,944,472,236,118,59,44,22,15,14,7,6,3,2,1]</pre>
=={{header|Java}}==
| |||