Addition-chain exponentiation: Difference between revisions

{{draft task|Logic}}{{wikipedia|Addition-chain exponentiation}}

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.

=={{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.

 

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

 

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

 

import (

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.

 

Continued fraction addition chains, as described in "Efficient computation

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

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

 

dichotomicChain n

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

 

Universal monoid multiplication that uses additive chain

0 `times` _ = mempty

n `times` x = res

Implementation of matrix multiplication as monoidal operation.

 

 

instance Num a => Semigroup (M a) where

=={{header|Nim}}==

{{trans|Go}}

 

const

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>

 

The addition chains correspond to binary exponentiation.

#lang racket

(define (chain n)

</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))

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

{{trans|Go}}

# 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,

{{libheader|Wren-fmt}}

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.

import "/fmt" for Fmt

 

[ 0.000000 0.000000 0.000000 0.000000 0.000000 1.000000]

</pre>

 

{{omit from|Brlcad}}

{{omit from|Openscad}}

{{omit from|TPP}}