Addition-chain exponentiation: Difference between revisions

Line 1:

[[Category:Matrices]]

In cases of special objects (such as with [[wp:Matrix (mathematics)|matrices]]) the operation of multiplication can be excessively expensive. In these cases the operation of multiplication should be avoided or reduced to a minimum.

Line 89:

Line 90:

=={{header|C}}==

Using complex instead of matrix. Requires [[Addition-chain exponentiation/Achain.c|Achain.c]]. It takes a long while to compute the shortest addition chains, such that if you don't have the chain lengths precomputed and stored somewhere, you are probably better off with a binary chain (normally not shortest but very simple to calculate) whatever you intend to use the chains for.

<syntaxhighlight lang=c>#include <stdio.h>

<syntaxhighlight lang="c">#include <stdio.h>

#include "achain.c" /* not common practice */

Line 189:

Line 190:

Calculating A ^ (m * n) from scratch using this method would take 'for ever' so I've calculated it instead as (A ^ m) ^ n.

<syntaxhighlight lang=go>package main

<syntaxhighlight lang="go">package main

import (

Line 662:

Line 663:

I think it should nevertheless be retained as it is an interesting approach and there are other solutions to this task which are based on it.

<syntaxhighlight lang=go>/*

<syntaxhighlight lang="go">/*

Continued fraction addition chains, as described in "Efficient computation

of addition chains" by F. Bergeron, J. Berstel, and S. Brlek, published in

Line 922:

Line 923:

Generators of a nearly-optimal addition chains for a given number.

<syntaxhighlight lang=haskell>dichotomicChain :: Integral a => a -> [a]

<syntaxhighlight lang="haskell">dichotomicChain :: Integral a => a -> [a]

dichotomicChain n

| n == 3 = [3, 2, 1]

Line 961:

Line 962:

Universal monoid multiplication that uses additive chain

<syntaxhighlight lang=haskell>times :: (Monoid p, Integral a) => a -> p -> p

<syntaxhighlight lang="haskell">times :: (Monoid p, Integral a) => a -> p -> p

0 `times` _ = mempty

n `times` x = res

Line 981:

Line 982:

Implementation of matrix multiplication as monoidal operation.

<syntaxhighlight lang=haskell>data M a = M [[a]] | I deriving Show

<syntaxhighlight lang="haskell">data M a = M [[a]] | I deriving Show

instance Num a => Semigroup (M a) where

Line 1,053:

Line 1,054:

=={{header|Nim}}==

<syntaxhighlight lang=~~Nim~~>import math, sequtils, strutils

<syntaxhighlight lang="nim">import math, sequtils, strutils

const

Line 1,486:

Line 1,487:

Note that "tries" overflows (crashes) at 1073741824, which I kept in as a deliberate limiter.

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

Line 1,614:

Line 1,615:

The addition chains correspond to binary exponentiation.

#lang racket

(define (chain n)

Line 1,657:

Line 1,658:

</syntaxhighlight>

Output:

Chain for 31415

((31415 31414 1) (31414 15707 15707) (15707 15706 1) (15706 7853 7853) (7853 7852 1) (7852 3926 3926) (3926 1963 1963) (1963 1962 1) (1962 981 981) (981 980 1) (980 490 490) (490 245 245) (245 244 1) (244 122 122) (122 61 61) (61 60 1) (60 30 30) (30 15 15) (15 14 1) (14 7 7) (7 6 1) (6 3 3) (3 2 1) (2 1 1))

Line 1,674:

Line 1,675:

Using code at [[Matrix multiplication#Tcl]] and [[Matrix Transpose#Tcl]] (not shown here).

<syntaxhighlight lang=tcl># Continued fraction addition chains, as described in "Efficient computation

<syntaxhighlight lang="tcl"># Continued fraction addition chains, as described in "Efficient computation

# of addition chains" by F. Bergeron, J. Berstel, and S. Brlek, published in

# Journal de théorie des nombres de Bordeaux, 6 no. 1 (1994), p. 21-38,

Line 1,793:

Line 1,794:

This is very slow (12 mins 50 secs) compared to Go (25 seconds) but, given the amount of calculation involved, not too bad for the Wren interpreter.

<syntaxhighlight lang=ecmascript>import "/dynamic" for Struct

<syntaxhighlight lang="ecmascript">import "/dynamic" for Struct

import "/fmt" for Fmt

Line 2,215:

Line 2,216:

[ 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000]

</pre>

Line 2,221:

Line 2,223:

⚫

[[Category:Matrices]]