Friday 19 August 2016

Endless Repetition

endless iteror #3

Repetition

Frances K*, 2016

Learn to create ever bigger numbers
in an article series on site and blog,
dedicated to Chelsea Manning hero.

© Kreative commons

#3 Repetition

We grab the tools to work out repetitions, and define multiplication by a series of empty additions.

3.1 Word reps

In programming languages Regular Expressions are used to scan text and find words that match a regex. We have similar tools to describe repetition of any subexpression.

Repeat a sign or variable either with a regex quantifier {r} inside an expression, or on the dots .. with a rep :r right outside.

@

a*{c}b 
= a*..b *:c
v{n1} 
= v{n}v  
= v.. :n1
a*{1}b 
= a*b
= a*..b *:1
v{1} 
= v{0}v  
= v
= v.. :1
a*{2}b 
= a**b
= a*..b *:2
v{2} 
= v{1}v  
= vv
= v.. :2
a*{3}b
= a***b
= a*..b *:3
v{3} 
= v{2}v  
= vvv
= v.. :3
a*{4}b 
= a****b
= a*..b *:4
v{4} 
= v{3}v  
= vvvv
= v.. :4
a*{5}b 
= a*****b
= a*..b *:5
v{5} 
= v{4}v 
= vvvvv
= v.. :5

Please click the boards for examples!
The yellow sidebar highlights the use of unary constants (not digits) and natural addition.

To select a word W by dots, a single dot can . mark the left side of W, while double dots .. mark it on the right.

@

X.V..Z :0 
= XZ
W..Y :0 = Y
X.V..Z :1 
= XVZ
W..Y :1 = WY
X.V..Z :2 
= XVVZ
W..Y :2 = WWY
X.V..Z :3 
= XVVVZ
W..Y :3 = WWWY
X.V..Z :4 
= XVVVVZ
W..Y :4 
= WWWWY
X.V..Z :5 
= XVVVVVZ
W..Y :5 
= WWWWWYX.V..Z :6 
= XVVVVVVZ
W..Y :6 
= WWWWWWY
X.V..Z :7 
= XVVVVVVVZ
W..Y :7 
= WWWWWWWY

In case right dots have no left dot(s) preceding and there is no word specified W:n in the rep, the repeated word starts at the left of the expression (after the space).

For a subexpression that is expanded from the middle to the left and right at once, we use a two-sided rep.

@

Vi(..X..)Wi :n:
Vi(..X..)Wi :0: 
= X
Vi(..X..)Wi :1: 
= V1(X)W1
Vi(..X..)Wi :2: 
= V2(V1(X)W1)W2
Vi(..X..)Wi :3:
    = V3(V2(V1(X)W1)W2)W3
Vi(..X..)Wi :4:
    = V4(V3(V2(V1(X)W1)W2)W3)W4

Click to show that iteration variable i increments at every step of the repetition. We can also let a secondary iterator j increment for each i all over again in a nested loop.

Our repex notation allows us to iterate over rewrite rules that are defined in single steps. It's an intuitive tool, you can pick it up as we go.

3.2 Multiplication

A common way to multiply two numbers r×n is to take r times the number n and add them together.
Here the item n is put left in the star multiplication n*r and repeated by the iterator r on the right.

When we concatenate unary numbers n.. the multiplication product is directly given. Concatenation works by natural addition, which is the initial superstar operation with zero *{0} stars.

We define multiplication by its addition step, that is trivially selected on the left or right of its product.

@

n*r1 
= n.. :r1 
= n.n.. :r
     = n(n*r) 
= n+n*r
n*3
= n.. :111
= n+n*11
    = n+n+n*1 
= n+n+n
2*3 
= 11.. :111
= 11+11+11
    = 1111+11 
= 111111 = 6n*4
= n+n*111
= n+n+n*11
    = n+n+n+n*1 
= n+n+n+n
2*4 
= 11.. :1111
= 11+11+11+11
    = 11111111 = 8

We already made two choices for evaluation here:
• to place the iterator that counts off steps on the right. The operands have the same order as with exponentiation.
• to derive the suboperation of addition on the left. Generally we scan expressions ltr (left to right) and reduce free suboperations first.

So we add unary numbers directly on the left, while multiplication is kept separated from the growing result by a single postponed + plus.
Or you can leave the + steps to work out later from either side.

Multiplication n*r = r×n is commutative, which means the factors (number item and iterator) can be reversed.
Show examples of stepwise multiplication of: three hands... eight pairs.. nine ones.

@

3×5 = 2×5+5 = 1×5+5+5
    = 5+5+5 = 10+5 = 15

5*3 = 5+5*2 = 55+5*1
    = 555 = 111111111111111
8×2 = 7×2+2
   == 1×2+2+2+2+2+2+2+2
    = 2+2+2+2+2+2+2+2 := 16

2*8 = 2+2*7 = 22+2*6
   == 2222222+2*1
    = 1111111111111111
9×1 = 8×1+1
   == 1×1+1+1+1+1+1+1+1+1
    = 1+1+1+1+1+1+1+1+1 := 9

1*9 = 1+1*8 = 11+1*7
   == 11111111+1*1
    = 111111111

At the final iteration the identity operation is dropped, so the item operand is left over. Either remove and finish the remaining additions, or remove pop + and *1 and return the result.


+ Advanced System

Without direct repetition we must protect a multiplication from its own stepwise evaluation. The single pop + plus, that we put in between, works the same as the old plus: it postpones addition.

n*r2 = n+n*r1
     = n+n+n*r = nn+n*r

Our multiplication rule inserts an addition n+ on the left. At next steps n+ the former addition shifts left and drops its plus, which adds n to the subtotal.
Generally we introduce a new pop and eliminate the plus from the former pop to activate that operation in one go. For each superoperation there is one suboperation kept waiting.

So we can multiply stepwise without inconsistency. But to allow the old addition + gives some pain. Then we should use a double plus ++ to set apart the evaluation subspace on the outside (far left).
Surely in big number arithmetic, we may require the use of brackets m*(n**r) to append lower operations under minority precedence. And deprecate the m+n**r legacy plus.

Berlin 1910, lady mason on a ladder high above a smokey city

No comments:

Post a Comment