Addition chains: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: added solution) |
(→{{header|Haskell}}: added practical solution) |
||
Line 1,295: | Line 1,295: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
Implementation using backtracking. |
|||
<lang haskell>import Data.List (union) |
<lang haskell>import Data.List (union) |
||
Line 1,413: | Line 1,415: | ||
Non-Brauer analysis suppressed</pre> |
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. |
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}}== |
=={{header|Java}}== |